Deficit weighted round robin queuing

Deficit weighted round robin queuing (DWRR) can limit queue starvation by providing a fairer distribution of available bandwidth across priorities. Lower priority queues are serviced, even when packets are present in higher priority queues. The degree to which this occurs depends on the queue weights.

Each queue is assigned a weight that is used to calculate a quantum. The quantum defines how many bytes each queue can send every scheduling round. An empty queue has a deficit counter, which is used to track the number of bytes it is allowed to send. The counter starts at zero when a packet arrives at an empty queue.

At the start of a round, the deficit counters of all non-empty queues are incremented by a quantum value in proportion to their weight. Next, the scheduler inspects all non-empty queues in decreasing priority order, comparing the deficit counter for the queue against the packet size at the head of the queue. The round ends when a deficit counter is found that is larger than the packet size. That packet is de-queued for transmission, and the queue counter for the queue is decremented.

In general, the deficit counters of lower priority queues will be larger (that is, they build up a deficit), than the deficit counters of higher priority queues. With a mix of large and small packet sizes of high priority traffic, the deficit counters of higher priority queues will have some rounds where they will be smaller than the packet size at the head of the queue. This occasionally allows traffic from lower priority queues to be selected for transmission.