TCP congestion control

Why it exists

If all senders transmit as fast as their receivers allow, the routers' queues overflow, packets are lost, and the retransmissions make it worse (congestion collapse). IP gives no feedback, so TCP senders themselves must slow down when they sense congestion and speed up again when the network seems free. The mechanism is the congestion window $\text{cwnd}$, a limit on the outstanding data computed by the sender (flow control, the receiver's limit, is on the previous page).

Prerequisites

You need TCP's window mechanism (TCP flow control) and cumulative acknowledgements (TCP basics).

Precise definitions

The sender may have at most $\min(\text{cwnd}, \text{rwnd})$ bytes outstanding. Measure cwnd in segments (units of MSS). In one round (one round-trip time) the sender sends cwnd segments and receives their acknowledgements. The sender infers loss from the absence of acknowledgements:

• a timeout (no acknowledgement for a segment within the timer): serious, probably many segments lost;
• three duplicate acknowledgements (four identical acknowledgements): one segment was lost but later segments are arriving, so the network still delivers.

The algorithm has two phases, separated by the slow start threshold $\text{ssthresh}$:

1. Slow start ($\text{cwnd} < \text{ssthresh}$): cwnd starts at $1$ segment and grows by $1$ segment for every acknowledgement received, which doubles it every round: $1, 2, 4, 8, \dots$ (exponential growth despite the name). In the round-based model it stops at ssthresh: $\text{cwnd} \leftarrow \min(2\,\text{cwnd}, \text{ssthresh})$.
2. Congestion avoidance ($\text{cwnd} \ge \text{ssthresh}$): cwnd grows by $1$ segment per round ($1/\text{cwnd}$ per acknowledgement): additive increase.

Reaction to loss (the model of this site):

Since the window is halved at a loss and grows by one per round otherwise, the behaviour is AIMD (additive increase, multiplicative decrease); the window plotted against time is a sawtooth.

How it works

Slow start and the threshold

Starting from $1$, the window doubles every round; it reaches a threshold $2^k$ in round $k + 1$, after $k$ doublings, having sent $2^k - 1$ segments in the earlier rounds. For example with ssthresh $= 16$ the windows are $1, 2, 4, 8, 16$ in rounds $1$ to $5$ ($31$ segments in total up to and including round $5$, $15$ before it), and then $17, 18, \dots$ (one more each round).

Tahoe and Reno side by side

Initial ssthresh $16$. Slow start for rounds $1$ to $5$ (cwnd $1 \to 16$), then congestion avoidance ($17, 18, 19, 20$). At the end of round $9$, when the window is $20$, three duplicate acknowledgements arrive. Tahoe: ssthresh $= 10$, cwnd $= 1$ and slow start again ($1, 2, 4, 8$, then $10$ and $11$). Reno: ssthresh $= 10$ and cwnd $= 10$ at once, then additive increase ($11, 12, 13, \dots$). At the end of round $15$ a timeout occurs: both restart from cwnd $= 1$; Tahoe has cwnd $11$ so ssthresh $= 5$, Reno has $15$ so ssthresh $= 7$.

Reno is better after duplicate acknowledgements because the network is still delivering packets (the duplicates themselves prove it), so there is no reason to fall back to one segment.

The sawtooth and the average rate

If the peak window at which loss occurs is $W$ segments, the window falls to $W/2$ and rises by $1$ per round: a cycle lasts $W/2$ rounds, the window rises from $W/2$ to $W$ and its average is $3W/4$. Hence the average throughput is

One cycle sends about $\frac{3W^2}{8}$ segments and ends with one loss, so the loss probability per segment is $p \approx \frac{8}{3W^2}$, i.e. $W = \sqrt{8/(3p)}$, and

(A simulation with random losses gave a constant of about $1.28$; the formula is approximate.) The throughput falls with the round-trip time and with the square root of the loss rate. TCP is fair in the sense that connections with equal RTT sharing a bottleneck converge to equal shares (quoted textbook argument).

Worked examples

Cheat box

Traps and GATE patterns

Connections

The window is the sliding window of sliding window protocols; the receiver's limit is flow control; the connection and acknowledgement numbers are from TCP basics. The bound throughput $\le$ window / RTT of performance metrics applies to the congestion window as well.

PYQs

A TCP sender successfully establishes a connection
with a TCP receiver and starts the transmission of
segments.
The
TCP
congestion
control
mechanism's slow-start threshold is set to 10000
segments. Assume that the round-trip time is fixed
at 1 millisecond. Assume that the sender always has
data to send, the segments are numbered from 1,
and no segment is lost.

Let t denote the time (in milliseconds) at which the
transmission of segment number 2000 starts.

Which one of the following options is correct?

Consider a new TCP connection between a sender
and a receiver. The receiver advertised window is
constant at 48 KB, the maximum segment size (MSS)
is 2 KB, and the slow start threshold (ssthresh) is 16
KB.

Assume there are no timeouts or duplicate
acknowledgements. The number of rounds of
transmission required for the congestion control

COMPUTER NETWORK
algorithm to reach the congestion avoidance phase
is ______.

Note: 1K = 210

Consider a TCP connection operating at a point of
time with the congestion window of size 12 MSS
(Maximum Segment Size), when a timeout occurs
due to packet loss. Assuming that all the segments
transmitted in the next two RTTs (Round Trip Time)
are acknowledged correctly, the congestion window
size (in MSS) during the third RTT will be
___________.

Consider a TCP connection between a client and a
server with the following specifications: the round
trip time is 6 ms, the size of the receiver advertised
window is 50 KB, slow-start threshold at the client is
32 KB, and the maximum segment size is 2 KB. The
connection is established at time t = 0. Assume that
there are no timeouts and errors during transmission.
Then the size of the congestion window (in KB) at
time t + 60 ms after all acknowledgments are
processed is __________.

COMPUTER NETWORK

Consider the following statements regarding the
slow start phase of the TCP congestion control
algorithm. Note the cwnd stands for the TCP
congestion window and MSS denotes the
Maximum Segment Size.

(i) The cwnd increases by 2 MSS on every
successful acknowledgment.
(ii) The cwnd approximately doubles on every
successful acknowledgment.
(iii) The cwnd increases by 1 MSS every round
trip time.
(iv) The cwnd approximately doubles every round
trip time.

Which one of the following is correct?

For a host machine that uses the token bucket
algorithm for congestion control, the token bucket has
a capacity of 1 megabyte and the maximum output
rate is 20 megabytes per second. Tokens arrive at a
rate to sustain output at a rate of 10 megabytes per
second. The token bucket is currently full and the
machine needs to send 12 megabytes of data. The

COMPUTER NETWORK
minimum time required to transmit the data is
______ seconds.

Let the size of the congestion window of a TCP
connection be 32 KB when a timeout occurs. The
round trip time of the connection is 100 msec and
the maximum segment size used is 2 KB. The time
taken (in msec) by the TCP connection to get back
to 32 KB congestion window is __________.

Consider an instance of TCP's Additive Increase
Multiplicative Decrease (AIMD) algorithm where
the windows size at the start of the slow start phase
is 2 MSS and the threshold at the start of the first
transmission is 8 MSS. Assume that a time-out
occurs during the fifth transmission. Find the
congestion window size at the end of the tenth
transmission.

In the slow start phase of the TCP congestion control
algorithm, the size of the congestion window

A computer on a 10 Mbps network is regulated by a
token bucket. The token bucket is filled at a rate of 2
Mbps. It is initially filled to capacity with 16
Megabits. What is the maximum duration for which
the computer can transmit at the full 10 Mbps?

Self-check

Revision card

References