您好,欢迎访问三一刀客
MakingGreedWorkinNetworks:AGame-TheoreticAnalysisofSwitchServiceDisciplines1ScottShenkerXeroxPaloAltoResearchCenter3333CoyoteHillRoadPaloAlto,CA94304-1314415-812-4840shenker@parc.xerox.comAbstractThispaperdiscussescongestioncontrolfromagame-theoreticperspective.Therearetwobasicpremises:(1)usersareassumedtobeindependentandsel sh,and(2)centraladministra-tivecontrolisexercisedonlyatthenetworkswitches.Theoperatingpointsresultingfromsel shuserbehaviordependcruciallyontheservicedisciplinesimplementedinnetworkswitches.Thise ectisinvestigatedinasimplemodelconsistingofasingleexponentialserversharedbymanyPoissonsources.Wediscusstheextenttowhichonecanguarantee,throughthechoiceofswitchservicedisciplines,thatthesesel shoperatingpointswillbee cientandfair.Wealsodiscusstowhatextentthechoiceofswitchservicedisciplinescanensurethatthesesel shoperatingpointsareuniqueandareeasilyandrapidlyaccessiblebysimpleself-optimizationtechniques.Weshowthatnoservicedisciplinecanguaranteeoptimale ciency.Asfortheotherproperties,weshowthatthetraditionalFIFOservicedisciplineguaranteesnoneoftheseproperties,butthataservicedisciplinecalledFairShareguaranteesallofthem.Whilethetreatmentutilizesgame-theoreticconcepts,nopreviousknowledgeofgametheoryisassumed.1Anotetoreviewers:Thisworkmightseemfamiliartosomeofyou;preliminaryversionshavebeencirculatedsince1990,andtheworkwaspresentedatMIT,AT&TBellLabs,andtheEnd-to-EndServicesResearchGroupin1989and1990(andalsoappearedinaveryabbreviatedforminthepostersessionofSigmetrics‘90).Theoriginalversionofthispapermotivatedthefollow-onworkbythisauthorandothers[23,24,35]intheeconomicsliterature.Whilethispaperpresentsasigni cantnumberofnewresults,italsoliberallyquotesresultsfromtheseeconomicreferencesinordertoprovideamorecompletepictureofthegame-theoreticperspectiveonthisproblem.11IntroductionCongestionhaslongbeenaproblemincomputernetworks.Duringthepastdecade,muche orthasbeendevotedtounderstandingthenatureofcongestionanddevelopingtechniquesforitscontrol.Manydi erentcongestioncontrolmechanismshavebeenproposed,andnumerousstudieshavebeenpublishedevaluatingtheirrelativeperformance.However,buriedbeneaththesedetailedmechanisticproposalsisafundamentaldisagreementaboutnetworkdesignphilosophy.Mostoftheearlierproposedcongestioncontrolschemesassumethecooperationofnetworkusers2,requiringthemtoimplementaparticular owcontrolalgorithmattheendhosts[11,13,27].Inthisapproach,usersadoptacentrallymandatedalgorithm,andtheroleofthedesigneristomaketheresultingsystem-widebehaviorachievecertainsystemicgoalssuchashighutilizationorlowdelay.Thisistheusualparadigminthestudyofdistributedsystems;whileevaluatingtherelativemeritsofthevariousproposalsisoftentechnicallydi cult,itposesnoparticularparadigmaticchallenge.Someofthemorerecentworktakesaratherdi erentapproach.Thisapproachnotonlyconcedesthatitisimpossibletocentrallymandatethebehaviorofendusers,butactivelycontendsthatsuchcentralizedadministrativecontrolisnotadvisable.Ratherthanfollowingsomemandatedalgorithm,inthisapproachusersareassumedtoact\sel shlytofurthertheirownindividualinterests.Theroleofthedesignerhereiscon nedtomandatingthebehaviorofnetworkswitches(whichareassumedtobeundercentralizedadministrativecontrol).Thegoalistodesigntheseswitchservicedisciplinessothatthenetworkwilldelivergoodserviceinspiteofsel shuserbehav-ior.Reference[3]isanexampleofthisapproach;itfocusesondesigninge ectiveservicedisciplinesinnetworkswitchesandthenlettingendhostsdowhateverisintheirownbestinterest.Thisapproach,withitsemphasisonindividualincentives,doesnot tthetypicalparadigmusedinthestudyofdistributedsystems.Ifusersarenotfollowingsomecentrallymandatedalgorithm,howcanonemodeluserbehavior?Howcanonedescribetheeventualnetworkoperatingpointinsuchnoncooperativesystems?Ifusersareactingtofurthertheirowninterests,ratherthanthatofthesystem,bywhatcriteriadoesoneevaluatetheresultingsystem-widebehavior?Thesequestions,whichinvolveindividualincentivesinafundamentalway,arelargelyforeigntocomputerscience;however,theyaretheverycoreofgametheory.Thepurposeofthispaperistoillustratehowgametheorycanbeusedtoformulateandanswer,atleastonatheoreticallevel,theseincentivequestions.Otherthanreviewingsomeoftheargumentsbrie yinSection2.2,wearenotrevisitingthebasicdebatebetweenthetwoapproachestocongestioncontrol.Rather,wearemerelyexhibitinghowonecanformalizeandanalyzethissecondapproachusingagame-theoreticperspective.Wewillapplythisgame-theoreticperspectivetoaverysimplesystem:asingleswitchsharedbyNusers.EachusersendsaPoissonstreamofpacketsthroughtheswitch.Therateofthei’thuser’sPoissonstreamisdenotedbyri;thealgorithmbywhichtheusercontrolsthisrateiscalledthe owcontrolalgorithm.Theswitchisservicedbyanexponentialserverwithpreemption.3Onemeasureofthecongestionexperiencedbyauseristheaveragenumberofthatuser’spacketsthat2Thetermuserhereispurposelyambiguous.Whilethehumanuserultimatelycontrolstheimplementationsusedonthenetworkdevice,itisthedevicewhichtypicallycontrolsthenetworkbehaviorintheshortterm.Toavoidcontinuallytrippingoverthisdistinction,wewillusethe
本文标题:Making greed work in networks A game-theoretic ana
链接地址:https://www.111doc.com/doc-3354343 .html