Deficit round robin


Deficit Round Robin, also Deficit Weighted Round Robin, is a scheduling algorithm for the network scheduler. DRR is, like weighted fair queuing, a packet-based implementation of the ideal Generalized Processor Sharing policy. It was proposed by M. Shreedhar and G. Varghese in 1995 as an efficient and fair algorithm.

Details

In DRR, a scheduler handling N flows is configured with one quantum for each flow. This global idea is that, at each round, the flow can send at most bytes, and the remaining, if any, is reported to the next round. In this way, the flow of number will achieve a minimal long term data rate of, where is the link rate.

Algorithm

The DRR scans all non empty queues in sequence. When a non empty queue 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, 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.
Variables and Constants
const integer N // Nb of queues
const integer Q // Per queue quantum
integer DC // Per queue deficit counter
queue queue // The queues
Scheduling Loop
while true do
for i in 1..N do
if not queue.empty then
DC:= DC + Q
while and
DC ≥ queue.head.size ) do
DC := DC − queue.head.size
send
queue.dequeue
end while
if queue.empty then
DC := 0
end if
end if
end for
end while

Performances: fairness, complexity

Like other GPS-like scheduling algorithm, the choice of the weights is left to the network administrator.
Like WFQ, DRR offers a minimal rate to each flow whatever the size of the packets is. In weighted round robin scheduling, the fraction of bandwidth used depend on the packet's sizes.
Compared with WFQ scheduler that has complexity of O, the complexity of DRR is O, if the quantum is larger than the maximum packet size of this flow. Nevertheless, this efficiency has a cost: the latency, i.e. the distance to the ideal GPS, is larger in DRR than in WFQ.

Implementations

An implementation of the deficit round robin algorithm was written by Patrick McHardy for the Linux kernel and published under the GNU General Public License.
In Cisco and Juniper routers, modified versions of DRR are implemented: since the latency of DRR can be larger for some class of traffic, these modified versions give higher priority to some queues, whereas the others are served with the standard DRR algorithm.