Deficit round robin

From Wikipedia, the free encyclopedia

Deficit round robin (DRR)^[1], also deficit weighted round robin (DWRR), is a modified weighted round robin scheduling discipline. DRR was proposed by M. Shreedhar and G. Varghese in 1995. It can handle packets of variable size without knowing their mean size. A maximum packet size number is subtracted from the packet length, and packets that exceed that number are held back until the next visit of the scheduler.

WRR serves every nonempty queue whereas DRR serves packets at the head of every nonempty queue which deficit counter is greater than the packet's size. If it is lower then deficit counter is increased by some given value called quantum. Deficit counter is decreased by the size of packets being served.

Compared with Fair queueing (FQ) scheduler that has complexity of O(log(n)) (n is the number of active flows), the complexity of DRR is O(1).

[edit] See also

scheduling disciplines

[edit] References

^ Shreedhar, M.; Varghese,G. (October 1995). "Efficient fair queueing using deficit round robin". ACM SIGCOMM Computer Communication Review 25 (4). ISSN 0146-4833.

[edit] External links

UC Berkeley EE122 lecture on DRR (http://www.cs.berkeley.edu/~kfall/EE122/lec27/sld007.htm)

 Efficient fair queueing using deficit round robin
 Source         Applications, Technologies, Architectures, and Protocols for Computer Communication archive
 Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication table of contents
 Cambridge, Massachusetts, United States
 Year of Publication: 1995
 ISSN:0146-4833
 Authors        
 M. Shreedhar    Microsoft Corporation
 George Varghese         Washington University in St. Louis.
 Sponsor        
 SIGCOMM: ACM Special Interest Group on Data Communication
 Publisher      
 ACM Press   New York, NY, USA