Path-independent load balancing with unreliable machines

ABSTRACT

We consider algorithms for load balancing on unreliable machines. The objective is to optimize the two criteria of minimizing the makespan and minimizing job reassignments in response to machine failures. We assume that the set of jobs is known in advance but that the pattern of machine failures is unpredictable. Motivated by the requirements of BGP routing, we consider path-independent algorithms, with the property that the job assignment is completely determined by the subset of available machines and not the previous history of the assignments. We examine first the question of performance measurement of path-independent load-balancing algorithms, giving the measure of makespan and the normalized measure of reassignments cost. We then describe two classes of algorithms for optimizing these measures against an oblivious adversary for identical machines. The first, based on independent random assignments, gives expected reassignment costs within a factor of 2 of optimal and gives a makespan within a factor of O (log m/log log m) of optimal with high probability, for unknown job sizes. The second, in which jobs are first grouped into bins and at most one bin is assigned to each machine, gives constant-factor ratios on both reassignment cost and makespan, for known job sizes. Several open problems are discussed.

REFERENCES

• 1: Gagan Aggarwal , Rajeev Motwani , An Zhu, The load rebalancing problem, Journal of Algorithms, v.60 n.1, p.42-59, July 2006 [doi>10.1016/j.jalgor.2004.10.002]
• 2: Susanne Albers, On randomized online scheduling, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509930]
• 3: M. Caesar and J. Rexford. BGP routing policies in ISP networks. IEEE Network Magazine, special issue on Interdomain Routing, Nov/Dev 2006.
• 4: R. Graham. Bounds for certain multi-processing anomalies. Bell Systems Technical Journal, 45:1563--1581, 1966.
• 5: R. Graham, E. Lawler, J. Lenstra, and A. Rinnooy Kan. Optimization and approximation in deterministic sequencing and scheduling: A survey. Annals of Discrete Mathematics, 5:287--326, 1979.
• 6: Timothy G. Griffin , F. Bruce Shepherd , Gordon Wilfong, The stable paths problem and interdomain routing, IEEE/ACM Transactions on Networking (TON), v.10 n.2, April 2002
• 7: B. Kalyanasundaram and K. Pruhs. Fault-tolerant real-time scheduling. Algorithmica, 28(1):125--144, 2000.
• 8: Bala Kalyanasundaram , Kirk R. Pruhs, Fault-Tolerant Scheduling, SIAM Journal on Computing, v.34 n.3, p.697-719, 2005 [doi>10.1137/S0097539794261799]
• 9: Joseph Leung , Laurie Kelly , James H. Anderson, Handbook of Scheduling: Algorithms, Models, and Performance Analysis, CRC Press, Inc., Boca Raton, FL, 2004
• 10: M. Mitzenmacher, A. W. Richa, and R. Sitaraman. The power of two random choices: A survey of techniques and results. In S. Rajasekaran, P. Pardalos, J. Reif, and J. Rolim, editors, Handbook of Randomized Computing, volume I, pages 255--305. Springer, 2001.
• 11: Martin Raab , Angelika Steger, "Balls into Bins" - A Simple and Tight Analysis, Proceedings of the Second International Workshop on Randomization and Approximation Techniques in Computer Science, p.159-170, October 08-10, 1998
• 12: Y. Rekhter , T. Li, A Border Gateway Protocol 4 (BGP-4), RFC Editor, 1995
• 13: J. F. Sibeyn. The sum of weighted balls. Technical Report RUU-CS-91-37, Department of Computer Science, Utrecht University, 1991.
• 14: Daniel D. Sleator , Robert E. Tarjan, Amortized efficiency of list update and paging rules, Communications of the ACM, v.28 n.2, p.202-208, Feb. 1985 [doi>10.1145/2786.2793]
• 15: João Luis Sobrinho, Network routing with path vector protocols: theory and applications, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany [doi>10.1145/863955.863963]
• 16: Lakshminarayanan Subramanian , Matthew Caesar , Cheng Tien Ee , Mark Handley , Morley Mao , Scott Shenker , Ion Stoica, HLP: a next generation inter-domain routing protocol, Proceedings of the 2005 conference on Applications, technologies, architectures, and protocols for computer communications, August 22-26, 2005, Philadelphia, Pennsylvania, USA
• 17: Hao Wang , Haiyong Xie , Yang Richard Yang , Avi Silberschatz Silberschatz , Li Erran Li , Yanbin Liu, Stable Egress Route Selection for Interdomain Traffic Engineering: Model and Analysis, Proceedings of the 13TH IEEE International Conference on Network Protocols, p.16-29, November 06-09, 2005 [doi>10.1109/ICNP.2005.39]