Deficit round robin

Deficit round robin, often shortened to DRR and also called deficit-weighted round robin, is a scheduling algorithm used by a network scheduler to decide which queued packets to send next. It is a packet-based approximation of the ideal generalized processor sharing policy, in the same family as weighted fair queueing. Each flow is given a quantum, and each time the scheduler visits a non-empty queue it adds that quantum to the flow's deficit counter, then sends packets from the head of the queue for as long as the counter covers the next packet's size. Any unused credit carries over to the next round, and an emptied queue has its counter reset to zero. Because it does no sorting, its cost per decision is constant when the quantum is at least the largest packet size, which is cheaper than weighted fair queueing, although it gives somewhat higher latency. It was proposed by M. Shreedhar and George Varghese in 1995, and modified versions run in Cisco and Juniper routers and in the Linux kernel.