TCP: sliding window, congestion control and fairness

IP delivers packets on a “best effort” basis: they may be lost, arrive out of order or duplicated. On top of it TCP builds a reliable, ordered byte stream between two programs, and does something more delicate too: it regulates each sender’s speed so that millions of connections share the network without making it collapse. In this lesson we look at reliable transmission with the sliding window and the proof of its efficiency, connection management, congestion control with additive increase and multiplicative decrease, and the proof that this mechanism shares bandwidth fairly.

The efficiency of stop-and-wait

The simplest way to transmit reliably: send a packet, wait for the acknowledgement (ACK), then send the next, retransmitting if the acknowledgement does not arrive within a timeout.

Theorem. With packets of bits, rate and round-trip time RTT, the fraction of time the link transmits with stop-and-wait is

Proof. The sender takes to send the packet; the last bit arrives after the propagation delay, and the acknowledgement comes back after another: in all, from the start of transmission to the acknowledgement, elapse (neglecting the duration of the acknowledgement). In this interval the link is used only for . ∎

With 1 Gb/s, 1500-byte packets (12 µs) and an RTT of 30 ms, : 0.04 % of the link is used. The solution is the sliding window: up to bytes can be sent without waiting for acknowledgements. The maximum rate becomes

and to fill the link the window must be at least the bandwidth-delay product (lesson on architecture): in the example 3.75 MB. If a packet is lost, everything from there on can be retransmitted (go-back-N) or only the lost packet (selective repeat, which TCP implements with selective acknowledgements, SACK).

The TCP connection

TCP opens the connection with the three-way handshake: SYN from the client, SYN-ACK from the server, ACK from the client. Every byte has a sequence number, and acknowledgements are cumulative: “I have received everything up to byte “. The receiver announces how much space it has in its buffer (the receive window): this is flow control, which prevents a fast sender from swamping a slow receiver. The retransmission timeout adapts continuously, estimating the mean and the variability of the RTT.

Congestion control

Flow control protects the receiver; the network must be protected separately. If everyone transmits too much, router queues fill up, packets are lost, senders retransmit, and the network can reach congestion collapse: all capacity is used for useless retransmissions. It really happened on the Internet in 1986, and Van Jacobson introduced the mechanism that, with variants, is still in use.

The sender keeps a congestion window , and the window used is the smaller of this and the receive window:

• slow start: at first doubles every RTT, to find the available capacity quickly;
• additive increase: past a threshold, grows by one packet per RTT, to probe cautiously for more room;
• multiplicative decrease: when a packet is lost, a sign that a queue is full, is halved.

In steady state the window oscillates in a sawtooth between and , with mean value . From this follows the well-known Mathis formula: with loss probability , the throughput is about , where MSS is the segment size. Doubling the distance halves the speed, and reaching 10 Gb/s over long distances requires tiny loss probabilities.

Fairness

Why exactly “additive increase, multiplicative decrease” (AIMD)? Because it is the combination that leads connections to share bandwidth equally, without anyone coordinating them.

Theorem. Two connections with the same RTT sharing a link with an AIMD policy converge to equal rates.

Proof. Let and be the two rates and the difference. During additive increase both grow by the same amount per RTT, so does not change. When the sum exceeds the capacity, both suffer a loss and halve: becomes . After losses the difference is , which tends to zero, while the sum keeps oscillating around the capacity. ∎

With multiplicative increase and additive decrease the difference would grow instead of shrinking. Connections with different RTTs are not treated equally: the closer one grows faster and gets more.

Modern variants

On fast, distant networks growth by one packet per RTT is too slow. CUBIC, the default in Linux, grows the window as a cubic function of the time since the last loss, independent of the RTT. BBR, developed by Google, does not wait for losses: it estimates the bottleneck bandwidth and the minimum RTT, and sends at the estimated rate, keeping queues short. The QUIC protocol, on which HTTP/3 is based, brings these functions on top of UDP, together with encryption, so that they can be updated without touching the operating system.