TABLE OF CONTENTS Packet schedulers determine the order in which a device transmits packets from its output queues. Shapers work with schedulers to regulate the queue transmit rate. As described earlier, scheduling and shaping work in conjunction with the remaining elements of traffic management:
The packet classifier determines the output queue for the packet.
The buffer manager decides whether the packet should be enqueued or dropped.
The queue manager enqueues the packet to the hardware queue.
The shaper and the scheduler determine which queue to service next and when.
The queue manager dequeues a packet from the hardware queue.
The transmit microblock transmits the packet.
The high-level function of a scheduler is to pick a queue that is not empty, not flow-controlled, and that is eligible to send per the constraints of the scheduling policy. This implies that the scheduler needs to perform the following functions.
The scheduler needs to maintain data structures that allow it to determine which queues are not empty or active. Different data structures typically used for this purpose include link-lists, bit vectors, and rings. Subsequent sections explore the trade-offs associated with each of these.
The scheduler needs to track which queues are flow-controlled. Just as in active queue tracking, the scheduler may use bit vectors, links lists, and rings for this purpose. Note that depending on the application, the flow control may not be applicable on a single queue, but on a group of...
