Deficit round robin

From Wikipedia, the free encyclopedia
Jump to: navigation, search
"DWRR" redirects here. For the radio station in Philippines, see DWRR-FM.

Deficit Round Robin (DRR), also Deficit Weighted Round Robin (DWRR), is a scheduling algorithm for the network scheduler, member of the fair queueing familly. DRR is, like weighted fair queuing (WFQ), a packet-based implentation of the ideal Generalized Processor Sharing (GPS) policy. It was was proposed by M. Shreedhar and G. Varghese in 1995 as an efficient (with O(1) complexity) and fair algorithm.[1]


In DRR, a scheduler handling N flows is configured with one quantum Q_i for each flow. Then, the flow of number i will achieve a minimal long term data rate of \frac{Q_i}{(Q_1+Q_2+...+Q_N)}R, where R is the link rate.

Details[edit]

In DRR, a scheduler handling N flows (also called "classes", or "sessions") is configured with one weight Q_i for each flow. This global idea is that, at each round, the flow i can send at most Q_i bytes, and the remaining, if any, is reported to the next round.

The DRR scans all non empty queues in sequence. When a non empty i queue is selected, its deficit counter is incremented by its quantum value. Then, the value of the deficit counter is a maximal abount of bytes that can be send 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 skip to the next queue. If the queue is empty, the value of the couter is reset to O.

Variables and constant
   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   
 Sending loop
 while (true)
   for i in 1..N
        if not queue[i].empty()
            DC[i]:= DC[i] + Q[i]
            while( not queue[i].empty() and
                   DC[i] >= queue[i].head().size() )
                DC[i]:= DC[i] - queue[i].head().size()
                send( queue[i].head() )
                queue[i].dequeue()
            end while 
            if queue[i].empty()
                DC[i]:= 0
            end if
        end if
   end for' 
 end while


Performances: fairness, complexity[edit]

Like other GPS-like scheduling algorithm, the choice of the weights is left to the network administrator.

As presented for fair queueing, there is no unique definition on what is "fair". Like Weighted fair queueing, DRR offers a minimal rate to each flow/queue whatever the size of the packets is (as opposed to a weighted round robin scheduling where the fraction of bandwidth used depend on the packets sizes).

Compared with Weighted fair queueing (WFQ) scheduler that has complexity of O(log(n)) (n is the number of active flows/queues), the complexity of DRR is O(1), if the quantum Q_i 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. [2]

Implementations[edit]

An implementation of the deficit round robin algorithm was written by Patrick McHardy for the Linux kernel[3] 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 allow to give some kind of higher priority to some queues, whereas the others are served with the standard DRR algorithm. [4] [5]

See also=[edit]

References[edit]

  1. ^ Shreedhar, M.; Varghese,G. (October 1995). "Efficient fair queueing using deficit round robin". ACM SIGCOMM Computer Communication Review 25 (4): 231. doi:10.1145/217391.217453. ISSN 0146-4833. 
  2. ^ Lenzini, L.; Mingozzi, E.; Stea, G. (2002). "IEEE 2002 Tenth IEEE International Workshop on Quality of Service (Cat. No.02EX564)". p. 77. doi:10.1109/IWQoS.2002.1006576. ISBN 0-7803-7426-6.  |chapter= ignored (help) edit
  3. ^ "DRR Linux kernel network scheduler module". kernel.org. Retrieved 2013-09-07. 
  4. ^ Lenzini, Luciano; Mingozzi, Enzo; Stea, Giovanni (2007). "Performance Analysis of Modified Deficit Round Robin Schedulers". IOS Journal of High Speed Networks. 
  5. ^ Lenzini, Luciano; Mingozzi, Enzo; Stea, Giovanni (2006). Performance Analysis of Modified Deficit Round Robin Schedulers (Technical report). Dipartimento di Ingegneria della Informazione, University of Pisa. 

External links[edit]