Congestion Control

Imagine a four-lane highway merging into a single lane. If cars enter the merge faster than they exit, a queue builds. If that queue grows unboundedly, cars stop. The same physics governs packet networks.

A bottleneck link is any link where the offered load exceeds capacity. Routers have finite buffers; when a buffer fills, the router must drop incoming packets. This is the fundamental signal: packet loss means congestion.

Congestion collapse is the catastrophic regime where retransmissions amplify the problem. Suppose 1000 senders each send 1 MB/s into a 100 MB/s link. Fine. But if they all retransmit lost packets without reducing their rate, they now send 1.1 MB/s each. More drops, more retransmits — throughput falls while offered load rises. This is precisely what happened in October 1986 on ARPANET: throughput on some paths fell from 32 Kbps to 40 bps.

The end-to-end principle means routers are dumb; they cannot negotiate rates with each sender. Only the endpoints can solve this — and they must do so with only local information: their own send rate, acknowledgments received, and RTT measurements.

Two key quantities:

• Bandwidth-delay product (BDP) = bottleneck bandwidth × RTT. This is the amount of data "in flight" when the pipe is full. A correctly-tuned sender keeps exactly BDP bytes in flight.
• cwnd (congestion window): TCP limits bytes in flight to min(cwnd, rwnd) where rwnd is the receiver's advertised window. Congestion control is fundamentally about how to set cwnd.

# Bandwidth-delay product intuition
bandwidth_bps = 100e6   # 100 Mbps bottleneck link
rtt_seconds   = 0.040   # 40 ms round-trip time

bdp_bytes = bandwidth_bps * rtt_seconds / 8
print(f"BDP = {bdp_bytes/1024:.1f} KB")  # ~488 KB

# A sender should keep this many bytes 'in flight' to fill the pipe
# Too few: underutilize the link
# Too many: build a queue, inflate RTT, eventually drop packets

TCP is a sliding-window protocol. At any moment, the sender has a window of unacknowledged bytes in flight. The congestion window cwnd caps this at the sender's end. Formally:

bytes_in_flight ≤ min(cwnd, rwnd)

where rwnd is the receiver's flow-control window.

The ACK clock is a subtle but crucial insight from Van Jacobson: acknowledgments arrive at the sender at the same rate that packets arrive at the receiver. If the bottleneck link clocks out one packet every 1 ms, ACKs arrive back at the sender every 1 ms (ignoring propagation). This means ACKs self-clock the sender: the sender should inject one new packet per ACK received, which keeps the pipe full without overloading it.

Why does this matter? Because it means TCP is not a timer-based protocol for normal operation — it is ACK-driven. The rhythm of ACKs naturally paces the send rate to match the bottleneck without explicit rate computation. This elegance is what makes TCP work across links that differ by six orders of magnitude in speed.

The send rate in steady state is approximately:

rate ≈ cwnd / RTT

So controlling the rate means controlling cwnd. All congestion control algorithms are, at heart, rules for updating cwnd.

# Simplified TCP sender state
class TCPSender:
    def __init__(self):
        self.cwnd = 1        # congestion window (in MSS units)
        self.ssthresh = 64   # slow-start threshold (MSS units)
        self.MSS = 1460      # max segment size (bytes)

    def on_ack(self, ack_seq):
        """Called each time a new ACK arrives."""
        if self.cwnd < self.ssthresh:
            # Slow start: exponential growth
            self.cwnd += 1
        else:
            # Congestion avoidance: linear (approx 1 MSS per RTT)
            self.cwnd += 1.0 / self.cwnd

    def bytes_in_flight_limit(self):
        return self.cwnd * self.MSS

When a TCP connection begins (or restarts after a timeout), it has no information about available bandwidth. Starting at full speed risks flooding the network. Starting at 1 packet is safe but slow. Slow start is a clever middle path: start conservatively but grow exponentially until you detect congestion or hit a threshold.

Algorithm:

1. Initialize cwnd = 1 MSS (the initial window — modern systems often start higher, e.g., 10 MSS per RFC 6928).
2. Initialize ssthresh = some large value (e.g., 64 KB).
3. For each ACK received: cwnd += 1 MSS.

