Editing Deficit round robin

{{Short description|Scheduling algorithm for the network scheduler}}
{{redirect|DWRR|the defunct radio station in Philippines|DWRR-FM}}

'''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 [[George Varghese|G. Varghese]] in 1995 as an efficient (with ''O(1)'' complexity) and fair algorithm.<ref name="shreedhar">{{cite journal|first=M.|last=Shreedhar|author2=Varghese, G.|title=Efficient fair queueing using deficit round robin|journal=ACM SIGCOMM Computer Communication Review|date=October 1995|volume=25|issue=4|issn=0146-4833|doi=10.1145/217391.217453|pages=231|url=https://openscholarship.wustl.edu/cgi/viewcontent.cgi?article=1339&context=cse_research|url-access=subscription}}</ref>

== Details ==
In DRR, a scheduler handling N flows{{efn|Flows may also be called queues, classes or sessions}} is configured with one quantum <math>Q_i</math> for each flow. This global idea is that, at each round, the flow <math>i</math> can send at most <math>Q_i</math> bytes, and the remaining, if any, is reported to the next round. In this way, the minimum rate that flow <math>i</math> will achieve over a long term is <math>\frac{Q_i}{(Q_1+Q_2+...+Q_N)}R</math>; where <math>R</math> is the link rate.

==Algorithm==
The DRR scans all non-empty queues in sequence. When a non-empty queue <math>i</math> is selected, its deficit counter is incremented by its quantum value. Then, the value of the deficit counter is a maximal number 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.

 ''Variables and Constants''
     const integer N             // Nb of queues
     const integer Q[1..N]       // Per queue quantum 
     integer DC[1..N]            // Per queue deficit counter
     queue queue[1..N]           // The queues

 ''Scheduling Loop''
 '''while''' true '''do'''
     '''for''' i in 1..N '''do'''
         '''if''' not queue[i].empty() '''then'''
             DC[i]:= DC[i] + Q[i]
             '''while'''( not queue[i].empty() '''and'''
                          DC[i] ≥ queue[i].head().size() ) '''do'''
                 DC[i] := DC[i] − queue[i].head().size()
                 send( queue[i].head() )
                 queue[i].dequeue()
             '''end while''' 
             '''if''' queue[i].empty() '''then'''
                 DC[i] := 0
             '''end if'''
         '''end if'''
     '''end for'''
 '''end while'''

== Performances: fairness, complexity, and latency==

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(log(n))'' (''n'' is the number of active [[Traffic flow (computer networking)|flows/queues]]), the complexity of DRR is ''O(1)'', if the quantum <math>Q_i</math> 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.<ref name="Aliquem-DRR">{{Cite book | doi = 10.1109/IWQoS.2002.1006576| chapter = Aliquem: A novel DRR implementation to achieve better latency and fairness at O(1) complexity| title = IEEE 2002 Tenth IEEE International Workshop on Quality of Service (Cat. No.02EX564)| pages = 77–86| year = 2002| last1 = Lenzini | first1 = L.| last2 = Mingozzi | first2 = E.| last3 = Stea | first3 = G.| isbn = 978-0-7803-7426-3| s2cid = 62158653}}</ref> More on the worst-case latencies can be found here.<ref>{{Cite book|last1=Tabatabaee|first1=Seyed Mohammadhossein|last2=Le Boudec|first2=Jean-Yves|title=2021 IEEE 27th Real-Time and Embedded Technology and Applications Symposium (RTAS) |chapter=Deficit Round-Robin: A Second Network Calculus Analysis |date=May 2021|chapter-url=https://ieeexplore.ieee.org/document/9470448|location=Nashville, TN, USA|publisher=IEEE|pages=171–183|doi=10.1109/RTAS52030.2021.00022|isbn=978-1-6654-0386-3|s2cid=235294011 |url=https://infoscience.epfl.ch/record/285728/files/DRR-RTAS2021.pdf }}</ref>

== Implementations ==

An implementation of the deficit round robin algorithm was written by Patrick McHardy for the [[Linux kernel]]<ref>{{cite web |url=https://git.kernel.org/cgit/linux/kernel/git/stable/linux-stable.git/tree/net/sched/sch_drr.c |title=DRR Linux kernel network scheduler module |publisher=[[kernel.org]] |accessdate=2013-09-07}}</ref> 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.<ref>{{cite journal
| last1       = Lenzini
| first1      = Luciano
| last2      = Mingozzi
| first2     = Enzo
| last3      = Stea
| first3     = Giovanni
| year       = 2007
| title      = Performance Analysis of Modified Deficit Round Robin Schedulers
| url        = http://dl.acm.org/citation.cfm?id=2692164.2692169
| journal    = IOS Journal of High Speed Networks
| volume = 16
| issue = 4
| pages = 399–422
}}</ref><ref>{{cite tech report 
| last       = Lenzini
| first      = Luciano
| last2      = Mingozzi
| first2     = Enzo
| last3      = Stea
| first3     = Giovanni
| title= Performance Analysis of Modified Deficit Round Robin Schedulers
| number= 
| institution= Dipartimento di Ingegneria della Informazione, University of Pisa
| year= 2006}}</ref>

==See also==
* [[Scheduling algorithm]]
* [[Fair Queuing]] 
* [[Generalized processor sharing]]
* [[Weighted Fair Queuing]] 
* [[Weighted round robin]]
* [[Fairness measure]]

==Notes==
{{notelist}}

==References==
{{reflist}}

==External links==
* [http://www.cs.berkeley.edu/~kfall/EE122/lec27/sld007.htm UC Berkeley EE122 lecture: Efficient fair queueing using deficit round robin]

{{DEFAULTSORT:Deficit Round Robin}}
[[Category:Network scheduling algorithms]]