Congestion Avoidance and Control

This classic paper introduces the bulk of the congestion avoidance and control mechanisms in TCP. Prior to this paper, TCP used a window only for flow control and transmitted packets gratuitously as long as the receiver had buffer space, leading to "congestion collapse" of the Internet (!). Its behavior in the face of losses was also bad, placing even more load on the network. Van Jacobson and Karels' work introduces two main ideas. The slow start algorithm increases the maximum window size exponentially until a packet is dropped and we are close to the path's bandwidth-delay product. The congestion avoidance algorithm performs a multiplicative decrease of the window size when a packet is lost and uses additive increase otherwise, a scheme which is argued to lead to fairness and stability. Underlying both of these is an improved RTT estimator which also estimates the standard deviation of the RTT in order to set timeouts appropriately. Finally, when multiple packet drops occur, indicating very heavy network load, the work suggests using exponential backoff for retramsissions, a very sensible policy also used in media access control.

One interesting aspect of this paper is the use of control theory and queueing theory to justify the algorithms, as in the previous paper. Although theory might not perfectly reflect reality, it provides a guide to what approaches to considerl. In this paper, the theory is also backed up by serious experiments using a real implementation. Also, unlike the previous paper, this one uses mathematics designed to deal with complex time-varying systems, such as the linear system theory result that motivates exponential backup.

This work was meant first and foremost to solve a real problem - collapse of the Internet. As a result, the main thing missing is some fine-tuning to get not just non-catastrophic, but really good behavior out of the system. The authors mention fairness as one area which is lacking and suggest that some work will have to be done at the gateways, which many future papers try to do. In addition, the recovery mechanism described in this paper overcompensates, aiming mostly to keep the Internet stable, so a lot of future work involved fast recovery, selective acknowledgements, etc.

One surprising and somewhat scary element of the paper is how it justifies constants chosen using measurements from the Arpanet at that time, such as the 1-packet increase per RTT and 0.5-decrease on congestion seen in Appendix D. Although these choices seem to have worked okay, it would have been more comforting to show a set of values that works in general, not just in the 1988 Arpanet.