21.6 Congestion Avoidance Algorithm

Slow start, which we described in Section 20.6, is the way to initiate data flow across a connection. But at some point we'll reach the limit of an intervening router, and packets can be dropped. Congestion avoidance is a way to deal with lost packets. It is described in [Jacobson 1988].

The assumption of the algorithm is that packet loss caused by damage is very small (much less than 1%), therefore the loss of a packet signals congestion somewhere in the network between the source and destination. There are two indications of packet loss: a timeout occurring and the receipt of duplicate ACKs. (We saw the latter in Section 21.5. If we are using a timeout as an indication of congestion, we can see the need for a good RTT algorithm, such as that described in Section 21.3.)

Congestion avoidance and slow start are independent algorithms with different objectives. But when congestion occurs we want to slow down the transmission rate of packets into the network, and then invoke slow start to get things going again. In practice they are implemented together.

Congestion avoidance and slow start require that two variables be maintained for each connection: a congestion window, cwnd, and a slow start threshold size , ssthresh. The combined algorithm operates as follows :

Initialization for a given connection sets cwnd to one segment and ssthresh to 65535 bytes.
The TCP output routine never sends more than the minimum of cwnd and the receiver's advertised window.

Congestion avoidance is flow control imposed by the sender, while the advertised window is flow control imposed by the receiver. The former is based on the sender's assessment of perceived network congestion; the latter is related to the amount of available buffer space at the receiver for this connection.
When congestion occurs (indicated by a timeout or the reception of duplicate ACKs), one-half of the current window size (the minimum of cwnd and the receiver's advertised window, but at least two segments) is saved in ssthresh. Additionally, if the congestion is indicated by a timeout, cwnd is set to one segment (i.e., slow start).
When new data is acknowledged by the other end, we increase cwnd, but the way it increases depends on whether we're performing slow start or congestion avoidance.

If cwnd is less than or equal to ssthresh, we're doing slow start; otherwise we're doing congestion avoidance. Slow start continues until we're halfway to where we were when congestion occurred (since we recorded half of the window size that got us into trouble in step 2), and then congestion avoidance takes over.

Slow start has cwnd start at one segment, and be incremented by one segment every time an ACK is received. As mentioned in Section 20.6, this opens the window exponentially: send one segment, then two, then four, and so on.

Congestion avoidance dictates that cwnd be incremented by 1 /cwnd each time an ACK is received. This is an additive increase, compared to slow start's exponential increase. We want to increase cwnd by at most one segment each round-trip time (regardless how many ACKs are received in that RTT), whereas slow start will increment cwnd by the number of ACKs received in a round-trip time.

All 4.3BSD releases and 4.4BSD incorrectly add a small fraction of the segment size (the segment size divided by 8) during congestion avoidance. This is wrong and should not be emulated in future releases [Floyd 1994]. Nevertheless, we show this term in future calculations, to arrive at the same answer as the (incorrect) implementation.

The 4.3BSD Tahoe release, described in [Leffler et al. 1989], performed slow start only if the other end was on a different network. This was changed with the 4.3BSD Reno release so that slow start is always performed.

Figure 21.8 is a visual description of slow start and congestion avoidance. We show cwnd and ssthresh in units of segments, but they're really maintained in bytes.

Figure 21.8. Visualization of slow start and congestion avoidance.

In this figure we assume that congestion occurred when cwnd had a value of 32 segments. ssthresh is then set to 16 segments and cwnd is set to 1 segment. One segment is then sent at time 0 and assuming its ACK is returned at time 1, cwnd is incremented to 2 segments. Two segments are then sent and assuming their ACKs return by time 2, cwnd is incremented to 4 segments (once for each ACK). This exponential increase continues until cwnd equals ssthresh, after 8 ACKs are received between times 3 and 4. From this point on the increase in cwnd is linear, with a maximum increase of one segment per round-trip time.

As we can see in this figure, the term "slow start" is not completely correct. It is a slower transmission of packets than what caused the congestion, but the rate of increase in the number of packets injected into the network increases during slow start. The rate of increase doesn't slow down until ssthresh is reached, when congestion avoidance takes over.