Back to index

Congestion Avoidance and Control

Van Jacobsen and Michael J. Karels

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):
        o 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.
        o 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):
        o round-trip time estimator essential core of timeout retransmits
        o 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.
        o exponential backoff (i.e. increase in retransmit timeout) is only
          known scheme that works in nearly all situations.
   * Congestion avoidance (adapting to the path):
        o 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.
        o In face of congestion queuing theory says queues back up
          exponentially. Thus packet loss says that windows should decrease
          exponentially.
        o 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).
        o 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

Fundamental performance issues for the internet today. TCP has handled many
orders of magnitude increase in load and scale of traffic, but of course
much voodoo has gone into TCP recently.

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.

  ------------------------------------------------------------------------
Back to index