Fairness

Fairnessandstabilityofend-to-endcongestioncontrol∗FrankKelly†AbstractInrecentyearstheInternethasattractedtheattentionofmanytheoreticians,eagertounderstandtheremarkablesuccessofthisdi-verseandcomplexartefact.Acentralelementofthedesignphiloso-phythatshapedtheInternetistheend-to-endargument,andakeyillustrationoftheargumentisprovidedbythecongestionavoidancealgorithmoftheTransmissionControlProtocol(TCP).Whydoesthisalgorithmworksowell?Howmight,orshould,itevolveinthefuture?Inthispaperweoutlinesomeofthemathematicalmodelsthathavebeendevelopedtohelpaddressthesequestions.Wereviewtheequilibriumanddynamicpropertiesofprimalanddualalgorithms,concentratinguponfairness,delayinstabilityandstochasticinstability.Primalalgorithmsbroadlycorrespondwithcon-gestioncontrolmechanismswherenoisyfeedbackfromthenetworkisaveragedatendpoints,usingincreaseanddecreaserulesgeneralizingthoseofTCP.Vinnicombehasshownthatdelayinstabilityischar-acterizedintermsoftheincreaserule;Otthasshownthatstochasticinstabilityisprimarilyinfluencedbythedecreaserule.TheneedtocontrolbothformsofinstabilityplacesconstraintsonpossiblevariantsofTCP,andonattemptstoremoveTCP’sround-triptimebias.Dualalgorithmsbroadlycorrespondwithcongestioncontrolmech-anismswhereaveragingatresourcesprecedesthefeedbackofmoreexplicitinformationtoendpoints,andmaybeespeciallyappropriatewhereround-triptimesareshort,asinad-hocnetworks.Previousworkhasconcentratedondelay-baseddualalgorithms,whichfindfairnessandstabilitydifficulttoreconcile.Wedescribeafamilyoffairdualalgorithms,withattractivestabilityproperties.∗PaperpreparedforaplenaryaddresstotheEuropeanControlConference,Cambridge,September2003,andavailablefrom:159-176.†CentreforMathematicalSciences,UniversityofCambridge,WilberforceRoad,Cam-bridgeCB30WBUK.Email:[e-mail]1Keywords:Internet,TCP,proportionalfairness,Ornstein-Uhlenbeckprocess1IntroductionAcentralelementofthedesignphilosophythatshapedtheInternet[8,46]istheend-to-endargument[40],summarizedasfollows[4]:“Anend-to-endprotocoldesignshouldnotrelyonthemaintenanceofstate(i.e.,informa-tionaboutthestateoftheend-to-endcommunication)insidethenetwork.Suchstateshouldbemaintainedonlyintheendpoints,insuchawaythatthestatecanonlybedestroyedwhentheendpointitselfbreaks.”Intelligenceandcontrolisend-to-endratherthanhiddeninthenetwork.Theresultingin-terconnectionofcommunicationlinksissometimestermedadumbnetwork,toemphasiseacontrastwiththeearliertelephonyinfrastructurewhereasmartnetworkconnectsendpoints(telephones)thathavelittleresponsibilityforcontrol.Adumbnetworkallowsnewapplicationstobedesigned,pro-totypedanddeployedwithoutrequiringchangestotheunderlyingnetwork,andhasresultedinanextraordinaryfloweringofinnovation.Italsoplacesaconsiderableresponsibilityforcooperativebehaviouronendpoints.Akeyillustrationoftheend-to-endargumentisTCP,thetransmissioncontrolprotocoloftheInternet,anditscongestionavoidancealgorithm,duetoJacobson[15].TherateatwhichpacketsenterthenetworkiscontrolledbyTCP,implementedassoftwareonthecomputers(theendpoints)thatarethesourceanddestinationofthedata.Thegeneralapproachisasfollows.Whenalinkwithinthenetworkbecomesoverloaded,oneormorepacketsarelost;lossofapacketistakenasanindicationofcongestion,thedestinationinformsthesource,andthesourceslowsdown.TheTCPthengraduallyincreasesitssendingrateuntilitagainreceivesanindicationofcongestion.Thiscycleofincreaseanddecreaseservestodiscoverandutilizeavailablebandwidth,andtoshareitbetweenflows.Jacobson’salgorithmhasbeenoutstandinglysuccessful,astheInternethasevolvedfromasmall-scaleresearchnetworktotoday’sinterconnectionoftensofmillionsofendpointsandlinks.Thisinitselfisastrikingobservation.Eachofalargebutindeterminatenumberofflowsiscontrolledbyafeedbackloopwhichcanknowonlyofitsownexperienceofcongestionandofitsownfeedbackdelay.Aflowdoesnotknowhowmanyotherflowsaresharingalinkonitspath,orevenhowmanylinksareonitspath.Thelinksvaryincapacitybymanyordersofmagnitude,asdothepropagationdelaysthatareaconsequenceofgeographicaldiversityandthefinitespeedoflight.Thatend-to-endcongestioncontrolcanhaveachievedsomuch,insucharapidlygrowingandheterogeneousnetwork,isremarkable.2Howeverthereareseveralinterrelateddevelopmentsthatposeachallenge.BufferingatqueueswithintheInternethasbeenimportantsincetheearlydaysofstore-and-forwardcommunicationnetworks[22],tosmoothstatisticalfluctuationsand,itiscommonlybelieved,tohelpstabilizethenetwork.Butthehugecapacityoftomorrow’slinks,togetherwiththedesiretocarrydelay-sensitivetraffic,maycauseanevolutiontowardsanetworkwithmuchsmallerqueueingdelays.Isend-to-endcongestioncontrolfeasibleinsuchanetwork,and,ifso,howshouldTCPevolve?Thispaperexplorespossibleanswerstothisquestion,andoutlinessomeoftheimportantinsightsthathavebeenobtainedfromsimplifiedmathe-maticalmodelsofcongestioncontrol.Theselectionofmaterialhasbeenprimarilyinfluencedbyrecentexperimentswithnew,incrementablydeploy-able,TCPs[10,21,38],therelatedmodellingadvances[35,37,43],andb