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 non-empty queue whereas DRR serves packets at the head of every non-empty queue whose deficit counter is greater than the packet's size at the head of the queue (HoQ). If the deficit counter is lower, then the queue is skipped ( HoQ packet is not served ) and its credit is increased by some given value called quantum. This increased value is used to calculate the deficit counter the next time around when the scheduler examines this queue for serving its head-of-line packet. If the queue is served, then the Credit is decremented by the size of packet 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).
See also
References
- ^ Shreedhar, M.; Varghese,G. (October 1995). "Efficient fair queueing using deficit round robin". ACM SIGCOMM Computer Communication Review 25 (4): 231. doi:. ISSN 0146-4833. http://portal.acm.org/citation.cfm?id=217391.217453&coll=portal&dl=ACM&idx=217391&part=periodical&WantType=periodical&title=ACM%20SIGCOMM%20Computer%20Communication%20Review&CFID=43003&CFTOKEN=48156662.
External links
This entry is from Wikipedia, the leading user-contributed encyclopedia. It may not have been reviewed by professional editors (see full disclaimer)
