Introduction

Every router on the Internet has a queue: a short waiting room where packets sit before they are forwarded. When traffic arrives faster than the link can drain it, the queue grows. Fill it completely and new packets are dropped. Leave it only half-full and the link sits idle. Finding the right balance is one of the oldest problems in networking.

For most of the 1990s, routers used a strategy called tail-drop: accept packets until the buffer is full, then discard. Simple — but disastrous. A large buffer means many packets are accepted before any signal reaches the sender, so TCP backs off late and the whole connection spends minutes at high latency. That phenomenon is bufferbloat: the paradox where adding more buffer to a router makes your video call worse.

Active Queue Management (AQM) is the family of algorithms that solved this. Instead of waiting for the buffer to overflow, an AQM algorithm drops or marks packets early, while the queue is still short. The signal reaches TCP fast, senders slow down sooner, and the queue stays shallow — which keeps latency low for everyone sharing the link.

The two landmark algorithms are RED (Random Early Detection, Sally Floyd & Van Jacobson, 1993) and CoDel (Controlled Delay, Kathleen Nichols & Van Jacobson, 2012). RED was the first practical AQM and shipped in countless routers; CoDel is parameter-free and has become the modern default in Linux and home routers worldwide.

Try It

This simulator runs three queue strategies side by side. Packets arrive in bursts; each strategy decides whether to drop early or wait for the buffer to fill.

<!-- AQM demo — three queue strategies compared side by side -->
<div class="controls">
  <label>Burst size: <input id="burst" type="range" min="1" max="20" value="10"> <span id="burst-val">10</span> pkts</label>
  <label>Buffer size: <input id="bufsize" type="range" min="10" max="60" value="30"> <span id="buf-val">30</span> pkts</label>
  <div class="btn-row">
    <button id="btn-run" type="button">Run</button>
    <button id="btn-pause" type="button" class="ghost" disabled>Pause</button>
    <button id="btn-reset" type="button" class="ghost">Reset</button>
  </div>
</div>
<div class="panels">
  <div class="panel" id="panel-tail">
    <div class="panel-title">Tail-Drop (no AQM)</div>
    <canvas id="cv-tail" width="220" height="120"></canvas>
    <div class="metric">Avg latency: <span id="lat-tail">0</span> ms</div>
    <div class="metric">Dropped: <span id="drop-tail">0</span></div>
  </div>
  <div class="panel" id="panel-red">
    <div class="panel-title">RED</div>
    <canvas id="cv-red" width="220" height="120"></canvas>
    <div class="metric">Avg latency: <span id="lat-red">0</span> ms</div>
    <div class="metric">Dropped: <span id="drop-red">0</span></div>
  </div>
  <div class="panel" id="panel-codel">
    <div class="panel-title">CoDel</div>
    <canvas id="cv-codel" width="220" height="120"></canvas>
    <div class="metric">Avg latency: <span id="lat-codel">0</span> ms</div>
    <div class="metric">Dropped: <span id="drop-codel">0</span></div>
  </div>
</div>
<div id="status-bar"></div>

