tcp: slow start, control avoidance, fast retra/fast recover

TCP Congestion Handling and Congestion Avoidance Algorithms
(Page 2 of 3)

TCP Congestion Handling Mechanisms

We must then decide what to do with this information. The main TCP standard, RFC 793, includes very little information about TCP congestion handling issues. That is because early versions of TCP based solely on this standard didn't include congestion handling measures—it was problems with these early implementations that lead to the discovery that congestion was an important issue. The measures used in modern devices were developed over the years, and eventually documented in RFC 2001, TCP Slow Start, Congestion Avoidance, Fast Retransmit, and Fast Recovery Algorithms.

Here is a simplified description of each of the four techniques that comprise the name of this standard.
Slow Start

In the original implementation of TCP, as soon as a connection was established between two devices, they could each go “hog wild”, sending segments as fast as they liked as long as there was room in the other device's receive window. In a busy internetwork the sudden appearance of a large amount of new traffic could exacerbate any existing congestion.

To alleviate this, modern TCP devices are restrained in the rate at which they initially send segments. Each sender is at first restricted to sending only an amount of data equal to one “full-sized” segment—that is, equal to the MSS value for the connection. Each time an acknowledgment is received, the amount of data the device can send is increased by the size of another full-sized segment. Thus, the device “starts slow” in terms of how much data it can send, with the amount it sends increasing until either the full window size is reached or congestion is detected on the link. In the latter case, the congestion avoidance feature, described below, is used.
Congestion Avoidance

When potential congestion is detected on a TCP link, a device responds by throttling back the rate at which it sends segments. A special algorithm is used that allows the device to drop the rate at which segments are sent quickly when congestion occurs. The device then uses the Slow Start algorithm just above to gradually increase the transmission rate back up again to try to maximize throughput without congestion occurring again.




TCP Congestion Handling and Congestion Avoidance Algorithms
(Page 3 of 3)

Fast Retransmit

We’ve already seen in our look at TCP segment retransmission that when segments are received by a device out of order (meaning, non-contiguously), the recipient will only acknowledge the ones received contiguously. The Acknowledgment Number will specify the sequence number of the byte it expects to receive next. So, in the example given in that topic, Segment #1 and #2 were acknowledged while #4 was not, because #3 was not received.

It is possible for a TCP device to in fact respond with an acknowledgment when it receives an out-of-order segment, simply “reiterating” that it is stuck waiting for a particular byte number. So, when the client in that example receives Segment #4 and not Segment #3, it could send back an Acknowledgment saying “I am expecting the first byte of Segment #3 next”.

Now, suppose this happens over and over. The server, not realizing that Segment #3 was lost, sends Segment #5, #6 and so on. Each time one is received, the client sends back an acknowledgment specifying the first byte number of Segment #3. Eventually, the server can reasonably conclude that Segment #3 is lost, even if its retransmission timer has not expired.

The Fast Retransmit feature dictates that if three or more of these acknowledgments are received, all saying “I want the segment starting with byte #N”, then it's probable that the segment starting with byte #N has been lost, usually because it was dropped due to congestion. In this case, the device will immediately retransmit the missing segment without going through the normal retransmission queue process. This improves performance by eliminating delays that would suspend effective data flow on the link.
Fast Recovery

When Fast Retransmit is used to re-send a lost segment, the device using it performs Congestion Avoidance, but does not use Slow Start to increase the transmission rate back up again. The rationale for this is that since multiple ACKs were received by the sender all indicating receipt of out-of-order segments, this indicates that several segments have already been removed from the flow of segments between the two devices. For efficiency reasons, then, the transmission rate can be increased more quickly than when congestion occurs in other ways. This improves performance compared to using the regular Congestion Avoidance algorithm after Fast Retransmit.
Relationship of Congestion Handling Mechanisms

In practice, these features are all related to each other. Slow Start and Congestion Avoidance are distinct algorithms but are implemented using a single mechanism, involving the definition of a Congestion Window that limits the size of transmissions and whose size is increased or decreased depending on congestion levels. Fast Retransmit and Fast Recovery are implemented as changes to the mechanism that implements Slow Start and Congestion Avoidance.

I realize that this is somewhat cryptic; congestion handling is a rather complex process. If you want to learn more, RFC 2001 contains the technical details, showing how each of the algorithms is implemented in each device. I have specifically omitted those details from this topic since I feel my summary descriptions are already complicated enough, and my goal was simply to help you get a feel for how congestion is handled in TCP in general terms.