Because each packet sent generates one ACK, and each ACK increments cwnd by 1, the window doubles each RTT:

• RTT 1: cwnd = 1, send 1 packet
• RTT 2: cwnd = 2, send 2 packets
• RTT 3: cwnd = 4, send 4 packets
• ...

This is exponential growth — it sounds dangerous but it is crucial for quickly discovering the available bandwidth. A 10 Gbps transatlantic link with 150 ms RTT has a BDP of ~187 MB. Starting at 1 MSS and growing linearly would take thousands of RTTs to fill the pipe. Doubling each RTT reaches it in ~log2(BDP/MSS) ≈ 17 RTTs.

Termination conditions:

• cwnd reaches ssthresh: switch to congestion avoidance (linear growth).
• A timeout (triple duplicate ACK or RTO fires): halve ssthresh, reset cwnd = 1 (TCP Tahoe) or to ssthresh (TCP Reno).

The name "slow start" is a misnomer — it is not slow, it is just slower than the naive "blast everything" strategy. The start is 1 MSS (slow relative to line rate), but the growth is fast (exponential).

def simulate_slow_start(ssthresh=16, loss_at_cwnd=24):
    cwnd = 1
    rtt = 0
    print(f"RTT {rtt:2d}: cwnd = {cwnd}")
    while True:
        rtt += 1
        if cwnd >= loss_at_cwnd:
            print(f"RTT {rtt:2d}: LOSS detected at cwnd={cwnd}")
            ssthresh = cwnd // 2
            cwnd = 1  # TCP Tahoe behavior
            print(f"  => ssthresh={ssthresh}, cwnd reset to {cwnd}")
            break
        if cwnd < ssthresh:
            cwnd = min(cwnd * 2, ssthresh)  # slow start: double
        else:
            cwnd += 1  # congestion avoidance: linear
        print(f"RTT {rtt:2d}: cwnd = {cwnd} {'(SS)' if cwnd<=ssthresh else '(CA)'}")

simulate_slow_start()

Once cwnd reaches ssthresh, TCP enters congestion avoidance: it probes for more bandwidth cautiously. The algorithm is Additive Increase / Multiplicative Decrease (AIMD):

• Additive Increase (AI): On each ACK in steady state, increase cwnd by 1/cwnd (so cwnd increases by ~1 MSS per RTT). This is the "probe" phase — gently feel out whether there is spare capacity.
• Multiplicative Decrease (MD): On detecting congestion (typically triple duplicate ACKs = a fast retransmit signal), halve cwnd: cwnd = cwnd / 2. This rapid backoff relieves the bottleneck quickly.

In equations:

• Per RTT: cwnd(t+1) = cwnd(t) + 1 (additive increase)
• On loss: cwnd = cwnd / 2 (multiplicative decrease)

Why additive increase, not multiplicative increase? Multiplicative increase grows too fast — if multiple flows simultaneously probe, they collectively overshoot before any loss signal propagates back. Additive increase gives the network time to signal distress.

Why multiplicative decrease, not additive decrease? Additive decrease (e.g., cwnd -= 1) is too slow to drain the bottleneck queue. The congestion event tells you the network was overloaded; you must cut sharply. Multiplicative decrease ensures the window halves regardless of whether cwnd is 2 or 200 — proportionally appropriate.

The sawtooth pattern: In steady state, TCP windows exhibit a characteristic sawtooth: slow linear ramp up, sharp drop on loss, repeat. This is the visible signature of AIMD.

Throughput formula (Mathis et al.): In steady state with loss rate p, the average throughput of a TCP flow is approximately:

throughput ≈ (MSS / RTT) × C / √p

where C ≈ 1.22. This square-root relationship has profound implications: to halve throughput, you must quadruple the loss rate. TCP is remarkably tolerant of moderate loss.

