From: Karthik Gopalratnam (karthikg@cs.washington.edu)
Date: Mon Oct 18 2004 - 01:16:16 PDT
Congestion Avoidance and Control - van Jacobson
This is a seminal paper on TCP congestion control that identifies the
situations under which congestion occurs in the internet, and proposes
mechanisms that the end host can incorporate into TCP in order to prevent
and recover from congestion.
All of the congestion handling mechanisms outlined in this paper are
motivated by the "Conservation of packets" principle, which views the
network as fluid flow in a set of pipes. Under this view, the author
identifies the three conditions under which packet flow is *NOT* conserved,
and proposes mechanisms that aim to counteract these conditions.
The first condition is not being able to get to equilibrium, for which the
author proposes using a congestion window that gets reset to a single packet
upon encountering a loss, and thereby slowly ramping up flow till
equilibrium is reached. This is the "slow start" policy.
The author correctly identifies that any congestion avoidance can only be
inferred from the loss of a packet, which is a really crucial point, since
that places the onus of congestion control on the end hosts, thereby
following the end-to-end design. In order for the end hosts to detect a lost
packet, they are heavily dependent on the mechanism used to estimate round
trip times - RTTs. The mechanism provided here is te exponential back off
scheme, which is based on estimating the variance of the RTTs, and
retransmitting after an "exponential" wait.
The third mechanism here is for congestion avoidance. This is based on
the fact that when the network is congested and the queue lengths are
increasing exponentially, the only way to stabilize is by rolling back the
sources at least as fast as the queues are growing. This is the
multiplicative decrease scheme. However, the authors show that in order to
optimize bandwidth utiliaztion and at the same time not overestimate
available bandwidth, an additive increase algorithm is needed. This
completes the design of congestion handling mechanisms for TCP.
These mechanisms have a number of advantages. THe first is that they are
relatively easy to deploy - as the authors show, they can essentially be
done by adding a few lines of code to existing implementations. Also, since
they are based on a rigorous mathematical theory of dynamical systems, the
schemes here are provably optimal under a number of different conditions,
and their effectivenesss have been demonstrated even in the present
internet. All in all a significant miletone paper in the evoluton of the
internet.
This archive was generated by hypermail 2.1.6 : Mon Oct 18 2004 - 01:16:17 PDT