Active Queue Management and Explicit Congestion Notification

A drop-tail queue has one moment at which it can speak: the instant its buffer is full, which is the behaviour described in tail drop and buffer sizing. Everything before that moment is silence, and the silence is what makes the queue’s delay grow without any sender noticing. Active queue management is the decision to speak earlier, and the design question is what to say and to whom.

Two mechanisms answer it. The queue can drop a packet before the buffer is full, which is a loss signal delivered early; or it can mark a packet, which requires the transport to carry a mark and the receiver to echo it back. The first is a change to the queue alone. The second is a change to the protocol stack at both endpoints and to every router on the path that must not clear the mark. The difference in deployment cost explains why early drop appears in RFC 2309, which recommends random early detection for routers, while marking needed a separate specification in RFC 3168: a router that can only drop packets can implement the first but not the second.

The problem RED was designed for

Random early detection starts from an observation about the drop-tail queue’s dynamics: the queue is either empty or full, and the transition between them is abrupt. A discipline that keeps the average queue length near a small target would keep the link busy while bounding the delay, and would signal congestion to senders before the buffer overflows.

RED computes an exponentially weighted moving average of the queue length and compares it against two thresholds. Below the minimum, nothing happens. Above the maximum, every arriving packet is dropped. Between them, each arriving packet is dropped with a probability that rises linearly from zero at the minimum to a configured maximum at the maximum threshold.

avg = (1 - w) * avg + w * q            (EWMA of queue length, w small)
if avg < min:      enqueue
elif avg >= max:   drop
else:              p = pmax * (avg - min) / (max - min)
                   drop with probability p / (1 - count * p)

count is the number of packets queued since the last drop. Dividing by 1 - count * p keeps the gap between consecutive drops roughly proportional to 1/p even when p is large, which is what spreads the losses over different senders instead of hitting one sender’s packets in a row.

The average is the important part. Using the instantaneous queue length would drop packets in response to a burst that is about to drain, punishing a sender for a transient that is not congestion. The weighting constant is small enough that the average responds over a timescale of many packet arrivals, which smooths bursts but also delays the signal. Choosing that constant is the central tuning problem: too small and RED does not react before the buffer fills, too large and it reacts to bursts as if they were congestion.

The random element has a specific purpose. If RED dropped every packet above the threshold, it would synchronize senders in exactly the way drop tail does, with all flows reducing at once. Dropping randomly spreads the losses across flows and across time, so different flows reduce at different moments and the aggregate rate varies smoothly. The randomness is also what gives RED its fairness property: flows are dropped in proportion to the number of packets they contribute, so a flow sending twice as fast loses twice as many packets, which is the correct proportional response.

Why RED is hard to deploy

RED’s specification is short, and its parameterization is not. The three thresholds and the weight interact with the traffic mix, and the correct values depend on the link rate, the number of flows, and the round-trip times of those flows, none of which the router knows.

The specific failure is that RED’s drop probability is computed per packet, not per unit time. On a link where the queue is measured in packets and the arrival rate varies, the same average queue length produces very different drop rates depending on how fast packets arrive. A 10 Gbit/s link and a 100 Mbit/s link with the same thresholds drop at rates that differ by two orders of magnitude. The senders’ response then differs by a corresponding amount, and the equilibrium the algorithm reaches is not the one the operator intended.

There is also a stability problem. RED’s control loop includes the senders’ own dynamics, and the loop gain depends on the number of flows and their round trips. With many flows and long round trips the loop can oscillate: the queue exceeds the threshold, RED drops heavily, the senders reduce, the queue drains below the minimum, RED stops dropping, the senders increase, and the cycle repeats with a period set by the round trip. The oscillation is at the queue level rather than the packet level, and it produces the same utilization loss as drop-tail synchronization.

Both problems stem from measuring the queue in packets. A queue length in packets says nothing about the delay that queue imposes, because the delay depends on the link rate. Two links with the same packet count in their queues have delays that differ by the ratio of their rates.

CoDel and the shift to time

The Controlled Delay algorithm, specified in RFC 8289, changes the measured quantity from packets to time. It tracks, for each packet that arrives, the time it has spent in the queue, and it computes the minimum of that sojourn time over a moving window. A queue whose minimum sojourn time stays below a target — 5 milliseconds in the specification’s default — is behaving; one whose minimum exceeds the target for a sustained interval is not, and CoDel starts dropping.

The use of the minimum over a window rather than the average is the design’s key choice. The minimum ignores transient bursts entirely: a burst that drains within the window does not raise the minimum, so CoDel does not react to it. Only a queue that persists long enough to keep every packet waiting is treated as congestion. This is precisely the discrimination that RED’s average fails to make, and it is why CoDel needs no tuning for link rate: 5 milliseconds is 5 milliseconds on any link.