def aimd_steady_state(cwnd_init=32, steps=50, loss_prob=0.02):
    import random
    cwnd = cwnd_init
    ssthresh = cwnd_init
    history = []
    for t in range(steps):
        history.append(cwnd)
        if random.random() < loss_prob:
            # Triple-dup ACK: multiplicative decrease
            ssthresh = max(cwnd // 2, 2)
            cwnd = ssthresh           # TCP Reno (not back to 1)
        else:
            if cwnd < ssthresh:
                cwnd = min(cwnd * 2, ssthresh)  # slow start
            else:
                cwnd += 1                        # additive increase
    return history

# Observe the sawtooth:
history = aimd_steady_state()
for i, w in enumerate(history):
    bar = '#' * w
    print(f"RTT {i:3d}: {bar} ({w})")

The evolution from TCP Tahoe (1988) to TCP Reno (1990) introduced a crucial distinction between two congestion signals:

1. Timeout (RTO expiry): The sender waited for an ACK and none came. This is a strong signal of severe congestion or catastrophic loss — the packet and all subsequent ones may be stuck in a congested queue. Response: treat as full congestion collapse — reset cwnd = 1, set ssthresh = cwnd/2, restart slow start. This is the Tahoe behavior.

2. Triple duplicate ACKs (3× dupACK): The receiver got packets after a gap, so it keeps ACK-ing the last good sequence number. Three duplicates strongly imply the missing packet was dropped but the pipe is not empty — data is still flowing. This is a milder signal.

Fast Retransmit (Reno innovation): Don't wait for the RTO — immediately retransmit the missing segment when 3 dupACKs arrive.

Fast Recovery (Reno innovation): After fast retransmit, don't collapse back to cwnd=1. Instead:

1. ssthresh = cwnd / 2
2. cwnd = ssthresh + 3 (the 3 dupACKs imply 3 packets left the network)
3. For each additional dupACK: cwnd += 1 (inflate — those packets are out of the network)
4. When the retransmitted segment is ACK'd: cwnd = ssthresh (deflate)

This fast recovery keeps the connection in congestion avoidance rather than triggering slow start — it wastes far fewer RTTs.

TCP NewReno improves on Reno's handling of multiple losses in one window. SACK (Selective ACK) allows the receiver to report which segments it has received, enabling more intelligent retransmission.

The key insight: the algorithm uses different responses calibrated to the severity of the congestion signal. This is principled, not ad hoc.

# Fast retransmit / fast recovery state machine (simplified)
class TCPReno:
    OPEN = 'OPEN'
    RECOVERY = 'RECOVERY'

    def __init__(self):
        self.cwnd = 10
        self.ssthresh = 64
        self.dup_ack_count = 0
        self.state = self.OPEN

    def on_ack(self, is_new_ack):
        if is_new_ack:
            self.dup_ack_count = 0
            if self.state == self.RECOVERY:
                # Deflate: new ACK covers the retransmitted seg
                self.cwnd = self.ssthresh
                self.state = self.OPEN
            elif self.cwnd < self.ssthresh:
                self.cwnd += 1            # slow start
            else:
                self.cwnd += 1.0/self.cwnd  # congestion avoidance
        else:  # duplicate ACK
            self.dup_ack_count += 1
            if self.dup_ack_count == 3:
                # Fast retransmit + enter recovery
                self.ssthresh = max(self.cwnd // 2, 2)
                self.cwnd = self.ssthresh + 3
                self.state = self.RECOVERY
                print("FAST RETRANSMIT triggered")
            elif self.dup_ack_count > 3 and self.state == self.RECOVERY:
                self.cwnd += 1  # inflate

    def on_timeout(self):
        self.ssthresh = max(self.cwnd // 2, 2)
        self.cwnd = 1
        self.dup_ack_count = 0
        self.state = self.OPEN
        print("TIMEOUT: back to slow start")

Why AIMD specifically? Why not some other increase/decrease policy? The answer is mathematical. AIMD has a provably desirable fairness property: all flows sharing a bottleneck converge to equal bandwidth shares.

The geometric proof (Chiu & Jain, 1989): Consider two flows with windows w1 and w2 sharing a bottleneck of capacity C. Plot (w1, w2) in 2D. The fairness line is w1 = w2. The efficiency line is w1 + w2 = C.

• Additive increase moves the point along a 45° vector (both flows increase at the same rate) — moving toward both the efficiency line AND the fairness line.
• Multiplicative decrease (both flows halve on congestion) moves the point along a line from the origin toward zero — it moves the point closer to the fairness line but also pulls it away from efficiency.

The combined effect: AI steps move diagonally toward the optimal corner (efficient AND fair). MD steps after each loss bring the point closer to the fairness axis. The trajectory spirals toward the intersection of the fairness and efficiency lines. This is the only increase/decrease policy with this property.

Jain's Fairness Index: For n flows with throughputs x_i:

F = (Σ xᵢ)² / (n × Σ xᵢ²)

F = 1 means perfect fairness (all equal). AIMD achieves F → 1 as connections synchronize.

Caveat — RTT unfairness: AIMD is unfair to long-RTT flows in practice. A flow with RTT = 200 ms increases cwnd once per 200 ms; a flow with RTT = 20 ms increases cwnd 10x faster. Long-RTT flows get less bandwidth even over the same bottleneck. This is a known limitation of classic TCP.

import math

def jain_fairness(throughputs):
    """Jain's fairness index. Range [1/n, 1]; 1 = perfectly fair."""
    n = len(throughputs)
    numerator   = sum(throughputs) ** 2
    denominator = n * sum(x**2 for x in throughputs)
    return numerator / denominator

# Two flows converging under AIMD
def simulate_aimd_fairness(w1=30, w2=5, C=20, rounds=30):
    print(f"{'Round':>6} {'w1':>6} {'w2':>6} {'w1+w2':>7} {'Fairness':>9}")
    for r in range(rounds):
        # Additive increase
        w1 += 1; w2 += 1
        # If over capacity: multiplicative decrease
        if w1 + w2 > C:
            w1 /= 2; w2 /= 2
        F = jain_fairness([w1, w2])
        print(f"{r:>6} {w1:>6.2f} {w2:>6.2f} {w1+w2:>7.2f} {F:>9.4f}")

simulate_aimd_fairness()

Classic TCP detects congestion only after packets are dropped — a wasteful, reactive signal. Explicit Congestion Notification (ECN, RFC 3168) allows routers to signal congestion before dropping packets, using bits in the IP header.

How it works:

1. The sender marks packets with the ECT (ECN-Capable Transport) bit in the IP ToS field.
2. A congested router marks a packet with CE (Congestion Experienced) instead of dropping it.
3. The receiver echoes the CE bit back in the TCP ACK header (the ECE flag).
4. The sender reacts as if a loss occurred (halve cwnd), but the packet was not actually lost — no retransmission needed.

Advantages: Lower latency (no packet drop = no retransmission delay), better throughput, reduced queueing.

AQM (Active Queue Management): ECN works best with AQM algorithms at routers:

• RED (Random Early Detection): Drop/mark packets probabilistically as queue length increases. Prevents buffers from filling completely.
• CoDel (Controlled Delay): Marks packets based on sojourn time (how long the packet spent in the queue) rather than queue length. Targets a minimum delay, not a length threshold. Very effective against bufferbloat.

Bufferbloat: Modern routers have enormous buffers (megabytes). A full buffer means packets queue for hundreds of milliseconds — killing latency even while throughput is high. CoDel's insight: a healthy queue drains quickly; a packet that sits for > 5 ms (the target interval) signals real congestion. This is the right signal, not buffer fill level.

# CoDel sojourn-time logic (simplified)
from collections import deque
import time

TARGET_DELAY_MS = 5.0   # target maximum sojourn time
INTERVAL_MS     = 100.0  # observation interval

class CoDelQueue:
    def __init__(self):
        self.q = deque()          # (enqueue_time, packet)
        self.dropping = False
        self.first_above_time = None

    def enqueue(self, packet):
        self.q.append((time.time(), packet))

    def dequeue(self):
        if not self.q:
            return None, False
        enq_time, packet = self.q.popleft()
        sojourn_ms = (time.time() - enq_time) * 1000
        should_mark = sojourn_ms > TARGET_DELAY_MS
        return packet, should_mark  # mark = signal ECN CE

Classical TCP (Reno) was designed in an era of 10 Mbps LANs and 100 ms RTTs. On a 10 Gbps link with 100 ms RTT, the BDP is 125 MB ≈ 83,000 MSS. To achieve full utilization, TCP must probe from cwnd = 41,500 (after halving on loss) back to 83,000 — a difference of 41,500 packets. Reno's additive increase adds 1 packet/RTT, so recovery takes 41,500 RTTs ≈ 1.15 hours. This is completely impractical.

CUBIC (the default TCP in Linux since 2006) solves this with a cubic growth function. After each loss event:

W(t) = C × (t − K)³ + W_max

where:

• W_max = cwnd just before the loss event
• K = ∛(W_max × β / C), the time at which the cubic function equals W_max
• C = 0.4 (scaling constant)
• β = 0.7 (CUBIC's multiplicative decrease factor, larger than Reno's 0.5)
• t = time since the last loss event

The cubic shape has three key phases:

1. Fast initial recovery: The cubic rises steeply far from W_max, quickly recovering lost bandwidth.
2. Slow probing near W_max: The curve flattens near W_max — cautious because this is where the last loss occurred.
3. Exploration above W_max: Rises steeply again to probe for new bandwidth.

RTT independence: CUBIC's increase is based on wall-clock time, not RTT count. This removes Reno's RTT unfairness — two flows with different RTTs but the same W_max have the same window evolution.

Friendliness: CUBIC falls back to Reno-like behavior on slow networks (when the cubic function grows slower than Reno would), ensuring it does not starve legacy connections.

import math

C = 0.4   # CUBIC scaling constant
beta = 0.7  # multiplicative decrease factor

def cubic_window(t_since_loss, W_max):
    """Return cwnd at time t_since_loss seconds after a loss event."""
    K = (W_max * (1 - beta) / C) ** (1/3)
    return C * (t_since_loss - K)**3 + W_max

# Compare CUBIC vs Reno recovery on a 10 Gbps link
W_max = 83000  # MSS (BDP of 10Gbps, 100ms)
reno_cwnd = W_max * 0.5   # Reno: halve on loss
print(f"W_max = {W_max} MSS")
print(f"Reno starts recovery at cwnd = {reno_cwnd:.0f}")
print(f"Reno recovery time: {W_max/2:.0f} RTTs\n")

print("CUBIC recovery (wall clock):")
for t in [0, 0.1, 0.5, 1.0, 2.0, 5.0, 10.0]:
    w = cubic_window(t, W_max)
    print(f"  t={t:.1f}s: cwnd = {w:.0f} MSS")

All classical algorithms (Reno, CUBIC) are loss-based: they increase cwnd until they observe loss, then back off. This has a fundamental problem: to detect the bottleneck, you must overflow it — building a queue, inflating RTT, and dropping packets. You are using network pain as a signal.

BBR (Bottleneck Bandwidth and RTT), developed at Google (Cardwell et al., 2016), takes a radically different approach: model-based control. Instead of reacting to loss, BBR tries to maintain the operating point at the BDP — filling the pipe without building a queue.

BBR continuously estimates two quantities:

1. BtlBw (bottleneck bandwidth): The maximum delivery rate recently achieved, measured over multiple RTTs using the ACK rate: BtlBw = max(delivered_bytes / delivery_interval) over a sliding window.
2. RTprop (minimum RTT): The minimum RTT observed over the last 10 seconds. This estimates the propagation delay (RTT without queue).

The BDP estimate = BtlBw × RTprop. BBR targets cwnd ≈ BDP × pacing_gain.

BBR's four states (phases):

1. STARTUP: Exponential cwnd increase (like slow start) until BtlBw stops growing — quickly finds the bottleneck.
2. DRAIN: Exponentially decrease pacing rate to drain the queue built during STARTUP.
3. PROBE_BW: Cycles pacing gain between 1.25 and 0.75 (and 1.0) to probe for bandwidth changes without building a persistent queue.
4. PROBE_RTT: Periodically reduces cwnd to 4 packets for 200 ms to get a fresh RTprop estimate.

Why BBR matters: BBR achieves much higher throughput on lossy links (like wireless or intercontinental paths) where CUBIC interprets random loss as congestion. On a 1% random-loss satellite link, CUBIC's throughput falls dramatically (recall: throughput ∝ 1/√p); BBR maintains near-full bandwidth.

BBR pitfalls: BBR v1 is known to cause latency spikes and unfairness against CUBIC flows. BBR v2 (and v3) address these but add complexity. It is an active research area.

# BBR conceptual model (not a real implementation)
class BBRState:
    STARTUP   = 'STARTUP'
    DRAIN     = 'DRAIN'
    PROBE_BW  = 'PROBE_BW'
    PROBE_RTT = 'PROBE_RTT'

class BBR:
    def __init__(self):
        self.state        = BBRState.STARTUP
        self.btl_bw       = 0       # estimated bottleneck bandwidth (bytes/s)
        self.rt_prop      = float('inf')  # estimated min RTT (seconds)
        self.pacing_gain  = 2.89    # startup gain (~ln2 growth/RTT approx)
        self.cwnd_gain    = 2.89

    def on_ack(self, delivery_rate, rtt, delivered):
        # Update BtlBw: max-filter over recent delivery rates
        self.btl_bw = max(self.btl_bw, delivery_rate)
        # Update RTprop: min-filter over 10-second window
        self.rt_prop = min(self.rt_prop, rtt)

        bdp = self.btl_bw * self.rt_prop  # bytes

        if self.state == BBRState.STARTUP:
            if self._bw_plateau():
                self.state = BBRState.DRAIN
                self.pacing_gain = 1 / 2.89
        elif self.state == BBRState.DRAIN:
            if self._queue_drained(bdp, delivered):
                self.state = BBRState.PROBE_BW
                self.pacing_gain = 1.0

        target_cwnd = self.cwnd_gain * bdp
        return target_cwnd

    def _bw_plateau(self): ...
    def _queue_drained(self, bdp, inflight): ...

QUIC (RFC 9000, standardized 2021) is the transport protocol underlying HTTP/3. It runs over UDP and implements its own congestion control in user space. This has a profound consequence: congestion control algorithms can be deployed without OS kernel updates.

QUIC ships with a CUBIC-like default but its pluggable architecture allows per-connection algorithm choice. Google deploys BBR for QUIC; Cloudflare experiments with newer algorithms. This is the "congestion control as software update" era.

QUIC also fixes a fundamental flaw in TCP: head-of-line blocking. In HTTP/2 over TCP, multiple streams share one TCP connection. A single lost packet stalls ALL streams because TCP's byte stream must be delivered in order. QUIC multiplexes streams at the transport layer — each stream has independent delivery, so one lost packet only stalls its own stream.

Multipath TCP (MPTCP) allows a single connection to use multiple network paths simultaneously (e.g., WiFi + cellular on a phone). Congestion control becomes much harder: sending too aggressively on one path while backing off another can be globally unfair. Coupled congestion control (MPTCP's approach) shares the ssthresh update across subflows so the aggregate TCP behaves like a single flow.

QUIC packet number spaces also enable more accurate RTT measurement than TCP (no retransmission ambiguity — each QUIC packet has a unique monotone packet number). This improves BBR's RTprop estimate significantly.

The trend is clear: congestion control is moving from kernel-space, protocol-specific code to application-level, rapidly-iteratable algorithms. The principles (probe for bandwidth, back off on congestion, be fair) remain the same; the implementation layer is rising up the stack.

# QUIC conceptual: congestion controller is pluggable
from abc import ABC, abstractmethod

class CongestionController(ABC):
    @abstractmethod
    def on_packet_sent(self, packet_number, size): ...
    @abstractmethod
    def on_packet_acked(self, packet_number, rtt): ...
    @abstractmethod
    def on_packet_lost(self, packet_number): ...
    @abstractmethod
    def get_cwnd(self) -> int: ...

class CUBICController(CongestionController):
    def __init__(self):
        self.cwnd = 10 * 1460  # 10 MSS initial
        self.w_max = self.cwnd
        self.beta = 0.7
        # ... cubic parameters

    def on_packet_lost(self, packet_number):
        self.w_max = self.cwnd
        self.cwnd = int(self.cwnd * self.beta)

    def get_cwnd(self):
        return self.cwnd

class BBRController(CongestionController):
    # ... BBR state machine
    pass

# QUIC connection picks its controller at connect time
class QUICConnection:
    def __init__(self, cc: CongestionController):
        self.cc = cc

    def send(self, data):
        if self.bytes_in_flight() < self.cc.get_cwnd():
            self._send_packet(data)

    def bytes_in_flight(self): ...
    def _send_packet(self, data): ...