Electrical computers and digital processing systems: memory – Storage accessing and control – Control technique
Reexamination Certificate
2001-06-15
2003-10-21
Gossage, Glenn (Department: 2186)
Electrical computers and digital processing systems: memory
Storage accessing and control
Control technique
C711S137000
Reexamination Certificate
active
06636952
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates generally to transmission systems and, more particularly, to high bandwidth data transmission fetching.
2. Description of Related Art
Conventional network devices, such as routers, relay data through a network from a source to a destination. Typically, the network devices include one or more memory subsystems to temporarily buffer data while the network devices perform network-related functions, such as route processing or accounting. Sometimes the data are stored as one or more linked lists in a memory subsystem that has a long access latency.
Consider, for example, a network device that uses a linked list to store packets in a memory subsystem that has a long access latency. The head of the list is usually stored in a queue and provided to a packet reader that must traverse the list to read each packet before transmitting the packet downstream. Network requirements dictate that a packet must be completely transmitted before the next packet from the queue is transmitted. If the latency of the memory subsystem is large, the linked-list structure limits the amount of pipelining that can be used for reading a packet and limits the bandwidth of the memory system. This problem gets worse over time as the memory latencies become large relative to the bandwidth of the links.
Therefore, there exists a need for systems and methods for increasing the memory bandwidth in a network device that includes a memory subsystem with a large latency.
SUMMARY OF THE INVENTION
Systems and methods consistent with the principles of present invention address this and other needs by performing a two-level prefetch process to efficiently use the read bandwidth of a memory subsystem. The prefetch process includes prefetching multiple packets and data addresses for multiple packets in parallel.
In accordance with the principles of the invention as embodied and broadly described herein, a system that processes streams in a network device includes a memory and output logic. The memory stores data and addresses corresponding to the streams received by the network device. The addresses store pointers to the data. The output logic determines whether an address is required to be fetched. When no address is required to be fetched, the output logic reads data from the memory. When an address is required to be fetched, however, the output logic fetches the address from the memory and reads data from the memory using the fetched address.
In another implementation consistent with the principles of the invention, a method for processing streams by a network device comprises storing data and addresses corresponding to a plurality of input streams received by the network device, the address storing pointers to the data; storing, in a notification buffer pool, notifications corresponding to the input streams; storing notification pointers that identify ones of the notifications in the notification buffer pool to be processed; providing one or more prefetch pointers that identify one or more of the notification pointers that identify notifications that have an associated stored address; storing, in a notification buffer, notifications from the notification buffer pool that are identified by the notification pointers; storing address pointers to the stored addresses that correspond to the notifications stored in the notification buffer; determining whether any additional address pointers can be stored; and storing one or more address pointers to the addresses associated with the notifications and corresponding to the one or more prefetch pointers when additional address pointers can be stored.
In a further implementation consistent with the principles of the invention, a network device comprises a memory and output logic. The memory is configured to store data cells and address cells corresponding to a plurality of packets of different size in a plurality of input streams received by the network device. At least some of the data cells have associated address cells. The address cells store pointers to the data cells. The output logic is configured to determine whether a packet has an associated address cell based on the size of the packet, prefetch address cells from the memory for packets having associated address cells, and read data cells from the memory using the prefetched address cells.
In another implementation consistent with the principles of the invention, an apparatus that retrieves transmission data includes a memory, an address buffer, and output logic. The memory stores data for transmission and addresses identifying data for transmission. The address buffer stores at least one pointer to the addresses. The output logic initiates processes of reading out transmission data from memory, transfers a first pointer to the address buffer, the first pointer being associated with an initiated process of reading transmission data from the memory, reads from the memory one of the addresses using the first pointer from the address buffer, and reads the data identified by the one address from the memory.
REFERENCES:
patent: 5854911 (1998-12-01), Watkins
patent: 5905725 (1999-05-01), Sindhu et al.
Cruz-Rios Jorge
Gupta Anurag P.
Lacroute Phil
Lim Raymond
Zhang Song
Gossage Glenn
Harrity & Snyder LLP
Juniper Networks, Inc.
LandOfFree
Systems and methods for processing packet streams in a... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Systems and methods for processing packet streams in a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Systems and methods for processing packet streams in a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3159101