CoDel: Killing Bufferbloat by Watching Delay, Not Queue Length

The disease: bufferbloat

Memory got cheap, and network gear got fat. Router, switch, cable-modem, and OS-driver designers reasoned that a bigger packet buffer means fewer drops, and fewer drops means better throughput — so they provisioned buffers holding hundreds of milliseconds, sometimes multiple seconds, of traffic. Jim Gettys named the resulting pathology bufferbloat around 2010 after watching his home uplink inject seconds of latency during a routine file upload.

The mechanism is a direct consequence of how loss-based TCP works. Classic TCP congestion control (Reno, CUBIC) has no way to know the pipe is full except by overflowing it: it keeps inflating its congestion window until a packet is dropped. On a link with a giant buffer, that means TCP fills the entire pipe and then fills the buffer too, and the buffer stays full. Every subsequent packet — your DNS lookup, your VoIP audio, a game update, a TCP ACK — must now sit behind that standing backlog. A 1 MB buffer draining at 1 Mbps is eight seconds of delay. The link still hits full throughput; it is the latency that becomes catastrophic.

Traditional drop-tail FIFO queuing makes this worse by only reacting at the very last moment: it drops a packet exactly when the buffer is completely full, by which point the queue — and the delay — is already maximal. The buffer that was supposed to absorb bursts instead becomes a permanent delay generator.

Queue length lies; sojourn delay tells the truth

Every earlier AQM, most famously RED (Random Early Detection, Floyd & Jacobson 1993), tried to react before the buffer filled by watching the average queue length. Nichols and Jacobson's central insight is that queue length is the wrong thing to look at, because it cannot distinguish a good queue from a bad queue.

• A good queue is a transient burst — a momentary pile-up that the link drains on its own within a round trip. It is exactly what a buffer is for. Punishing it wastes capacity.
• A bad queue is a standing queue that never empties, the signature of bufferbloat. This is what must be attacked.

A snapshot of queue length looks identical in both cases. What separates them is time. CoDel therefore measures each packet's sojourn time: the delay it personally experienced sitting in this queue, computed as dequeue_time − enqueue_time from a timestamp attached at enqueue. Then comes the key statistic — CoDel tracks the minimum sojourn over a sliding window, not the average. Why the minimum? Because a standing queue forces every packet to wait at least the backlog's depth, so the minimum sojourn is the floor of the standing queue. A transient burst, by contrast, always contains at least one packet that arrives to find the queue nearly empty — a near-zero sojourn that pulls the minimum down and tells CoDel to leave the queue alone.

The algorithm, step by step

CoDel decorates an ordinary FIFO with two operations and a handful of state variables. On enqueue, stamp the packet with the current time — O(1). On dequeue, compute its sojourn time and update the state.

Two constants define "acceptable": target (default 5 ms), the standing queue delay we tolerate, and interval (default 100 ms), roughly a worst-case RTT — how long the delay must persist before we believe it is standing rather than transient.

The elegant part is how CoDel checks "minimum sojourn stayed above target for a whole interval" without storing a window of samples. It keeps a single timestamp, first_above_time. Whenever it dequeues a packet whose sojourn is below target, it clears that timer — a good packet just proved the queue is not standing. The first time sojourn goes above target, it sets first_above_time = now + interval. If the timer ever survives to fire — meaning no below-target packet appeared for a full interval — then by definition the minimum sojourn over that interval was above target, and CoDel enters the dropping state. This is the min-over-a-window test collapsed into O(1) state.

One guard protects small links: CoDel never drops if the queue holds less than one MTU (~1514 bytes), so it cannot starve a link that is barely backed up. And when a flow marks itself ECN-capable, CoDel marks the packet's Congestion Experienced codepoint instead of dropping it — same control logic, no retransmit.

The 1/√count control law

Once in the dropping state, CoDel does not drop wildly; it drops on a schedule that gets tighter over time. Each successive drop is spaced by interval / √count, where count is the number of drops since entering the state:

• First drop, then wait interval/√1 = 100 ms; if still bloated, drop again and wait interval/√2 ≈ 71 ms; then interval/√3 ≈ 58 ms; and so on — a smoothly accelerating cadence.

