Active Queue Management and Latency Under Load

A queue with a fixed maximum length and a single drop policy is the default in most forwarding hardware, and it has three failure modes that a queue manager can remove. It fills completely before it signals anything, so the signal arrives when the delay is already at its maximum. It drops whatever arrives when full, which is biased against bursts and against flows that happen to be sending at that instant. And because every flow sees the same full queue and backs off together, the result is a synchronised oscillation in which the link alternates between fully loaded and nearly idle.

Active queue management is the family of techniques that decide which packet to drop, or mark, before the buffer is full. The design question for all of them is the same: what signal should a sender receive, and how early should it receive it.

Tail drop and the behaviour it produces

With tail drop, the buffer accepts packets until it is full and then discards every arrival until space frees. Three consequences follow directly.

The first is latency. A packet that arrives when the buffer is nearly full waits behind almost the entire buffer, so the delay distribution’s tail is the buffer’s drain time. On a link with 200 milliseconds of buffering, the worst-case queueing delay is 200 milliseconds, and it is reached regularly under load rather than exceptionally.

The second is lockout. When a queue is full, a burst from one flow can occupy the freed space before another flow’s packets get a chance, and the second flow sees repeated loss even though its own rate is modest. The loss is not proportional to a flow’s contribution to congestion, which makes the feedback misleading.

The third is global synchronisation. All flows sharing the queue experience the loss at the same moment, so they all reduce their rates at the same moment, and the link goes idle. They then all increase again, and the cycle repeats. The link’s average utilisation is below capacity even though the flows are collectively offering more than capacity, and the oscillation shows up as delay and loss variation at a period set by the round-trip times involved.

Full queues also defeat the purpose of a buffer in a subtler way. A queue that is permanently full has no room to absorb a burst, so it cannot smooth anything; it can only delay and drop.

Early random signalling

The first widely deployed answer was random early detection, which maintains an exponentially weighted moving average of the queue length and drops arriving packets with a probability that rises linearly from zero at a minimum threshold to a maximum at a second threshold. Above the maximum threshold, drops become certain.

The averaging is the essential part. Reacting to the instantaneous queue length would make the drop probability track every burst, and a burst is exactly what a buffer is supposed to absorb. The moving average is a low-pass filter with a time constant chosen to be long compared with typical burst durations and short compared with the congestion episodes the algorithm is meant to detect, which in the original design works out to roughly a second of traffic at the packet rates it was tuned for.

Dropping at random rather than from the front or back of the queue distributes the signal across flows in proportion to their packet rates, which approximates proportionality to their rates. A flow sending twice as many packets is twice as likely to be selected, so it reduces its rate twice as much, which is roughly the fair outcome. Dropping from the tail would instead punish whichever flow happened to have a packet at the back.

Random early detection’s weakness is its dependence on queue length as the signal. The length that corresponds to a given delay depends on the link rate, so thresholds that are correct on a 10 Mbit/s link are far too permissive on a 1 Gbit/s link, where the same length drains in a hundredth of the time. It also depends on the average packet size, and on whether the traffic is bursty enough that the average hides a short but deep queue. Tuning it correctly across a range of link rates was the practical problem that motivated its successors.

Measuring sojourn time instead of length

The controlled delay algorithm takes a different signal: how long a packet has been in the queue. It timestamps each packet on arrival and, at dequeue, compares the current time with that timestamp. The queue’s characteristic delay is the minimum sojourn time observed over a recent window, which approximates the persistent queue depth and rejects the transient spikes caused by a single burst.

The algorithm’s parameters follow from the dynamics it has to control. The target is 5 milliseconds, the delay the algorithm tries to hold the queue at. The interval is 100 milliseconds, the window over which it decides whether the queue is persistently above target. The reasoning is that a queue below target is not a problem, a queue above target for longer than the interval is a standing queue that will not drain on its own, and a queue above target for a shorter period is a burst that the buffer should absorb. When the queue has been above target for a full interval, the algorithm enters a dropping state and drops packets at intervals that shorten as the queue persists, until the queue falls below target.

The choice of 5 milliseconds as a target is a compromise. It is large enough that a single burst of a few packets at a moderate link rate does not trip the algorithm, and small enough that the resulting delay is acceptable for interactive traffic. The choice of 100 milliseconds as an interval reflects the round-trip times of the flows the algorithm expects to control: a signal delivered faster than a sender can react would be wasted, and one delivered much more slowly would allow the queue to grow further.

Because the signal is a time rather than a length, the algorithm’s behaviour does not change with link rate. The same configuration holds the queue at 5 milliseconds whether the link runs at 10 Mbit/s or 10 Gbit/s, which is what made it deployable without per-link tuning. This is the central design insight: a queue’s length is only meaningful relative to the rate at which it drains.

The proportional integral controller enhanced algorithm takes a related but distinct approach. It estimates the queueing delay directly, from the queue length divided by the estimated departure rate, and computes a drop probability from both the current delay and its trend. The trend term is the integral action: a delay that is growing even though it is below target produces a stronger response than a delay that is stable at the same value. The practical effect is a faster response to a queue that is building and a gentler one to a queue that is merely present.

Marking instead of dropping

Explicit congestion notification lets a router signal congestion by setting a bit in the IP header rather than discarding the packet. The sender receives the signal through the receiver’s acknowledgement and reduces its rate as it would after a loss, but no packet is lost and no retransmission is needed.

The advantage is largest for short flows and for latency-sensitive traffic. A lost packet costs a retransmission, which costs at least one round trip, and for a flow that only sends a few packets the retransmission may cost more than the flow’s entire transfer. A marked packet costs nothing except the rate reduction the sender applies. Marking also avoids the ambiguity between congestion loss and corruption loss, which loss-based senders cannot distinguish.

The costs are deployment-related. Both endpoints must negotiate support, the marking must survive every device on the path, and a device that clears the bits silently removes the signal. Tunnels that copy the outer header’s bits, or that do not copy them, break the mechanism in ways that are hard to see from the endpoints. Where marking is available it is preferable; where it is not, dropping is the fallback.

Where queue management cannot help

An active queue manager acts only on the queue it manages. If the bottleneck is elsewhere on the path, the managed queue never builds, the algorithm never signals, and the delay at the real bottleneck is unchanged. Deploying it on a fast access router while the actual constraint is a congested upstream link has no effect on latency, a point that matters when interpreting the results of measuring latency under load.

The algorithm also cannot fix a sender that ignores the signal. A sender whose congestion control responds only to loss will not react to a mark, and a sender that keeps a large amount of data in flight regardless of feedback will keep the queue occupied. The queue manager’s job is to deliver a timely signal, not to enforce compliance.

Finally, the algorithm’s own overhead is per packet. Timestamping every arrival and comparing at dequeue costs a few operations and a few bytes of per-packet state, which is negligible in software and awkward in hardware pipelines that were designed without it. This is the practical reason queue management appears first in software datapaths and in the queueing discipline of the host’s own transmit path, and only later in switching silicon.

Where the queue sits relative to the traffic mix is the remaining design question, since a single managed queue still makes bulk and interactive traffic share one delay distribution. Splitting traffic into classes before applying the algorithm to each is treated in priority and fair queueing.