Queueing Delay as a Congestion Signal and the Base RTT Problem

Loss-based control learns about congestion only when a buffer overflows, which means it learns late and pays for the lesson with dropped data. Delay-based control observes the same congestion earlier: a queue that is growing adds to the round-trip time from the first packet that joins it, long before it is full. In principle a sender that watches the round trip can hold its window just below the point where queues form, keeping utilization high and latency low, with no loss at all.

In practice delay is a much harder signal to use than loss, for a reason that is structural rather than incidental. Loss is an event attributed to a specific segment, and its detection has its own machinery in duplicate ACK recovery. Delay is a continuous quantity measured over a path whose propagation delay is unknown and whose measurement is contaminated by the receiver, by the acknowledgement path, and by every queue in both directions. The signal exists, but extracting the part of it that reflects congestion at the bottleneck requires an estimate that the algorithm can never verify.

What the round trip actually contains

A measured RTT is a sum of parts:

RTT = propagation (forward) + serialization + queueing (forward)
    + receiver processing + ACK delay
    + propagation (reverse) + queueing (reverse)

Only the queueing terms respond to congestion in the useful direction, and both directions contribute. A sender that measures delay through the forward path alone would need timestamps echoed by the receiver, which the timestamp option provides; a sender that measures the full round trip gets the reverse path’s queueing added in, including the queue in front of the receiver’s own uplink. On an asymmetric path, the reverse queue can dominate, and a sender that responds to it reduces its rate in response to congestion caused by other traffic sharing its own return path.

Serialization delay is also part of the sum and is not constant. A 1500-byte packet takes about 12 microseconds on a 1 Gbit/s link and about 12 milliseconds on a 1 Mbit/s link. On a low-rate access link, the serialization term is comparable to the propagation term, so a change in packet size changes the measured RTT without any change in queue occupancy. An algorithm that treats all RTT variation as queueing will misread a shift in packet size mix as congestion.

The base RTT and why the minimum is the estimate

The standard approach is to define the base RTT as the minimum observed over the connection’s lifetime and treat the excess over it as queueing delay. The minimum is the right estimator because queueing delay is non-negative: any sample taken while a queue was empty is a sample of the propagation-plus-serialization floor, and the minimum over many samples converges to that floor from above.

The estimator has three defects, and each one has consequences for the control loop.

It can only decrease, so early samples dominate. If the first measurements were taken while a queue was present, the base is inflated and stays inflated for the connection’s life. The algorithm then tolerates that much standing queue as normal. On a path where a sender starts during a busy period, this is the common case rather than the exception.

It is a lifetime statistic on a path that changes. A route change to a longer path increases the propagation delay permanently, and the algorithm reads the increase as queueing. A route change to a shorter path decreases it, and the minimum drops, which retroactively makes all previous samples look like they contained queueing. Both errors persist until the estimator is reset, and nothing in the protocol says when to reset it.

A single anomalously short sample poisons it. One measurement taken when the queue was empty and the path was momentarily shorter than usual sets a floor that no subsequent sample can reach, so every later measurement shows positive queueing delay. The algorithm then behaves as if the path were permanently congested. Filtering the minimum over a window rather than over the lifetime helps, at the cost of forgetting the floor when the path genuinely improves.

RFC 6298’s RTT estimator for the retransmission timer uses a smoothed average and a variance term, which is the right tool for setting a timer and the wrong tool for detecting queueing. An average dilutes a queue that has just started to build, which is exactly the moment the signal is most useful. Delay-based congestion control therefore uses the raw sample or a lightly filtered one, and accepts the noise that comes with it.

Vegas: comparing the window against the delay

The clearest formulation of delay-based control is Vegas, which compares the rate the sender is achieving against the rate it would achieve if the path had no queue.

The sender knows its window cwnd and measures the RTT of the data it sends. Two derived rates:

Expected = cwnd / RTTmin        (what the window would deliver on an unqueued path)
Actual   = bytes_in_flight / RTT_sample

The difference, scaled by the base RTT, is an estimate of how many bytes are sitting in the queue:

Diff = (Expected - Actual) * RTTmin  ≈  bytes queued

Vegas then compares Diff against two thresholds. Below the lower threshold the window is increased, above the upper threshold it is decreased, and between them it is held. The thresholds are expressed in segments, so the algorithm targets a standing queue of a few segments rather than zero. Targeting zero is not achievable: a window that exactly equals the bandwidth-delay product leaves the bottleneck idle whenever a packet arrives late, and utilization falls. A small standing queue is the price of keeping the link busy.

