Distributed algorithms for QoS load balancing

ABSTRACT

We consider a dynamic load balancing scenario in which users allocate resources in a non-cooperative and selfish fashion. The perceived performance of a resource for a user decreases with the number of users that allocate the resource. In our dynamic, concurrent model, users may reallocate resources in a round-based fashion. As opposed to various settings analyzed in the literature, we assume that users have quality of service (QoS) demands. A user has zero utility when falling short of a certain minimum performance threshold and having positive utility otherwise.

Whereas various load-balancing protocols have been proposed for the setting without quality of service requirements, we consider protocols that satisfy an additional locality constraint: The behavior of a user depends merely on the state of the resource it currently allocates. This property is particularly useful in scenarios where the state of other resources is not readily accessible. For instance, if resources represent channels in a mobile network, then accessing channel information may require time-intensive measurements.

We consider several variants of the model, where the quality of service demands may depend on the user, the resource, or both. For all cases we present protocols for which the dynamics converge to a state in which all users are satisfied. More importantly, the time to reach such a state scales nicely. It is only logarithmic in the number of users, which makes our protocols applicable in large-scale systems.

REFERENCES

• 1: Heiner Ackermann , Petra Berenbrink , Simon Fischer , Martin Hoefer, Concurrent imitation dynamics in congestion games, Proceedings of the 28th ACM symposium on Principles of distributed computing, August 10-12, 2009, Calgary, AB, Canada [doi>10.1145/1582716.1582732]
• 2: Petra Berenbrink , Tom Friedetzky , Leslie Ann Goldberg , Paul W. Goldberg , Zengjian Hu , Russell Martin, Distributed Selfish Load Balancing, SIAM Journal on Computing, v.37 n.4, p.1163-1181, September 2007 [doi>10.1137/060660345]
• 3: Petra Berenbrink, Tom Friedetzky, Iman Hajirasouliha, and Zengjian Hu. Convergence to equilibria in distributed, selfish reallocation processes with weighted tasks. In Proc. 15th Annual European Symposium on Algorithms (ESA), pages 41--52, 2007.
• 4: Eyal Even-Dar , Alex Kesselman , Yishay Mansour, Convergence time to Nash equilibrium in load balancing, ACM Transactions on Algorithms (TALG), v.3 n.3, p.32-es, August 2007 [doi>10.1145/1273340.1273348]
• 5: Eyal Even-Dar , Yishay Mansour, Fast convergence of selfish rerouting, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 6: Rainer Feldmann, Martin Gairing, Thomas Lücking, Burkhard Monien, and Manuel Rode. Nashification and the coordination ratio for a selfish routing game. In Proc. 30th Intl Colloquium on Automata, Languages and Programming (ICALP'03), pages 514--526, 2003.
• 7: Simon Fischer, Petri Mähönen, Marcel Schöngens, and Berthold Vöcking. Load balancing for dynamic spectrum assignment with local information for secondary users. In Proc. IEEE International Symposium on Dynamic Spectrum Access in Networks (DySPAN), 2008.
• 8: Simon Fischer, Lars Olbrich, and Berthold Vöcking. Approximating Wardrop equilibria with finitely many agents. Distributed Computing, 21(2):129--139, 2008. Special Issue DISC 2007.
• 9: Dimitris Fotakis , Alexis C. Kaporis , Paul G. Spirakis, Atomic Congestion Games: Fast, Myopic and Concurrent, Proceedings of the 1st International Symposium on Algorithmic Game Theory, April 30-May 02, 2008, Paderborn, Germany [doi>10.1007/978-3-540-79309-0_12]
• 10: Paul W. Goldberg, Bounds for the convergence rate of randomized local search in a multiplayer load-balancing game, Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, July 25-28, 2004, St. John's, Newfoundland, Canada [doi>10.1145/1011767.1011787]
• 11: Elias Koutsoupias and Christos Papadimitriou. Worst-case equilibria. In Proc. 16th International Symposium on Theoretical Aspects of Computer Science (STACS), pages 404--413, 1999.
• 12: Berthold Vöcking. Selfish load balancing. In Noam Nisan, Tim Roughgarden, Éva Tardos, and Vijay Vazirani, editors, Algorithmic Game Theory, chapter 20. Cambridge University Press, 2007.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.m Miscellaneous

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.m Miscellaneous

General Terms:
Algorithms, Design, Performance, Theory

Keywords:
dynamics, load balancing, quality of service