Deficit round robin

Deficit round robin
"DWRR" redirects here. For the radio station in Philippines, see DWRR-FM.

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).

The major advantage of this method of scheduling is that it does not require the size of the incoming packets on the different links to be known to the scheduler, as opposed to a simpler weighted round robin scheduling.

See also

  • Scheduling disciplines

References

  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. 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


Wikimedia Foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Look at other dictionaries:

  • Round-robin scheduling — Round robin (RR) is one of the simplest scheduling algorithms for processes in an operating system, which assigns time slices to each process in equal portions and in order, handling all processes without priority. Round robin scheduling is both… …   Wikipedia

  • Round robin (disambiguation) — Round robin may mean:* Round robin (taking turns) * Round robin tournament (sports) * Round robin scheduling (computer science) * Deficit round robin (computer networking) * Weighted round robin (computer networking) …   Wikipedia

  • Weighted round robin — (WRR) is a best effort connection scheduling discipline. Each packet flow or connection has its own packet queue in a network interface card. It is the simplest emulation of generalized processor sharing (GPS) discipline. While GPS serves… …   Wikipedia

  • Fair queuing — is a scheduling algorithm used in computer and telecommunications networks to allow multiple packet flows to fairly share the link capacity. The advantage over conventional first in first out (FIFO) queuing is that a high data rate flow,… …   Wikipedia

  • Сертификации Cisco — Эта статья или раздел нуждается в переработке. Пожалуйста, улучшите статью в соответствии с правилами написания статей. Сертификаци …   Википедия

  • List of combinatorics topics — This is a list of combinatorics topics.A few decades ago it might have been said that combinatorics is little more than a way to classify poorly understood problems, and some standard remedies. Great progress has been made since 1960.This page is …   Wikipedia

  • Weighted fair queuing — (WFQ) is a data packet scheduling technique allowing different scheduling priorities to statistically multiplexed data flows. WFQ is a generalization of fair queuing (FQ). Both in WFQ and FQ, each data flow has a separate FIFO queue. In FQ, with… …   Wikipedia

  • George Varghese — is a Professor of Computer Science at the University of California San Diego where he leads the Internet Algorithms Lab and also works with the Center for Network Systems and the Center for Internet Epidemiology. He is the author of the textbook… …   Wikipedia

  • DRR — may refer to: Digitally Reconstructed Radiograph Disaster Response Route, emergency response road network in British Columbia, Canada Disaster Risk Reduction Deficit round robin Directorate of Rice Research See also DRRS (disambiguation) …   Wikipedia

  • performing arts — arts or skills that require public performance, as acting, singing, or dancing. [1945 50] * * * ▪ 2009 Introduction Music Classical.       The last vestiges of the Cold War seemed to thaw for a moment on Feb. 26, 2008, when the unfamiliar strains …   Universalium

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”