Electrical computers and digital data processing systems: input/ – Input/output data processing – Input/output data buffering
Reexamination Certificate
2000-05-31
2004-02-17
Gaffin, Jeffrey (Department: 2182)
Electrical computers and digital data processing systems: input/
Input/output data processing
Input/output data buffering
C710S052000, C710S053000, C710S054000, C710S055000, C710S056000
Reexamination Certificate
active
06694388
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to queuing systems and more particularly relates to a dynamic queuing system wherein a single memory is shared
BACKGROUND OF THE INVENTION
Currently, the number of data networks and the volume of traffic these networks carry are increasing at an ever faster rate. The network devices that make up these networks generally consist of specialized hardware designed to move data at very high speeds. Typical networks, such as Ethernet based networs, are mainly comprised of end stations, Ethernet hubs, switches, routers, bridges and gateways. ATM networks are constructed with similar network devices adapted to carry ATM traffic, e.g., ATM capable end stations, edge devices and ATM switches.
With the ever increasing user demand for faster and faster data communications, network devices have had to perform at higher and higher speeds. A primary function of many network devices is to receive frames (packets, cells, etc.) at one or more ingress ports, and forward the frame to the appropriate egress port. Accomplishing this requires that the network device store and process data at one or more stages. The device may queue data received from the input ports, data waiting to be written to output ports and data generated at one or more intermediate processing stages. This requires the creation of a plurality of queues within the internal memory of the device. The size of the queues required typically depends on the internal architecture of the device, the required processing speed, and other parameters.
It is thus desirable to have an efficient mechanism of creating and maintaing a plurality of queues in a network device. Due to the potentially rapid changes in network traffic that a network device may essence from one moment to the next it is also desirable to implement the queuing system in a dynamic fashion. In such a system, queues may be created, utilized and removed on a dynamic basis. Further, it is desirable to be able to dynamically change the size of a queue depending on the requirements of the network device at any particular point in time.
SUMMARY OF THE INVENTION
The present invention provides a dynamic queuing system wherein a single memory is shared among a plurality of different queues. The queues may comprise any suitable type of queue such as the well known Last In First Out (LIFO) type queue or First In First Out (FIFO) type queue. Each queue is created using one or more blocks of queue memory. On a dynamic basis, the queue may take additional blocks from memory in order to increase its size. Conversely, it may return unused blocks to memory on a dynamic basis as well thus reducing the size of the queue.
For illustration purposes, the principles of the present invention are described in the context of an example network device comprising an ATM edge device having a plurality of Ethernet ports and one or more ATM ports. Note, however, it is not intended that the invention be limited to the network device described herein.
In accordance with the present invention, a single memory, termed a queue memory, is dynamically shared by one or more queues. The queue memory is divided into a plurality of memory blocks that are initially empty. An empty list functions to track which memory blocks are my and available for use in a queue. Each queue that is constructed utilizes one or more memory blocks. When a queue becomes full, an additional memory block is allocated to it. Conversely, as memory blocks of a queue are read, i.e. Emptied, they are returned to the pool of empty memory blocks for use by mother queues.
The queue memory may be constructed from single or multiple physical memories and may or may not have a contiguous address space. Preferably, the memory comprises a single contiguous memory block in order to simplify the queue control circuitry used to read and write data from and to the queue Memory.
The queue memory is divided into a plurality of memory blocks. Preferably, all memory blocks are of a uniform size. The invention can also operate with memory blocks having different sizes as long as the queue control circuitry is adapted accordingly.
In operation, the queue memory is the shared memory that is used by all the queues. The memory is divided into a plurality of memory blocks wherein each memory block is represented by an entry in an empty list. The empty list is stored in a group memory and preferably implemented as a singly or doubly linked list. A first pointer points to an entry that is the first empty memory block on the empty list. When a memory block is to be allocated to a queue, the memory block pointed to the first pointer is the memory block to be allocated.
A last pointer functions to point to an entry that is the last empty memory block on the empty list When a memory block is to be de-allocated from a queue, the memory block de-allocated is written to the last pointer. An empty counter function to track the number of memory blocks currently on the empty list.
Note that upon reset or initialization of the queue system, all the entries in the group memory are linked together on the empty list. As memory blocks are allocated, entries are removed from the empty list.
There is thus provided in accordance with the present invention a dynamic queuing system comprising a queue memory divided into a plurality of equal length memory blocks, a first list for storing a list of empty memory blocks that are currently not in use, means for creating a queue by allocating an empty memory block from the queue memory, removing the allocated memory block from the first list and creating a second list for storing the memory blocks that make up the queue, a queue control circuit including, means for writing to the queue including a write pointer for identifying the next location in the queue available for writing, means for reading from the memory queue including a read pointer for identifying the next location in the queue to be read, means for increasing the size of the queue when the queue is full, including allocating an additional memory block from the queue memory, removing the allocated memory block from the first list and adding the newly allocated memory block to the second list and means for reducing the size of the queue when a memory block becomes empty, including de-allocating the empty memory block, adding the de-allocated memory block to the first list and removing the de-allocated memory block from the second list.
There is also provided in accordance with the present invention a dynamic queuing method, the method comprising the steps of dividing a queue memory into a plurality of equal length memory blocks, storing a first list of empty memory blocks that are currently not in use, creating a queue by allocating an empty memory block from the queue memory, removing the allocated memory block from the first list and creating a second list for storing the memory blocks making up the queue, writing to the queue utilizing a write pointer for identifying the next location in the queue available for writing, reading from the memory queue utilizing a read pointer for identifying the next location in the queue to be read, increasing the size of the queue when the queue is full by allocating an additional memory block from the queue memory, removing the allocated memory block from the first list and adding the newly allocated memory block to the second list and reducing the size of the queue when a memory block becomes empty by de-allocating the empty memory block, adding the de-allocated memory block to the first list and removing the de-allocated memory block from the second list.
REFERENCES:
patent: 4807111 (1989-02-01), Cohen et al.
patent: 5541912 (1996-07-01), Choudhury et al.
patent: 5625625 (1997-04-01), Oskouy et al.
patent: 5881316 (1999-03-01), Chaney et al.
patent: WO 99/00738 (1999-01-01), None
Introduction to Algorithms by Cormen, Leiserson, Rivest, Stein; MIT Press, 2ndEdition, Sections 10.2 and 10.3.*
ATM Practical Implementations Here and Now, 3COM Corporation, 1996.
Bronstein Zvika
Elran Roni
Schzukin Golan
Shimony Ilan
3Com Corporation
Chen Alan
Gaffin Jeffrey
Zaretsky Howard
LandOfFree
Dynamic queuing system incorporating multiple queues sharing... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Dynamic queuing system incorporating multiple queues sharing..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Dynamic queuing system incorporating multiple queues sharing... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3316915