/* Layout for the three-panel AQM simulator */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; padding: 14px .5rem .5rem; }
.controls { display: flex; flex-direction: column; gap: .4rem; margin-bottom: .6rem; }
.controls label { font-size: .85rem; display: flex; align-items: center; gap: .4rem; flex-wrap: wrap; }
input[type=range] { width: 110px; }
.btn-row { display: flex; gap: .4rem; flex-wrap: wrap; margin-top: .2rem; }
button { font: 600 13px system-ui; padding: .35rem .8rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 7px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button:disabled { opacity: .45; cursor: not-allowed; }
.panels { display: flex; gap: .6rem; flex-wrap: wrap; }
.panel { background: #f4f7fa; border: 1px solid #cdd9e3; border-radius: 10px;
         padding: .5rem .6rem; min-width: 200px; flex: 1; }
.panel-title { font-weight: 700; font-size: .85rem; margin-bottom: .3rem; color: #1d3557; }
canvas { display: block; width: 100%; height: auto; border-radius: 5px; background: #fff; border: 1px solid #e0e6ed; }
.metric { font-size: .8rem; margin-top: .25rem; color: #444; }
.metric span { font-weight: 700; color: #1d3557; }
#status-bar { font-size: .82rem; margin-top: .5rem; min-height: 1.2em; color: #555; }

const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));

/* Discrete-time queue simulator — each tick one burst arrives and LINK_RATE packets are drained. */
/* All three queues share the same link rate and burst size so the comparison is fair. */

const LINK_RATE = 5;     /* packets drained per tick */
const ARRIVAL_INTERVAL = 80;  /* ms between burst ticks (unused directly, kept for reference) */
const TICK_MS = 50;      /* wall-clock ms per simulation tick */
const HISTORY = 60;      /* number of ticks kept in the chart history */

/* AQM tuning parameters */
const RED_MIN_TH = 0.3;  /* RED min threshold (fraction of buffer) */
const RED_MAX_TH = 0.7;  /* RED max threshold (fraction of buffer) */
const RED_P_MAX  = 0.1;  /* RED max drop probability */
const RED_WQ     = 0.002;/* EWMA weight for queue length average */
const CODEL_TARGET_MS = 5;   /* CoDel target sojourn time in ms */
const CODEL_INTERVAL_MS = 100;/* CoDel sliding window length in ms */

let bufSize = 30, burstSize = 10;
let timer = null;
let tick = 0;

/* Per-strategy simulation state */
function makeState() {
  return {
    queue: [],        /* packets currently waiting */
    dropped: 0,
    latencies: [],
    avgQ: 0,          /* EWMA queue length for RED */
    codelMin: Infinity,/* minimum sojourn seen in current window */
    codelSince: null, /* when overload was first detected */
    codelDropping: false,
    codelDropCount: 0,
    history: [],      /* rolling chart data */
    totalSent: 0
  };
}

const states = { tail: makeState(), red: makeState(), codel: makeState() };

/* Arrival phase — add burstSize packets, apply AQM drop logic before enqueue */
function enqueue(st, mode) {
  for (let i = 0; i < burstSize; i++) {
    if (st.queue.length >= bufSize) {
      st.dropped++;
      continue;
    }
    const pkt = { arrivedAt: tick * TICK_MS };
    /* RED drop decision before enqueue */
    if (mode === 'red') {
      st.avgQ = (1 - RED_WQ) * st.avgQ + RED_WQ * st.queue.length;
      const fill = st.avgQ / bufSize;
      if (fill >= RED_MIN_TH) {
        const p = fill >= RED_MAX_TH ? RED_P_MAX : RED_P_MAX * (fill - RED_MIN_TH) / (RED_MAX_TH - RED_MIN_TH);
        if (Math.random() < p) { st.dropped++; continue; }
      }
    }
    st.queue.push(pkt);
    st.totalSent++;
  }
}

/* Drain phase — remove up to LINK_RATE packets and record sojourn times */
function dequeue(st, mode) {
  const drained = Math.min(LINK_RATE, st.queue.length);
  for (let i = 0; i < drained; i++) {
    const pkt = st.queue.shift();
    const sojourn = tick * TICK_MS - pkt.arrivedAt;
    st.latencies.push(sojourn);
    if (st.latencies.length > 200) st.latencies.shift();

    /* CoDel sojourn-time tracking and drop decision */
    if (mode === 'codel') {
      st.codelMin = Math.min(st.codelMin, sojourn);
      const now = tick * TICK_MS;
      if (st.codelMin > CODEL_TARGET_MS) {
        if (!st.codelSince) st.codelSince = now;
        if (now - st.codelSince >= CODEL_INTERVAL_MS) {
          st.codelDropping = true;
        }
      } else {
        st.codelSince = null;
        st.codelDropping = false;
        st.codelDropCount = 0;
      }
      if (st.codelDropping && st.queue.length > 0) {
        const dropInterval = CODEL_INTERVAL_MS / Math.sqrt(st.codelDropCount + 1);
        if (now - (st.codelSince || now) >= dropInterval) {
          st.queue.shift();
          st.dropped++;
          st.codelDropCount++;
        }
      }
      if (tick % Math.round(CODEL_INTERVAL_MS / TICK_MS) === 0) st.codelMin = Infinity;
    }
  }
  /* record a snapshot for the rolling chart */
  const avgLat = st.latencies.length ? st.latencies.reduce((a, b) => a + b, 0) / st.latencies.length : 0;
  st.history.push({ q: st.queue.length, lat: avgLat });
  if (st.history.length > HISTORY) st.history.shift();
}

/* Draw latency curve (solid) and queue fill (dashed) on the canvas */
function draw(id, st, color) {
  const cv = document.getElementById(id);
  const ctx = cv.getContext('2d');
  const W = cv.width, H = cv.height;
  ctx.clearRect(0, 0, W, H);
  if (!st.history.length) return;
  const maxLat = Math.max(bufSize * (TICK_MS / LINK_RATE) * 2, 10);
  /* latency curve (solid) */
  ctx.strokeStyle = color;
  ctx.lineWidth = 2;
  ctx.beginPath();
  st.history.forEach((h, i) => {
    const x = (i / (HISTORY - 1)) * W;
    const y = H - (h.lat / maxLat) * H;
    i === 0 ? ctx.moveTo(x, y) : ctx.lineTo(x, y);
  });
  ctx.stroke();
  /* queue fill curve (dashed) */
  ctx.strokeStyle = '#aab4be';
  ctx.lineWidth = 1;
  ctx.setLineDash([3, 3]);
  ctx.beginPath();
  st.history.forEach((h, i) => {
    const x = (i / (HISTORY - 1)) * W;
    const y = H - (h.q / bufSize) * H;
    i === 0 ? ctx.moveTo(x, y) : ctx.lineTo(x, y);
  });
  ctx.stroke();
  ctx.setLineDash([]);
  /* CoDel 5 ms target line (red dashes) */
  const ty = H - (CODEL_TARGET_MS / maxLat) * H;
  ctx.strokeStyle = '#e63946';
  ctx.lineWidth = 1;
  ctx.setLineDash([4, 4]);
  ctx.beginPath(); ctx.moveTo(0, ty); ctx.lineTo(W, ty); ctx.stroke();
  ctx.setLineDash([]);
}

/* Update all three panels */
function updateUI() {
  const modes = ['tail', 'red', 'codel'];
  const colors = ['#1d3557', '#2a9d8f', '#e76f51'];
  const cvIds = ['cv-tail', 'cv-red', 'cv-codel'];
  modes.forEach((m, i) => {
    const st = states[m];
    draw(cvIds[i], st, colors[i]);
    const avgLat = st.latencies.length ? Math.round(st.latencies.reduce((a, b) => a + b, 0) / st.latencies.length) : 0;
    document.getElementById('lat-' + m).textContent = avgLat;
    document.getElementById('drop-' + m).textContent = st.dropped;
  });
}

function step() {
  tick++;
  enqueue(states.tail, 'tail');
  enqueue(states.red,  'red');
  enqueue(states.codel,'codel');
  dequeue(states.tail, 'tail');
  dequeue(states.red,  'red');
  dequeue(states.codel,'codel');
  updateUI();
  const elapsed = Math.round(tick * TICK_MS / 1000);
  document.getElementById('status-bar').textContent = i18nFmt('Running — %t% s elapsed', { t: elapsed });
}

function startSim() {
  if (timer) return;
  timer = setInterval(step, TICK_MS);
  document.getElementById('btn-run').disabled = true;
  document.getElementById('btn-pause').disabled = false;
}

function pauseSim() {
  clearInterval(timer); timer = null;
  document.getElementById('btn-run').disabled = false;
  document.getElementById('btn-pause').disabled = true;
  document.getElementById('status-bar').textContent = 'Paused.';
}

function resetSim() {
  pauseSim();
  tick = 0;
  ['tail', 'red', 'codel'].forEach(m => { states[m] = makeState(); });
  updateUI();
  document.getElementById('status-bar').textContent = 'Press Run to start the simulation.';
}

document.getElementById('burst').addEventListener('input', function () {
  burstSize = +this.value;
  document.getElementById('burst-val').textContent = burstSize;
});
document.getElementById('bufsize').addEventListener('input', function () {
  bufSize = +this.value;
  document.getElementById('buf-val').textContent = bufSize;
});
document.getElementById('btn-run').addEventListener('click', startSim);
document.getElementById('btn-pause').addEventListener('click', pauseSim);
document.getElementById('btn-reset').addEventListener('click', resetSim);

updateUI();
document.getElementById('status-bar').textContent = 'Press Run to start the simulation.';
Result
Console

Notice how Tail-Drop (no AQM) lets the queue fill completely before dropping — latency climbs to the buffer limit and stays there. RED starts dropping probabilistically once the average queue crosses a threshold, keeping latency lower on average. CoDel targets a minimum delay (5 ms here) and drops only when packets sit longer than that — the queue stays near-empty and latency is consistently low.

The key insight: a packet dropped early by AQM costs one retransmission. A full buffer delayed by tail-drop costs hundreds of milliseconds for every packet in the queue.

The Real Complexity

Both RED and CoDel are solved, deployed algorithms — the engineering challenge was finding the right signal and making the control loop stable.

RED — Random Early Detection (Floyd & Jacobson, 1993)

RED computes an exponential weighted moving average of the queue length, qˉ\bar{q}:

qˉ←(1−wq) qˉ+wq q\bar{q} \leftarrow (1 - w_q)\,\bar{q} + w_q\,q

where wqw_q is a small weight (typically 0.0020.002) and qq is the instantaneous queue size. When qˉ\bar{q} crosses a minimum threshold min⁡th\min_{th}, RED begins dropping packets with probability pp, rising linearly to pmaxp_{max} at max⁡th\max_{th}:

p=pmax⋅qˉ−min⁡thmax⁡th−min⁡thp = p_{max} \cdot \frac{\bar{q} - \min_{th}}{\max_{th} - \min_{th}}

Randomness spreads the drops across different TCP connections so no single flow is punished while others go unchecked. RED's weakness: those three parameters (wqw_q, min⁡th\min_{th}, max⁡th\max_{th}) must be tuned per link — and they are hard to set correctly.

CoDel — Controlled Delay (Nichols & Jacobson, 2012)

CoDel sidesteps the parameter problem by measuring the sojourn time — how long each packet actually waits inside the queue. Every packet is timestamped on arrival; when it is dequeued, CoDel records its wait. If the minimum sojourn time over a sliding window of length TT (100 ms) exceeds a target τ\tau (5 ms), CoDel declares the queue is persistently full and begins dropping. The drop rate increases as 1/t1/\sqrt{t}, where tt is time since the overload began — matching the square-root throughput of TCP.

The elegance: CoDel needs no per-link tuning. The 5 ms and 100 ms constants work across a vast range of access speeds because they track time, not queue length in bytes — a metric that is invariant to link speed.

Both algorithms exploit the same feedback loop: early signals → TCP slows → queue drains → latency falls. The difference is in what they measure and how they adapt.

Where It Matters

AQM moved from research papers into every corner of networking:

  • Home routers: fq-CoDel (fair-queue CoDel) ships in OpenWrt, DD-WRT, and most ISP-supplied routers since 2014. Enabling it on a congested home connection can cut ping times from 200 ms to under 10 ms without reducing throughput.
  • Linux kernel: tc qdisc fq_codel is the default queueing discipline in Linux since kernel 3.5 and is used on billions of Android and desktop devices.
  • Data-center switches: DCTCP (Data Center TCP) pairs with ECN-capable AQM (marking instead of dropping) to keep queues near-empty in fat-tree networks, dramatically reducing tail latency for distributed databases.
  • Video calls and gaming: a single large download sharing a link with a video call becomes tolerable under AQM, because the call's small packets are no longer stuck behind a buffer full of bulk data.
  • Streaming and CDNs: AQM at the network edge helps ABR (adaptive bitrate) streaming algorithms converge faster because the bandwidth signal they receive reflects current congestion, not a queue that has been full for several seconds.

AQM is also the complement to max-flow thinking: where max-flow asks "how much can the network carry?", AQM asks "how do we keep the carrying fast and fair for everyone?"

Conclusion

Active Queue Management turns an apparent paradox into a solution: deliberately dropping packets early keeps the Internet faster and fairer than letting buffers fill. RED showed in 1993 that probability-based early detection could replace tail-drop without sacrificing throughput. CoDel showed in 2012 that you do not even need tuning — just measure sojourn time, and the queue manages itself.

The next time your video call stays smooth while someone else downloads a large file on the same connection, thank the router's AQM algorithm. It is doing something counter-intuitive at wire speed: choosing to discard data so that less data gets stuck.

For a deeper look at how networks route those packets before the queue even forms, see the related article on max-flow.

Share this article

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

Comments

Loading comments...

https://www.kipuhub.com/en/article/active-queue-management/Content licensed under CC BY-NC 4.0.