• The four algorithms, Slow Start, Congestion Avoidance, Fast Retransmit and Fast Recovery are described below.

Slow Start

• Slow Start, a requirement for TCP software implementations is a mechanism used by the sender to control the transmission rate, otherwise known as sender-based flow control.

• This is accomplished through the return rate of acknowledgements from the receiver.

• In other words, the rate of acknowledgements returned by the receiver determine the rate at which the sender can transmit data.

• When a TCP connection first begins, the Slow Start algorithm initializes a congestion window to one segment, which is the maximum segment size (MSS) initialized by the receiver during the connection establishment phase.

• When acknowledgements are returned by the receiver, the congestion window increases by one segment for each acknowledgement returned.

• Thus, the sender can transmit the minimum of the congestion window and the advertised window of the receiver, which is simply called the transmission window.

• Slow Start is actually not very slow when the network is not congested and network response time is good.

• For example, the first successful transmission and acknowledgement of a TCP segment increases the window to two segments.

• After successful transmission of these two segments and acknowledgements completes, the window is increased to four segments.

• Then eight segments, then sixteen segments and so on, doubling from there on out up to the maximum window size advertised by the receiver or until congestion finally does occur.

• At some point the congestion window may become too large for the network or network conditions may change such that packets may be dropped.

• Packets lost will trigger a timeout at the sender. When this happens, the sender goes into congestion avoidance mode as described in the next section.

Congestion Avoidance

• During the initial data transfer phase of a TCP connection the Slow Start algorithm is used.

• However, there may be a point during Slow Start that the network is forced to drop one or more packets due to overload or congestion.

• If this happens, Congestion Avoidance is used to slow the transmission rate. However, Slow Start is used in conjunction with Congestion Avoidance as the means to get the data transfer going again so it doesn’t slow down and stay slow.

• In the Congestion Avoidance algorithm a retransmission timer expiring or the reception of duplicate ACKs can implicitly signal the sender that a network congestion situation is occurring.

• The sender immediately sets its transmission window to one half of the current window size (the minimum of the congestion window and the receiver’s advertised window size), but to at least two segments.

• If congestion was indicated by a timeout, the congestion window is reset to one segment, which automatically puts the sender into Slow Start mode.

• If congestion was indicated by duplicate ACKs, the Fast Retransmit and Fast Recovery algorithms are invoked (see below).

• As data is received during Congestion Avoidance, the congestion window is increased.

• However, Slow Start is only used up to the halfway point where congestion originally occurred.

• This halfway point was recorded earlier as the new transmission window.

• After this halfway point, the congestion window is increased by one segment for all segments in the transmission window that are acknowledged.

• This mechanism will force the sender to more slowly grow its transmission rate, as it will approach the point where congestion had previously been detected.

Fast Retransmit

• When a duplicate ACK is received, the sender does not know if it is because a TCP segment was lost or simply that a segment was delayed and received out of order at the receiver.

• If the receiver can re-order segments, it should not be long before the receiver sends the latest expected acknowledgement.

• Typically no more than one or two duplicate ACKs should be received when simple out of order conditions exist.

• If however more than two duplicate ACKs are received by the sender, it is a strong indication that at least one segment has been lost.

• The TCP sender will assume enough time has lapsed for all segments to be properly re-ordered by the fact that the receiver had enough time to send three duplicate ACKs.

• When three or more duplicate ACKs are received, the sender does not even wait for a retransmission timer to expire before retransmitting the segment (as indicated by the position of the duplicate ACK in the byte stream). This process is called the Fast Retransmit algorithm .

• Immediately following Fast Retransmit is the Fast Recovery algorithm.

Fast Recovery

• Since the Fast Retransmit algorithm is used when duplicate ACKs are being received, the TCP sender has implicit knowledge that there is data still flowing to the receiver. Why?

• The reason is because duplicate ACKs can only be generated when a segment is received.

• This is a strong indication that serious network congestion may not exist and that the lost segment was a rare event.

• So instead of reducing the flow of data abruptly by going all the way into Slow Start, the sender only enters Congestion Avoidance mode.

• Rather than start at a window of one segment as in Slow Start mode, the sender resumes transmission with a larger window, incrementing as if in Congestion Avoidance mode.

• This allows for higher throughput under the condition of only moderate congestion .

• To summarize this section of the paper, figure below depicts what a typical TCP data transfer phase using TCP congestion control might look like.

• Notice the periods of exponential window size increase, linear increase and drop-off.

• Each of these scenarios depicts the sender’s response to implicit or explicit signals it receives about network conditions.