DCTCP and the Proportional Response to Congestion Marks

Every loss-based algorithm reduces its window by a fixed fraction when it detects congestion. Reno halves. The reduction is the same whether the queue was one packet over the threshold or a hundred, whether one flow out of twenty is responsible or all twenty are. The signal is binary and the response is constant, so the control loop discards the information that would let it respond in proportion.

Explicit congestion notification was designed to carry a richer signal, but the way TCP uses it throws that richness away. A marked packet causes one window reduction, exactly as a dropped packet would. The mark says that the queue exceeded a threshold and nothing about by how much or for how long. Recovering the missing information requires looking at marks in aggregate rather than one at a time, and that is the idea behind Data Center TCP.

The information in a mark rate

Consider a queue with a marking threshold and a set of flows passing through it. If the aggregate arrival rate slightly exceeds the drain rate, the queue hovers just above the threshold and only a small fraction of arriving packets is marked. If the excess is large, the queue sits well above the threshold and nearly every packet is marked. The fraction of marked packets is therefore a measure of how far the offered load exceeds capacity, and it is available to any receiver that counts.

That fraction is what a sender needs. A window reduction proportional to the fraction gives a small reduction when the queue is barely over the threshold and a large reduction when it is far over, which is the behaviour a stable controller should have. A fixed reduction cannot do this: it must be large enough to control the worst case, so it over-reacts in the common case, and the over-reaction is what produces the sawtooth’s amplitude.

There is a second, subtler piece of information in the mark rate. Because the marking threshold is crossed by the aggregate of all flows, the fraction is a property of the bottleneck rather than of the individual flow. Every flow sharing the queue sees approximately the same mark fraction, so every flow computes approximately the same reduction factor, and the reductions are proportional to each flow’s current window. Proportional reduction is the multiplicative decrease that AIMD requires, and here it comes with a magnitude that tracks the actual congestion.

Three pieces that must fit together

DCTCP is not a single algorithm but a coordinated change at the switch, the receiver, and the sender. Each piece exists because the others require it.

The switch marks on instantaneous queue length, not randomly. When the queue exceeds a threshold K, every arriving ECN-capable packet is marked; below it, none is. This is a step function rather than the linear probability ramp of random early detection. The step is deliberate: a probability ramp would add randomness to the mark fraction, and the sender’s estimate of congestion would then include that noise. With a step, the mark fraction is a clean function of how long the queue has been above the threshold, and the queue length itself stays close to K because any excursion is marked heavily and corrected quickly.

The threshold is expressed in packets, and it is small: tens of packets rather than a fraction of the buffer. The reason it can be small is that the queue is not being used to absorb a window’s worth of overshoot. The feedback is fine-grained enough that the senders keep the queue near the threshold rather than cycling up to a buffer limit, so the buffer’s depth is irrelevant to the steady state and matters only for absorbing bursts.

The receiver estimates the fraction over a window. A TCP acknowledgement carries one ECN-Echo bit, so the receiver cannot report a fraction directly. It counts the bytes marked over a window of roughly one round trip and sets ECE on acknowledgements so that the fraction of ACKs carrying the flag approximates the fraction of marked bytes. With a window of N packets of which m were marked, the receiver flags about m/N of the acknowledgements. The sender sees a sequence of ACKs with and without the flag and can recover the fraction by counting.

The approximation is coarse at low mark rates. If one packet in a hundred is marked, the receiver must flag roughly one ACK in a hundred, which means the sender sees long runs with no flag and occasional isolated flags. Estimating a fraction from such a sparse signal requires averaging over many samples, and that averaging is the sender’s job.

The sender maintains an exponentially weighted average. Let F be the fraction of marked bytes reported in the most recent window. The sender updates:

α ← (1 - g) α + g F,        with g = 1/16

and on congestion reduces its window by the factor 1 - α/2:

G = 1.0 / 16.0      # EWMA weight; the average spans about 16 windows

class DctcpSender:
    def __init__(self, cwnd, mss):
        self.cwnd = cwnd
        self.mss = mss
        self.alpha = 1.0       # start at full reduction, as the specification does
        self.marked = 0        # bytes marked in the current window
        self.acked = 0         # bytes acknowledged in the current window

    def on_ack(self, acked_bytes, marked_bytes):
        self.acked += acked_bytes
        self.marked += marked_bytes
        if self.acked < self.cwnd:
            return             # the window has not closed yet
        f = self.marked / self.acked
        self.alpha = (1 - G) * self.alpha + G * f
        if f > 0:
            self.cwnd = max(self.cwnd * (1.0 - self.alpha / 2.0), 2 * self.mss)
        self.marked = self.acked = 0

The window closes when the bytes acknowledged since the last reduction reach the congestion window, which is the sender’s estimate of one round trip’s worth of data. At most one reduction happens per such window, and it is sized by the mark fraction over that window rather than by any single mark.

