Services processor having a queue operations unit and an output scheduler
In a services processor, a queue operations unit controls the output of processed data packets from the services processor. In accordance with a hybrid list/calendar queue priority scheme, the queue operations unit uses a unique data structure comprising a tree of calendar arrays and queue lists to schedule the data packets for output.
1. A computer-readable medium encoded with a data structure to implement a calendar queue of queue control blocks, each queue control block associated with a set of data packets to be outputted from a network services processor, the data structure comprising:
a hierarchy of bit maps having at least an upper layer and a lower layer, each bit map on the lower layer associated with a bucket of the calendar queue; and
a bucket pointer array including a pointer for each bucket, the bucket pointer array associating the queue control blocks with a bucket in the calendar queue.
2. The computer-readable medium of claim 1 , wherein each upper layer bit map is associated with a group of lower layer bit maps and indicates the occupied status of any bucket corresponding to the associated lower layer bit maps.
3. The computer-readable medium of claim 1 , wherein each queue control block is further associated with an output time relative to a system time, and each queue control block is associated with the bucket corresponding to the queue control block's output time.
4. A method to schedule data packets for output by a services processor, the method comprising:
organizing the data packets into a plurality of queues;
scheduling the plurality of queues for output according to a calendar queue, the calendar queue defined by a data structure comprising:
a hierarchy of bit maps having at least an upper layer and a lower layer, each bit map on the lower layer associated with a bucket of the calendar queue, and
a bucket pointer array including a pointer for each bucket, the bucket pointer array associating the queues with a bucket in the calendar queue; and
outputting the queues according to the calendar queue.
5. The method of claim 4 , wherein each queue is identified by a queue control block, and the queues are represented in the calendar queue by their associated queue control block.
6. A device to schedule data packets for output according to a calendar queue, the device comprising:
a queue operations unit for organizing the data packets into a plurality of queues;
a memory for storing a data structure that defines the calendar queue, the data structure comprising:
a hierarchy of bit maps having at least an upper layer and a lower layer, each bit map on the lower layer associated with a bucket of the calendar queue, and
a bucket pointer array including a pointer for each bucket, the bucket pointer array associating the queues with a bucket in the calendar queue; and
an output scheduler for scheduling the plurality of queues for output according to the calendar queue, wherein the output scheduler adds each queue to a bucket of the calendar queue.
7. The device of claim 6 , further comprising:
a packet output unit that outputs the queues according to the calendar queue.