Fair online load balancing

ABSTRACT

We revisit from a fairness point of view the problem of online load balancing in the restricted assignment model and the 1-∞ model. We consider both a job-centric and a machine-centric view of fairness, as proposed by Goel et al. [11]. These notions are equivalent to the approximate notion of prefix competitiveness proposed by Kleinberg, Rabani and Tardos [14], as well as to the notion of approximate majorization, and they generalize the well studied notion of max-min fairness.We resolve a question posed by Goel,Meyerson and Plotkin [11] proving that the greedy strategy is globally O(logm)-fair, where m denotes the number of machines. This result improves upon the analysis of [11] who showed that the greedy strategy is globally O(log n)-fair, where n is the number of jobs. Typically, n > m, and therefore our improvement is significant. Our proof matches the known lower bound for the problem with respect to the measure of global fairness.The improved bound is obtained by analyzing, in a more accurate way, the more general restricted assignment model studied previously in [6]. We provide an alternative bound which is not worse than the bounds of [6], and it is strictly better in many cases. The bound we prove is, in fact, much more general and it bounds the load on any prefix of most loaded machines. As a corollary from this more general bound we get that the greedy algorithm results in an assignment that is globally O(logm)-balanced. The last result generalizes the previous result of [11] who proved that the greedy algorithm yields an assignment that is globally O(logm)-balanced for the 1-∞ model.

REFERENCES

• 1: Miriam Allalouf and Yuval Shavitt. Maximum flow routing with weighted max-min fairness. In First International Workshop on QoS Routing (WQoSR), 2004.
• 2: Javed Aslam , April Rasala , Cliff Stein , Neal Young, Improved bicriteria existence theorems for scheduling, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.846-847, January 17-19, 1999, Baltimore, Maryland, United States
• 3: 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]
• 4: Yossi Azar, On-line Load Balancing, Developments from a June 1996 seminar on Online algorithms: the state of the art, p.178-195, January 1998
• 5: Yossi Azar , Leah Epstein , Yossi Richter , Gerhard J. Woeginger, All-norm approximation algorithms, Journal of Algorithms, v.52 n.2, p.120-133, August 2004 [doi>10.1016/j.jalgor.2004.02.003]
• 6: Yossi Azar , Joseph Seffi Naor , Raphael Rom, The competitiveness of on-line assignments, Journal of Algorithms, v.18 n.2, p.221-237, March 1995 [doi>10.1006/jagm.1995.1008]
• 7: Dimitri Bertsekas , Robert Gallager, Data networks, Prentice-Hall, Inc., Upper Saddle River, NJ, 1987
• 8: N. Buchbinder and J. Naor. A primal-dual approach to online routing and packing. In Manuscript, 2006.
• 9: John E. Littlewood Godfrey H. Hardy and George P'olya. Some simple inequalities satisfied by convex functions. In Messenger Math, pages 58:145--152, 1929.
• 10: Ashish Goel and Adam Meyerson. Simultaneous optimization via approximate majorization for concave profits or convex costs. 2005.
• 11: Ashish Goel , Adam Meyerson , Serge Plotkin, Approximate majorization and fair online load balancing, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.384-390, January 07-09, 2001, Washington, D.C., United States
• 12: Ashish Goel , Adam Meyerson , Serge Plotkin, Combining fairness with throughout: online routing with multiple objectives, Journal of Computer and System Sciences, v.63 n.1, p.62-79, August 2001 [doi>10.1006/jcss.2001.1755]
• 13: J.M. Jaffe. Bottleneck flow control. IEEE Transactions on Communications, 29(7):954--962, 1981.
• 14: Jon Kleinberg , Eva Tardos , Yuval Rabani, Fairness in Routing and Load Balancing, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.568, October 17-18, 1999
• 15: A. Kumar , J. Kleinberg, Fairness measures for resource allocation, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.75, November 12-14, 2000
• 16: R. K. lain, Dab-Ming Chiu, and William Howe. A quantitative measure of fairness and discrimination for resource allocation in shared systems. In DEC Res. Rep. TR-301, 1984.
• 17: A. W. Marshal and I. Olkin. Inequalities: Theory of majorization and its applications. In volume 143 of Mathematics in Science and Engineering. Academic Press, New York, 1979.
• 18: Clifford Stein , Joel Wein, On the Existence of Schedules that are Near-Optimal for both Makespan and Total Weighted Completion time, Dartmouth College, Hanover, NH, 1996

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.0 General

Additional Classification:
  G. Mathematics of Computing
  G.0 GENERAL

General Terms:
Algorithms, Theory

Keywords:
competitive analysis, greedy algorithm, load balancing, online algorithms, scheduling