Fair Queueing

Picture a road with a single lane merging from four on-ramps. If one driver floors the accelerator and never yields, everyone else waits indefinitely — a textbook starvation scenario. The same thing happens on shared network links: a single flow that sends as fast as it can can crowd out every other conversation on the wire.

Fair queueing is the family of scheduling algorithms that prevent this. The core idea dates to Alan Demers, Srinivasan Keshav, and Scott Shenker's 1989 paper on simulating a bit-by-bit round robin: instead of draining one sender's queue until it is empty, the router serves each flow in turn, one chunk at a time, so that every flow gets its share of the link capacity.

Two widely deployed variants keep the idea practical:

• Weighted Fair Queueing (WFQ) — assigns each flow a weight and serves it proportionally. A flow with weight 2 gets twice the bandwidth of one with weight 1.
• Deficit Round-Robin (DRR) — simpler to implement in hardware. Each flow accumulates a deficit counter every round; if a packet fits in the current credit, it is sent and the cost is deducted.

Both guarantee that no flow starves: even if one sender blasts packets at line rate, the others still receive their allocated share. That guarantee is surprisingly hard to get right — and the math behind it is where things get interesting.

Three flows share a single bottleneck link. Flow A is greedy and submits packets continuously. Flows B and C send at a modest rate. Switch between scheduling modes to see the difference.

<!-- {{c_html_intro}} -->
<div class="controls">
  <label class="mode-label">{{label_mode}}</label>
  <div class="btn-group">
    <button id="btn-fifo" class="mode-btn active" type="button">FIFO</button>
    <button id="btn-fq" class="mode-btn" type="button">{{label_fq}}</button>
  </div>
  <button id="btn-reset" class="ghost" type="button">{{btn_reset}}</button>
</div>
<p class="hint">{{hint_para}}</p>
<div class="flows" id="flows-container">
  <!-- {{c_flows_rendered}} -->
</div>
<div class="link-bar">
  <span class="link-label">{{label_link}}</span>
  <div id="link-vis" class="link-vis"></div>
</div>
<div id="status" class="status"></div>

