On the Price of Anarchy and the Optimal Routing of Parallel non-Observable Queues

Jonatha Anselmi 1 Bruno Gaujal 1
1 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'', an index measuring the worst-case performance loss of a decentralized system with respect to its centralized counterpart. Our analysis is undertaken from the new point of view where the router has the memory of previous dispatching choices, which significantly complicates the nature of the problem. In the limiting regime where the demands proportionally grow with the network capacity, we provide a tight lower bound on the socially-optimal response time and a tight upper bound on the price of anarchy by means of convex programming. Then, we exploit this result to show, by simulation, that the billiard routing scheme yields a response time which is remarkably close to our lower bound, implying that billiards minimize response time. To study the added-value of non-Bernoulli routers, we introduce the ``price of forgetting'' and prove that it is bounded from above by two, which is tight in heavy-traffic. Finally, other structural properties are derived numerically for the price of forgetting. These claim that the benefit of having memory in the router is independent of the network size and heterogeneity, while monotonically depending on the network load only. These properties yield simple product-forms well-approximating the socially-optimal response time.
Type de document :
Rapport
[Research Report] 2010
Liste complète des métadonnées

Littérature citée [2 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00457603
Contributeur : Jonatha Anselmi <>
Soumis le : jeudi 18 février 2010 - 10:53:03
Dernière modification le : jeudi 11 octobre 2018 - 08:48:02
Document(s) archivé(s) le : jeudi 18 octobre 2012 - 15:20:32

Fichier

AnselmiGaujal.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00457603, version 1

Collections

Citation

Jonatha Anselmi, Bruno Gaujal. On the Price of Anarchy and the Optimal Routing of Parallel non-Observable Queues. [Research Report] 2010. 〈inria-00457603〉

Partager

Métriques

Consultations de la notice

383

Téléchargements de fichiers

113