END-TO-ENDCONGESTIONDETECTIONAND AVOIDANCE INWIDEAREANETWORKS by Lawrence Sivert Brakmo Copyright cLawrence Sivert Brakmo 1996 A Dissertation Submitted to the Faculty of the DEPARTMENT OF COMPUTER SCIENCE In Partial Fulllment of the Requirements For the Degree of DOCTOR OF PHILOSOPHY In the Graduate College THE UNIVERSITY OF ARIZONA 1996 END-TO-END CONGESTION DETECTION AND AVOIDANCE IN WIDE AREA NETWORKS Lawrence Sivert Brakmo, Ph.D. The University of Arizona, 1996 Director: Larry L. Peterson As human dependence on wide area networks like the Internet increases, so does contention for the network's resources. This contention has noticeably aected the performance of these networks, reducing their usability. This dissertation addresses this problem in two ways. First, it describes TCP Vegas, a new implementation of TCP that is distin guished from current TCP implementations by containing a new congestion detec tion and avoidance mechanism. This mechanism was designed to work in currently available wide area networks and achieves between 37% and 71% better throughput on the Internet, with one-fth to one-half the losses, as compared to the current implementation of TCP. Second, it describes x-Sim, a network simulator based on thex-kernel, that is able to simulate the topologies and trac patterns of large scale networks. The usefulness of the simulator to analyze and debug network components is illustrated throughout this dissertation. STATEMENT BYAUTHOR This dissertation has been submitted in partial fulllment of the requirements for an advanced degree at The University of Arizona and is deposited in the University Library to be made available to borrowers under rules of the Library. Brief quotations from this dissertation are allowable without special permission, provided that accurate acknowledgment of the source is made. Requests for permis sion for extended quotation from or reproduction of this manuscript in whole or in part may be granted by the copyright holder. SIGNED: ACKNOWLEDGMENTS I would like to express my gratitude to my advisor, Larry Peterson. He has been the ideal advisor, one whose experience and knowledge provided me with the haven that allowed me the freedom to explore my own ideas. I have been very fortunate to have both his guidance and friendship during this journey. I am also grateful to the other members of my committee, Pete Downey and John Hartman, for their comments and suggestions on my work. I am thankful to Udi Manber for our many enjoyable discussions. I would like to thank the minor members ofmy committee,Ted Laetsch, and specially WilliamVelez, who hasbeen a great counselor and friend for many years. I also want to thank everyone in the Computer Science department at Arizona for making my stay here so pleasurable. Special thanks to Cara Wallace, Margaret Newman, Wendy Swartz, John Cropper, Cli Hathaway and John Luiten. Finally, I would like to thank my fellow graduate students, Vince Freeh, David Mosberger, Peter Drushel, Mark Abbot, David Lowenthal, Nina Bhatti, and Mudita Jain for their friendship. This work was supported by the National Science Fundation under Grant IRI 9015407 and by ARPA under Contract DABT63-91-C-0030. DEDICATION To my parents, for always supporting my quest for knowledge, even when the journey strayed from the direct path. For raising me in an environment that en couraged the pursuit of knowledge. For always giving of themselves. And most importantly, for teaching me the meaning of love, caring, and sel essness through their example. LACCIHHBSSAA11222T....TPP23413ORTTFAEECCPDT2S222VC....RRFiroohii1123mssoTImne..sut43151314G12ugeoax:p:lerUclau-ts:iISoKtaztRntiloiatemsteoSSMPxLNLFCREritrrronue-iioirouoSeonoKnNennsopaldald::esnskaeatdpeerusliOeotstos::traoTGsceocewnnugrtdo:orTreteitoGoloaOllarW:AiRlnOiOknrnMsnba::sodoebeBbjiouredn:::jjkVdceteeLi::tcTicdinstsEto::esucsTosaa:::lotOlsoii:::zolaFsn::tsi:::otCno:::OT:::Suo::Npo:::lpsTo:::rEt::::Nt::h:::eT:::SSi:::::m:::ul::at::o::::r::::::::::::::::::::::::::11121222233369257085437790241 CCCHHHAAA3334445.......PPP1251462351234TTTEEEBRFGA3CDPCOCI5S5O5D555n.......RRRilraoooeneie4t23t4mtosehhlcntnnneawciv211213321345akueeragggelui:::yingrrrlbeeeolsCaasreesssTiNEusMEitoltttldtoisisiriixiouevntoGoooFJOBSFODIABeaRGnowpyanCnntncnnantaafraSlelentredhdarcoutsisaholsRArDeTrCaAAbetoameanapuiklen-prmpbneyipCgtoo:vvhlgrRlneiVhstisiepeinnsoorosPseuastoE::enssDoatriismynnDtltnitdd'Orodurxto:isrtieo'iaaavsseeopnCaansasnlnnCc::ensncnldeiterhcOnccCtrirosRiA:roeeAiitTmEnoriVptmTneepp:iorngviDxtrsgasinaptCeietoitup:iliouCanrrsniioPlVeandodorttt::oanrcniisaslaeanniloV:::dcgmtnPnggPhiaec:::oerFegesreSCnsonosaa:tltMotpssoios::o:::tnwocentsR:::o-craSlhoDe:l::tlacae::onMtrviet:::::seecmrct::yihso:::aMnn::iaes:::::cnmhd:::a::::Aniv:::smo::::ids::::an:::::c::e::::::::::::::::::::::::4546645778889887011313785529425619 CCRHHEFAA677...EPP12132RTTEEE6A666G666SFCN.......RRuuon1111u222mtCn.aiu2134578134567dtlEm::ryreeiSslECbaiinDsruxo:yeENSOLqHFCSARIBUtiopnnsriuueiirfoyeeannpceoensnnrebfatmlrntwnait:cBooeaunswdieolitdlsareriilaoSpscyepitsolnrvionnyaDrDaiziNtitorv:cnenntisIinirknKcen4ermeenigisd:tsantsHtd.gcCTynuawanBgr::wLe-oirsoRSldeotLliaawitnisaygoRrTmetdhiAsknlths::eeeAeNieeiugccmCrtdtSxhu:ClDoeraTgtKiSPeatr-rftmsKei:SwoaoCniritTonintuueshs:o:Pemnirmdigrlreoracasc::kienincFiCtentt:::itssPyrtooifeTo:ae:nnqVnrrigu:::msaeeCerms:::esntooieci:::oduotyneen::tsrEs::::Wosf:::tiniT:::mdC::oaPwt:::esLa:::ni::::tde::A:::C:::K::::in::g:::Fr:::e::::-::::11111111119909002222858332572805807469 1122223333333.............23143567128456879111024ISSEDTEDDGBSGWTWPTSEBNBBCnwmtlaxxxiliCeeeoaaaerrotrmomiicaahhhaaatmtttiennweaPctkwaaappmmmaaaraededlck-mecbbblvvvhhmolshoottpppodiaaaiiitrcPrwwnsoooonllsslaiksssoaneeenPerhhrrreeensrnceo ceptoorxnoteeoootgetooo:orooowwiawcffffe-olemeuuunwwteKctCtsciinSoCTTTotttimewnntoeorpppeclocdeccgoCCCggo-lkonreeonuuudooslunwnr.iPPPnlbgttrtrnnnbrokgsemootn-yea:ttfeececcslsuuwwwserrdattsaotoostnLcoootttiinoatwiiiimmmlinowoeelleftttinoord.IonerrhhhntntwotnFpppT'Snwe.oao:ssrcaaaafnFFuCkitwogoTolrrrwsnqa::aaitrurriiitcPnimvussnnnkrinrub:nFttkeseResgggaOdarlitrsda.utomRRreriaopTTTsoineecatFwgot:eeowunktrCCCcensttnaaltRe::irrasP.PPbdinzsFoaainttegi::eoizsunniiztnriiiI.mmeoutbmmmerssagGnpnammlvpievoppps::untdpehiiecUallltsarttrm::seeerkmns.or.smmmbauiRd::te:ubeinaoscteeesson:dthc.Ennn.tuitdoaitttm:::iFnmlwSaaanmad:::tttegiiessiiiaedrooo.:::omtratnnnfihpR::.esssnhs.e::f:e..ocx::::rotva::::eervs:::ype.:::nect::::.i:::e:d:::::lin:::::k::::.123123434455559346556870198568102436 43444656666666..............12365718145123117289534250TTNTTTCTTNETTRQCGTTQGNSTCGiTxCCCCCoChhCoCCCoeeeururrmaaatntamtmrreeTPPPPPPPPPPwwwoopppmpguuppuuhhheloooeeaRwVRVVLRLLepllsggrrsreniiitbboloeeekkkieeehhSttxtxenidsgggffnnneeeeppeoihcccdaaamhhooos.o.SnqquuRoooo13wosssifaaiuuttmwnnnuwwwwTmdvviwworwweeltvvieiieuiiisOnuauunhooiittitigggtsstlttttteehhhlrgrgru.uueahthihhaNeaorcthrrrssddtSSntNaxanitnaaaiiontNNiceouuzzeeroiapocstttopootneennrNroommpiiiOnlhlinooooeiiddilOo.nnasneibfnnnOOttipNhbctttattgghhetBBlh,:-wigttoeneffhtfeeamgbhhootfoeeuuewwtsdrroeloewowrrnrrxee.erroniupTttrrep:onakcoeetsssrtrerTerrvhriiierr.rgkTTlarmamlmaraekrorlaaa.rriSSataniiino::traauuumnedriiecegdizzdgclllfca:scdeaaaeoeeiec(mknc(cctntt.(rbt:TbTiciitmThta.ioeoo((heTaa:nCrhcTTnCnnarclockihrePsss:::otkhhnPluoog...rciuugrrnoguorttVdgoortnoshugrohruu::::iteuaphgnaiuhlpgggnnnh:oupngnehhausdsptusd:s:s:ppfttm:rfute.i:euutim:rdttg1rirtt1srnahus27u:::::::a6.-t3ae10lm991.a::n2ctKKtc3daKo:::i7.xoBKBBKta:nKc/b/Bv/.Bp:::::ssaBes/)l)rr)i:::./bsa.s)sg:::.)ti.rn:ag::::::.c:::.::::::::::::111111 ABSTRACT As human dependence on wide area networks like the Internet increases, so does contention for the network's resources. This contention has noticeably aected the performance of these networks, reducing their usability. This dissertation addresses this problem in two ways. First, it describes TCP Vegas, a new implementation of TCP that is distin guished from current TCP implementations by containing a new congestion detec tion and avoidance mechanism. This mechanism was designed to work in currently available wide area networks and achieves between 37% and 71% better throughput on the Internet, with one-fth to one-half the losses, as compared to the current implementation of TCP. Second, it describes x-Sim, a network simulator based on thex-kernel, that is able to simulate the topologies and trac patterns of large scale networks. The usefulness of the simulator to analyze and debug network components is illustrated throughout this dissertation. CHAPTER1 Introduction Our society's dependence on computer networks and computer communication has been increasing during the last two decades, a trend that is likely to continue in the foreseeable future. The importance of computer networks in our daily life can be attested by the exponential growth of the Internet, a global computer network consisting of thousands of connected heterogeneous networks. When traced back to its origins, the number of hosts connected to the Internet has been doubling in size every year since 1981. This growth has been fueled by applications that have enabled new levels of com munication and information sharing between people in dierent cities or countries. Graphical World Wide Web (WWW) browsers, like Mosaic and Netscape, have been responsible for most of the Internet's growth in the last two years by simplifying the chore of making information publicly available and easy to nd on the Internet. A downside to this growth has been an increase in contention for Internet re sources. This contention has noticeably aected the performance of distributed applications like Mosaic, at the same time that our dependence on such applications is increasing. This dissertation addresses this problem in two ways. First, it pro poses a new technique to manage this contention, and second, it describes a set of tools to analyze the performance and behavior of such mechanisms. 1.1ComputerNetworks Computer communication is made possible by the connectivity provided by com puter networks [24]. At the lowest level, computers are directly connected with each other through a physical medium, such as a cable. We call such a physical medium alink, and refer to the computers it connects asnodes , to underscore the fact that Figure 1.1: Switch network. they may be implemented by specialized hardware rather than general purpose com puters. Links can be point-to-point , connecting a pair of nodes, ormultipleaccess , connecting more than two nodes. Thebandwidth (throughput) of a link is given by the maximum number of bits than can be transfered over the link in a certain period of time. Thelatency (delay) of the link refers to the time it takes a particular bit to travel from one end of the link to the other. Links provide direct connectivity between nodes and are one of the basic blocks upon which indirect connectivity is built. The need for indirect connectivity arises from the desire to have total connectivity: the ability of reach any node from any other node. It would be prohibitively expensive to achieve this with direct connec 2 tivity, since the number of links needed would be O(n ), where n is the number of nodes. Figure 1.1 shows a network with limited direct connectivity. Indirect connectivity is achieved by having any node connected to at least two links, shown in the gure by squares with dashed lines, forward (or route) data received on one link out on another. If this is done in a systematic way, data from any node can reach any other node. This type of network is known as a switched network. Figure 1.2: Interconnection of networks. The most common type of computer network is a packet-switched network, where nodes send discrete blocks of data to each other. These blocks are calledpackets ormessages. The most common strategy used to forward the packets in packet- switched networks is called store-and-forward . Each node waits until it has received a whole packet before forwarding it at a later time to the appropriate output link. Theend-to-endlatency of a packet is dened as the amount of time it takes the packet to go from the source host to the destination host. The nodes inside the network, connected to two links or more, usually have the sole function of storing and forwarding packets. They are generally calledswitches or routers . The nodes at the periphery of the network, connected to only one link, are general purpose computers whose goal is to support users and run their applications. They are calledhosts. Packets must contain special information so routers know how to forward them. This information is usually held at the beginning of the packet in an area called the packet header .