Dynamic selfish routing [Elektronische Ressource] / vorgelegt von Simon Fischer

Simon Fischer

Sujets

• Informatik

Informations

• Publié par: rheinisch-westfalischen_technischen_hochschule_-rwth-_aachen
• Publié le: 01 janvier 2007
• Nombre de lectures: 15
• Langue: English
• Poids de l'ouvrage: 2 Mo

Extrait

DYNAMIC SELFISH ROUTING
VonderFakultat¨ fur¨ Mathematik,InformatikundNaturwissenschaften
derRheinisch Westf alischen¨ TechnischenHochschuleAachenzur
ErlangungdesakademischenGradeseinesDoktorsder
NaturwissenschaftengenehmigteDissertation
vorgelegtvon
Diplom Informatiker
SIMON FISCHER
ausHagen
Berichter: Universitatspr¨ ofessorDr. BertholdVocking¨atspr¨Dr. PetriMah¨ onen¨
Tagdermundlichen¨ Prufung:¨ 13. Juni2007
DieseDissertationistaufdenInternetseitenderHochschulbibliothekonlineverfugbar¨ .DynamicSelfishRouting
SIMON FISCHER
Aachen•June2007ivAbstract
This thesis deals with dynamic, load adaptive rerouting policies in game
theoretic settings. In the Wardrop model, which forms the basis of our
dynamicpopulationmodel,eachofaninfinitenumberofagentsinjectsan
infinitesimalamountofflowintoanetwork,whichinturninduceslatency
on the edges. Each agent may choose from a set of paths and strives to
minimiseitssustainedlatencyselfishly. Populationstateswhicharestable
in that no agent can improve its latency by switching to another path are
referredtoasWardropequilibria.
A variety of results in this model have been obtained recently. Most
of these revolve around the price of anarchy, which measures the degrada
tionofperformanceduetotheselfishbehaviouroftheagentsascompared
to a centrally optimised solution. Most of these analyses consider the no
tion of Wardrop equilibria as a solution concept of selfish routing games,
but disregard the question of how such an equilibrium can be attained in
thefirstplace. Infact,commongametheoreticassumptionsneededforthe
motivationofequilibriaingeneralstrategicgamesarenotsatisfiedforrout
ing games in large networks, the Internet being the prime example. These
assumptions comprise accurate knowledge of the network and its latency
functionsaswellasunboundedrationalityandreasoningcapabilities. The
questionofhowWardropequilibriacanbeattainedbyapopulationofself
ishagentsisthecentraltopicofthisthesis.
Our first approach is inspired by evolutionary game theory. We show
thatWardropequilibriaactuallysatisfyastrongerstabilitycriterion,called
evolutionarystability,whichcanbemotivatedbymilderassumptions. We
modelapopulationofagentsfollowingsomeverysimplerandomisedself
ish rules allowing them to exchange their path for a better one from time
totime. Anagentsamplesanotherpathaccordingtosomeprobabilitydis
tribution and possibly exchanges its current path for the new one with a
probability that increases with the latency gain. The behaviour of such a
population over time can be described in terms of a system of differential
equations. For a concrete choice of probability distributions involved in
the above rules, these differential equations take the form of the so called
vreplicatordynamics. Asafirstresult,weshowthatapopulationfollowing
thisdynamicsconvergestowardsthesetofWardropequilibria.
This convergence result implicitly assumes perfect information in that
rerouting decisions made by other agents are observable by other agents
immediately. In communication networks, however, such rerouting deci
sions may be observed only with a delay. In both theory and practise, it
is known that rerouting decisions based on stale information may lead to
undesirableoscillationeffectswhichseriouslyharmperformance. Wecon
sideranextensionofourdynamicpopulationmodelinwhichinformation
isupdatedonlyatintervalsofagivenlength. Weshowthat,despiteofthis,
convergencetoWardropequilibriaisstillpossible. Foranyclassoflatency
functionswithboundedslopeandanyfiniteupdateperiodlength,policies
fromalargeclassconvergetowardsWardropequilibriaprovidedthatthey
satisfy a certain smoothness condition. This condition requires the migra
tion rate to be reduced by a factor that is reciprocal to the maximum slope
andtheupdateperiodlength.
Finally, we show that Wardrop equilibria can be approached quickly.
Thisisanissueofparticularimportanceifthenetworkortheflowdemands
themselves may change over time. To measure the speed of convergence,
we consider the time to reach approximate Wardrop equilibria. We show
that by applying a clever sampling technique it is possible to reach an ap
proximate Wardrop equilibrium in time polynomial in the approximation
qualityandtherepresentationlengthofthenetwork,e.g.,forpositivepoly
nomial latency functions in coefficient representation. In particular, our
bounds depend on the maximum slope of the latency functions only log
arithmically, which improves over earlier results in similar models which
dependlinearlyonthisparameter. Weshowthatthecrucialparameterthat
limitsthespeedofconvergenceisnottheslope, butrathertheelasticityof
the latency functions. This parameter is closely related to the degree of
polynomials.
Based on these positive theoretical results, we design a dynamic traf
fic engineering protocol which we evaluate by simulations. Our protocol
splits traffic bound for the same destination among alternative next hop
routersandcontinuouslyadjuststhesplittingratios. Thesimulationframe
workinvolvessignificantlymoredetailsthantheWardropmodeldoes. For
example,oursimulationsfeatureafullTCPimplementationatpacketlevel
andincluderealisticHTTPworkloadgeneratedonthebasisofrealisticsta
tistical properties of Web users. The simulation results are in good corre
spondence with theory. We see that our protocol in fact converges quickly
andsignificantlyimprovesthethroughputofanautonomoussystem.
viviiAcknowledgements
First of all, I thank Berthold Vocking¨ for being my advisor, not only with
respect to this thesis, for his clear sightedness, and for always knowing
what is important and what is not. I thank Petri Mah¨ onen¨ for his interest
inthisworkandforactingasaco referee.
IthankHaraldRacke,¨ NilsKammenhuber,andAnjaFeldmannforthepro
ductive collaboration and many inspiring discussions. I am particularly
grateful to Nils for introducing me to SSFNet, though this gratefulness is
kindofambivalent.
I also thank the whole team of Computer Science 1 at Aachen for the nice
working atmosphere, many interesting discussions, and also for assigning
me to exercise six of the BuK 2007 test. I am in debt to Lars Olbrich for
readingthroughearlyversionsofsomeoftheproofs.
Finally, I thank Gisela for her substantial support, in particular during the
lastfourweeksofwritingupthisthesis.
ThisresearchwassupportedbytheDFGSchwerpunktprogramm1126“Al
gorithmikgroßerundkomplexerNetzwerke”andpartiallybytheEUwithin
the6thFrameworkProgrammeundercontract001907(DELIS).
viiiTableofContents
1 Introduction 1
1.1 FoundationsofGameTheory . . . . . . . . . . . . . . . . . . 2
1.2 EvolutionaryGameTheory: AGuidedTour . . . . . . . . . . 5
1.2.1 TheFirstApproach: EvolutionaryGameDynamics . 6
1.2.2 TheSecondApproach: RefinedSolutionConcepts . . 12
1.2.3 Synthesis: ConvergenceTheorems . . . . . . . . . . . 17
1.2.4 RelatedWork . . . . . . . . . . . . . . . . . . . . . . . 20
1.3 SelfishRouting . . . . . . . . . . . . . . . . . . . . . . . . . . 20
1.3.1 TheWardropModel . . . . . . . . . . . . . . . . . . . 20
1.3.2 WardropEquilibria . . . . . . . . . . . . . . . . . . . . 22
1.3.3 TheBeckmann McGuire WinstenPotential . . . . . . 23
1.3.4 RelatedWork . . . . . . . . . . . . . . . . . . . . . . . 24
1.4 OutlineoftheThesis . . . . . . . . . . . . . . . . . . . . . . . 25
1.4.1 BibliographicalNotes . . . . . . . . . . . . . . . . . . 27
2 EvolutionofSelfishRouting 29
2.1 TheReplicatorDynamicsintheWardropModel . . . . . . . 30
2.1.1 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . 32
2.2 EvolutionaryStabilityandConvergence . . . . . . . . . . . . 33
2.2.1 EvolutionaryStability . . . . . . . . . . . . . . . . . . 33
2.2.2 ConvergenceforSingle CommodityInstances . . . . 34
2.2.3genceofMulti Commodity . . . . . 36
2.3 ApproximateEquilibriaandConvergenceTime . . . . . . . 37
2.3.1 UpperBoundforInstances . . . . 38
2.3.2forMulti Commodity . . . . 40
2.3.3 LowerBoundforSingle CommodityInstances . . . . 41
2.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
3 CopingwithStaleInformation 49
3.1 RelatedWork . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
3.2 SmoothReroutingPoliciesandStaleInformation . . . . . . . 51
3.2.1 SmoothReroutingPolicies . . . . . . . . . . . . . . . . 51
ixTABLEOFCONTENTS
3.2.2 StaleInformation . . . . . . . . . . . . . . . . . . . . . 54
3.3 StaleInformationMakesConvergenceHard . . . . . . . . . 55
3.3.1 ConvergenceUnderUp To DateInformation . . . . . 55
3.3.2 OscillationofBest Response . . . . . . . . . . . . . . 56
3.4 ConvergenceUnderStaleInformation . . . . . . . . . . . . . 57
3.5genceTime . . . . . . . . . . . . . . . . . . . . . . . . 63
3.5.1 UniformSampling . . . . . . . . . . . . . . . . . . . . 63
3.5.2 ProportionalSampling . . . . . . . . . . . . . . . . . . 65
3.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
4 FastConvergencebyExplorationandReplication 69
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
4.1.1 OurResults . . . . . . . . . . . . . . . . . . . . . . . . 70
4.1.2 RelatedWork . . . . . . . . . . . . . . . . . . . . . . . 72
4.1.3 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . 73
4.2 TheExploration ReplicationPo