A Hierarchical Load Balancing Policy for Grid Computing Environment

Full Text (PDF, 580KB), PP.1-12

Views: 0 Downloads: 0


Said Fathy El-Zoghdy 1,*

1. Computer Science Dep., College of Computers & Information Technology, Taif University, Taif, KSA

* Corresponding author.

DOI: https://doi.org/10.5815/ijcnis.2012.05.01

Received: 23 Jul. 2011 / Revised: 2 Nov. 2011 / Accepted: 17 Jan. 2012 / Published: 8 Jun. 2012

Index Terms

Grid Computing, Resource Management, Load Balancing, Performance Evaluation, Queuing Theory


With the rapid development of high-speed wide-area networks and powerful yet low-cost computational resources, grid computing has emerged as an attractive computing paradigm. It provides resources for solving large scientific applications. It is typically composed of heterogeneous resources such as clusters or sites at different administrative domains connected by networks with widely varying performance characteristics. The service level of the grid software infrastructure provides two essential functions for workload and resource management. To efficiently utilize the resources at these environments, effective load balancing and resource management policies are fundamentally important. This paper addresses the problem of load balancing and task migration in grid computing environments. We propose a fully decentralized two-level load balancing policy for computationally intensive tasks on a heterogeneous multi-cluster grid environment. It resolves the single point of failure problem which many of the current policies suffer from. In this policy, any site manager receives two kinds of tasks namely, remote tasks arriving from its associated local grid manager, and local tasks submitted directly to the site manager by local users in its domain, which makes this policy closer to reality and distinguishes it from any other similar policy. It distributes the grid workload based on the resources occupation ratio and the communication cost. The grid overall mean task response time is considered as the main performance metric that need to be minimized. The simulation results show that the proposed load balancing policy improves the grid overall mean task response time.

Cite This Paper

Said Fathy El-Zoghdy,"A Hierarchical Load Balancing Policy for Grid Computing Environment", International Journal of Computer Network and Information Security(IJCNIS), vol.4, no.5, pp.1-12, 2012. DOI:10.5815/ijcnis.2012.05.01


