搜索
AachenDepartmentofComputerScienceTechnicalReportAdaptiveRoutingwithStaleInformationSimonFischerandBertholdV¨ockingISSN0935–3232·AachenerInformatikBerichte·AIB-2005-06RWTHAachen·DepartmentofComputerScience·April2005ThepublicationsoftheDepartmentofComputerScienceofRWTHAachenUniversityareingeneralaccessiblethroughtheWorldWideWeb.⋆SimonFischerandBertholdV¨ockingDepartmentofComputerScience,RWTHAachenUniversity,52056Aachen,Germany{fischer,voecking}@cs.rwth-aachen.deAbstract.Weinvestigateadaptiveroutingpoliciesforlargenetworksinwhichagentsreroutetrafficbasedonoldinformation.Itisawellknownandpracti-callyrelevantproblemthatoldinformationcanleadtoundesirableoscillationeffectsresultinginpoorperformance.Weinvestigatehowadaptiveroutingpoli-ciesshouldbedesignedsuchthattheseeffectscanbeavoided.Inourtheoreticalmodel,thenetworkisrepresentedbyageneralgraphwithlatencyfunctionsontheedges.Trafficismanagedbyalargenumberofagentseachofwhichisresponsibleforanegligibleamountoftraffic.Initiallytheagents’routingpathsarechoseninanarbitraryfashion.Fromtimetotimeeachagentrevisesherroutingstrategybysamplinganotherpathandswitchingwithpositiveprobabilitytothispathifitpromisessmallerlatencies.Astheinformationonwhichtheagentbasesherdecisionmightbestale,however,thisdoesnotneces-sarilyleadtoanimprovement.ThepointsoftimeatwhichagentsrevisetheirstrategyaregeneratedbyaPoissondistribution.Staleinformationismodelledinformofabulletinboardthatisupdatedperiodicallyandliststhelatenciesonalledges.Weanalyzesuchadistributedroutingprocessintheso-calledfluidlimit,thatis,weusedifferentialequationsdescribingthefractionsoftrafficondifferentpathsovertime.Inourmodel,wecanshowthefollowingeffects.Simpleroutingpoli-ciesthatalwaysswitchtothebetteralternativeleadtooscillation,regardlessatwhichfrequencythebulletinboardisupdated.Oscillationeffectscanbeavoided,however,whenusingsmoothadaptionpoliciesthatdonotalwaysswitchtobet-teralternativesbutonlywithaprobabilitydependingontheadvantageinthelatency.Infact,suchpolicieshavedynamicsthatconvergetoafixedpointcor-respondingtoaNashequilibriumfortheunderlyingroutinggame,providedtheupdateperiodsarenottoolarge.Inaddition,wealsoanalyzethespeedofconvergencetowardsapproximateequi-libriaoftwospecificvariantsofsmoothadaptiveroutingpolicies,e.g.,forareplicationpolicyadoptedfromevolutionarygametheory.Keywords:adaptiverouting,staleinformation,(evolutionary)gametheory1IntroductionWestudyaroutinggamefornetworksdefinedbygeneralgraphswhereinfinites-imallysmallpiecesoftrafficaremanagedbyselfishagentseachofwhichaimsatminimizingherownlatency.Incontrasttomostpreviousstudiesforthiskindofgame,wedonotpresumethatfullyrationalbehavioroftheagentsnecessarilyleadstoaso-calledWardropequilibrium.Insteadwestudythequestionofhowtheagentsshouldbehavesuchthatthegame(quickly)convergestosuchanequi-librium.Usingwell-knownpotentialfunctionargumentsknownfromtheanalysisofcongestiongamesonecanshowthatsimplebestorbetterresponsepoliciesinwhichagentsmovetheirtrafficfromslowertofasterroutingpathsleadinfactto⋆SupportedinpartbytheEUwithinthe6thFrameworkProgrammeundercontract001907(DELIS)andbyDFGgrantVo889/1-2.aWardropequilibrium.Thiskindofconvergenceresult,however,requiresthatagentsalwayshaveavailablethemostrecentinformationaboutthelatenciesandcanreactinstantaneouslytothisinformation.Thisassumption,however,seemsbeproblematichavinginmindreal-worldtrafficorcommunicationnetworks.Inthispaper,weinvestigatehowagentsshouldbehaveiftheyhavetobasetheirdecisionsonpossiblystaleinformation.Inouranalysis,werepresentstaleinformationusingavariantofthebulletinboardmodelintroducedbyMitzen-macher[12]inthecontextofdynamicloadbalancing:Fromtimetotimeagentsreconsidertheirroutingstrategyandpossiblymaptheirtraffictoadifferentrout-ingpath.Thetimeintervalsbetweenthepointsatwhichagentsrethinktheirstrategyareexponentiallydistributed.Foreachindividualagent,thereconsid-erationpointsaregeneratedatacertainPoissonrate.Atthesepointsoftime,theagentcandecidetomaphertraffictoadifferentpathbasedoninformationpublishedonabulletinboard.Thisbulletinboarditvisibletoallagentsbutitdoesnotalwayscontainthemostrecentinformation.TheboardisupdatedfromtimetotimeatleastonceeveryTtimesteps.Usingthisadmittedlysimplisticmodelofstaleinformation,weobserveaphenomenonknownalsofrompracticalstudies,namelythatnaivebestandbetterresponsestrategiesdonotconvergetoanequilibriumbutresultinundesirableoscillationeffects[10,11,13,17].Thismotivatesustostudythequestionofhowagentsshouldbehaveinordertoavoidtheseeffects.Infact,wecanshowthatforeverysetofnon-decreasinglatencyfunctionswithfinitefirstderivativethereisapolicyfortheagentstoreroutetheirtrafficthatavoidsoscillationandguaranteesconvergencetotheWardropequilibrium.Ouradaptiveroutingpoliciesareinspiredbytheso-calledreplicatordynamicsknownfromevolutionarygametheory.Westudythesepoliciesinthefluidlimitevaluatingdifferentialequationsatdiscretetimesteps.WedonotonlyshowthattheconsidereddynamicsconvergetoaWardropequilibriumbutalsoanalyzethetimeofconvergencetowardsapprox