ifnodoraemon

Posted on Oct 21 Originally published at blog.llmgo.top

TCP Congestion Control Evolution & High-Performance Transport: From Reno and Cubic to BBR Mathematical Models, and HTTP/2 to HTTP/3 (QUIC)

#congestioncontrolquic #networking #ai #programming

[!NOTE] Executive Summary (TL;DR)

Congestion Control Progression: Compares loss-based Reno against cubic-growth CUBIC (standard multiplicative decrease factor beta=0.7) and Google's BDP-model BBR.

Kernel Implementation Truths: Clarifies that modern Linux kernel BBR implementations do not strictly mandate the external fq qdisc, utilizing internal pacing engines.

Modern Transport: Explores UDP-based QUIC and HTTP/3 0-RTT migrations, safeguarding distributed LLM API pipelines against volatile network degradation.

Introduction: The Fundamental Division Between Flow Control and Congestion Control

In Chapter 5 of our series, Network & Transport Layers in Depth: IP Routing, CIDR, TCP 11-State Machine, and Sliding Window First Principles, we saw how TCP's sliding window uses the Advertised Window (rwnd) to protect the receiver's socket buffer.

However, network communications do not travel through an isolated two-party pipe; they traverse complex mesh fabrics composed of hundreds of physical switches and routers:

Flow Control: An end-to-end local contract designed to prevent a fast sender from overrunning a slow receiver's application memory buffer;
Congestion Control: A global, fabric-wide coordination mechanism designed to prevent participating hosts from injecting more aggregate traffic into the network than the intermediate switches' queues and optical links can physically sustain.

In 1986, the young Internet experienced its first catastrophic "Congestion Collapse": throughput across the NSFnet backbone plummeted from 32 Kbps to 40 bps—an 800-fold collapse!

To rescue the Internet, Van Jacobson published his seminal 1988 paper defining modern congestion control algorithms. This article breaks down the three generational paradigm shifts in congestion control: Loss-based classical control (Reno/Cubic) $\to$ Model-based delay-bandwidth control (Google BBR) $\to$ Application-layer transport unification (HTTP/3 QUIC).

1. Loss-Based Congestion Control: AIMD, Reno, and the Cubic Polynomial

1.1 Classical AIMD Philosophy and TCP Reno

Loss-based congestion control relies on a core premise: the network is a black box, and packet loss signals congestion. The sender tracks a Congestion Window (cwnd), and the effective volume of inflight data permitted into the network is governed by:

$$W = \min(cwnd, rwnd)$$

TCP Reno introduced the iconic AIMD (Additive Increase Multiplicative Decrease) feedback loop:

stateDiagram-v2
    [*] --> SlowStart: Connection Initialized (cwnd = 10 MSS)
    SlowStart --> CongestionAvoidance: cwnd >= ssthresh (Exponential to Linear)
    SlowStart --> FastRecovery: 3 Duplicate ACKs received (Mild Loss)
    CongestionAvoidance --> FastRecovery: 3 Duplicate ACKs received
    CongestionAvoidance --> SlowStart: RTO Timeout occurs (Severe Congestion)
    FastRecovery --> CongestionAvoidance: New Full ACK received (Window Restored)
    FastRecovery --> SlowStart: RTO Timeout occurs again

Slow Start: For each Round-Trip Time (RTT), cwnd doubles exponentially ($1, 2, 4, 8 \dots$) until reaching the slow-start threshold ssthresh;
Congestion Avoidance (Additive Increase): Once in steady state, cwnd grows by only 1 MSS per RTT (linear growth), cautiously probing for spare network bandwidth;
Fast Retransmit & Fast Recovery (Multiplicative Decrease): Upon receiving 3 duplicate ACKs, the sender infers an isolated dropped segment rather than total route failure. It immediately retransmits the missing segment, cuts ssthresh in half ($\text{ssthresh} = \frac{cwnd}{2}$), sets cwnd to ssthresh + 3, and enters Fast Recovery, skipping a painful fallback to Slow Start.

