Summary

  • Ordinary packet round robin gives queues equal transmission opportunities, not equal byte service. Shreedhar and Varghese’s DRR assigns each queue a quantum, spends a deficit counter on whole packets and preserves unused credit while the queue remains backlogged.
  • DRR was designed for bounded throughput fairness with low packet-processing work. Its guarantee belongs to the queues and weights that operators configure; basic DRR does not itself bound packet latency, classify users, control congestion, shape arrivals or prove end-to-end quality.

A turn was never a unit of bandwidth

The seduction of round robin is visual. Put the active queues in a circle, move a pointer from one to the next, and allow each to transmit one packet. No queue appears to be favoured. The scheduler is easy to implement and its work does not grow into a search for the globally earliest virtual finishing time.

But a packet is a container, not a standard measure of service. Suppose queue A always has 1,500-byte packets and queue B always has 500-byte packets. One packet from A followed by one from B repeats the same sequence of turns, yet A receives three times as many transmitted bytes. The pointer is even-handed about visits and biased about the scarce resource the link actually spends.

This is the problem M. Shreedhar and George Varghese framed in their 1994 technical report and the 1995–96 paper, “Efficient Fair Queuing Using Deficit Round-Robin.” Earlier fair-queuing schemes could approximate a fluid allocation closely but imposed more selection work. Cheaper cyclic schemes were attractive at high speed but could inherit packet-size unfairness. DRR asked whether a small amount of memory could preserve the cycle and repair its unit of account.

Credit survives the visit

Each DRR queue has a quantum, expressed in bytes, and a deficit counter. When the scheduler visits an active non-empty queue, it adds the quantum to the counter. It examines the packet at the head. If the packet fits within the available credit, the scheduler transmits the whole packet and subtracts its size. It may continue until the next head packet no longer fits.

The decisive step comes when a packet is too large for the remaining credit. The scheduler does not discard the remainder or force the packet into fragments. If the queue stays backlogged, the counter survives. On the next visit, another quantum is added. A 1,500-byte packet facing a 1,000-byte quantum can wait through the first visit with 1,000 units of credit, receive another 1,000 on the next, transmit, and leave 500 for subsequent work.

The counter does not remember an application promise or a particular human’s deprivation. It records unused service credit for a queue under this scheduler. If the queue empties, the counter resets, preventing an idle source from banking an unlimited burst claim for later. The small state variable repairs a mismatch between indivisible packets and byte-based shares over repeated rounds.

The quantum writes the weight

Equal quanta express equal intended long-run shares among queues that remain backlogged. Unequal quanta turn the same mechanism into weighted service: a queue receiving twice the quantum can be assigned roughly twice the long-run link share, subject to packetisation error and the active set.

The paper bounds service around the number of opportunities multiplied by the queue’s quantum, with an error related to maximum packet size. That is a stronger and more careful statement than saying every instant is equal. During a short interval, one queue may be ahead because a whole packet has just crossed the wire. Over continued service, retained deficits compensate the shortfall instead of erasing it at each rotation.

This accounting also explains the algorithm’s speed. DRR keeps an active list, visits queues in cyclic order and uses simple additions, comparisons and subtractions. It avoids ranking every active flow by a changing timestamp. The original work presented nearly perfect throughput fairness with O(1) packet-processing work and an implementation simple enough for hardware, under its stated quantum and packet assumptions.

Those qualifications matter. “O(1)” is not a claim that every line card, queue hierarchy or classifier consumes literally the same cycles. It describes how the scheduling operation scales rather than promising a universal implementation cost. Likewise, the fairness bound does not turn packet transmission into ideal infinitesimal fluid service.

Fairness begins after classification

A scheduler can only be fair to the objects it can see. A DRR queue might correspond to one flow, a hashed group of flows, a customer, a traffic class or a child scheduler. If ten applications collide in one queue while another application receives a private queue, DRR divides service between those queues; it does not reach inside the shared queue to restore per-application equality.

The phrase “fair to flows” therefore hides a control decision. Someone defines a flow key or class, chooses how many queues exist, assigns packets to them and sets the quanta. An incorrect classifier can convert a mathematically sound service discipline into an operationally perverse allocation. A well-chosen quantum can express relative capacity but cannot identify who deserves it.

Packet-size distribution is another condition. The simple 1,500-versus-500 example exposes ordinary round robin’s bias, but it is not a measurement from a backbone router. Real queues carry changing mixes. Operators need maximum packet assumptions, observed distributions and the active-set history before interpreting a counter or a fairness chart.

Throughput fairness is not a delay bound

The original paper says plainly that basic DRR provides fairness in throughput but no latency bounds, then explores augmentation for latency-sensitive service. This is not a footnote. A continuously backlogged queue can receive its bounded long-run share while an individual packet waits behind service opportunities for many other active queues. Queue count, quanta, packet sizes and hierarchy shape the delay.

DRR also does not decide whether a packet should have entered the system. It is a scheduler: it chooses among eligible queued packets. Admission control asks whether work should be accepted. Shaping controls an arrival or departure rate. Active queue management decides when to mark or drop before a buffer is full. Congestion control changes sender behaviour. RFC 7567 lists fair-queuing schedulers, including DRR, while treating their role separately from AQM.

Combining these mechanisms can be sensible. Confusing them makes evidence unusable. A low DRR deficit is not proof of low congestion. A high counter is not a customer debt. Equal byte shares do not prove equal application latency, and a scheduler’s successful dequeue does not prove delivery across the network.

George Varghese’s place in the fast path

UCLA Samueli lists George Varghese as a Distinguished Professor of Computer Science and holder of the Jonathan B. Postel Chair in Networking. His work is associated with network algorithmics: finding bottlenecks in routers and end systems, then matching algorithms to hardware and implementation constraints. UCLA records that he joined in 2016 after Microsoft Research and faculty appointments at UC San Diego and Washington University in St. Louis.

ACM SIGCOMM recognised him in 2014 for sustained, diverse contributions to network algorithmics with impact in research and industry. The Internet Hall of Fame, which inducted him in 2021, cites DRR among those contributions and reports its historical use in Cisco’s Gigabit Switch Router.

Yet the historical grammar must remain plural. The paper lists M. Shreedhar first and George Varghese second. DRR is their joint work. Profiling Varghese can illuminate the network-algorithmics method — begin with the precise resource a fast path consumes, preserve a cheap structure, and add only the state needed to correct it — without manufacturing a sole-inventor legend.

What the counter proves, and what it cannot

A deficit trace can show how much service credit a queue carried between visits. Together with its quantum, packet lengths and dequeue history, it can help reconstruct why a packet was or was not sent. It cannot identify a subscriber unless classification supplies that link. It cannot disclose the downstream path, congestion state or application result.

For an audit, record the active queues, quantum per queue, packet-size distribution, counter evolution, queue occupancy and transmitted bytes. Keep separate records for drops or marks from AQM, shaping state, classifier changes and performance. If throughput shares look correct while tail latency deteriorates, that is not a contradiction: the two measurements answer different questions.

The deeper lesson is almost administrative. Fairness is not created by a symmetrical pointer. It emerges from the unit being counted, the history retained and the population placed behind each counter. DRR made round robin count the link’s scarce unit rather than the envelope carrying it. It did not relieve operators of deciding whose traffic each envelope represents.

Sources