The Price of Anarchy in Parallel Queues Revisited

Jonatha Anselmi 1, 2 Bruno Gaujal 2
2 MESCAL - Middleware efficiently scalable
Inria Grenoble - Rhône-Alpes, LIG - Laboratoire d'Informatique de Grenoble
Abstract : We consider a network of parallel, non-observable queues and analyze the Price of Anarchy (PoA) from the new point of view where the router has the memory of previous dispatching choices. In the regime where the demands grow with the network size, we provide an upper bound on the PoA by means of convex programming. To study the impact of non-Bernoulli routers, we introduce the Price of Forgetting (PoF) and prove that it is bounded from above by two. Numerical experiments show that the benefit of having memory in the router is independent of the network size and heterogeneity, and monotonically depends on the network load only.
Type de document :
Communication dans un congrès
ACM sigmetrics, 2010, New-York, United States. ACM, pp.353-354, 2010, 〈10.1145/1811039.1811083〉
Liste complète des métadonnées

https://hal.inria.fr/hal-00788887
Contributeur : Arnaud Legrand <>
Soumis le : vendredi 15 février 2013 - 13:11:27
Dernière modification le : mercredi 11 avril 2018 - 01:56:09

Identifiants

Collections

Citation

Jonatha Anselmi, Bruno Gaujal. The Price of Anarchy in Parallel Queues Revisited. ACM sigmetrics, 2010, New-York, United States. ACM, pp.353-354, 2010, 〈10.1145/1811039.1811083〉. 〈hal-00788887〉

Partager

Métriques

Consultations de la notice

189