/* {{c_css_intro}} */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; padding: 14px; }
.controls { display: flex; align-items: center; gap: .6rem; flex-wrap: wrap; margin-bottom: .5rem; }
.mode-label { font-weight: 600; font-size: .9rem; }
.btn-group { display: flex; border: 1px solid #1d3557; border-radius: 8px; overflow: hidden; }
.mode-btn { font: 600 13px system-ui; padding: .3rem .7rem; border: none; background: #fff; color: #1d3557; cursor: pointer; }
.mode-btn.active { background: #1d3557; color: #fff; }
button.ghost { font: 600 13px system-ui; padding: .3rem .8rem; border: 1px solid #aaa; background: #fff; color: #444; border-radius: 8px; cursor: pointer; }
.hint { font-size: .85rem; color: #555; margin: 0 0 .7rem; line-height: 1.4; }
.flows { display: flex; flex-direction: column; gap: .45rem; margin-bottom: .6rem; }
.flow-row { display: flex; align-items: center; gap: .5rem; }
.flow-name { width: 64px; font-weight: 700; font-size: .88rem; }
.bar-track { flex: 1; height: 22px; background: #e8eef3; border-radius: 6px; overflow: hidden; position: relative; }
.bar-fill { height: 100%; border-radius: 6px; transition: width .18s ease; }
.bar-label { position: absolute; right: 6px; top: 50%; transform: translateY(-50%); font-size: .75rem; color: #333; font-weight: 600; }
.flow-a .bar-fill { background: #e63946; }
.flow-b .bar-fill { background: #2a9d8f; }
.flow-c .bar-fill { background: #f4a261; }
.link-bar { display: flex; align-items: center; gap: .5rem; margin-bottom: .5rem; }
.link-label { font-size: .8rem; font-weight: 600; color: #555; width: 64px; }
.link-vis { flex: 1; height: 14px; background: #cdd9e3; border-radius: 4px; overflow: hidden; display: flex; gap: 1px; }
.link-seg { height: 100%; flex: 0 0 auto; }
.seg-a { background: #e63946; }
.seg-b { background: #2a9d8f; }
.seg-c { background: #f4a261; }
.status { font-size: .88rem; font-weight: 600; min-height: 1.2em; color: #1d3557; margin-top: .2rem; }

// Code not found

Under FIFO, Flow A dominates and the others starve. Under Fair Queueing (DRR), each flow gets its allocated share regardless of how aggressively Flow A sends. Notice how the byte counters diverge in FIFO mode but stay proportional in fair mode.

The ideal fair scheduler would interleave flows bit by bit — giving each flow exactly $\frac{1}{n}$ of the link at every instant. That is perfectly fair but physically impossible: network packets are indivisible.

Real algorithms approximate this ideal, and the differences matter:

• Bit-by-bit round robin (GPS) — the theoretical reference point. Every active flow is served simultaneously at rate $\frac{C}{n}$ (where $C$ is link capacity and $n$ is the number of active flows). Perfectly fair, impossible to implement.
• WFQ (Weighted Fair Queueing) — approximates GPS by computing a virtual finish time for each packet and sending the one with the smallest finish time. Complexity: $O(\log n)$ per packet (priority queue over $n$ flows). Provable delay bound: a packet of size $L$ in a flow with weight $w_i$ experiences at most $\frac{L}{C}$ extra delay versus GPS.
• DRR (Deficit Round-Robin) — avoids the priority queue. Each flow gets a quantum $Q$ of credit per round. If the head-of-line packet fits in the current deficit, it is sent; otherwise the credit carries over. Complexity: $O(1)$ per packet. No per-packet timestamp needed. Preferred in line-rate hardware.

The max-min fairness guarantee both WFQ and DRR provide can be stated precisely: if any flow is bottlenecked, its allocation cannot be increased without reducing the allocation of another flow that is receiving less. This is the scheduler's version of the cake-cutting problem — and like load balancing, the right answer depends heavily on how you define "fair."

One subtlety: DRR's fairness guarantee is per-round, not per-instant. A large packet in one flow can delay a small packet in another for up to one quantum. WFQ's GPS approximation is tighter but costs more in hardware resources.

The "give every tenant its share" problem appears everywhere a bottleneck is shared:

• Internet routers — ISPs use WFQ or DRR to enforce per-customer bandwidth contracts and prevent one heavy user from degrading voice/video for neighbors.
• Operating system schedulers — Linux's Completely Fair Scheduler (CFS) applies the same max-min principle to CPU time: each process gets a share proportional to its weight (nice value), and no runnable process starves.
• Disk and storage I/O — SSDs and storage arrays use fair-queueing variants to balance latency between competing tenants in multi-tenant environments.
• Cloud and datacenter networking — hypervisors enforce per-VM bandwidth limits using DRR-like token buckets so a noisy neighbor cannot monopolize a shared NIC.
• Active Queue Management (AQM) — algorithms like FQ-CoDel pair fair queueing with congestion signals to keep latency low while ensuring fairness; this is the default in many Linux deployments today.

Fair queueing is also conceptually related to max-flow: both ask how to route capacity through a shared resource, but fair queueing adds the time dimension — capacity must be allocated not just in total but per unit time.

Fair queueing solves a deceptively simple problem: how do you share a wire so that no single sender can crowd out everyone else? The answer — serve each flow in round-robin turns, one quantum at a time — is easy to state but took careful math to get right.

The key insight is that fairness is not free: FIFO queues are trivial to implement but silently reward aggression. Weighted Fair Queueing and Deficit Round-Robin both pay a small bookkeeping cost to enforce the max-min guarantee, and that cost turns out to be very reasonable — $O(\log n)$ or even $O(1)$ per packet.

The next time a video call stays crisp while someone else on the same network downloads a huge file, thank a fair queueing scheduler running somewhere in the path — quietly giving every flow its fair share, one packet at a time.