Deficit round robin

Deficit Round Robin (DRR), also Deficit Weighted Round Robin (DWRR), is a scheduling algorithm for the network scheduler. DRR is, like weighted fair queuing (WFQ), a packet-based implementation of the ideal Generalized Processor Sharing (GPS) policy. It was proposed by M. Shreedhar and G. Varghese in 1995 as an efficient (with O(1) complexity) and fair algorithm. Deficit Round Robin (DRR), also Deficit Weighted Round Robin (DWRR), is a scheduling algorithm for the network scheduler. DRR is, like weighted fair queuing (WFQ), a packet-based implementation of the ideal Generalized Processor Sharing (GPS) policy. It was proposed by M. Shreedhar and G. Varghese in 1995 as an efficient (with O(1) complexity) and fair algorithm. In DRR, a scheduler handling N flows is configured with one quantum Q i {displaystyle Q_{i}} for each flow. This global idea is that, at each round, the flow i {displaystyle i} can send at most Q i {displaystyle Q_{i}} bytes, and the remaining, if any, is reported to the next round. In this way, the flow of number i will achieve a minimal long term data rate of Q i ( Q 1 + Q 2 + . . . + Q N ) R {displaystyle {frac {Q_{i}}{(Q_{1}+Q_{2}+...+Q_{N})}}R} , where R {displaystyle R} is the link rate. The DRR scans all non empty queues in sequence. When a non empty queue i {displaystyle i} is selected, its deficit counter is incremented by its quantum value. Then, the value of the deficit counter is a maximal amount of bytes that can be sent at this turn: if the deficit counter is greater than the packet's size at the head of the queue (HoQ), this packet can be sent and the value of the counter is decremented by the packet size. Then, the size of the next packet is compared to the counter value, etc. Once the queue is empty or the value of the counter is insufficient, the scheduler will skip to the next queue. If the queue is empty, the value of the deficit counter is reset to 0.