Congestion Avoidance and Control

One-line summary: Seven new algorithms were put into TCP to make sure that it adhered to the "packet conservation" principle; these congestion avoidance and control algorithms are motivated and described.

Overview/Main Points

• Motivation: factor of 1000 throughput degradation observed on link between LBL and UCB in 86; poor TCP congestion control techniques were identified as the cause.
• Packet conservation principle: for stability in a network (especially in the face of congestion), a host in equilibrium should only inject one packet into the network for every packet removed from the network, leading to "self-pacing". Failures to obey this principle can occur for three reasons:
  1. connection doesn't get to equilibrium
  2. sender injects a new packet before an old packet has exited
  3. equilibrium can't be reached because of resource limits along the path.
• Slow-start (getting to equilibrium):
  • mechanism: add a congestion window (cwnd) to the per connection state. When starting or restarting after a loss, set cwnd to one packet. On each ack for new data, increase cwnd by one packet. When sending, send the minimum of the receiver's advertised window and cwnd.
  • slow start increases congestion window slowly but exponentially until the sender hits the receiver's advertised window size. Eliminates huge bursts of data into the network when a new connection starts up.
• Round-trip timing (conservation at equilibrium):
  • round-trip time estimator essential core of timeout retransmits
  • round-trip time and variation in round-trip time increase quickly with load. Setting the timeout to (variation estimate * RTT estimate) is much better than using (constant * RTT estimate); eliminates wasted bandwidth when load gets high and delayed packets are retransmitted.
  • exponential backoff (i.e. increase in retransmit timeout) is only known scheme that works in nearly all situations.
• Congestion avoidance (adapting to the path):
  • If timers are sensible, then timeout indicates lost packet. Lost packet happen either because of packet corruption or congestion causing a router queue backup and packet drop. Packet corruption extremely rare (no longer true in wireless), thus timeout implies congestion.
  • In face of congestion queuing theory says queues back up exponentially. Thus packet loss says that windows should decrease exponentially.
  • If no congestion, window sizes need to increase (as no indication from network that there is no congestion). Small, linear increase in window size is best (exponential increase will lead to oscillations).
  • mechanism: on any timeout, set cwnd to half the current window size. On each ack for new data, increase cwnd by 1/cwnd. Of course, slow-start must be used after congestion control kicks in. Slow-start and congestion control are separate mechanisms, however.
• Gateways and fairness: it is suggested that since gateways/routers are where multiple TCP sessions converge, this is the only place to ensure fairness. Gateways could drop packets from overly active connections to enforce this fairness. (Sounds like a pretty wild-eyed idea, and many details are totally ignored.) (Armando sez: I think Packeteer's commercial product does something very much like this, to allow net administrators to enforce "selective fairness" among different classes of users coming into a server!)

Relevance

Van Jacobson is an excellent research. He brings the rigour and formalism of science to an engineering practise, resulting in great benefit.

Flaws

• The algorithms have much "black magic"; it is fortunate that the TCP engineers are competent shaman.
• Slow-start is extremely expensive for short-lived connections.