Services processor having a queue operations unit and an output scheduler
AssigneeIntel Corporation
InventorsAlex E. Henderson, Walter E. Croft
Life of this patent
Estimating the term…
Abstract
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.
Claims7
A data structure encoded on a computer-readable medium, the data structure for implementing 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.
A method for scheduling 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.
A device for scheduling data packets for output according to a calendar queue, the method 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.
Dependencies are inferred from the claim text.