Monday, September 8, 2008

Congestion Avoidance and Control

Following the major collapse of ARPANET due to congestion, several new algorithms were developed to further prevent congestion instead of congestion control. Particularly, the paper discusses RTT estimation, exponential backoff, slow-start, aggressive receiver acking, and dynamic window sizing. The paper points out that the main cause of the collapse was not due to errors in design, but more due to mis-steps in implementation.

The paper first introduces slow start, which focuses on getting to equilibrium. The idea is to increase the packet window based on the number of acks that have been received. Then once the upper limit is reached, the system will try to maintain this level of transfer, partially by use of the RTT estimation. In order to maintain this equilibrium, the new implementation utilizes congestion avoidance to adapt to the capacity of the network.

This scheme utilizes the same principles from the previous paper, mainly additive increase and multiplicative decrease by increasing cwnd by 1/cwnd on every ack (additive increase), and halving cwind on any loss (multiplicative decrease) in addition to exponential backoff. However, it does not use the suggested additional "congestion bit", but rather utilizes existing signals and packet loss to determine congestion.

This paper was much more well-rounded than the previous paper, and discussed more of the details of implementation and its direct application. The papers both share many of the same goals, this paper simply looks at all aspects of a tcp transaction and determines what needs to be done at each stage to achieve its goals.

Having the appendix for the RTT calculation seemed ineffectual - I would have preferred that the implementation details were placed into the body of the paper at the appropriate stage. Even though it may not have flowed as elegantly, it would have given a more complete view of the improvements.

This is really some of the early work with congestion avoidance over congestion control, and clearly this was only meant to be a starting point. Nevertheless, many of the techniques used today remain the same as presented in this paper, as they have stood the test of time. Perhaps to implement further congestion avoidance would require additions to the protocol instead of additions to the implementation.

No comments: