Making greed work in networks A game-theoretic ana

MakingGreedWorkinNetworks:AGame-TheoreticAnalysisofSwitchServiceDisciplines1ScottShenkerXeroxPaloAltoResearchCenter3333CoyoteHillRoadPaloAlto,CA94304-1314415-812-4840shenker@parc.xerox.comAbstractThispaperdiscussescongestioncontrolfromagame-theoreticperspective.Therearetwobasicpremises:(1)usersareassumedtobeindependentandselsh,and(2)centraladministra-tivecontrolisexercisedonlyatthenetworkswitches.Theoperatingpointsresultingfromselshuserbehaviordependcruciallyontheservicedisciplinesimplementedinnetworkswitches.ThiseectisinvestigatedinasimplemodelconsistingofasingleexponentialserversharedbymanyPoissonsources.Wediscusstheextenttowhichonecanguarantee,throughthechoiceofswitchservicedisciplines,thattheseselshoperatingpointswillbeecientandfair.Wealsodiscusstowhatextentthechoiceofswitchservicedisciplinescanensurethattheseselshoperatingpointsareuniqueandareeasilyandrapidlyaccessiblebysimpleself-optimizationtechniques.Weshowthatnoservicedisciplinecanguaranteeoptimaleciency.Asfortheotherproperties,weshowthatthetraditionalFIFOservicedisciplineguaranteesnoneoftheseproperties,butthataservicedisciplinecalledFairShareguaranteesallofthem.Whilethetreatmentutilizesgame-theoreticconcepts,nopreviousknowledgeofgametheoryisassumed.1Anotetoreviewers:Thisworkmightseemfamiliartosomeofyou;preliminaryversionshavebeencirculatedsince1990,andtheworkwaspresentedatMIT,AT&TBellLabs,andtheEnd-to-EndServicesResearchGroupin1989and1990(andalsoappearedinaveryabbreviatedforminthepostersessionofSigmetrics‘90).Theoriginalversionofthispapermotivatedthefollow-onworkbythisauthorandothers[23,24,35]intheeconomicsliterature.Whilethispaperpresentsasignicantnumberofnewresults,italsoliberallyquotesresultsfromtheseeconomicreferencesinordertoprovideamorecompletepictureofthegame-theoreticperspectiveonthisproblem.11IntroductionCongestionhaslongbeenaproblemincomputernetworks.Duringthepastdecade,mucheorthasbeendevotedtounderstandingthenatureofcongestionanddevelopingtechniquesforitscontrol.Manydierentcongestioncontrolmechanismshavebeenproposed,andnumerousstudieshavebeenpublishedevaluatingtheirrelativeperformance.However,buriedbeneaththesedetailedmechanisticproposalsisafundamentaldisagreementaboutnetworkdesignphilosophy.Mostoftheearlierproposedcongestioncontrolschemesassumethecooperationofnetworkusers2,requiringthemtoimplementaparticularowcontrolalgorithmattheendhosts[11,13,27].Inthisapproach,usersadoptacentrallymandatedalgorithm,andtheroleofthedesigneristomaketheresultingsystem-widebehaviorachievecertainsystemicgoalssuchashighutilizationorlowdelay.Thisistheusualparadigminthestudyofdistributedsystems;whileevaluatingtherelativemeritsofthevariousproposalsisoftentechnicallydicult,itposesnoparticularparadigmaticchallenge.Someofthemorerecentworktakesaratherdierentapproach.Thisapproachnotonlyconcedesthatitisimpossibletocentrallymandatethebehaviorofendusers,butactivelycontendsthatsuchcentralizedadministrativecontrolisnotadvisable.Ratherthanfollowingsomemandatedalgorithm,inthisapproachusersareassumedtoact\selshlytofurthertheirownindividualinterests.Theroleofthedesignerhereisconnedtomandatingthebehaviorofnetworkswitches(whichareassumedtobeundercentralizedadministrativecontrol).Thegoalistodesigntheseswitchservicedisciplinessothatthenetworkwilldelivergoodserviceinspiteofselshuserbehav-ior.Reference[3]isanexampleofthisapproach;itfocusesondesigningeectiveservicedisciplinesinnetworkswitchesandthenlettingendhostsdowhateverisintheirownbestinterest.Thisapproach,withitsemphasisonindividualincentives,doesnottthetypicalparadigmusedinthestudyofdistributedsystems.Ifusersarenotfollowingsomecentrallymandatedalgorithm,howcanonemodeluserbehavior?Howcanonedescribetheeventualnetworkoperatingpointinsuchnoncooperativesystems?Ifusersareactingtofurthertheirowninterests,ratherthanthatofthesystem,bywhatcriteriadoesoneevaluatetheresultingsystem-widebehavior?Thesequestions,whichinvolveindividualincentivesinafundamentalway,arelargelyforeigntocomputerscience;however,theyaretheverycoreofgametheory.Thepurposeofthispaperistoillustratehowgametheorycanbeusedtoformulateandanswer,atleastonatheoreticallevel,theseincentivequestions.OtherthanreviewingsomeoftheargumentsbrieyinSection2.2,wearenotrevisitingthebasicdebatebetweenthetwoapproachestocongestioncontrol.Rather,wearemerelyexhibitinghowonecanformalizeandanalyzethissecondapproachusingagame-theoreticperspective.Wewillapplythisgame-theoreticperspectivetoaverysimplesystem:asingleswitchsharedbyNusers.EachusersendsaPoissonstreamofpacketsthroughtheswitch.Therateofthei’thuser’sPoissonstreamisdenotedbyri;thealgorithmbywhichtheusercontrolsthisrateiscalledtheowcontrolalgorithm.Theswitchisservicedbyanexponentialserverwithpreemption.3Onemeasureofthecongestionexperiencedbyauseristheaveragenumberofthatuser’spacketsthat2Thetermuserhereispurposelyambiguous.Whilethehumanuserultimatelycontrolstheimplementationsusedonthenetworkdevice,itisthedevicewhichtypicallycontrolsthenetworkbehaviorintheshortterm.Toavoidcontinuallytrippingoverthisdistinction,wewillusethe