Prioritized continuous-deficit round robin scheduling

Abstract

A method and apparatus for queue selection is described below as Prioritized Continuous-Deficit Round Robin (PC-DRR) Scheduling. In PC-DRR scheduling a queue is selected as a source for the shared datapath using a modified round-robin approach, where queues are cyclically, sequentially evaluated to determine whether or not there is data stored in the queue. In PC-DRR scheduling, each queue is assigned a weight, wherein the weight corresponds to a predefined bandwidth that is allocated to the queue. Thus, the weight defines a fixed allotment of transmit opportunities that are to be allowed for the associated queue during its transmit tenure. In a preferred embodiment, a minimum permissible weight that is assigned to a queue is equal to a Maximum Packet Size. As data are drained from the queue, the weight is decreased incrementally by the amount of data sent, providing a balance. Thus the balance represents the instantaneous count of the number of output transmits that are remain for the queue within its transmit tenure. The queue continues to drain until the quantity of data transmitted is greater than the remaining balance, at which point the balance associated with the queue will become negative or zero. Once one queue is drained, or has exceeded its balance, the next sequential queue that has data to transmit is selected, where its associated weight will correspond to the number of fined transmit opportunities that are permitted for the queue.