Congestion Avoidance and Control

Van Jacobson, 1988

Study prompted by drop from 32Kbps to 40Kbps between LBL (Lawrence Berkeley Labs) and UCB (UC Berkeley) in October 86.

Packet conservation – a new packet should not be put into the network until an old packet leaves.

Three ways packet conservation fails:

1) Connection never achieve equilibrium

2) Sender injects new packet before an old packet has exited

3) Equilibrium cannot be reached because of resource limit along the path

New algorithms:

1) Slow-start

Add connection window (cwnd) to per connection state.

When starting or restarting after packet loss, set cwnd = 1.

On each ack, cwnd += 1.

Send min (receive window, cwnd) packets.

This causes cwnd size to increase exponentially with acknowledgements.

2) Round-trip timing (RTT) estimate

Sender injects new packets into network based on RTT estimate. If RTT estimate is too low, many packets will get dropped, and there will be congestion. If RTT estimate is too high, there will be low bandwidth utilization.

Sub-problem 1: Bad RTT Variance estimation

TCP Spec suggests using low pass filter to estimate RTT, R.

R = alpha * Rprevious + (1 – alpha) *Rlast_measured

Retransmit timeout interval (RTO) for next packet then set: RTO = beta * R.

TCP Spec suggests beta = 2.. Authors find this setting results in unnecessary retransmits for loads > 30% where packets are simply delayed. The beta = 2 setting generates useless work for packets that will be eventually delivered at a time when the network is having trouble with useful work! Authors provide better estimator (not a brain-dead constanct) for RTT variance (based on mean deviation) in appendix of paper that can be implemented quickly using only integer operations and shifts.

Sub-problem 2: Retransmission Backoff

If a packet needs to be retransmitted more than once, what is the time delay between retransmits that should be used?

Exponential backoff is the only scheme that has any hope of working.

3) Congestion avoidance strategy

Sub-problem 1: Network must be able to signal transport endpoints that congestion is occurring (or is going to occur).

Packet loss can be due to damage (bits getting flipped; highly unlikely), or due to them getting dropped due to congestion (running out of buffer space in routers along the way; highly likely).

Once retransmit timers are fixed, and lost packets are not due to broken timers, we can be quite sure that lost packets are due to congestion.

Sub-problem 2: Endpoints must decrease utilization once they receive a congestion signal, and they should increase utilization if they do not receive the signal.

When the network is congested, buffer queue lengths will stare increasing exponentially. To compensate, windows should be cut exponentially to throttle back traffic at least as quickly as the queue lengths are growing.

If there is no congestion, window sizes should not be increased exponentially as this will create a highly unstable network (high oscillation; poor throughput; rush-hour effect)!

If there is no congestion, window sizes should be increased by small constant sizes.

Alg:

On any timeout, cwnd = cwnd / 2. (exponential backoff)

On each ack, cwnd = cwnd + 1/cwnd. (small additive increase)

Send min (receiver window size, cwnd) packets.

Combined slow-start / congestion avoidance alg: use ssthresh = ½ of window size on last timeout.

If (cwnd < ssthresh)

Cwnd += 1;

Else

Cwnd += 1/cwnd;