Tail Drop, Buffer Bloat, and How Much Queue a Link Actually Needs

A router’s output queue is a bounded buffer between a fast input and a slower output. When the output is saturated, packets accumulate; when the buffer is full, the next packet to arrive is discarded. That discard policy is called tail drop because the packet that dies is the one at the tail of the queue, and it is the simplest possible queue management: no state beyond a length counter, no computation, no configuration.

Its simplicity is why it was deployed everywhere and why it is the reference against which every other queue discipline is judged. Its defects are equally simple to state, and they are the reason the field spent three decades replacing it.

The signal is late by construction

Tail drop emits exactly one kind of feedback: a dropped packet, and only when the queue is already full. By that time the queue has been growing for as long as it took to fill, which on a path with a large bandwidth-delay product is many round trips. Every sender sharing the queue has been increasing its window throughout that period, because nothing told it to stop.

The consequence is a synchronization effect. When the buffer overflows, several senders lose packets within a short interval, so several halve their windows at nearly the same time. The aggregate rate falls sharply, the queue drains completely, and the link goes idle. Then all senders increase again, in step, until the buffer fills once more. The oscillation is at the scale of the whole set of flows rather than of individual ones, and its amplitude is set by the buffer size.

The effect is worse with a small number of large flows. A single flow that fills a buffer overflows it, halves, and then must climb back; with only that one flow, the link oscillates between full and partially idle. This is the mechanism that makes a drop-tail queue’s utilization depend on how many flows share it, and on how well their increase and decrease cycles happen to interleave.

What the buffer depth costs in latency

A buffer of B bytes on a link of rate R holds at most B/R seconds of data. That is the queueing delay a packet experiences when the queue is full, and it applies to every packet that traverses the queue, including packets from flows that are not responsible for the queue’s depth.

The numbers are large enough to matter. A 1 Gbit/s link with a 1 MB buffer holds 8 milliseconds. The same link with an 8 MB buffer holds 64 milliseconds, which is comparable to a transatlantic propagation delay. On a consumer uplink of 10 Mbit/s with a 1 MB buffer, the queueing delay reaches 800 milliseconds, which is enough to make interactive traffic unusable and to break the timing assumptions of protocols layered above. The pathology is called bufferbloat, and its defining feature is that the buffer is sized by the memory the device happens to have rather than by the delay the network can tolerate.

The latency is not merely an inconvenience for other traffic. It corrupts the congestion control loop’s own measurement. A sender that measures round-trip time to estimate capacity sees the queue’s delay as part of the path’s delay, so its estimate of the bandwidth-delay product grows as the queue grows. Delay-based algorithms then interpret their own contribution to the queue as evidence that the path is longer than it is, which is the base-RTT problem described in queueing delay as a signal.

The bandwidth-delay product rule and its limits

The classic sizing rule is that a link needs a buffer equal to its bandwidth-delay product, so that a single flow can keep the link busy while its window is recovering from a loss. The argument is a throughput argument: if the buffer holds less than one window’s worth of data, a sender that halves its window on loss cannot refill the pipe before the queue drains, and the link goes idle. On a link with R bits per second and round trip T, the product is R*T bits, and the rule says the buffer should hold that much.

For a 1 Gbit/s link with a 100 ms round trip, the product is 12.5 MB, which at 1500 bytes per packet is about 8300 packets. That is a large buffer, and the rule’s critics point out that filling it costs 100 ms of delay for every flow crossing the link. The rule is a statement about one flow’s ability to keep the link busy; it says nothing about what the queue depth does to latency for everyone else.

The counter-rule from the small-buffer literature is that the requirement shrinks as the number of flows grows: with N flows sharing a link, the buffer needed to keep the link busy is on the order of R*T/sqrt(N) rather than R*T, because the flows’ window swings are independent and partly cancel, so no single swing has to be absorbed by the buffer. The two rules describe different regimes: the product rule applies when few flows share a link and each has a large window, and the square-root rule applies when many flows share it and their swings average out. Neither is right in general, and the correct size depends on the number of flows, which the router does not know.

There is also a hard constraint that neither rule addresses. A buffer that is too small drops packets from flows that are behaving correctly, because bursts arrive at the queue faster than the output can drain them even when the average rate is below capacity. A burst of k packets arriving back-to-back at a link serving one packet per slot requires k slots of buffer to avoid a drop, regardless of the average rate. This is why very small buffers work in data centers, where the traffic is many small flows and the round trips are microseconds, and fail on wide-area links where a single flow’s window can be megabytes.

The drop-tail fairness problem

Tail drop has no notion of which flow a packet belongs to, so the packets it drops are the ones that happen to arrive when the queue is full. That is not the same as dropping from the flows that are causing the congestion.

Two effects follow. A flow that sends in bursts is more likely to have a packet at the tail when the queue overflows than a flow that sends smoothly at the same average rate, so bursty flows are penalized. And a flow that has already lost a packet and reduced its window is less likely to have packets in the queue at the moment of the next overflow, so it is less likely to lose again — which sounds fair but interacts badly with the synchronization effect, because the flows that just reduced are precisely the ones that are not represented when the next loss event occurs.

The lock-out phenomenon is the extreme case. A flow whose packets are consistently dropped never gets an acknowledgement, never increases its window, and can be starved indefinitely while other flows cycle through the queue. The mechanism requires a specific timing relationship between the starved flow’s retransmissions and the queue’s occupancy, which makes it rare in practice and catastrophic when it occurs.

Global synchronization and lock-out are both consequences of the same design choice: the queue’s drop decision is made on arrival order alone, with no memory of which flows are contributing to the congestion. Any scheme that keeps per-flow state can do better, at the cost of the state.

What a drop-tail queue is still good for

The case for tail drop is not nostalgia. It has three properties that more sophisticated disciplines struggle to match.

It is stateless, so it costs nothing per packet and nothing per flow, which matters at line rate on a device with a deep pipeline. It is deterministic in the sense that the drop decision depends only on the current queue length, so its behaviour under overload is easy to reason about. And it is transparent to transport protocols: it does not require ECN support, does not require the sender to interpret a new signal, and does not change its behaviour based on what the transport is doing.

The last property is also the reason it is hard to replace. A queue discipline that drops packets early, before the buffer is full, changes the loss process that every congestion control algorithm was tuned against. Senders that expect losses at a particular queue depth see them earlier, and their window dynamics shift. The deployment of an early-drop discipline therefore has to be coordinated with the algorithms running above it, which is why the transition described in active queue management has been gradual and uneven.

Sizing in practice

The rules that survive scrutiny are about bounds rather than about a single number. A buffer should be large enough to absorb the burst that a single flow’s window can produce in one round trip, which gives the bandwidth-delay product as an upper bound for a lightly multiplexed link. It should be small enough that the queueing delay it can add is a small fraction of the delay budget of the applications crossing it, which gives a bound in milliseconds rather than in bytes. And it should be deep enough that a burst of back-to-back packets from a correct sender is not dropped, which gives a bound in packets rather than in bytes.

These three bounds conflict, and the resolution is to stop treating the buffer as the only place where congestion is signalled. If the queue can report its state before it is full, as ECN allows, then the buffer’s depth stops being the mechanism that delivers the signal, and it can be sized for burst absorption alone. That decoupling is the central idea of the next stage, and it is why buffer sizing and queue management are the same subject rather than two.