A Binary Feedback Scheme for Congestion Avoidance in Computer Networks

One-line summary: If router's avg queue length over some interval is >1, set a sticky "congestion bit" in IP-level header of an ACK, which will cause source to modify its window size. How quickly to react to changes in congestion-bit state, and by how much, are parameters arrived at by trial and error. Averaging interval is adaptively measured by observing repeated "busy+idle" cycles at each router. Resulting algorithm is fair, adapts quickly, and finds an efficient and stable operating point.

Overview/Main Points

• Goal: transmit "congestion notifications" to users when routers become congested, without using additional bandwidth.
• Optimization criteria:
  • Power = (T^a)/R, where T=throughput, R=response time (latency), and 0<a<1. Can be measured at any router, or for the whole system. For a=1, power is maximized at the knee of the delay curve (i.e. right before the network falls off the "congestion collapse cliff").
  • Efficiency = Power/(Power at knee when a=1), i.e. power normalized to optimum.
  • Fairness: all users sharing a path achieve equal window sizes of W=Throughput/Rtt.
• Mechanism: congestion indication sticky bit in network level packet header. Bit is set based on average queue length in router, since this metric is not very sensitive to distribution of service times.
• Dangers of using instantaneous queue length instead of average:
  • Want to provide some built-in hysteresis (Surprise! Routers don't need to use separate hysteresis to determine when to set/unset the bit if you use average queue length)
  • By the time a packet reaches user, congestion info in it may not be relevant if it was based solely on instantaneous queue size
  • Some users may (unfairly) get the bit set while others on the same link don't.
• Picking an averaging interval and averaging method:
  • Congestion-bit generation results in fair allocation when averaging interval is close to roundtrip delay seen by users.
  • Same result whether "simple" or weighted-moving average used.
  • Solution: pick interval adaptively at each router, by detecting "busy+idle" intervals ("regeneration cycles") and computing average queue length by integrating under the time vs. queue length curve and dividing by the time.
• How often to change user window size based on congestion notification:
  • If you do it after every packet, wild instability.
  • If source changes window size to Wc, need to wait Wc+1 acks to see any congestion-related result of the change. So, keep 2 "cycles" worth of state: If Wp and Wc are window sizes before and after a source-generated window size change, wait for Wp+Wc packets to be ack'd before thinking about another window size change.
• Need multiplicative decrease for additive increase, since additive decrease preserves an existing unfair condition.
• Performance: generally adapts well to network changes, achieves fairness, converges to efficient operating point. Some of the parameters had to be tweaked by trial and error to get "good" values (i.e. the additive/multiplicative constants).
• Other cases:
  • arbitary initial window sizes: all users soon converge to fair (equal) window sizes that sum to network capacity.
  • source-bottlenecked networks: ensure that window size is not increased if source hasn't been able to implement a previously-generated window size increase.
  • overloaded network: as load quiets down, remaining users see congestion bit turned off, and their window sizes go back up.
  • Note - the windows do appear to oscillate quite a bit for small numbers of users.

Relevance

Flaws

• Hysteresis argument seems shaky. Maybe instability is avoided because the system is additive increase/multiplicative decrease. For small numbers of users on unloaded network, fig 13 seems to show some nontrivial oscillation, indicating that maybe some kind of additional hysteresis would be useful after all.
• If traffic is self-similar and bursty, how do you detect the "regeneration cycles" (busy+idle interval)?
• All routers must be modified to be able to generate the congestion bit. Jacobson proposes deducing congestion from timeouts instead, since that info is already available to all packet networks.