The Fatal Flaw: Bufferbloat

Algorithms like Reno assume that "loss equals congestion." As a result, the sender continuously inflates cwnd, filling up the deep buffers of intermediate routers. While no packets are dropped initially, packets languish in router queues for hundreds of milliseconds or even seconds, producing severe RTT inflation and devastating queueing delays that destroy interactive real-time performance!

1.2 TCP Cubic: Cubic Polynomial Curve and RTT Independence

Over high-bandwidth, high-latency (High-BDP) optical networks, Reno's linear 1 MSS per RTT increment is painfully sluggish—taking hours to saturate a 10 Gbps transoceanic link.

Linux kernel 2.6.19 introduced TCP Cubic, making it the long-standing default. Cubic replaces linear growth with a cubic polynomial function governed by elapsed real time $t$:

$$W_{cubic}(t) = C \cdot (t - K)^3 + W_{max}$$

Where:

$W_{max}$ is the congestion window size right before the previous packet loss event;
$K = \sqrt[3]{\frac{W_{max} \cdot (1 - \beta)}{C}}$ is the time constant required to scale the window back to $W_{max}$;
$C$ is a scaling constant (typically ~0.4), and $\beta$ is the multiplicative decrease factor specified by RFC 8312 / RFC 9438 (default 0.7, yielding an initial window reduction of $1 - \beta = 0.3$).

Cubic Window Growth Curve (Concave and Convex Phases):
      cwnd ^                                    / (Convex Phase: Probing New Capacity)
           |                                  /
           |                                /
   W_max --+---------------------+        /
           |   (Concave Phase)     \    /
           |   (Rapid Catch-up)     \  /
           |                         \/
           +---------------------------------------------> Time t
                                  t = K

Concave Phase: Following packet loss, the window climbs rapidly, decelerating as it nears $W_{max}$ to gently approximate past capacity;
Plateau Phase: Around $t \approx K$, growth stays relatively flat, maximizing link saturation with minimal risk of triggering buffer drops;
Convex Phase: If no packet loss occurs, window growth accelerates exponentially upward, aggressively discovering whether more physical bandwidth is available;
Time and RTT: CUBIC uses elapsed time for its main growth function and retains a TCP-friendly region. Actual throughput and fairness still depend on RTT, ACKs, and competing flows.

2. Model-Based Congestion Control: Google BBR Physical Modeling

Both Reno and Cubic are loss-based algorithms. However, loss is an indirect, lagging indicator of congestion, and on wireless links, random electromagnetic noise drops packets without any queue overflow.

In 2016, Google introduced BBR (Bottleneck Bandwidth and RTT), a revolutionary model-driven algorithm.

2.1 The Kleinrock Optimal Operating Point and BDP

flowchart TD
    subgraph Kleinrock["Kleinrock Optimal Operating Point"]
        Optimal["<b>Optimal State</b><br/>Throughput Maximized (BtlBw)<br/>Queueing Delay Minimized (RTprop)<br/>Inflight Data = BDP"]
    end

According to queueing theory, the physical capacity of any communication network is governed by two independent physical parameters:

$BtlBw$ (Bottleneck Bandwidth): Dictated by the slowest physical switch or optical interface along the route;
$RTprop$ (Round-Trip Propagation Time): Dictated by the speed of light through physical fiber and the physical distance between endpoints.

This defines the ideal volume of in-flight data—the Bandwidth-Delay Product (BDP):

$$BDP = BtlBw \times RTprop$$

Region 1 (Underutilized, $\text{Inflight} < BDP$): The pipe is not filled, and available capacity is wasted;
Region 2 (Optimal Kleinrock Point, $\text{Inflight} = BDP$): Throughput reaches physical maximum, router queues remain empty, and latency equals the minimum speed-of-light propagation delay!
Region 3 (Bufferbloat, $\text{Inflight} > BDP$): The pipe is saturated; additional packets queue up in switch buffers, inducing latency spikes;
Region 4 (Congestion Collapse): Switch buffers overflow, triggering severe packet loss.

