3 ADAPTING TO THE PATH: CONGESTION AVOIDANCE A congestion avoidance strategy, such as the one proposed in [15], will have two components: The network must be able to signal the transport endpoints that congestion is occurring (or about to occur). And the endpoints must have a policy that decreases utilization if this signal is received and increases utilization if the signal isnt received If packet loss is(almost)al ways due to congestion and if a timeout is(almost)always due to a lost packet, we have a good candidate for the ' network is congested signal. Partic ularly since this signal is delivered automatically by all existing networks, without special modification(as opposed to [15] which requires a new bit in the packet headers and a mod- ification to all existing gateways to set this bit) The other part of a congestion avoidance strategy, the endnode action, is almost identical in the DEC/ISO scheme and our TCP and follows directly from a first-order time-series model of the network: Say network load is measured by average queue length over fixed ntervals of some appropriate length(something near the round trip time). If Li is the load at interval i, an uncongested network can be modeled by saying Li changes slowly compared to the sampling time. I.e (N constant). If the network is subject to congestion, this zeroth order model breaks down The average queue length becomes the sum of two terms, the n above that accounts for the average arrival rate of new traffic and intrinsic delay, and a new term that accounts for the fraction of traffic left over from the last time interval and the effect of this left-over traffic (e.g, induced retransmits) These are the first two terms in a Taylor series expansion of L((). There is reason to believe one might eventually need a three term, second order model, but not until the Internet has When the network is congested, y must be large and the queue lengths will start in creasing exponentially. The system will stabilize only if the traffic sources throttle back at least as quickly as the queues are growing. Since a source controls load in a window-based protocol by adjusting the size of the window, w, we end up with the sender policy On congestion W=dW-1(d<1) I.e., a multiplicative decrease of the window size(which becomes an exponential decrease over time if the congestion persists) threshold is about 5%. At this high loss rate, the empty window effect described above has already degraded throughput by 44% and the additional degradation from the congestion avoidance window shrinking is the least We are concerned that the congestion control noise sensitivity is quadratic in w but it will take at least another generation of network evolution to reach window sizes where this will be significant. If experience shows this sensitivity to be a liability, a trivial modification to the algorithm makes it linear in w. An in-progress paper explores this subject in detail 7 This is not an accident: We copied Jain s scheme after hearing his presentation at [10]and realizing that the scheme was. in a sense. universal &See any good control theory text for the relationship between a system model and admissible controls for that system. A nice introduction appears in [21], chap. 8 I.e., the system behaves like Li N yLi-I, a difference equation with the solution Ln=r"Lo3 ADAPTING TO THE PATH: CONGESTION AVOIDANCE 9 A ‘congestion avoidance’ strategy, such as the one proposed in [15], will have two components: The network must be able to signal the transport endpoints that congestion is occurring (or about to occur). And the endpoints must have a policy that decreases utilization if this signal is received and increases utilization if the signal isn’t received. If packet loss is (almost) always due to congestion and if a timeout is (almost) always due to a lost packet, we have a good candidate for the ‘network is congested’ signal. Partic￾ularly since this signal is delivered automatically by all existing networks, without special modification (as opposed to [15] which requires a new bit in the packet headers and a mod￾ification to all existing gateways to set this bit). The other part of a congestion avoidance strategy, the endnode action, is almost identical in the DEC/ISO scheme and our TCP7 and follows directly from a first-order time-series model of the network:8 Say network load is measured by average queue length over fixed intervals of some appropriate length (something near the round trip time). If Li is the load at interval i, an uncongested network can be modeled by saying Li changes slowly compared to the sampling time. I.e., Li = N (N constant). If the network is subject to congestion, this zeroth order model breaks down. The average queue length becomes the sum of two terms, the N above that accounts for the average arrival rate of new traffic and intrinsic delay, and a new term that accounts for the fraction of traffic left over from the last time interval and the effect of this left-over traffic (e.g., induced retransmits): Li = N +γLi−1 (These are the first two terms in a Taylor series expansion of L(t). There is reason to believe one might eventually need a three term, second order model, but not until the Internet has grown substantially.) When the network is congested, γ must be large and the queue lengths will start in￾creasing exponentially.9 The system will stabilize only if the traffic sources throttle back at least as quickly as the queues are growing. Since a source controls load in a window-based protocol by adjusting the size of the window, W, we end up with the sender policy On congestion: Wi = dWi−1 (d < 1) I.e., a multiplicative decrease of the window size (which becomes an exponential decrease over time if the congestion persists). threshold is about 5%. At this high loss rate, the empty window effect described above has already degraded throughput by 44% and the additional degradation from the congestion avoidance window shrinking is the least of one’s problems. We are concerned that the congestion control noise sensitivity is quadratic in w but it will take at least another generation of network evolution to reach window sizes where this will be significant. If experience shows this sensitivity to be a liability, a trivial modification to the algorithm makes it linear in w. An in-progress paper explores this subject in detail. 7This is not an accident: We copied Jain’s scheme after hearing his presentation at [10] and realizing that the scheme was, in a sense, universal. 8See any good control theory text for the relationship between a system model and admissible controls for that system. A nice introduction appears in [21], chap. 8. 9I.e., the system behaves like Li ≈ γLi−1, a difference equation with the solution Ln = γ nL0 which goes exponentially to infinity for any γ > 1