Skip to content
Tutorials Center
My learning

Topics

Lesson 41 of 79 ยท Transport Layer

TCP Congestion Control

Learn how TCP finds the network's capacity: slow start, congestion avoidance, AIMD, fast recovery, Reno, CUBIC, BBR and ECN, with cwnd simulations in Python.

Flow control stops a sender from overwhelming the receiver. But there is another thing a sender can overwhelm: the network. Every link and router queue on the path has a limited capacity, and thousands of connections share them. If every sender simply blasted data at the rate its receiver allowed, routers would drop most of the packets, senders would retransmit, the retransmissions would cause more drops, and throughput would collapse. This real event happened in 1986 and is called congestion collapse. TCP's congestion control, designed by Van Jacobson, is the reason it hasn't happened again.

TCP does not get explicit help from the network, at least not traditionally. It has to infer congestion from what it sees (mostly packet loss), and it must find a sending rate that is as high as the path allows without staying above it. The tool is a second window, the congestion window (cwnd), kept by the sender. You will watch it grow and shrink in several simulations, and compare the classic Reno algorithm with CUBIC and BBR.

The congestion window

At any moment the sender may have this many bytes unacknowledged:

Text
bytes in flight <= min(rwnd, cwnd)

rwnd is the receiver's advertised window. cwnd is the sender's own estimate of what the network can carry, measured in bytes but usually discussed in segments (multiples of the MSS). Roughly, the sending rate is cwnd / RTT: one window of data per round trip. Each returning ACK is a signal that a packet has left the network, so new data can enter in its place. This ACK clocking makes TCP self-pacing, since data goes out at about the rate ACKs come back.

The algorithm has two jobs: grow cwnd to discover more capacity, and cut it sharply when congestion appears. The classic design has three phases, shown below.

stateDiagram-v2
    [*] --> SlowStart
    SlowStart --> CongestionAvoidance : cwnd reaches ssthresh
    SlowStart --> SlowStart : timeout (cwnd = 1)
    CongestionAvoidance --> FastRecovery : 3 duplicate ACKs
    FastRecovery --> CongestionAvoidance : new ACK (cwnd = ssthresh)
    CongestionAvoidance --> SlowStart : timeout (cwnd = 1)
    FastRecovery --> SlowStart : timeout

The Reno phases. The slow start threshold, ssthresh, decides where exponential growth ends and linear growth begins.

Slow start

A new connection does not know the path's capacity, so it starts small and grows quickly. The initial window is 10 segments on modern systems (it used to be 1 to 4). In slow start, cwnd grows by one segment for every ACK received. Since one window's worth of ACKs returns each round trip, cwnd doubles every RTT: 10, 20, 40, 80... The name is ironic; exponential growth is fast, and it is "slow" only compared with sending everything at once.

Slow start ends in one of two ways: cwnd reaches the slow start threshold (ssthresh), or a loss occurs. This matters a lot for short transfers. A web page of a few hundred kilobytes may finish before cwnd has ever grown big, so latency (the number of RTTs) rather than bandwidth decides the speed. That is why a handshake plus several slow-start rounds make distance so expensive.

Congestion avoidance and AIMD

Once cwnd reaches ssthresh, the sender becomes cautious. In congestion avoidance, it grows cwnd by about one segment per round trip (technically MSS x MSS / cwnd bytes per ACK). Growth is now linear: probe gently for extra capacity.

When congestion is detected, the sender cuts cwnd in half. This pattern, additive increase, multiplicative decrease (AIMD), produces the famous sawtooth: slowly climb, suddenly drop, climb again. AIMD is not an accident. It is the combination that makes competing flows converge to a stable and fair sharing of a bottleneck link.

Reacting to loss

TCP reads loss as congestion, and reacts differently depending on the evidence, using the signals from the reliability lesson:

  • Three duplicate ACKs. Packets are still getting through (they generate the duplicates), so the network is only mildly congested. Reno performs fast retransmit and then fast recovery: ssthresh = cwnd / 2 and cwnd = ssthresh (plus a few segments of inflation while recovering). It continues in congestion avoidance, not from scratch.
  • Timeout. No ACKs are coming back at all, a much worse sign. The sender sets ssthresh = cwnd / 2 and cwnd = 1 segment, and returns to slow start.