BBR's Core Breakthrough: Never let traffic spill into Regions 3 and 4. By continuously estimating both $BtlBw$ and $RTprop$, BBR pins network inflight data precisely to the Kleinrock optimal point ($\text{Inflight} = BDP$)!

2.2 BBR State Machine and Pacing Rate Control

BBR replaces sliding window packet bursts with an autonomous Pacing Engine, dispatching individual packets at precise nanosecond intervals:

pacing_rate = pacing_gain * BtlBw

stateDiagram-v2
    [*] --> STARTUP: Connection start (pacing_gain = 2/ln(2) ≈ 2.89)
    STARTUP --> DRAIN: BtlBw plateaus (Pipe filled)
    DRAIN --> PROBE_BW: Drain excess queue (pacing_gain = ln(2)/2 ≈ 0.35)

    state PROBE_BW {
        [*] --> Gain125: 1.25x Probe higher bandwidth (1 RTT)
        Gain125 --> Gain075: 0.75x Drain newly created queue (1 RTT)
        Gain075 --> Gain100: 1.00x Cruise at steady state (6 RTTs)
        Gain100 --> Gain125: Loop cycle
    }

    PROBE_BW --> PROBE_RTT: Triggered if RTprop not updated in 10s
    PROBE_RTT --> PROBE_BW: cwnd capped at 4 packets for 200ms to measure true RTprop

STARTUP Phase: Uses a high pacing gain ($2.89\times$) to rapidly probe physical bottleneck bandwidth;
DRAIN Phase: Drops pacing gain to $0.35\times$ to flush out the queue accumulated during STARTUP;
PROBE_BW Phase (Cruising): Cycles through 8 phases ($1.25 \to 0.75 \to 1.0 \times 6$). It accelerates briefly to discover new capacity, slows down to drain queues, and cruises smoothly for the remaining cycles;
PROBE_RTT Phase: Every 10 seconds, caps cwnd at 4 packets for 200ms to completely empty all in-flight buffers, exposing the pristine speed-of-light $RTprop$.

3. Application and Transport Protocol Unification: HTTP/1.1, HTTP/2 to HTTP/3 (QUIC)

Even with optimal congestion control algorithms, TCP's kernel-bound architecture and single-stream abstraction remained a major bottleneck for modern web applications.

3.1 Protocol Stack Evolution and Head-of-Line (HoL) Blocking

flowchart TD
    subgraph HTTP1["HTTP/1.1: Plaintext Sequential Execution"]
        H1_Req1["GET /index.html"] --> H1_Wait["Wait for response..."]
        H1_Wait --> H1_Req2["GET /style.css"]
        H1_Note["Drawback: Head-of-line blocking; requires 6 parallel TCP connections workaround"]
    end

    subgraph HTTP2["HTTP/2: Multiplexing over Single TCP (Binary Framing)"]
        H2_Stream1["Stream 1 (HTML)"] & H2_Stream2["Stream 2 (CSS)"] & H2_Stream3["Stream 3 (JS)"] --> TCP_Pipe["Single TCP Connection Pipe"]
        TCP_Pipe --> Drop["1 TCP Packet Lost in Transit!"]
        Drop --> TCP_HoL["<b>Fatal TCP HoL Blocking</b>: Kernel stalls all multiplexed streams<br/>waiting for TCP retransmission, blocking all application data!"]
    end

    subgraph HTTP3["HTTP/3: QUIC Independent Streams over UDP"]
        H3_Stream1["Stream 1 (Healthy)"] & H3_Stream2["Stream 2 (Packet Lost)"] & H3_Stream3["Stream 3 (Healthy)"] --> UDP_Pipe["Independent UDP Datagrams"]
        UDP_Pipe --> H3_Fix["Independent stream delivery<br/>Shared congestion control still applies"]
    end

3.2 HTTP/3 and QUIC Capabilities and Limits

