Electrical computers and digital processing systems: memory – Storage accessing and control – Memory configuring
Reexamination Certificate
2001-12-21
2004-06-22
Ellis, Kevin L. (Department: 2188)
Electrical computers and digital processing systems: memory
Storage accessing and control
Memory configuring
C707S793000
Reexamination Certificate
active
06754795
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to data processing systems, and more particularly to techniques for forming a linked list queue using a chunk-based structure.
BACKGROUND OF THE INVENTION
As is known, in a router or other type of packet switch of a packet processing system, packets that pass through and/or are processed by the router are maintained, at least temporarily, in a packet buffer memory. Typically, a memory data structure known as a linked list queue is maintained in association with the packet buffer memory. A linked list queue contains a list of pointers respectively pointing to each memory location in the packet buffer memory in which data associated with each packet is stored.
A conventional queue structure typically stores, in one continuous, sequential list, each pointer associated with each packet that is currently stored in the packet buffer memory. Each pointer in the list, however, may be stored at non-contiguous memory locations of the memory in which the queue resides. When a packet from the packet buffer memory is to be processed in some operation performed by the router, the link list queue must be accessed or addressed such that the pointer associated with that packet is obtained. Thus, with the conventional linked list structure, queue accessing must be done each and every time a pointer needs to be obtained and a packet is to be processed.
However, as processing speeds associated with routers or other packet switches increase (e.g., 10 gigabits per second and faster), the input and output bandwidth and access latency associated with the memory used to maintain the linked list queue becomes critical. That is, given the fact that a conventional queue must be accessed each and every time a packet pointer is needed, the queue memory can become a significant bottleneck.
It is therefore apparent that a need exists for techniques which address these and other drawbacks associated with the use of a single, non-contiguous linked list queue in data processing systems.
SUMMARY OF THE INVENTION
The present invention provides techniques for forming a linked list queue using a multiple memory chunk-based or block-based structure thereby addressing the drawbacks associated with the use of conventional linked list queues in data processing systems.
In one aspect of the invention, a processing system comprises processing circuitry and memory circuitry coupled to the processing circuitry. The memory circuitry is configurable to maintain at least one queue structure representing a list of data units (e.g., pointers to packets stored in a packet memory). The queue structure is partitioned into two or more blocks (e.g., chunks) wherein at least some of the blocks of the queue structure include two or more data units. Further, at least some of the blocks of the queue structure may include a pointer to a next block of the queue structure (e.g., a next chunk pointer).
Given such a queue structure, the processing circuitry is configurable to address or access a first block of the queue structure, and then address a next block of the queue structure by setting the next block pointer of the first block to point to the next block.
Advantageously, since the data units in a given block are contiguously located in memory (while each block does not necessarily have to be), the processing circuitry has only to address the block in order to effectively address each data unit in that block. Thus, in the case where the data units are packet pointers, the queue structure need not be accessed each and every time a pointer needs to be obtained and a packet is to be processed, as with a conventional queue structure. Rather, the queue structure of the invention need only be accessed when pointers in a next block are required. This is accomplished by setting the next block pointer of the current block to point to the next block. Such a queue accessing technique significantly reduces the bandwidth and access latency requirements of the queue memory and also prevents the queue memory from becoming a bottleneck in processing operations.
In another aspect of the invention, at least one list of pointers representing available blocks of the queue structure (e.g., a free chunk list) is maintained. In this manner, the available blocks list is referenced when adding a data unit (e.g., packet pointer) to the queue structure, and is updated when removing a data unit from the queue structure and/or releasing a block. In one embodiment, two separate available blocks lists are used in tandem to increase the speed with which available blocks of the queue structure are identified and accessed.
In an illustrative embodiment, the queue structure of the invention may be associated with a traffic manager of a router or other type of packet switch.: Further, the processing circuitry and the memory circuitry used to maintain and access the inventive block-based queue structure may be implemented on one or more integrated circuits.
REFERENCES:
patent: 5850395 (1998-12-01), Hauser et al.
patent: 6233244 (2001-05-01), Runaldue et al.
patent: 6298339 (2001-10-01), Björnson
patent: 6505283 (2003-01-01), Stoney
patent: 6526314 (2003-02-01), Eberle et al.
patent: 6578131 (2003-06-01), Larson et al.
patent: 0 622 922 (1994-11-01), None
T. Siladin, “Improving File System Performance for Lookups in Large Directories,” Department of Computer Science, College of William and Mary, pp. 1-41, Dec. 1997.
Chen Jian-Guo
Clune David E.
Moller Hanan Z.
Sonnier David P.
Agere Systems Inc.
Ellis Kevin L.
Ryan & Mason & Lewis, LLP
LandOfFree
Methods and apparatus for forming linked list queue using... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Methods and apparatus for forming linked list queue using..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Methods and apparatus for forming linked list queue using... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3310237