brakmo

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 .