TCP Congestion Control: AIMD

We’ve already looked at what congestion control is in a previous lesson. Let’s get into some TCP-specific congestion control algorithms now!

But first:

Requirements of a Congestion Control Algorithm

1. The congestion control scheme must avoid congestion. In practice, this means that the algorithm should ensure that the bandwidth allocated to a certain host at any given time does not exceed the bandwidth of the bottleneck link.

2. The congestion control scheme must be efficient. The congestion control scheme should ensure that the available bandwidth is efficiently used. Namely that the bandwidth allocated to a certain host at any given time doesn’t fall too far below the bandwidth of the bottleneck link.

3. The congestion control scheme should be fair. Most congestion schemes aim at achieving max-min fairness, which we had a lesson dedicated to.

TCP Congestion Control Algorithms

To implement most TCP congestion control algorithms, a TCP host must be able to control its transmission rate. In order to do so, it can constrain its sending window. Recall that after transmitting data equal to the window size, the sender must pause and wait at least one RTT for the ACK before it can transmit more data. Thus the maximum data rate is: $\frac{window}{rtt}$ where $window$ is the maximum between the host’s sending window and the window advertised by the receiver.

Hence, TCP’s congestion control scheme can restrict sending windows based on a congestion window. The current value of the congestion window is stored in the TCB of each TCP connection. The value of the window that can be used by the sender is $min(congestion \ window,\ receiving \ window,\ sending \ window)$.

Additive Increase Multiplicative Decrease

The Additive Increase Multiplicative Decrease algorithm decreases the transmission rate of a host when congestion has been detected in the network. Congestion is detected when acknowledgments for packets do not arrive before the transmission timer times out. Furthermore, it increases their transmission rate when the network is not congested. Hence, the rate allocated to each host fluctuates with time, depending on the feedback received from the network.

The figure below illustrates the evolution of the transmission rates allocated to a host in a network.