Review: Congestion Avoidance and Control

The paper identifies poor protocol implementation as the cause for drop in throughput due to congestion. Therefore, to
reduce congestion, they propose new algorithms into 4BSD TCP with the idea that network stability can be achieved by
forcing the transport connection to obey a packet conservation principle (which states that a connection that is running
stably with a full window of data to transmit does not put a new packet into the network until an old packet leaves).
The paper list 3 ways packet conservation fails and addresses each one:
1) The connection may never reach equilibrium and hence slow-start should be used. In this algorithm:
        - Add a congestion window, cwnd, to the per_connection state.
        - Set the cwnd to one packet at start (or restart after packet loss).
        - Increase cwnd by one packet for each ack received.
        - Transmitter sends a minimum of the receiver advertised window size and cwnd.

2) A sender injects a new packet before an old one has exited, in other words, the equilibrium was reached but then
disturbed, most likely due to a fault in the sender retransmit timer. In order to deal with this, the paper suggests:
        - that to calculate the retransmit time out interval from the estimated round trip time (RTT) it is necessary to
estimate RTT variation rather than use a constant value to account for it.
        - to use an exponential back-off when a packet has to be re-transmitted more that once.

3) Resource limits along the path prevent the connection from reaching equilibrium, that is, a congested network and
insufficient buffer capacity at some point has led to packet loss. The paper identifies congestion avoidance as a two step
process:
        a) the network first signals to the end-points that congestion is occurring. Since packet loss is caused by
congestion and packet loss causes a timeout at the sender, this can be used as a signal to the end-points.
        b) the end-points then reduce utilization (but must also ensure that under-utilization does not occur). The paper
suggests dynamic window sizing using additive increase-multiplicative decrease algorithm to adapt to network changes:
                - Congestion window, cwnd, is decreased by 0.5 on any timeout (multiplicative decrease).
                - cwnd is increase by 1/cwnd when a new ack is received (additive increase).
                - Sender sends the minimum of the receiver advertised window and cwnd.

The paper concludes by saying that the only way to ensure fair allocation of the resources is to use gateway congestion
detection.

The usefulness of the ideas presented in the paper is evident from the fact that they are now a part of TCP.
Received on Mon Sep 25 2006 - 14:49:10 EDT