Two properties follow immediately. With α = 0, meaning no marks in the recent past, the reduction factor is 1 and the window does not shrink at all. With α = 1, meaning every packet has been marked recently, the factor is 1/2 and the behaviour matches Reno. Everything between is a partial reduction, and the steady state settles at whatever α makes the reduction balance the additive increase.

The 1/16 weight sets the averaging window at roughly sixteen observations, which is a few round trips. It must be long enough to average the receiver’s coarse feedback into a stable estimate and short enough to track a change in the load. The choice is the algorithm’s main tuning parameter, and it trades responsiveness against the variance of the estimate.

Why the reduction is bounded to once per window

A sender that reduced on every marked ACK would collapse its window catastrophically, because a period of heavy marking produces many marked ACKs in a single round trip and each would trigger a multiplication. The algorithm therefore counts acknowledgements and permits at most one reduction per window of data, where the window is the number of bytes acknowledged since the last reduction compared against the current congestion window.

The rule has a side effect that matters for correctness. The reduction factor is applied once, using the α that was current at that moment, so a burst of marks within a window produces exactly one reduction sized by the average mark rate rather than a cascade. The counting must be reset when the reduction occurs and must not be reset by a spurious retransmission, or the sender will reduce more often than the algorithm intends.

The window estimate itself is derived from the congestion window and the round trip, which means the sender is using the same ACK clock as a loss-based sender. The difference is that the clock is used to measure a window of data rather than to trigger a transmission, and the transmissions are paced.

The steady state

The equilibrium is worth deriving because it shows how the queue is held near the threshold rather than allowed to cycle.

In each window, the sender’s window grows by about one segment, as additive increase does, and it is reduced by the factor α/2 when marks are present. Writing the window in segments, the growth is 1 segment and the reduction is (α/2) * cwnd segments, so in steady state:

1  ≈  (α/2) * cwnd          →        α ≈ 2 / cwnd

The mark fraction is therefore inversely proportional to the window, which is the correct relationship: a large window means many packets in flight per round trip, so a small fraction of them need to be marked to signal the same absolute excess. The queue length that produces that fraction is set by the marking threshold and the number of flows, so the steady-state queue stays just above K and the delay it adds is K packets’ worth of serialization rather than a buffer’s worth.

The variance around that equilibrium is small compared to a loss-based sawtooth, because the response scales with the deviation rather than being a fixed step. A flow that is slightly over the threshold reduces slightly; one that is far over reduces heavily. The feedback is proportional, and proportional feedback around an operating point produces a small limit cycle rather than a large one.

Where the design depends on its assumptions

DCTCP was designed for a fabric with specific properties, and each property is load-bearing.

Uniform, small round trips. In a data-center fabric every flow has a round trip of microseconds to a few hundred microseconds, so all flows respond to marks within the same interval and their reduction factors are comparable. The RTT bias described in RTT fairness is negligible because there is nothing to bias. On a wide-area path with round trips spanning two orders of magnitude, the proportional response does not restore fairness, and a short-RTT flow still turns its window over more often.

A single bottleneck with a shallow queue. The marking threshold must be above the burst that a single flow’s window produces in one round trip, or a well-behaved flow will be marked for its own burst and reduce unnecessarily. In a fabric, a flow’s window is bounded by the small bandwidth-delay product, so a threshold of a few tens of packets suffices. On a long-haul link with a megabyte-scale window, the burst from a single flow exceeds any small threshold, and the algorithm would mark constantly.

Senders that honour the mark. A DCTCP flow reduces by α/2, which for small α is far less than the halving a loss-based flow performs. A DCTCP flow sharing a queue with a loss-based flow therefore reduces less and, in the short run, takes more capacity. The queue stays near the threshold because the loss-based flow’s buffer-filling behaviour is what the threshold is protecting against, but the capacity shares are not equal. Mixing the two kinds of sender in one queue is a configuration error, and the fact that the algorithm’s fairness properties depend on all senders using it is the design’s largest practical constraint.

Marking at the switch, not at the host. The mechanism requires the congested device to mark, which means the device must support ECN and must have a threshold configured. A fabric where some switches mark and others drop produces a mixed signal in which α estimates a fraction that has no consistent meaning, since drops are invisible to the receiver’s counting.

The general lesson

The specific algorithm is less important than the shape of the idea, which is that a congestion signal carries two things: whether there is congestion and how much. Loss-based control uses only the first. ECN as originally specified also uses only the first. DCTCP recovers the second by aggregating the signal over a window and converting a count into a fraction, and it then sizes its response to that fraction.

The same reasoning applies to any signal that arrives as a sequence of binary events. A count of events over an interval is an estimate of a rate, and a rate is a measure of severity. The receiver’s coarse encoding, the sender’s averaging window, and the reduction rule are all machinery for extracting that rate from a one-bit channel. Where the machinery is absent, the sender is left with a binary response to an analog problem, and the cost is the oscillation that every fixed-step control loop exhibits when it is tuned for the worst case.