def vegas_update(cwnd, rtt_min, rtt_sample, in_flight, alpha=2, beta=4, mss=1460):
    """Window adjustment from the Vegas queue estimate, in bytes."""
    if rtt_sample <= 0 or rtt_min <= 0:
        return cwnd
    expected = cwnd / rtt_min
    actual = in_flight / rtt_sample
    diff_bytes = (expected - actual) * rtt_min
    if diff_bytes < alpha * mss:
        return cwnd + mss                 # queue smaller than target: grow
    if diff_bytes > beta * mss:
        return max(cwnd - mss, 2 * mss)   # queue larger than target: shrink
    return cwnd                            # inside the band: hold

The control law is additive in both directions, which is the first structural difference from the AIMD sawtooth. An additive decrease does not converge to fairness between flows with different round trips. Vegas compensates with a band: a queue below the lower threshold grows the window, a queue above the upper threshold shrinks it, and a queue in between leaves it alone, so the size of the excess decides which of three responses applies rather than how large a single response is.

The second structural difference is that Vegas reacts to delay before loss, so a Vegas flow sharing a bottleneck with a Reno flow will back off while the Reno flow keeps increasing. The delay-based flow yields capacity to the loss-based flow and ends up with a smaller share. This is not a bug in Vegas; it is the predictable consequence of using a signal that the competing flow ignores. The Reno flow fills the queue until it overflows, at which point Vegas sees a large delay and reduces further, while Reno takes the capacity Vegas releases.

The LEDBAT inversion

LEDBAT, specified in RFC 6817, takes delay-based control in the opposite direction: it is designed to scavenge spare capacity and yield to any other traffic. Its target is a queueing delay of no more than 100 milliseconds above the base, the upper bound the specification places on the extra delay the algorithm may introduce. Unlike the algorithms above it does not measure the round trip: the receiver computes a one-way delay from timestamps in the data packets and returns that sample in the acknowledgement, and the sender compares it against its own base delay. The window then increases while the measured delay is below target and decreases while it is above, so the control is driven by an explicit target rather than by a threshold band.

The design intent is that a LEDBAT flow’s standing queue makes loss-based flows fill the buffer faster, so they get the capacity and LEDBAT backs off. That works against Reno. It fails against another LEDBAT flow, because both flows converge to the same standing queue, and the queue is shared in proportion to each flow’s contribution. Two LEDBAT flows with different round trips do not share equally, and the standard’s own analysis acknowledges that the algorithm’s fairness properties are weak. Latecomer advantage is the specific pathology: a new flow that starts when the queue is already at target measures the existing queue as its base and immediately believes it has room, so it grows until it captures a share disproportionate to its age.

The larger lesson from LEDBAT is that delay-based control is self-referential. The signal it uses is the queue it and its competitors create, so the meaning of a delay measurement depends on what every other flow is doing. Loss has the same property in principle, but loss is bounded by buffer size and occurs at a definite instant, which makes the interaction more predictable.

When delay is the right signal anyway

Despite these problems, delay-based control is the correct choice in three situations, and naming them clarifies what the signal is good for.

Shallow buffers. Where the buffer is smaller than the bandwidth-delay product, a loss-based sender loses segments before it has filled the path, and its throughput is limited by the buffer rather than by capacity. A delay-based sender can hold the window at the right size without needing the buffer to absorb an overshoot.

Shared bottlenecks with latency-sensitive traffic. A queue that stays short keeps interactive traffic responsive. The queueing delay is the latency that other flows experience, so controlling it directly is the only way to control it at all.

Wireless and lossy links. A loss-based sender cannot distinguish congestion loss from corruption loss, and on a link with a 1 percent corruption rate it will run at a window appropriate to a 1 percent congestion rate, which is far below capacity. Delay is unaffected by corruption, so a delay-based sender on such a link keeps its window high. The reverse problem appears when the link’s own retransmissions add delay that the sender reads as queueing.

The mechanisms that make delay usable in practice are the same ones that make any signal usable: measure the quantity that matters rather than a proxy for it, filter the estimate to remove the noise that the control loop would otherwise amplify, and accept that a signal derived from a shared resource carries information about other users of that resource. The last of these is why delay-based algorithms tend to be deployed either where they are the only traffic, as in a data-center fabric, or where they are explicitly subordinate, as in background transfer. The intermediate case, delay-based control competing on equal terms with loss-based control on the open internet, is the one that has consistently failed to hold its share.