Congestion Avoidance and Control Van Jacobson Lawrence Berkeley Laboratory Michael J Karels University of California at Berkeley November 1988 Introduction Computer networks have experienced an explosive growth over the past few years and with that growth have come severe congestion problems For example it is now common to see internet gateways drop 10 of the incoming packets because of local buffer overflows Our investigation of some of these problems has shown that much of the cause lies in transport protocol implementations not in the protocols themselves The obvious ways to implement a window based transport protocol can result in exactly the wrong behavior in response to network congestion We give examples of wrong behavior and describe some simple algorithms that can be used to make right things happen The algorithms are rooted in the idea of achieving network stability by forcing the transport connection to obey a packet conservation principle We show how the algorithms derive from this principle and what effect they have on traffic over congested networks In October of 86 the Internet had the first of what became a series of congestion collapses During this period the data throughput from LBL to UC Berkeley sites separated by 400 yards and two IMP hops dropped from 32 Kbps to 40 bps We were fascinated by this sudden factor of thousand drop in bandwidth and embarked on an investigation of why things had gotten so bad In particular we wondered if the 4 3BSD Berkeley UNIX TCP was mis behaving or if it could be tuned to work better under abysmal network conditions The answer to both of these questions was yes Note This is a very slightly revised version of a paper originally presented at SIGCOMM 88 11 If you wish to reference this work please cite 11 This work was supported in part by the U S Department of Energy under Contract Number DE AC03 76SF00098 This work was supported by the U S Department of Commerce National Bureau of Standards under Grant Number 60NANB8D0830 Since that time we have put seven new algorithms into the 4BSD TCP i round trip time variance estimation ii exponential retransmit timer backoff iii slow start iv more aggressive receiver ack policy v dynamic window sizing on congestion vi Karn s clamped retransmit backoff vii fast retransmit Our measurements and the reports of beta testers suggest that the final product is fairly good at dealing with congested conditions on the Internet This paper is a brief description of i v and the rationale behind them vi is an algorithm recently developed by Phil Karn of Bell Communications Research described in 15 vii is described in a soon to be published RFC ARPANET Request for Comments Algorithms i v spring from one observation The flow on a TCP connection or ISO TP 4 or Xerox NS SPP connection should obey a conservation of packets principle And if this principle were obeyed congestion collapse would become the exception rather than the rule Thus congestion control involves finding places that violate conservation and fixing them By conservation of packets we mean that for a connection in equilibrium i e running stably with a full window of data in transit the packet flow is what a physicist would call conservative A new packet isn t put into the network until an old packet leaves The physics of flow predicts that systems with this property should be robust in the face of congestion 1 Observation of the Internet suggests that it was not particularly robust Why the discrepancy 1 A conservative flow means that for any given time the integral of the packet density around the sender receiver sender loop is a constant Since 2 CONSERVATION AT EQUILIBRIUM ROUND TRIP TIMING There are only three ways for packet conservation to fail 2 When sending send the minimum of the receiver s advertised window and cwnd 1 The connection doesn t get to equilibrium or 2 A sender injects a new packet before an old packet has exited or 3 The equilibrium can t be reached because of resource limits along the path In the following sections we treat each of these in turn 1 Getting to Equilibrium Slow start Failure 1 has to be from a connection that is either starting or restarting after a packet loss Another way to look at the conservation property is to say that the sender uses acks as a clock to strobe new packets into the network Since the receiver can generate acks no faster than data packets can get through the network the protocol is self clocking fig 1 Self clocking systems automatically adjust to bandwidth and delay variations and have a wide dynamic range important considering that TCP spans a range from 800 Mbps Cray channels to 1200 bps packet radio links But the same thing that makes a self clocked system stable when it s running makes it hard to start to get data flowing there must be acks to clock out packets but to get acks there must be data flowing To start the clock we developed a slow start algorithm to gradually increase the amount of data in transit 2 Although we flatter ourselves that the design of this algorithm is rather subtle the implementation is trivial one new state variable and three lines of code in the sender Add a congestion window cwnd to the per connection state When starting or restarting after a loss set cwnd to one packet On each ack for new data increase cwnd by one packet packets have to diffuse around this loop the integral is sufficiently continuous to be a Lyapunov function for the system A constant function trivially meets the conditions for Lyapunov stability so the system is stable and any superposition of such systems is stable See 2 chap 11 12 or 20 chap 9 for excellent introductions to system stability theory 2 Slow start is quite similar to the CUTE algorithm described in 13 We didn t know about CUTE at the time we were developing slow start but we should have CUTE preceded our work by several months When describing our algorithm at the Feb 1987 Internet Engineering Task Force IETF meeting we called it soft start a reference to an electronics engineer s technique to limit in rush current The name slow start was coined by John Nagle in a message to the IETF mailing list in March 87 This name was clearly superior to ours and we promptly adopted it Actually the slow start window increase isn t that slow it takes time log2 where is the round trip time and is the window size in packets fig 2 This means the window opens quickly enough to have a negligible effect on performance even on links with a
View Full Document
Unlocking...