CS262A Reading Summary 28

Congestio Avoidance and Control

V. Jacobson and M. J. Karels
Summary by Feng Zhou
11/7/2002

1. Slow start. Old naive method of using the advertised receiver window as the initial sender window causes extremely low throughput under heavy load. The Slow Start algorithm is proposed to solve this problem. Without knowledge of the maximal usable bandwidth between the sender and the receiver, Slow-Start gradually grows the sender window (cwnd) exponentially until the system reaches equilibrium.
2. Round-trip timing. Timeout is used to detect possible packet lost. To be able to do that, accurate estimation of RTT and its deviation is needed. A fast algorithm, only using integer arithmetic, is proposed to calculate the mean of RTT and its mean deviation. It is also shown that mean deviation, which is easy to calculate, is a good estimation of standard deviation.
3. Congestion avoidance. The authors claim that the main reason for packet loss on Internet is congestion, not packet damage. Based on this assumption, packet loss can be used as an indication of congestion. Thus in the new TCP implementation, whenever packet loss happens, the congestion window is shrinked in half to alleviate the possible congestion. Before that, the congestion window is incremented by a constant size each time an ACK is received, which corresponds to equilibrium..

Using timeout to detect packet loss isn't always a good method. On links with large RTTs, the sender can do nothing with the possibily-lost packet before 2 times RTT passes. Fast-retransmission, in which the receiver gives the sender hints about possible packet lost, can be a better choice then.