Congestion Avoidance and Control

V. Jacobson, M. Karels, "Congestion Avoidance and Control," ACM SIGCOMM Conference, (August 1988).

One line summary: This paper describes several important algorithms for congestion control in TCP, including slow-start, exponential backoff, multiplicative decrease additive increase, and RTT variance estimation; the paper also provides results that demonstrate that implementations of TCP using the algorithms described in the paper are better than older implementations.

Summary

The authors note that due to an explosive increase in size, computer networks have increasingly experienced congestion problems. Seven algorithms added to TCP are meant to help deal with this: round-trip time (RTT) variance estimation, exponential backoff, slow start, aggressive receiver ACK policy, dynamic window sizing, Karn’s algorithm, and fast retransmit. The authors describe the first five of these algorithms. According to the authors, these algorithms stem from the observation that a TCP connection should obey a “conservation of packets” principle, which basically states that for a connection in equilibrium, the sender should not place a new packet into the connection until an old packet leaves. There are three instances in which this principle will not be upheld: when the connection doesn’t initially reach equilibrium, when after equilibrium is reached, a new packet is sent before an old packet leaves, and when resource limitations along the connection path make equilibrium unattainable. The authors address each of these in turn.

The first failure occurs when a connection is being started or restarted. The authors note that a TCP connection is a self-clocking system, which help makes it stable, however, this also means that in order to get packets flowing there must be ACKS to clock them out, but to get ACKS there must be packets flowing. The authors thus describe the slow-start algorithm as a method for “starting the clock” and gradually increasing the number of packets flowing. The slow-start algorithm is as follows: For each connection, store a variable called the congestion window that will be used to determine the number of packets to send. When starting or restarting, set the congestion window to 1 packet. Every time a packet is acknowledged, increase the congestion window by 1. To select how many packets to send at a time, choose the minimum of the congestion window and the receiver’s advertised window. The result of this algorithm is that if no packets are lost or delayed, the congestion window doubles every RTT, and never will the sender send packets at a rate faster than twice the maximum send rate on the connection path. The authors find that this algorithm greatly decreases the number of retransmits and increases effective bandwidth.

The authors next explain that the second failure must be due to a sender’s faulty retransmit timer. This timer should estimate the RTT, which increases when load increases, in order to determine when a packet should be retransmitted, but one mistake in doing this is not estimating the variance in the RTT. The authors present an easy-to-calculate method for estimating the variance in their appendix. Another mistake is not choosing the correct backoff after a packet is retransmitted. The authors argue that only exponential backoff schemes have any hope of working in the general case. The authors demonstrate that a timer that estimates RTT using their method more accurately approximates RTT than the method previously used in TCP.

Lastly, the authors point out that if the timers are doing a good job of estimating RTT, then a timeout probably indicates a lost packet instead of a broken timer. Lost packets are typically a sign that the network is congested, causing connections to encounter resource limits, which is the third failure case. Connection endpoints must have a way of responding to congestion such that they decrease the amount they send when the network is congested and increase the amount they send when it is possible to do so, in order to achieve the proper utilization of network resources while avoiding congestion. To this end, the authors introduce a multiplicative decrease additive increase algorithm. The reason the decrease happens much faster than the increase is because it is easy for the network to become congested and much harder for it to become uncongested. The algorithm works as follows: On a timeout, the congestion window is set to half of the current congestion window size (multiplicative decrease). For each packet acknowledgement received thereafter, increase the congestion window (cwnd) by 1/cwnd (additive increase). Then when choosing the number of packets to send, choose the minimum of the congestion window and the receiver’s advertised window. The authors note that this does not include slow-start because they are two entirely different algorithms, but they should be implemented together, which is done usually by having separate slow-start and congestion avoidance phases. The authors show that their congestion avoidance approach results in fewer retransmits and higher bandwidth utilization.

Critique

The algorithms the authors propose in this paper later made it into newer implementations of TCP, so in that sense, they were very successful. Their results demonstrate that their algorithms were generally an improvement over previous implementations. However, as the authors point out, there are still improvements to be made. For instance, none of their solutions ensure fair sharing of network bandwidth, so they propose this as an area of future work. (Then again, according to Kurose and Ross, the multiplicative decrease additive increase algorithm was later shown to converge to provide equal sharing of bandwidth by Chui in 1989, a year after this paper was published, so perhaps it was the case that this work did not need to be done after all.)

Also, in certain situations, TCP’s exponential backoff and congestion avoidance can cause serious performance problems. Regular TCP can be improved for high-performance networks and there are apparently some extensions to TCP for this. Investigation reveals that some of the later changes to TCP’s congestion avoidance algorithms were suggested in order to allow it to more appropriately handle networks with LFNs and high-latency links. Lastly, some of the assumptions that the authors make about the network aren’t necessarily always valid. For instance, the authors state that packets are lost due to either network congestion or packet damage, but that the latter occurs so infrequently that it is safe to assume that a timeout is almost always a sign of network congestion. However, in wireless networks, this assumption does not generally hold, so TCP’s congestion avoidance can in this case result in link underutilization. Thus, a modified mechanism that takes this into account would be appropriate for TCP in wireless networks.

I thought this paper was good, and obviously the algorithms described in the paper are important, as they are now an integral part of TCP. Congestion control is a very important service, without which the Internet could not function well, if at all. I was somewhat confused as to how much of the algorithms suggested were original contributions, since some of the footnotes seem to indicate very similar algorithms had first been suggested elsewhere. I found that the authors’ tendency to reference a handful of papers I hadn’t read without really explaining briefly what was in those papers inhibited my understanding. And just as a matter of personal taste, I did not like it that so much information was crammed into the footnotes and appendices; to me this made the paper less readable, although aside from this it was well-written.

[EDIT: From my comment about fairness as examined by Chui it's probably clear that I read this paper before I read the other one. ;-) ]