Introduction

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.

Try It

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.

<!-- Fair Queueing demo — FIFO vs DRR (Deficit Round-Robin) -->
<div class="controls">
  <label class="mode-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">Fair Queueing (DRR)</button>
  </div>
  <button id="btn-reset" class="ghost" type="button">Reset</button>
</div>
<p class="hint">Flow A is greedy (sends 3x as much). Flows B and C are modest. Watch how FIFO lets A dominate while DRR keeps all flows proportional to their weights.</p>
<div class="flows" id="flows-container">
  <!-- flow rows injected by JS -->
</div>
<div class="link-bar">
  <span class="link-label">Link:</span>
  <div id="link-vis" class="link-vis"></div>
</div>
<div id="status" class="status"></div>

/* Styles for the fair-queueing demo */
* { 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; }

/* Fair Queueing demo logic — FIFO vs Deficit Round-Robin */
const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));

/* Flow definitions with weights */
const FLOWS = [
  { id: 'a', cls: 'flow-a', weight: 3 }, /* Flow A is greedy with weight 3 */
  { id: 'b', cls: 'flow-b', weight: 1 },
  { id: 'c', cls: 'flow-c', weight: 1 }
];
const LINK_CAPACITY = 10; /* link capacity in bytes per tick */
const QUANTUM = 1;        /* DRR quantum — each flow earns QUANTUM*weight credits per round */
const TICK_MS = 320;      /* milliseconds per simulation tick */

let mode = 'fifo'; /* current scheduling mode */
let bytes = { a: 0, b: 0, c: 0 }; /* cumulative bytes sent per flow */
let deficit = { a: 0, b: 0, c: 0 }; /* DRR deficit counters */
let rrIndex = 0; /* round-robin index for DRR */
let timer = null;
let linkHistory = []; /* history of which flow used the link each byte */

/* Render per-flow byte bars */
function renderFlows() {
  const container = document.getElementById('flows-container');
  container.innerHTML = '';
  const total = bytes.a + bytes.b + bytes.c || 1;
  FLOWS.forEach(f => {
    const row = document.createElement('div');
    row.className = 'flow-row ' + f.cls;
    const pct = Math.round((bytes[f.id] / total) * 100);
    row.innerHTML =
      '<span class="flow-name">Flow ' + f.id.toUpperCase() + ' (w=' + f.weight + ')</span>' +
      '<div class="bar-track"><div class="bar-fill" style="width:' + pct + '%"></div>' +
      '<span class="bar-label">' + bytes[f.id] + ' B</span></div>';
    container.appendChild(row);
  });
}

/* Render the link utilisation strip */
function renderLink() {
  const vis = document.getElementById('link-vis');
  const segs = linkHistory.slice(-30);
  vis.innerHTML = '';
  const w = 100 / 30;
  segs.forEach(id => {
    const seg = document.createElement('div');
    seg.className = 'link-seg seg-' + id;
    seg.style.width = w + '%';
    vis.appendChild(seg);
  });
}

/* FIFO step — Flow A sends greedily and gets most of the link */
function stepFIFO() {
  /* Flow A sends 8 bytes, B and C get only 1 each per tick */
  const SEND_A = 8, SEND_B = 1, SEND_C = 1;
  bytes.a += SEND_A;
  bytes.b += SEND_B;
  bytes.c += SEND_C;
  /* record which flow owned each byte on the link */
  for (let i = 0; i < SEND_A; i++) linkHistory.push('a');
  for (let i = 0; i < SEND_B; i++) linkHistory.push('b');
  for (let i = 0; i < SEND_C; i++) linkHistory.push('c');
}

/* DRR step — serve flows round-robin proportional to weights */
function stepDRR() {
  /* Each flow gets credit proportional to its weight each round */
  const sent = { a: 0, b: 0, c: 0 };
  let budget = LINK_CAPACITY;
  let rounds = 0;
  while (budget > 0 && rounds < 20) {
    rounds++;
    for (let i = 0; i < FLOWS.length && budget > 0; i++) {
      const f = FLOWS[(rrIndex + i) % FLOWS.length];
      /* all flows use 1-byte packets so weight alone determines the share */
      const pktSize = 1;
      deficit[f.id] += QUANTUM * f.weight;
      while (deficit[f.id] >= pktSize && budget >= pktSize) {
        deficit[f.id] -= pktSize;
        sent[f.id] += pktSize;
        budget -= pktSize;
      }
    }
    rrIndex = (rrIndex + 1) % FLOWS.length;
  }
  bytes.a += sent.a;
  bytes.b += sent.b;
  bytes.c += sent.c;
  for (let i = 0; i < sent.a; i++) linkHistory.push('a');
  for (let i = 0; i < sent.b; i++) linkHistory.push('b');
  for (let i = 0; i < sent.c; i++) linkHistory.push('c');
}

/* Update the status line with current share percentages */
function updateStatus() {
  const total = bytes.a + bytes.b + bytes.c || 1;
  const pctA = Math.round((bytes.a / total) * 100);
  const pctB = Math.round((bytes.b / total) * 100);
  const pctC = Math.round((bytes.c / total) * 100);
  const el = document.getElementById('status');
  if (mode === 'fifo') {
    el.textContent = i18nFmt('FIFO — A: %a%% · B: %b%% · C: %c%% (A starves the others)', { a: pctA, b: pctB, c: pctC });
  } else {
    el.textContent = i18nFmt('Fair (DRR) — A: %a%% · B: %b%% · C: %c%% (proportional to weights)', { a: pctA, b: pctB, c: pctC });
  }
}

function tick() {
  if (mode === 'fifo') stepFIFO();
  else stepDRR();
  renderFlows();
  renderLink();
  updateStatus();
}

function startTimer() {
  if (timer) clearInterval(timer);
  timer = setInterval(tick, TICK_MS);
}

/* Mode switch buttons */
document.getElementById('btn-fifo').addEventListener('click', () => {
  mode = 'fifo';
  document.getElementById('btn-fifo').classList.add('active');
  document.getElementById('btn-fq').classList.remove('active');
  reset();
});
document.getElementById('btn-fq').addEventListener('click', () => {
  mode = 'fq';
  document.getElementById('btn-fq').classList.add('active');
  document.getElementById('btn-fifo').classList.remove('active');
  reset();
});

function reset() {
  bytes = { a: 0, b: 0, c: 0 };
  deficit = { a: 0, b: 0, c: 0 };
  rrIndex = 0;
  linkHistory = [];
  renderFlows();
  renderLink();
  document.getElementById('status').textContent = '';
  startTimer();
}

document.getElementById('btn-reset').addEventListener('click', reset);

/* Initial render */
renderFlows();
startTimer();
Result
Console

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 Real Complexity

The ideal fair scheduler would interleave flows bit by bit — giving each flow exactly 1n\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 Cn\frac{C}{n} (where CC is link capacity and nn 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)O(\log n) per packet (priority queue over nn flows). Provable delay bound: a packet of size LL in a flow with weight wiw_i experiences at most LC\frac{L}{C} extra delay versus GPS.
  • DRR (Deficit Round-Robin) — avoids the priority queue. Each flow gets a quantum QQ 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)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.

Where It Matters

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.

Conclusion

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)O(\log n) or even O(1)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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/fair-queueing/Content licensed under CC BY-NC 4.0.