Deficit Round Robin (DRR), also Deficit Weighted Round Robin (DWRR), is a scheduling algorithm for the network scheduler. DRR is, like weighted fair queuing (WFQ), a packet-based implementation of the ideal Generalized Processor Sharing (GPS) policy. It was proposed by M. Shreedhar and G. Varghese in 1995 as an efficient (with O(1) complexity) and fair algorithm.
Contents
Details
In DRR, a scheduler handling N flows is configured with one quantum
Algorithm
The DRR scans all non empty queues in sequence. When a non empty queue
Performances: fairness, complexity
Like other GPS-like scheduling algorithm, the choice of the weights is left to the network administrator.
Like WFQ, DRR offers a minimal rate to each flow whatever the size of the packets is. In weighted round robin scheduling, the fraction of bandwidth used depend on the packet's sizes.
Compared with 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
Implementations
An implementation of the deficit round robin algorithm was written by Patrick McHardy for the Linux kernel 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 give higher priority to some queues, whereas the others are served with the standard DRR algorithm.