Selfish routing revisited: degeneracy, evolution and stochastic fluctuations

Panayotis Mertikopoulos 1 Aris L. Moustakas
1 MESCAL - Middleware efficiently scalable
Inria Grenoble - Rhône-Alpes, LIG - Laboratoire d'Informatique de Grenoble
Abstract : We study the traffic routing problem in networks whose users try to minimize their latencies by employing a distributed learning rule inspired by the replicator dynamics of evolutionary game theory. The stable states of these dynamics coincide with the network's (Wardrop) equilibrium points and we find that they form a convex polytope whose dimension is determined by the network's degeneracy index (an important concept which measures the overlap of the users' paths). Still, despite this abundance of stable states, we find that (almost) every solution trajectory converges to an equilibrium point at an exponential rate. On the other hand, a major challenge occurs when network latencies fluctuate unpredictably due to random exogenous factors. In that case, we show that the time-average of the traffic flows of sufficiently patient users is still concentrated in a neighborhood of evolutionarily stable equilibria and we estimate analytically the corresponding stationary distribution and convergence times.
Type de document :
Communication dans un congrès
ICST. ValueTools '11: ACM Proceedings of the 5th International Conference on Performance Evaluation Methodologies and Tools, 2011, Cargèse, France. pp.217-226, 2011, 〈http://dl.acm.org/ft_gateway.cfm?id=2151713&ftid=1153423&dwn=1&CFID=187087905&CFTOKEN=71869014〉
Liste complète des métadonnées

https://hal.inria.fr/hal-00788801
Contributeur : Arnaud Legrand <>
Soumis le : vendredi 15 février 2013 - 11:16:46
Dernière modification le : jeudi 8 novembre 2018 - 14:28:02

Identifiants

  • HAL Id : hal-00788801, version 1

Collections

Citation

Panayotis Mertikopoulos, Aris L. Moustakas. Selfish routing revisited: degeneracy, evolution and stochastic fluctuations. ICST. ValueTools '11: ACM Proceedings of the 5th International Conference on Performance Evaluation Methodologies and Tools, 2011, Cargèse, France. pp.217-226, 2011, 〈http://dl.acm.org/ft_gateway.cfm?id=2151713&ftid=1153423&dwn=1&CFID=187087905&CFTOKEN=71869014〉. 〈hal-00788801〉

Partager

Métriques

Consultations de la notice

210