Back to index
Congestion Avoidance and Control
Van Jacobsen and Michael J. Karels
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.
- 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:
- connection doesn't get to equilibrium
- sender injects a new packet before an old packet has
- 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
- 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
- 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
- exponential backoff (i.e. increase in retransmit
timeout) is only known scheme that works in nearly all
- 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
- 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,
- 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
(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!)
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.
- 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