| | This Article | |
| |
| |
| | Share | |
| |
| |
| | Bibliographic References | |
| |
| |
| | Add to: | |
| |
 Digg
 Furl
 Spurl
 Blink
 Simpy
 Google
 Del.icio.us
 Y!MyWeb
| |
| | Search | |
| |
| |
| | |
Design and Performance Evaluation of Queue-and-Rate-Adjustment Dynamic Load Balancing Policies for Distributed Networks
November 2006 (vol. 55 no. 11)
pp. 1410-1422
In this paper, we classify the dynamic distributed load balancing algorithms for heterogenous distributed computer systems into three policies: Queue Adjustment Policy (QAP), Rate Adjustment Policy (RAP), and Queue and Rate Adjustment Policy (QRAP). We propose two efficient algorithms, referred to as Rate-based Load Balancing via Virtual Routing (RLBVR) and Queue-based Load Balancing via Virtual Routing (QLBVR), which belong to the above RAP and QRAP policies, respectively. We also consider algorithms Estimated Load Information Scheduling Algorithm (ELISA) and Perfect Information Algorithm, which were introduced in the literature, to implement QAP policy. Our focus is to analyze and understand the behaviors of these algorithms in terms of their load balancing abilities under varying load conditions (light, moderate, or high) and the minimization of the mean response time of jobs. We compare the above classes of algorithms by a number of rigorous simulation experiments to elicit their behaviors under some influencing parameters, such as load on the system and status exchange intervals. We also extend our experimental verification to large scale cluster systems such as a Mesh architecture, which is widely used in real-life situations. From these experiments, recommendations are drawn to prescribe the suitability of the algorithms under various situations.
[1] L. Anand, D. Ghose, and V. Mani, “ELISA: An Estimated Load Information Scheduling Algorithm for Distributed Computing System,” Computers and Math. with Applications, vol. 37, pp. 57-85, 1999.
[2] D. Evans and W. Butt, “Dynamic Load Balancing Using Task-Transfer Probabilities,” Parallel Computing, vol. 19, pp. 279-301, 1993.
[3] C. Walshaw and M. Berzins, “Dynamic Load-Blancing for PDE Solvers on Adaptive Unstructured Meshes,” Concurrency: Practice and Experience, vol. 7, pp. 17-28, 1995.
[4] Y. Zhang, K. Hakozaki, H. Kameda, and K. Shimizu, “A Performance Comparison of Adaptive and Static Load Balancing in Heterogeneous Distributed Systems,” Proc. IEEE 28th Ann. Simulation Symp., pp. 332-340, Apr. 1995.
[5] Y. Amir, B. Awerbuch, A. Barak, R.S. Borgstrom, and A. Keren, “An Opportunity Cost Approach for Job Assignment in a Scalable Computing Cluster,” IEEE Trans. Parallel and Distributed Systems, vol. 11, no. 7, pp. 760-768, July 2000.
[6] J. Watts and S. Taylor, “A Practical Approach to Dynamic Load Balancing,” IEEE Trans. Parallel and Distributed Systems, vol. 9, no. 3, pp. 235-248, Mar. 1998.
[7] L. Fratta, M. Gerla, and L. Kleinrock, “The Flow Deviation Network Design,” Networks, vol. 3, pp. 97-133, 1973.
[8] D. Grosu and A.T. Chronopoulos, “A Game-Theoretic Model and Algorithm for Load Balancing in Distributed Systems,” Proc. 16th Int'l Parallel & Distributed Symp., Apr. 2002.
[9] M. Mitzenmacher, “The Power of Two Choices in Randomized Load Balancing,” IEEE Trans. Parallel and Distributed Systems, vol. 12, no. 10, pp. 1094-1104, Oct. 2001.
[10] M. Mitzenmacher, “How Useful Is Old Information?” IEEE Trans. Parallel and Distributed Systems, vol. 11, no. 1, pp. 6-20, Jan. 2000.
[11] J. Li and H. Kameda, “Load Balancing Problems for Multiclass Jobs in Distributed/Parallel Computer Systems,” IEEE Trans. Computers, vol. 47, no. 3, pp. 322-332, Mar. 1998.
[12] A.N. Tantawi and D. Towsley, “Optimal Static Load Balancing in Distributed Computer Systems,” J. ACM, vol. 32, no. 2, pp. 445-465, Apr. 1985.
[13] J. Li and H. Kameda, “Optimal Static Load Balancing of Multi-Class Jobs in a Distributed Computer System,” Proc. 10th Int'l Conf. Distributed Computing Systems, pp. 562-569, 1990.
[14] A.E. Kostin, I. Aybay, and G. Oz, “A Randomized Contention-Based Load-Balancing Protocol for a Distributed Multiserver Queuing System,” IEEE Trans. Parallel and Distributed Systems, vol. 11, no. 12, Dec. 2000.
[15] F.E. Beichelt and L.P. Fatti, Stochastic Processes and Their Application. Taylor & Francis, 2002.
[16] D. Bertsekas and R. Gallager, Data Networks. Prentice-Hall, 1992.
[17] Z. Zeng and V. Bharadwaj, “A Static Load Balancing Algorithm via Virtual Routing,” Proc. Conf. Parallel and Distributed Computing and Systems (PDCS '03), Nov. 2003.
[18] M. Avriel, Nonlinear Programming Analysis and Methods. Prentice-Hall, 1997.
[19] N.U. Prabhu, Foundations of Queuing Theory. Kluwer Academic, 1997.
[20] Y. Zhang, H. Kameda, and K. Shimizu, “Adaptive Bidding Load Balancing Algorithms in Heterogeneous Distributed Systems,” Proc. IEEE Second Int'l Workshop Modeling, Analysis, and Simulation of Computer and Telecomm. Systems, pp. 250-254, Jan. 1994.
[21] O. Akay and K. Erciyes, “A Dynamic Load Balancing Model for a Distributed System,” Math. and Computational Applications, vol. 8, nos. 1-3, pp. 353-360, 2003.
[22] http://www.top500.org/ORSC/1997paragon.html, 1997.
[23] Y. Zhang, H. Franke, J. Moreira, and A. Sivasubramaniam, “An Integrated Approach to Parallel Scheduling Using Gang-Scheduling, Backfilling, and Migration,” IEEE Trans. Parallel and Distributed Systems, vol. 14, no. 3, pp. 236-247, Mar. 2003.
[24] E. Choi, “Performance Test and Analysis for an Adaptive Load Balancing Mechanism on Distributed Server Cluster Systems,” Future Generation Computer Systems, vol. 20, pp. 237-247, 2004.
[25] Z. Zeng and V. Bharadwaj, “Design and Analysis of a Non-Preemptive Decentralized Load Balancing Algorithm for Multi-Class Jobs in Distributed Networks,” Computer Comm., vol. 27, pp.679-694, 2004.
[26] M.H. McDougall, Simulating Computer Systems. MIT Press, 1987.
Index Terms:
Dynamic load balancing, cluster or distributed computer system, mean response time, queuing theory, status exchange interval.
Citation:
Zeng Zeng, Bharadwaj Veeravalli, "Design and Performance Evaluation of Queue-and-Rate-Adjustment Dynamic Load Balancing Policies for Distributed Networks," IEEE Transactions on Computers, vol. 55, no. 11, pp. 1410-1422, Nov. 2006, doi:10.1109/TC.2006.180