The square root is not arbitrary. The classic Mathis TCP model says a bulk TCP flow's throughput is proportional to 1/√p, where p is the packet drop probability. Increasing the drop rate on a 1/√count schedule therefore produces a roughly linear reduction in the sending rate — and hence a linear drain of the standing queue — over time. CoDel is, in effect, a linear controller for queue delay wearing a very cheap disguise. The moment sojourn falls back below target, CoDel leaves the dropping state and stops.

Two refinements keep it responsive. When CoDel re-enters the dropping state soon after leaving it (within roughly 16 intervals), it resumes near the previous count rather than starting over at 1, so a queue that keeps rebuilding is beaten down quickly instead of slowly re-ramping each time. And to avoid a real square root per drop, the Linux implementation maintains a reciprocal-square-root estimate (rec_inv_sqrt) updated with a single Newton step — keeping the whole thing integer-cheap.

Why it is parameter-free

RED's fatal flaw was configuration: its thresholds are expressed in bytes or packets, so the "right" value depends on the link rate and traffic mix. A setting tuned for a 1 Mbps DSL line is nonsense on a 1 Gbps fiber drop, and operators mostly gave up and left RED off. CoDel sidesteps this entirely because its two constants are expressed in time. Five milliseconds of standing delay is five milliseconds of standing delay whether the link runs at 56 kbps or 10 Gbps — the time-based threshold is self-normalizing across five orders of magnitude of bandwidth. That is what "essentially parameter-free" means: the defaults just work, and CoDel adapts to the link's actual behavior instead of to a number an operator guessed.

The cost is genuinely tiny. Per packet, CoDel does O(1) work — one timestamp at enqueue, one subtraction and a few comparisons at dequeue — with no sorting, no scanning, and no per-packet iteration. The state per queue is a boolean dropping, the counters count and lastcount, drop_next, and first_above_time: a handful of scalars plus one timestamp per buffered packet. It slots into a router's fast path without measurable overhead.

fq_codel and where it runs

Plain CoDel manages a single FIFO, so a greedy bulk flow can still make a latency-sensitive flow queue behind it. fq_codel (FlowQueue-CoDel, RFC 8290) fixes this by hashing packets into many sub-queues (default 1024), running an independent CoDel instance in each, and serving them with a Deficit Round Robin scheduler (quantum ≈ one MTU). Crucially, it maintains separate "new flows" and "old flows" lists and gives brand-new or sparse flows priority. The practical effect is dramatic: a DNS query, a VoIP packet, a game update, or a bare TCP ACK sails through with near-zero queuing delay even while a bulk download saturates the link, because those thin flows land in their own lightly-loaded queues.

This is not a paper result. fq_codel is the default qdisc in Linux (via net.core.default_qdisc), the default in OpenWrt home routers, and shipped through the bufferbloat.net / CeroWrt effort led by Dave Täht alongside Nichols and Jacobson. Apple deployed fq_codel-style AQM across macOS and iOS. Its successor CAKE adds built-in shaping and per-host fairness. On cable, DOCSIS 3.1 mandated AQM but chose the delay-based PIE controller (RFC 8033) instead. And the modern L4S architecture builds a dual-queue, ECN-marking AQM on the same "watch the delay" foundation CoDel established.

The honest limits: CoDel manages delay, not bandwidth — it cannot conjure capacity, only keep the standing queue small while the link stays full. It relies on responsive senders, so an unresponsive UDP flood needs fq_codel's per-flow isolation to be contained. And it only governs the buffer it lives in; if the real bottleneck buffer sits in a driver ring or a modem you do not control, CoDel upstream cannot help — which is exactly why Byte Queue Limits (BQL) and the make-wifi-fast airtime work grew up alongside it.

Active Queue Management schemes, and what signal each one actually watches to decide when to drop.

Scheme	Signal watched	Tuning needed	Key idea
Drop-tail (FIFO)	Buffer full / not full	Buffer size	Drops only when the buffer overflows — the direct cause of bufferbloat
RED (1993)	Average queue length (bytes)	min/max thresholds, max_p, weight — all rate-dependent	Probabilistic early drop; notoriously hard to configure
PIE (RFC 8033)	Estimated queue delay (from dequeue rate)	A few, mostly auto	Proportional-Integral controller; chosen for DOCSIS 3.1 modems
CoDel (2012)	Min packet sojourn time over an interval	None — target & interval are fixed times	Drop only when standing delay persists past target
fq_codel (2018)	Per-flow sojourn + deficit-round-robin fairness	None	CoDel per hashed flow + fair scheduling; the Linux default