TCP Congestion Control

Flow control protects the receiver. Congestion control protects the network: if every sender transmits as fast as its receiver allows, router queues overflow, packets are dropped and retransmitted, and useful throughput collapses. TCP senders therefore slow down when they see signs of congestion.

The congestion window

The sender keeps a second window, the congestion window (cwnd), which it adjusts itself. The amount of unacknowledged data is limited by both windows:

Sending window = min(cwnd, rwnd)

Below, windows are counted in MSS (maximum segment size, one full segment), and time in RTTs ("rounds"), as GATE questions usually do.

Slow start

A new connection starts with cwnd = 1 MSS. Every ACK increases cwnd by 1 MSS, so cwnd doubles every RTT: 1, 2, 4, 8, ... The name is historical: the growth is exponential, only the start is small.

Slow start continues until cwnd reaches the slow-start threshold (ssthresh). (In this lesson, a doubling that would pass ssthresh stops at ssthresh.)

Congestion avoidance (AIMD)

Above ssthresh, TCP grows cwnd by only 1 MSS per RTT (additive increase), probing gently for more bandwidth. When it detects a loss, it cuts the window (multiplicative decrease). This AIMD pattern (additive increase, multiplicative decrease) gives TCP's typical sawtooth and shares a bottleneck link fairly between connections.

Reacting to loss

TCP sees two signals of loss:

Three duplicate ACKs (four identical ACKs in a row) mean the receiver keeps getting segments past a gap, so the network is still delivering: there is no need to drop back to 1.

The simulation below shows cwnd at the start of each round, with ssthresh = 16 at first and a loss detected in round 8:

def tcp_cwnd(rounds, ssthresh, losses):
    cwnd, trace = 1, []
    for r in range(1, rounds + 1):
        trace.append(cwnd)
        event = losses.get(r)
        if event == "timeout":                 # Tahoe and Reno
            ssthresh, cwnd = max(cwnd // 2, 2), 1
        elif event == "3 dup ACKs":            # Reno: fast recovery
            ssthresh = max(cwnd // 2, 2)
            cwnd = ssthresh
        elif cwnd < ssthresh:                  # slow start
            cwnd = min(2 * cwnd, ssthresh)
        else:                                  # congestion avoidance
            cwnd += 1
    return trace

print("timeout in round 8:   ", tcp_cwnd(14, 16, {8: "timeout"}))
print("3 dup ACKs in round 8:", tcp_cwnd(14, 16, {8: "3 dup ACKs"}))

timeout in round 8:    [1, 2, 4, 8, 16, 17, 18, 19, 1, 2, 4, 8, 9, 10]
3 dup ACKs in round 8: [1, 2, 4, 8, 16, 17, 18, 19, 9, 10, 11, 12, 13, 14]

In both cases cwnd grows 1, 2, 4, 8, 16 (slow start), then 17, 18, 19 (congestion avoidance). In round 8 (cwnd = 19), ssthresh becomes 9. After a timeout, cwnd restarts at 1 and slow start runs up to 9; after three duplicate ACKs, Reno continues from 9 with linear growth.

The retransmission timer

TCP must guess how long to wait for an ACK. Too short a timeout causes needless retransmissions; too long reacts slowly to loss. TCP keeps a smoothed RTT and its variation (Jacobson's algorithm, with α = 1/8 and β = 1/4):

• DevRTT = (1 − β) · DevRTT + β · |SampleRTT − EstimatedRTT|
• EstimatedRTT = (1 − α) · EstimatedRTT + α · SampleRTT
• Timeout = EstimatedRTT + 4 · DevRTT

(DevRTT is updated first, with the old EstimatedRTT.) After a timeout, the timer value is doubled (exponential backoff).

Karn's algorithm: never take an RTT sample from a segment that was retransmitted, because it is unknown which transmission the ACK belongs to.

est, dev = 100.0, 10.0               # ms
for sample in [120, 90, 140]:
    dev = 0.75 * dev + 0.25 * abs(sample - est)
    est = 0.875 * est + 0.125 * sample
    print(f"sample {sample}: estimated {est:.2f}, dev {dev:.2f}, timeout {est + 4 * dev:.2f} ms")

sample 120: estimated 102.50, dev 12.50, timeout 152.50 ms
sample 90: estimated 100.94, dev 12.50, timeout 150.94 ms
sample 140: estimated 105.82, dev 19.14, timeout 182.38 ms

Throughput

If a connection's window oscillates between W/2 and W (the AIMD sawtooth), its average window is about 3W/4, so its average throughput ≈ 0.75 · W · MSS / RTT.

Practice questions