NewReno improves fast recovery when several segments of one window are lost, staying in recovery until all are repaired. With SACK, modern stacks recover multiple losses efficiently.

Python Reno: slow start, congestion avoidance and two kinds of loss

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Compare the two losses. After the three duplicate ACKs, cwnd falls from 76 to 38 and keeps growing linearly. After the timeout, cwnd drops from 51 to 1, ssthresh becomes 25.5, and the sender has to climb back through slow start.

Why AIMD is fair

Suppose two flows share a bottleneck link of capacity 100 units. Both add 1 unit per RTT while the link has room (additive increase). When their sum exceeds the capacity, both detect loss and halve their rate (multiplicative decrease). Addition keeps the difference between the two rates constant, while halving cuts the difference in half every time. Over many cycles, the gap vanishes: the flows converge to equal shares. By contrast, "multiplicative increase" would keep the ratio unchanged and never converge.

Python Two flows converge to a fair share under AIMD

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Real fairness is rougher than this model. Flows with a shorter RTT grow faster and take a larger share. An application that opens eight parallel connections is, to the network, eight flows. And different algorithms behave differently when they meet.

Throughput and loss

Because loss halves the window, loss rate and throughput are tightly linked. A well-known approximation (the Mathis formula) for a long-running Reno flow says:

Text
throughput ~ (MSS / RTT) x (1.22 / sqrt(p))

where p is the packet loss probability. Throughput falls with the square root of the loss rate and in direct proportion to the RTT. This explains why a tiny amount of random loss (for example on a radio link) can ruin a long-distance transfer: TCP interprets the loss as congestion.

Python The Mathis formula: loss rate vs throughput

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The numbers are an upper-bound estimate for one Reno flow in steady state, not a promise. They show the shape: 100 times less loss gives 10 times more speed, and five times the RTT gives one-fifth of the speed.

CUBIC

Reno's one-segment-per-RTT growth is very slow on a modern long, fast path, where the window may need to be thousands of segments. CUBIC, the default congestion control in Linux (and widely used elsewhere), grows cwnd as a cubic function of the time since the last loss, not of the number of RTTs. After a loss at window Wmax, it cuts to 70 % (not 50 %), then follows

Text
W(t) = C x (t - K)^3 + Wmax        K = cube root( Wmax x 0.3 / C ),   C = 0.4

The curve rises fast, flattens near Wmax (cautious where congestion was last seen), and then speeds up again to probe for more capacity. Because it depends on time rather than ACK count, CUBIC treats flows with different RTTs more evenly.

Python CUBIC versus Reno after a loss at 100 segments

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

In this simplified model, Reno restarts from half of the old window and reaches 100 after five seconds on a 100 ms path. CUBIC jumps back almost to 100 within three seconds and then flattens before probing further. At larger windows the difference grows.

BBR: modelling the path instead of reacting to loss

Loss-based algorithms (Reno, CUBIC) have a built-in flaw. They keep increasing until a buffer overflows, so they fill every queue on the path. Large router buffers turn that into bufferbloat: high latency for everyone, even though the link is "busy". BBR (Bottleneck Bandwidth and Round-trip propagation time), developed at Google, takes a different approach. It continuously measures the maximum delivery rate (the bottleneck bandwidth) and the minimum RTT, and sends at a rate close to the bandwidth-delay product, aiming to keep the pipe full but the queue short. Loss is not the main signal.

BBR can achieve high throughput even on links with random loss, where CUBIC would back off, and keeps latency lower. Its first version could be unfair to loss-based flows sharing a bottleneck and cause many retransmissions in shallow buffers; later versions (v2, v3) addressed some of this. Which algorithm a server uses is a setting (on Linux, net.ipv4.tcp_congestion_control), and each connection makes its own choice.

ECN: congestion without loss

Dropping packets is a blunt way to say "slow down". Explicit Congestion Notification (ECN) lets a router signal congestion by marking packets instead of dropping them. The two ECN bits in the IP header (once part of the "type of service" byte) are set by a sender that supports ECN to ECT; a congested router changes them to CE (Congestion Experienced). The receiver sees CE and echoes it to the sender in the TCP ECE flag, and the sender reduces cwnd and replies with CWR. The sender gets the message without losing a single packet. ECN must be negotiated in the handshake and needs routers that mark. Data-center variants such as DCTCP make finer use of the marks.