[1]B. Yagoubi and Y. Slimani, "Task Load Balancing Strategy for Grid Computing", Journal of Computer Science, vol. 3, no. 3: pp. 186-194, 2007.
[2]I. Foster and C. Kesselman (editors), " The Grid2: Blueprint for a New Computing Infrastructure", Morgan Kaufmann Puplishers, 2nd edition, USA, 2004.
[3]K. Lu, R. Subrata, and A. Y. Zomaya,"On The Performance-Driven Load Distribution For Heterogeneous Computational Grids", Journal of Computer and System Science, vol. 73, no. 8, pp. 1191-1206, 2007.
[4]Paritosh Kumar, "Load Balancing and Job Migration in Grid Environment", MS. Thesis, THAPAR UNIVERSITY, 2009.
[5]K. Li, "Optimal load distribution in nondedicated heterogeneous cluster and grid computing environments", Journal of Systems Architecture, vol. 54, pp. 111–123, 2008.
[6]S. Parsa and R. Entezari-Maleki ," RASA: A New Task Scheduling Algorithm in Grid Environment", World Applied Sciences Journal 7 (Special Issue of Computer & IT), pp. 152-160, 2009
[7]Y. Li, Y. Yang, M. Ma, and L. Zhou, "A hybrid load balancing strategy of sequential jobs for grid computing Environments", Future Generation Computer Systems, vol. 25, pp.) 819_828, 2009.
[8]S. F. El-Zoghdy, A capacity-based load balancing and job migration algorithm for heterogeneous Computational grids, International Journal of Computer Networks & Communications (IJCNC) Vol.4, No.1, pp. 113-125, 2012.
[9]S. F. El-Zoghdy, H. Kameda, and J. Li, A comparative study of static and dynamic individually optimal load balancing policies, Proc. of the IASTED Inter. Conf. on Networks, Parallel and Distributed Processing and Applications, pp. 200-205. 2002.
[10]H. Kameda, J. Li, C. Kim, and Y. Zhang, "Optimal Load Balancing in Distributed Computer Systems", Springer, London, 1997.
[11]S. K. Goyal, Adaptive and dynamic load balancing methodologies for distributed environment: a review, International Journal of Engineering Science and Technology (IJEST), Vol. 3 No. 3, pp. 1835-1840, 2011.
[12]Malarvizhi Nandagopal and Rhymend V. Uthariaraj, Hierarchical Status Information Exchange Scheduling and Load Balancing For Computational Grid Environments, IJCSNS International Journal of Computer Science and Network Security, VOL.10 No.2, pp. 177-185, 2010.
[13]J. Balasangameshwara, N. Raju, " A Decentralized Recent Neighbour Load Balancing Algorithm for Computational Grid", Int. J. of ACM Jordan, vol. 1,no. 3, pp. 128-133, 2010.
[14]E. Saravanakumar and P. Gomathy," A novel load balancing algorithm for computational grid", Int. J. of Computational Intelligence Techniques, vol. 1, no. 1, 2010.
[15]O. Beaumont, A. Legrand, L. Marchal and Y. Robert. Steady-State Scheduling on Heterogeneous Clusters. Int. J. of Foundations of Computer Science, Vol. 16, No.2,pp. 163-194, 2005.
[16]R. Sharma, V. K. Soni, M. K. Mishra, and P. Bhuyan, A survey of job scheduling and resource management in grid computing, World Academy of Science, Engineering and Technology, 64, pp.461-466, 2010.
[17]Grosu, D., and Chronopoulos, A.T.: Noncooperative load balancing in distributed systems. J. Parallel Distrib. Comput. 65(9), pp. 1022–1034, 2005.
[18]Penmatsa, S., and Chronopoulos, A.T.: Job allocation schemes in computational Grids based on cost optimization. In: Proc. of 19th IEEE Inter. Parallel and Distributed Processing Symposium, Denver, 2005.
[19]N.Malarvizhi, and V.Rhymend Uthariaraj , "A New Mechanism for Job Scheduling in Computational Grid Network Environments", Proc. of 5th Inter. Conference on Active Media Technology , vol. 5820 of Lecture Notes in Computer Science, Springer, 2009,pp. 490-500.
[20]H. Johansson and J. Steensland, "A performance characterization of load balancing algorithms for parallel SAMR applications," Uppsala University, Department of Information Technology, Tech. Rep. 2006- 047, 2006.
[21]A. Touzene, S. Al Yahia, K.Day, B. Arafeh, "Load Balancing Grid Computing Middleware", IASTED Inter. Conf. on Web Technologies, Applications, and Services, 2005.
[22]Zikos, S., Karatza, H.D., 2008. Resource allocation strategies in a 2-level hierarchical grid system. In: Proceedings of the 41st Annual Simulation Symposium (ANSS), April 13–16, 2008. IEEE Computer Society Press, SCS, pp. 157–164.
[23]A. Touzene, H. Al Maqbali, "Analytical Model for Performance Evaluation of Load Balancing Algorithm for Grid Computing", Proc. of the 25th IASTED Inter. Multi-Conference: Parallel and Distributed Computing and Networks, pp. 98-102, 2007.
[24]N. Malarvizhi, and V.Rhymend Uthariaraj, "Hierarchical Load Balancing Scheme for Computational Intensive Jobs in Grid Computing Environment", in Proc. Int. Conf on Advanced Computing, India, Dec 2009, pp. 97-104.
[25]C. K. Pushpendra, and S. Bibhudatta, Dynamic load distribution algorithm performance in heterogeneous distributed system for I/O- intensive task, TENCON 2008, IEEE Region 10 Conference,19-21 Nov. 2008, pp.1 – 5.
[26]Raj Jain," The Art of Computer System Performance Analysis", John Wiley & Sons, Inc, 1991.
[27]Y. ZHU, "A survey on grid scheduling systems", Technical report, Department of Computer Science, Hong Kong University of Science and Technology, 2003.
[28]R. Buyya, "A grid simulation toolkit for resource modelling and application scheduling for parallel and distributed computing", www.buyya.com/gridsim/