Online client-server load balancing without global information

ABSTRACT

We consider distributed online algorithms for maximizing through-put in a network of clients and servers, modeled as a bipartite graph. Unlike most prior work on online load balancing, we do not assume centralized control and seek algorithms and lower bounds for decentralized algorithms in which each participant has only local knowledge about the state of itself and its neighbors. Our problem can be seen as analogous to the recent work on oblivious routing in [8, 14, 19], but with the objective of maximizing through-put rather than minimizing congestion. In contrast to that work, we prove a strong lower bound (polynomial in n, the size of the graph) on the competitive ratio of any oblivious algorithm. This is accompanied by simple algorithms achieving upper bounds which are tight in terms of k, the maximum throughput achievable by an omniscient algorithm. Finally, we examine a restricted model in which clients, upon becoming active, must remain so for at least log(n) time steps. In contrast to the primarily negative results in the oblivious case, here we present an algorithm which is constant-competitive. Our lower bounds justify the intuition, implicit in earlier work on the subject [2], that some such restriction (i.e. requiring some stability in the demand pattern over time) is necessary in order to achieve a constant --- or even polylogarithmic --- competitive ratio.

REFERENCES

• 1: James Aspnes , Yossi Azar , Amos Fiat , Serge Plotkin , Orli Waarts, On-line routing of virtual circuits with applications to load balancing and machine scheduling, Journal of the ACM (JACM), v.44 n.3, p.486-504, May 1997 [doi>10.1145/258128.258201]
• 2: B. Awerbuch and Y. Azar, Local optimization of global objectives: Competitive distributed deadlock resolution and resource allocation, in Proc. 35th IEEE Symposium on Foundations of Computer Science, 1994, pp. 240--249.
• 3: B. Awerbuch, Y. Azar, and S. Plotkin, Throughput competitive on-line routing, in Proc. 34th IEEE Symposium on Foundations of Computer Science, 1993, pp. 32--40.
• 4: B. Awerbuch and T. Leighton. A simple local-control approximation algorithm for multicommodity flow, in Proceedings of the 34th Annual Symposium on Foundations of Computer Science, 1993, pp. 459--468.
• 5: Baruch Awerbuch , Tom Leighton, Improved approximation algorithms for the multi-commodity flow problem and local competitive routing in dynamic networks, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.487-496, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195238]
• 6: Yossi Azar , Edith Cohen , Amos Fiat , Haim Kaplan , Harald Racke, Optimal oblivious routing in polynomial time, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780599]
• 7: Yair Bartal , John W. Byers , Danny Raz, Global Optimization Using Local Information with Applications to Flow Control, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.303, October 19-22, 1997
• 8: Marcin Bienkowski , Miroslaw Korzeniowski , Harald Räcke, A practical algorithm for constructing oblivious routing schemes, Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures, June 07-09, 2003, San Diego, California, USA [doi>10.1145/777412.777418]
• 9: E. Cohen, Approximate max flow on small depth networks, in Proc. 33rd IEEE Symposium on Foundations of Computer Science, 1992, pp. 648--658.
• 10: Naveen Garg , Jochen Koenemann, Faster and Simpler Algorithms for Multicommodity Flow and other Fractional Packing Problems., Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.300, November 08-11, 1998
• 11: Naveen Garg , Neal E. Young, On-Line End-to-End Congestion Control, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.303-312, November 16-19, 2002
• 12: Andrew V. Goldberg , Robert E. Tarjan, A new approach to the maximum-flow problem, Journal of the ACM (JACM), v.35 n.4, p.921-940, Oct. 1988 [doi>10.1145/48014.61051]
• 13: Mohammad T. Hajiaghayi , Robert D. Kleinberg , Tom Leighton , Harald Räcke, Oblivious routing on node-capacitated and directed graphs, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 14: Chris Harrelson , Kirsten Hildrum , Satish Rao, A polynomial-time tree decomposition to minimize congestion, Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures, June 07-09, 2003, San Diego, California, USA [doi>10.1145/777412.777419]
• 15: R M Karp , E Upfal , A Wigderson, Constructing a perfect matching is in random NC, Combinatorica, v.6 n.1, p.35-48, 1986 [doi>10.1007/BF02579407]
• 16: Michael Luby , Noam Nisan, A parallel approximation algorithm for positive linear programming, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.448-457, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167211]
• 17: Christos H. Papadimitriou , Mihalis Yannakakis, Linear programming without the matrix, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.121-129, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167127]
• 18: Serge A. Plotkin , David B. Shmoys , Éva Tardos, Fast approximation algorithms for fractional packing and covering problems, Mathematics of Operations Research, v.20 n.2, p.257-301, May 1995 [doi>10.1287/moor.20.2.257]
• 19: Harald Räcke, Minimizing Congestion in General Networks, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.43-52, November 16-19, 2002
• 20: Harald Räcke , Adi Rosén, Distributed online call control on general networks, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia