- Congestion vs. Flow Control)
- Flow control is an end-to-end property.
- Congestion is a property within the network.
- Three steps to happiness:
- Round-trip variance estimation.
- Exponential retransmit timer back-off.
- Slow-start.
- The other steps are
- Aggressive receiver acks.
- Dynamic window sizing.
- Clamped retransmit backoff.
- Fast retransmit.
- Packet concervation.
- Run the network to capacity, but not over or under.
- Packet conversion fails when the connection doesn't reache equilibrium or
the sender drives the connection past equilibrium.
- Self-clocking packet entry.
- A constant number of chips flowing through the network.
- How do you figure out the proper number of chips?
- The slow-start algorithm.
- Start or restart a congestion window to one packet.
- Increase the congestion window by one for each ack received.
- Send the smaller of the sender-side window or the congestion window.
- Slow-start effects.
- A quick ramp-up to maximum capacity.
- Proper round-trip estimates.
- A too-short round-trip estimates inject too many packets into the
network.
- Too long estimates are bad too, but don't cause congestion.
- Changes in the round-trip estimates vary with network load.
- Current estimates.
- R = alpha*R + (1 - alpha)M where
- M is the most recently measured rtt.
- R is the most recently estimated R.
- alpha is a history factor (0.9).
- After computation, the retransmit timeout is beta*R, where
beta is fudge for rtt variation.
- Improved estimates.
- Computer the error Err = m - a.
- Compute the new average a = a + g*Err.
- Compute the new variance v = v + g(|Err| - v).
- Congestion avoidance.
- Lost packets could mean either damage or congestion.
- Failed checksums or full buffers result in dropped packets.
- Loss due to corruption is small; think full buffers.
- Congestion signals.
- Reliable timers mean time-outs are due to full buffers.
- Congestion analysis.
- Take queue length per time period as a measure of network congestion.
- In uncongested networks, the queue length remains (relatively)
constant.
- Once congestion occurs, queue length grows as a function of past queue
length.
- This leads to exponential queue growth.
- Congestion adjustment.
- If congestion grows exponentially, load must be reduced exponentially.
- On congestion, reduce the window size by d < 1: Wi = dWi - 1.
- This is multiplicative reduction.
- Repeated multiplicative reductions are exponential in effect.
- Conjestion-adjust recovery.
- When is congestion cleared, and how should be window size be recovered?
- A multiplicative increase is not advisible, because it leads to
oscillations.
- Use a linear increase of u: Wi = Wi - 1 + u.
- Congestion avoidance.
- Set the congestion window to half on each timeout.
- On each new ack, increase the congestion window by 1/s, where
s is the current congestion window size.
- Don't confuse this with increasing the congestion window by one for
each ack in slow-start.
- Send the smaller of the send and congestion windows.
This page last modified on 14 November 2004.