On the Efficiency of Non-Cooperative Load Balancing

Josu Doncel (1) , Balakrishna Prabhu (1) , Olivier Brun (1) , Urtzi Ayesta (1)

1 LAAS-SARA - Équipe Services et Architectures pour Réseaux Avancés

Price of Anarchy is an oft-used worst-case measure of the inefficiency of non-cooperative decentralized architectures. In practice, though, the worst-case scenario may occur rarely, if at all. For non-cooperative decentralized load-balancing in server farms, we show that the Price of Anarchy is an overly pessimistic measure that does not reflect the performance obtained in most instances of the problem. In the case of two classes of servers, we show that non-cooperative load-balancing provides a close-to-optimal solution in most cases, and that the worst-case performance given by the Price of Anarchy occurs only in a very specific setting, namely, when the slower servers are infinitely more numerous and infinitely slower than the faster ones. We explicitly characterize the worst-case traffic conditions for the efficiency of non-cooperative load-balancing schemes, and show that, contrary to a common belief, the worst inefficiency is in general not achieved in heavy-traffic or close to saturation conditions.

Domaines: Recherche opérationnelle [math.OC]

Josu Doncel, Balakrishna Prabhu, Olivier Brun, Urtzi Ayesta. On the Efficiency of Non-Cooperative Load Balancing. IFIP Networking 2013, May 2013, Brooklyn, United States. 15p. ⟨hal-00768339⟩