Congestion Control on the Internet

Congestion control on the Internet is implemented by the transport protocols layered above IP. It is a simple matter to explain the congestion control functions of UDP ”there are none unless they are implemented by the applications layered above UDP ”but TCP has an extensive set of algorithms for congestion control. ^{29 , 81 , 112}

TCP is an example of a sliding window protocol. The source includes sequence numbers with each data packet it sends, and these are echoed back to it in ACK (positive acknowledgment) packets from the receiver. The simplest sliding window protocol requires each packet to be acknowledged immediately, before the next can be sent, as shown in Figure 10.2. This is known as a stop-and-wait protocol because the sender must wait for the acknowledgment before it can send the next packet. Clearly, a stop-and-wait protocol provides flow control ”preventing the sender from overrunning the receiver ”but it also hinders performance, especially if the round-trip time between sender and receiver is long.

Figure 10.2. A Simple Stop-and-Wait Protocol

Use of a larger window allows more than one packet to be sent before an ACK is received. Each TCP ACK packet includes a receiver window, indicating to the source how many octets of data can be accepted at any time, and the highest continuous sequence number from the data packets. The source is allowed to send enough packets to fill the receive window, before it receives an ACK. As ACKs come in, the receive window slides along, allowing more data to be sent. This process is shown in Figure 10.3, in which the window allows three outstanding packets. The larger receive window improves performance compared to a simple stop-and-wait protocol.

Figure 10.3. Use of a Sliding Receiver Window

In addition to the receive window, TCP senders implement a congestion window. The congestion window is sized according to an estimate of the network capacity, and it prevents the sender from overrunning the network (that is, it provides congestion control). At any time, the sender can send enough packets to fill the minimum of the congestion window and the receive window.

The congestion window starts at the size of one packet. It increases according to either the slow-start algorithm or the congestion avoidance algorithm, as long as no loss occurs. New connections initially use slow start and then transition to congestion avoidance .

In slow-start mode, the congestion window increases by the size of a packet with each ACK received. As a result, the sender gradually builds up to the full rate the network can handle, as shown in Figure 10.4. Slow start continues until a packet is lost, or until the slow-start threshold is exceeded.

Figure 10.4. TCP Slow Start

In congestion avoidance mode, the congestion window is increased by the size of one packet per round-trip time (instead of one per ACK). The result is linear growth of the congestion window, an additive increase in the sending rate.

TCP connections increase their sending rate according to one of these two algorithms until a packet is lost. Loss of a packet indicates that the network capacity has been reached and momentary congestion has occurred. The sender can detect congestion in two ways: by a timeout or by receipt of a triple duplicate ACK.

If no ACK is received for an extended time after data has been sent, data is assumed to have been lost. This is a timeout situation: it can occur when the last packet in the receive window is lost, or if there is a (temporary) failure that prevents packets from reaching their destination. When a timeout occurs, the sender sets the slow-start threshold to be one-half the number of packets in flight, or two packets, whichever is larger. It then sets the congestion window to the size of one packet, and enters slow start. The slow-start process continues until the slow-start threshold is exceeded, when the sender enters congestion avoidance mode. Prolonged timeout will cause the sender to give up, breaking the connection.

The other way a sender can detect congestion is by the presence of duplicate ACK packets, which occur when a data packet is lost or reordered (see Figure 10.5). The ACK packets contain the highest continuous sequence number received, so if a data packet is lost, the following ACK packets will contain the sequence number before the loss, until the missing packet is retransmitted. A duplicate ACK will also be generated if a packet is reordered, but in this case the ACK sequence returns to normal when the reordered packet finally arrives.

Figure 10.5. Generation of Duplicate ACK Packets

If the sender receives three duplicate ACK packets, it assumes that a packet was lost because of congestion. The sender responds by setting its congestion window and slow-start threshold to one-half the number of packets in flight, or two packets, whichever is larger. It then retransmits the lost packet and enters congestion avoidance mode.

The combination of these algorithms gives TCP connection throughput as shown in Figure 10.6. The characteristic is an additive-increase, multiplicative-decrease (AIMD) sawtooth pattern, with large variations in throughput over short time intervals.

Figure 10.6. Variation in the TCP Sending Rate

This rapid variation in throughput is actually the key behavior that makes a system using TCP stable. The multiplicative decrease ensures a rapid response to congestion, preventing congestion collapse; additive increase, probing for the maximum possible throughput, ensures that the network capacity is fully utilized.

There have been many studies of the variation in TCP throughput, and of the behavior of competing TCP flows. ^{73 , 81 , 94 , 95 , 124} These studies have shown that competing flows get approximately equal shares of the capacity on average, although the jagged throughput profile means that their instantaneous share of the bandwidth is unlikely to be fair.

There is one systematic unfairness in TCP: Because the algorithm responds to feedback, connections with lower round-trip times return feedback faster and therefore work better. Thus, connections with longer network round-trip time systematically receive a lower average share of the network capacity.