Deficit round robin
Encyclopedia
Deficit round robin 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.
Weighted round robin
Weighted round robin is a scheduling discipline. Each packet flow or connection has its own packet queue in a network interface card. It is the simplest approximation of generalized processor sharing...
scheduling discipline. DRR was proposed by M. Shreedhar and G. Varghese
George Varghese
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...
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
Fair queueing
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 queuing is that a high-data-rate flow, consisting of large or many data packets, cannot take...
(FQ) scheduler that has complexity of O(log(n)) (n is the number of active flows
Flow (computer networking)
In packet switching networks, traffic flow, packet flow or network flow is a sequence of packets from a source computer to a destination, which may be another host, a multicast group, or a broadcast domain...
), 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.