The second choice is the controlled interval. Once the minimum sojourn exceeds the target, CoDel waits for a fixed interval before dropping, so a queue that is draining is not punished. If the condition persists past the interval, it drops one packet and schedules the next drop at an interval that shrinks as the condition persists, down to a floor. The shrinking interval is what makes the drop rate proportional to the persistence of the congestion rather than to the arrival rate, which fixes RED’s rate dependence.

class CoDel:
    """Sojourn-time gate; the drop schedule itself is left to the caller."""
    def __init__(self, target=0.005, interval=0.100):
        self.target = target          # acceptable sojourn time, seconds
        self.interval = interval      # observation window
        self.first_above = None       # when the queue last went above target

    def congested(self, sojourn, now):
        if sojourn < self.target:
            self.first_above = None   # a packet left promptly: not congested
            return False
        if self.first_above is None:
            self.first_above = now
            return False
        return now - self.first_above >= self.interval

The grace interval is the whole of the gate: a queue that recovers within it resets first_above and is never penalized. The real algorithm adds a drop schedule on top, counting drops since the queue last fell below target and dividing the interval by that count, so the drop rate accelerates while the condition persists and resets when it clears. The structure above is what matters: evidence must persist for a fixed interval before anything is done.

ECN: marking instead of dropping

Every AQM described so far signals by dropping, which costs a retransmission and, in a loss-based sender, a window halving. ECN replaces the drop with a mark. The router sets a bit in the IP header instead of discarding the packet, the receiver sees the mark, and the receiver echoes it back to the sender in a TCP header flag. The sender then reduces its window as it would after a loss, without any data being lost.

RFC 3168 defines the encoding using two bits in the IP header’s former Type of Service field. Four combinations: Not-ECN-Capable, ECN-Capable(0), ECN-Capable(1), and Congestion Experienced. A sender that wishes to use ECN sets one of the ECN-Capable codepoints; a router that would have dropped the packet instead sets Congestion Experienced if the packet is ECN-Capable and drops it otherwise. A router must never set the mark on a Not-ECN-Capable packet, and must never clear a mark that is already set.

The receiver’s job is to remember that it saw a mark and report it. TCP uses two flags, ECE and CWR, in the reserved bits of the TCP header. The receiver sets ECE on the acknowledgement for a marked packet and continues to set it until the sender responds by setting CWR, which tells the receiver to stop echoing. The handshake at connection setup negotiates capability with SYN, SYN-ACK, and ACK, and a middlebox that clears the bits breaks the negotiation silently.

The benefit is bounded by what fraction of losses are ECN-markable. On a path where the AQM marks rather than drops, a sender never loses data to congestion, so it never retransmits unnecessarily and never pays the timeout cost. The window still halves, so the rate still falls, but the fall is smooth and the recovery is not delayed by retransmission. The observation behind DCTCP is that a queue which marks can be held near its threshold, where a queue that drops cycles between empty and full, because marking lets the sender react to the queue’s depth rather than to its exhaustion.

What ECN does not fix

Three limits are worth stating, because ECN is often described as a complete replacement for loss signalling and it is not.

It requires cooperation along the whole path. The mark must survive every router, be seen by the receiver, and be echoed. A single device that clears the ECN field, or a receiver that ignores the mark, disables the mechanism for that connection. Paths through equipment that rewrites the IP header are common, and the failure is silent: the connection simply behaves as if ECN were not negotiated.

It does not change the control law. An ECN mark and a dropped packet produce the same window reduction in a Reno sender. The gain is in avoiding retransmission and in the timing of the signal, not in the shape of the response. Algorithms that respond to the fraction of marked packets rather than to a single mark, such as DCTCP, extract much more information from the signal, and that is the subject of proportional response to marking.

It has no meaning without an AQM. A drop-tail queue has no threshold at which to mark, so an ECN-capable sender on a path with drop-tail queues gets no benefit at all. The two mechanisms are complementary, and deploying one without the other gains nothing.

The scheduling problem underneath

All of these disciplines decide whether to drop or mark an arriving packet. None of them decides which packet to send next, and that decision is where fairness among flows is actually determined. A queue shared by ten flows serves them in arrival order, so a flow that sends in a burst occupies the link for the duration of its burst. Flow queue CoDel, specified in RFC 8290, separates arriving packets into per-flow queues and schedules among them, which gives each flow a share determined by the scheduler rather than by arrival timing. The AQM then operates on each flow’s queue separately, so a flow that is behaving badly is dropped from its own queue without affecting the others.

The separation matters because it changes what a loss means. In a shared queue, a drop is a signal about the aggregate. In a per-flow queue, a drop is a signal about that flow, which is both more informative and harder to spoof. The cost is state per flow and a scheduler that must run at line rate, which is why the mechanism is more common on links with a modest number of active flows than on backbone interfaces carrying hundreds of thousands.