Congestion control refers to techniques and mechanisms that can either prevent congestion, before it happens, or remove congestion, after it has happened. Congestion control in TCP is based on both open-loop and closed-loop mechanisms. TCP uses a congestion window and a congestion policy that avoid congestion and detect and alleviate congestion after it has occurred.

Sender window size is determined by the available buffer space in the receiver (rwnd). If the network cannot deliver the data as fast as it is created by the sender, it must tell the sender to slow down. The sender has two pieces of information: the receiver-advertised window size and the congestion window size. The actual size of the window is the minimum of these two.

Actual window size = minimum (rwnd, cwnd)

TCP’s general policy for handling congestion is based on three phases: slow start, congestion avoidance, and congestion detection.

Slow Start: Exponential Increase

The slow start algorithm is based on the idea that the size of the congestion window (cwnd) starts with one maximum segment size (MSS). The size of the window increases one MSS each time one acknowledgement arrives. In the slow start algorithm, the size of the congestion window increases exponentially until it reaches a threshold. As the name implies, the algorithm starts slowly, but grows exponentially as shown in Fig. 1.

For simplicity, we ignore delayed-ACK policy and assume that each segment is acknowledged individually. The sender starts with cwnd = 1 MSS. This means that the sender can send only one segment. After the first ACK arrives, the size of the congestion window is increased by 1, which means that cwnd is now 2. Now two more segments can be sent. When two more ACKs arrive, the size of the window is increased by 1 MSS for each ACK, which means cwnd is now 4. Now four more segments can be sent. When four ACKs arrive, the size of the window increases by 4, which means that cwnd is now 8.

If we look at the size of the cwnd in terms of round-trip times (RTTs), we find that the growth rate is exponential as shown below:

Start → cwnd = 1

After 1 RTT → cwnd = 1 × 2 = 2 → 2¹

After 2 RTT → cwnd = 2 × 2 = 4 → 2²

After 3 RTT → cwnd = 4 × 2 = 8 → 2³

Slow start cannot continue indefinitely. There must be a threshold to stop this phase. The sender keeps track of a variable named ssthresh (slow start threshold). When the size of window in bytes reaches this threshold, slow start stops and the next phase starts.

Congestion Avoidance: Additive Increase

If we start with the slow start algorithm, the size of the congestion window increases exponentially. To avoid congestion before it happens, one must slow down this exponential growth. TCP defines another algorithm called congestion avoidance, which increases the cwnd additively instead of exponentially. In the congestion avoidance algorithm the size of the congestion window increases additively until congestion is detected. The Congestion avoidance, additive increase is shown in Fig. 2.

When the size of the congestion window reaches the slow start threshold in the case where cwnd = i, the slow start phase stops and the additive phase begins. In this algorithm, each time the whole “window” of segments is acknowledged, the size of the congestion window is increased by one. The window size increase is based on RTT, not on the number of arrived ACKs. In this case, after the sender has received acknowledgments for a complete window-size of segments, the size of the window is increased one segment. If we look at the size of cwnd in terms of round-trip time (RTT), we find that the rate is additive as shown below:

Start → cwnd = i

After 1 RTT → cwnd = i + 1

After 2 RTT → cwnd = i + 2

After 3 RTT → cwnd = i + 3

Congestion Detection: Multiplicative Decrease

If congestion occurs, the congestion window size must be decreased. The only way a sender can guess that congestion has occurred is the need to retransmit a segment. This is a major assumption made by TCP. Retransmission is needed to recover a missing packet which is assumed to have been dropped (i.e., lost) by a router. Retransmission can occur in one of two cases: when the Retransmission Time Out (RTO) timer times out or when three duplicate ACKs are received. In both cases, the size of the threshold is dropped to half (multiplicative decrease).

Most TCP implementations have two reactions:

1. If a time-out occurs, there is a stronger possibility of congestion; a segment has probably been dropped in the network and there is no news about the following sent segments. In this case TCP reacts strongly:

   a. It sets the value of the threshold to half of the current window size.

   b. It reduces cwnd back to one segment.

   c. It starts the slow start phase again.

2. If three duplicate ACKs are received, there is a weaker possibility of congestion; a segment may have been dropped but some segments after that have arrived safely since three duplicate ACKs are received. This is called fast transmission and fast recovery. In this case, TCP has a weaker reaction as shown below:

   a. It sets the value of the threshold to half of the current window size.

   b. It sets cwnd to the value of the threshold (some implementations add three segment sizes to the threshold).

   c. It starts the congestion avoidance phase.