Congestion Avoidance and ControlVan JacobsonLawrence Berkeley LaboratoryMichael J. KarelsUniversity of California at BerkeleyNovember, 1988IntroductionComputer networks have experienced an explosive growthoverthepast few years andwith that growthhave come severecongestion problems. For example, it is now common to seeinternet gateways drop 10% of the incoming packets becauseof local buffer overflows. Our investigation of some of theseproblems has shown that much of the cause lies in transportprotocol implementations (not in the protocols themselves):The ‘obvious’ ways to implement a window-based transportprotocol can result in exactly the wrong behavior in responseto network congestion. We give examples of ‘wrong’ behav-ior and describe some simple algorithms that can be used tomake right things happen. The algorithms are rooted in theidea of achieving network stability by forcing the transportconnection to obey a ‘packet conservation’ principle. Weshow how the algorithms derive from this principle and whateffect they have on traffic over congested networks.InOctober of ’86, the Internet hadthe first ofwhat becamea series of ‘congestion collapses’. During this period, thedata throughput from LBL to UC Berkeley (sites separatedby 400 yards and two IMP hops) dropped from 32 Kbps to 40bps. We were fascinated by this sudden factor-of-thousanddrop in bandwidth and embarked on an investigation of whythings had gotten so bad. In particular, we wondered if the4.3BSD (Berkeley UNIX) TCP was mis-behaving or if it couldbe 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 pre-sented at SIGCOMM ’88 [11]. If you wish to reference this work, pleasecite [11].This work was supported in part by the U.S. Department of Energyunder Contract Number DE-AC03-76SF00098.This work was supported by the U.S. Department of Commerce, Na-tional Bureau of Standards, under Grant Number 60NANB8D0830.Since that time, we have put seven new algorithms intothe 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 retransmitOur measurements and the reports of beta testers suggest thatthe final product is fairly good at dealing with congested con-ditions on the Internet.This paper is a brief description of (i) –(v) and the ra-tionale behind them. (vi) is an algorithm recently developedby Phil Karn of Bell Communications Research, describedin [15]. (vii) is described in a soon-to-be-published RFC(ARPANET “Request for Comments”).Algorithms (i) –(v) spring from one observation: Theflow on aTCP connection (or ISO TP-4 or Xerox NS SPP con-nection) should obey a ‘conservation of packets’ principle.And, ifthis principle were obeyed, congestion collapse wouldbecome the exception rather than the rule. Thus congestioncontrol involves finding places that violate conservation andfixing them.By ‘conservation of packets’ we mean that for a connec-tion ‘in equilibrium’, i.e., running stably with a full windowof data in transit, the packet flow is what a physicist wouldcall ‘conservative’: A new packet isn’t put into the networkuntil an old packet leaves. The physics of flow predicts thatsystems with this property should be robust in the face ofcongestion.1Observation of the Internet suggests that it wasnot particularly robust. Why the discrepancy?1A conservative flow means that for any given time, the integral of thepacket density around the sender–receiver–sender loop is a constant. Since2 CONSERVATION AT EQUILIBRIUM: ROUND-TRIP TIMING2There are only three ways for packet conservation to fail:1. The connection doesn’t get to equilibrium, or2. A sender injects a new packet before an old packet hasexited, or3. The equilibrium can’t be reached because of resourcelimits along the path.In the following sections, we treat each of these in turn.1 Getting to Equilibrium: Slow-startFailure (1) has to be from a connection that is either startingor restarting after a packet loss. Another way to look at theconservation property is to say that the sender uses acks asa ‘clock’ to strobe new packets into the network. Since thereceiver can generate acks no faster than data packets can getthrough the network, the protocol is ‘self clocking’ (fig. 1).Self clocking systems automatically adjust to bandwidth anddelay variations and have a wide dynamic range (importantconsideringthatTCP spans a range from 800 Mbps Cray chan-nels to 1200 bps packet radio links). But the same thing thatmakes a self-clocked system stable when it’s running makesit hard to start — to get data flowing there must be acks toclock out packets but to get acks there must be data flowing.To start the ‘clock’, we developed a slow-start algorithmto gradually increase the amount of data in-transit.2Al-though we flatter ourselves that the design of this algorithmis rather subtle, the implementation is trivial — one new statevariable and three lines of code in the sender:Add a congestion window, cwnd, to the per-connectionstate.When starting or restarting after a loss, set cwnd to onepacket.On each ack for new data, increase cwnd by one packet.packets have to ‘diffuse’ around this loop, the integral is sufficiently contin-uous to be a Lyapunovfunction for the system. A constant function triviallymeets the conditions for Lyapunov stability so the system is stable and anysuperpositionofsuchsystemsisstable. (See [2], chap. 11–12or[20],chap.9for excellent introductions to system stability theory.)2Slow-start is quite similar to the CUTE algorithm described in [13]. Wedidn’t know aboutCUTEat the time we were developing slow-start but weshould have—CUTE preceded our work by several months.When describing our algorithm at the Feb., 1987, Internet EngineeringTask Force (IETF) meeting, we called it soft-start, a reference to an elec-tronics engineer’s technique to limit in-rush current. The name slow-startwas 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.When sending, send the minimum of the receiver’sadvertised window and cwnd.Actually, the slow-start window increase isn’t that slow:it takes time log2where is the
View Full Document
Unlocking...