Back to index
A Binary Feedback Scheme for Congestion Avoidance in Computer Networks
K.K. Ramakrishnan and Raj Jain, DEC
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.
- Goal: transmit "congestion notifications" to users when routers
become congested, without using additional bandwidth.
- Optimization criteria:
- Power = (Ta)/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
- 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
- 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
- Same result whether "simple" or weighted-moving average
- 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
- 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
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
- Note - the windows do appear to oscillate quite a bit for
small numbers of users.
Exploration of congestion as an "end to end visible property" of
connectionless networks, and of a way to aggregate intermediate-router
congestion information (though just 1 bit) by piggybacking on ACKs.
- 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.
Back to index