Independent stream delivery: Streams use byte offsets; packet numbers belong to connection packet-number spaces, not individual streams. Loss on one stream need not block others, though shared congestion control and application dependencies still couple progress.
Handshake and 0-RTT: Initial connections typically take 1 RTT. Resumption can attempt 0-RTT early data, but servers may reject it, and applications must account for replay. Repeat visits do not guarantee zero waiting.
Connection migration: Variable-length CIDs enable continuity across address changes when endpoint support, path validation, and reachability permit it.
User-space implementation: QUIC libraries can evolve independently of kernel TCP. Deploying a new binary does not imply arbitrary hot-swapping of algorithms on existing connections.
Encryption and visible metadata: TLS 1.3 protects handshake and application data, and QUIC applies header protection. Some fields, including versions and CIDs, remain visible. Networks can still discard or delay packets; not all headers are encrypted.

4. Production Tuning: Enabling Google BBR and Fair Queueing

To enable BBR on modern Linux servers (Linux kernel 4.9+, recommended 5.15+ or 6.x):

# 1. Inspect current congestion control algorithms
sysctl net.ipv4.tcp_congestion_control
sysctl net.ipv4.tcp_available_congestion_control

# 2. Append production configuration
cat << 'EOF' >> /etc/sysctl.conf
# BBR pacing strictly requires the Fair Queueing (FQ) packet scheduler
net.core.default_qdisc = fq
# Set TCP congestion control to BBR
net.ipv4.tcp_congestion_control = bbr
EOF

# 3. Reload configuration immediately
sysctl -p

# 4. Verify BBR module activation
lsmod | grep bbr

5. Summary and Next Steps

From physical links to IP routing, TCP state machines, sliding windows, and the transition from Reno/Cubic to BBR and HTTP/3 QUIC, we have surveyed how modern Internet communication guarantees reliability across wide-area networks.

However, we have yet to open one critical black box: when an electrical or optical pulse arrives at a Linux server's network adapter, how does the operating system kernel retrieve bytes in nanoseconds, schedule multi-core CPUs, and deliver payloads into socket buffers?

Why did early hardware-interrupt-only designs trigger fatal interrupt storms, and how did NAPI hybrid polling resolve them?
How does Linux's core sk_buff data structure use pointer arithmetic to achieve zero-copy protocol traversals?
Why do standard kernel stacks become bottlenecks on 100 Gbps interfaces, and how does eBPF XDP achieve 20M+ PPS wire-speed packet processing inside the network driver?

In Chapter 7 of our masterclass, we dive straight into the Linux networking subsystem: Linux Kernel Networking Subsystem in Depth: From NIC Drivers, NAPI, and Ring Buffers to eBPF XDP Wire-Speed Forwarding!

Frequently Asked Questions (FAQ)

Q1: Does BBR require fq?

Modern Linux TCP has internal pacing as a fallback without fq. The fq qdisc is a common pacing and flow-fairness choice, not a universal protocol requirement or hardware-offload guarantee. Verify kernel version, qdisc behavior, and measured latency. See the Linux BBR implementation notes.

Q2: Must BBR outperform CUBIC under random loss?

No. CUBIC normally multiplies its window by $\beta=0.7$ after a congestion event rather than Reno's halving rule. BBR models delivery rate and RTT but remains affected by loss, retransmission, ACK behavior, and implementation version. It cannot guarantee 90% line rate at 10% loss. Control RTT, queues, loss models, and competing flows. See RFC 9438.

Q3: How does QUIC provide reliable streams over UDP?

UDP/IP packets can still be lost. QUIC uses acknowledgments, loss detection, and retransmission of unacknowledged data for reliable byte streams. Retransmitted data appears in new packets, without reusing the original packet number. TLS 1.3 protects handshake and application data, while some routing headers remain visible. Separate streams reduce cross-stream transport head-of-line blocking; shared congestion control and application dependencies can still couple their progress. See RFC 9000 and RFC 9001.

Originally published at LLM Systems Architecture on blog.llmgo.top.

DEV Community