Congestion control also exists outside TCP: QUIC implements the same algorithms (Reno, CUBIC, BBR) in user space, and applications using UDP must provide their own, or they can harm everyone else on the path.

Congestion control in general: open loop and closed loop

TCP's window is one answer to congestion, but congestion control is a broader topic. Congestion means that more traffic arrives at part of the network than it can carry, so queues grow, packets are delayed and then dropped, and senders retransmit, which can make things worse. Controlling it improves the stability of the network and shares capacity more fairly. The costs are extra complexity, some wasted capacity when the controls are conservative, and a delay before the controls take effect.

Techniques fall into two families.

Open-loop (prevention). Try to design the system so congestion does not happen, without using feedback from the network. The controls are applied at the source or at the edge:

  • Admission policy and admission control: a new flow is accepted only if the network can carry it (see QoS).
  • Retransmission, window and acknowledgment policies: sensible timers, selective repeat instead of go-back-N and acknowledging several packets together reduce needless traffic.
  • Discarding policy: routers drop the less important packets first, for example older audio packets that would arrive too late anyway.
  • Traffic shaping: smoothing bursts with a leaky or token bucket.
  • Overprovisioning: building more capacity than the expected peak. Simple, but expensive.

Closed-loop (cure). Detect congestion that has started and react using feedback:

  • Backpressure: a congested router stops accepting traffic from the upstream router, which fills its own queue and in turn pushes back toward the source, hop by hop. It works in networks with virtual circuits and in link-level flow control.
  • Choke packet: the congested router sends a message directly to the source, asking it to slow down, and the source cuts its rate until choke packets stop. This is the direct ancestor of ICMP Source Quench (now deprecated).
  • Implicit signaling: the source infers congestion without being told, from delay or lost packets, which is what classic TCP does.
  • Explicit (network-assisted) signaling: routers mark packets, as with ECN, or tell the sender a rate, as in ATM-style explicit rate schemes.
Python A choke packet slows the senders

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Without feedback the queue stays full and the router keeps dropping packets (60 in ten ticks). With choke packets the senders back off, the queue drains, and the offered load settles near the link capacity.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. A connection starts slow start with cwnd = 10 segments and no loss occurs. What is cwnd after three round trips?

    Slow start doubles cwnd every RTT: 10, 20, 40, 80. After three round trips it is 80 (assuming ssthresh is higher).
  2. 2. Reno detects loss through three duplicate ACKs while cwnd = 60. What does it do?

    Duplicate ACKs show that some packets still get through, so Reno halves the window and uses fast recovery. Only a timeout sends it back to a window of one segment.
  3. 3. Why does AIMD lead competing flows to a fair share of a link?

    Adding the same amount to both flows leaves their difference unchanged, but halving both on loss halves the difference, so repeated cycles squeeze it toward zero.
  4. 4. What is the main idea that distinguishes BBR from Reno and CUBIC?

    BBR builds a model of the path and sends at the estimated capacity, so it does not need to overflow a buffer to find the limit.
  5. 5. How does ECN signal congestion?

    ECN gives the sender the message without dropping a packet: CE in the IP header, ECE back in TCP, then a smaller window and a CWR reply.

Summary

  • TCP limits data in flight to min(rwnd, cwnd). The congestion window cwnd protects the network; the receive window protects the receiver.
  • Slow start doubles cwnd every RTT from an initial window of about 10 segments until ssthresh; congestion avoidance then adds about one segment per RTT.
  • AIMD halves the window on loss and grows it linearly, giving the sawtooth and driving competing flows toward a fair share.
  • Three duplicate ACKs trigger fast retransmit and fast recovery (halve); a timeout drops cwnd to one segment and returns to slow start.
  • Loss rate and RTT limit throughput (about MSS / RTT x 1.22 / sqrt(p) for Reno).
  • CUBIC grows with time since the last loss and is the usual default; BBR models bandwidth and RTT instead of waiting for loss; ECN lets routers signal congestion without dropping packets.

Next, put TCP to work from code with socket programming basics.