|Year : 2011 | Volume
| Issue : 2 | Page : 70-73
An Adaptive Load Balancing Algorithm for Computational Grid
Manpreet Singh, Sandip Kumar Goyal, Vishal Gupta
Department of Computer Engineering, M. M. Engineering College, M. M. University, Mullana, Ambala, Haryana, India
|Date of Web Publication||24-Oct-2011|
Department of Computer Engineering, M. M. Engineering College, M. M. University, Mullana, Ambala, Haryana
Source of Support: None, Conflict of Interest: None
| Abstract|| |
To improve the global throughput of computational grid, effective and efficient load balancing algorithms are fundamentally important. A computational grid differs from traditional high-performance computing system in the heterogeneity of computing nodes, as well as the communication links that connect the different nodes together. In this paper, we propose a resource queue length based solution to the grid load balancing problem. The proposed algorithm will balance the load in the grid based on the queue length of each resource and transfer the job to the resource having minimum queue length. The simulation results show that our algorithm can achieve a better load balancing performance than its counterpart provided in simulation.
Keywords: Grid computing, load balancing, queue length
|How to cite this article:|
Singh M, Goyal SK, Gupta V. An Adaptive Load Balancing Algorithm for Computational Grid. J Eng Technol 2011;1:70-3
| 1. Introduction|| |
The availability of low-cost powerful computers coupled with the popularity of the Internet and high-speed networks has led the computing environment to be mapped from classical distributed to grid environments  . To improve the global throughput of these environments, effective and efficient load balancing algorithms are fundamentally important. Emerging as new distributed computing environments, computational grids  provide an opportunity to share a large number of resources among different organizations. Performance enhancement is one of the most important issues in such grid systems. One obvious way of achieving this goal is to add more computing nodes to the grid. However, in many situations, poor performance is due to uneven load distribution among the nodes in the system. Therefore, to fully exploit the computing power of such grid systems, it is crucial to employ a judicious load balancing strategy for proper allocation and sequencing of tasks on the computing nodes. Load balancing algorithms in classical distributed systems, which usually run on homogeneous and dedicated resources, cannot work well in the grid architectures. Grids have a lot of specific characteristics  , like heterogeneity, autonomy and dynamicity, which remain obstacles for applications to harness conventional load balancing algorithms directly. Load balancing is a mapping strategy that efficiently equilibrates the task load into multiple computational resources in the network based on the system status to improve performance  . A lot of research has already been done in the field of grid environment related to load balancing. In  a computational grid is partitioned into multiple regional grids around well-known broker sites. A hybrid load balancing policy integrated static and dynamic techniques is employed to make efficient load balancing on each region and across regions. A load balancing model based on tree representation of a grid is proposed in  . It includes a hierarchical load balancing strategy which uses a task-level load balancing and privileges, as much as possible, a local load balancing to avoid the use of WAN communication. In  , authors analyze and compare the effectiveness of dynamic load balancing and job replication by means of trace-driven simulations. Agent-based approaches have been tried to provide load balancing in cluster of machines  . In  , authors propose a decentralized grid model as a collection of clusters and then introduce a dynamic load balancing algorithm (DLBA) which performs intra-cluster and inter-cluster (grid) load balancing. In  , authors present an efficient desirability-aware load balancing algorithm to tackle the new challenges in heterogeneous grid systems along with the simulation results.
In this paper, we propose an adaptive load balancing algorithm that can handle heterogeneous grid sites. Here, the heterogeneity only refers to the processing power of sites. The proposed algorithm will balance the load in the grid based on the queue length of each resource and transfer the job to the resource having minimum queue length. The proposed algorithm will be implemented using GridSim Toolkit.
| 2. The Adaptive Load Balancing Algorithm|| |
The computational grid comprises Grid Information Server (GIS), users and resources as shown in [Figure 1]. Each resource is a computational unit with different processing power. All resources and users register their information to GIS.
The proposed algorithm for adaptive load balancing in computational grid is as follows:
- Input the value of number of Users (NU) and Resources (NR).
- Initialize the GridSim toolkit.
- Create the gridlength of each User.
- Get the availability of all registered Resources.
- Initialize the NextUser = 0 and QueueLength of each resource = 0.
- Find the resource 'R' with minimum QueueLength.
- Allocate the job of NextUser to R and Sub_Time_job = GridSim.Clock().
- NextUser = NextUser + 1.
- QueueLength_R = QueueLength_R + 1.
- Check for the arrival of any job 'J' from Resource 'R' after completing the execution.
- If no resource arrival exists then go to step 14.
- QueueLength_R = QueueLength_R-1.
- ExecutionTime_J = GridSim.Clock()-Sub_Time_J.
- If NextUser < = NU then go to step 6.
- Print ExecutionTime_J of all jobs.
| 3. Sequence Diagram|| |
- Initially all resources register (REG) their information to GIS as shown in [Figure 2].
- Then all users send request (REQ) to GIS for Resource Characteristics.
- After that, GIS sends Resource Characteristics (RC) to each user.
- Now each user starts determining the queue length (DQL) of each resource and then sends gridlet to the resource having minimum queue length (QL).
- After gridlet execution is over, it is sent back to user sending that gridlet.
- When all gridlets' execution is over, each user prints execution time (ET) of gridlets.
| 4. Simulation Results|| |
In this section, we study the performance of proposed algorithm under different system parameters as described in [Table 1] via simulations using GridSim.
The execution time of jobs corresponding to different users using Adaptive Load Balancing Algorithm (ALBA) and Non-adaptive Load Balancing Algorithm (NALBA) is shown in [Table 2] and [Table 3], [Figure 3] and [Figure 4]. The graph shows that the execution time of jobs under NALBA is more than that of execution time of jobs with ALBA.
|Figure 3: Execution time of jobs of various users when number of resources = 3|
Click here to view
|Figure 4: Execution time of jobs of various users when number of resources = 5|
Click here to view
|Table 2: Execution time of jobs of various users when number of resources = 3|
Click here to view
|Table 3: Execution time of jobs of various users when number of resources = 5|
Click here to view
The execution time of jobs corresponding to different resources using ALBA and NALBA is shown in [Table 4] and [Table 5], [Figure 5] and [Figure 6]. The graph shows that execution time of jobs under ALBA is still less as compared to NALBA even when the number of resources is increased due to selection of only those resources which has minimum load.
|Figure 6: Execution times at various resources when number of users = 50|
Click here to view
The results show that ALBA is better than the NALBA in all scenarios.
| 5. Conclusion|| |
This paper has addressed the load balancing issues for jobs in computational grids. The effect of load balancing on job in terms of execution time is analyzed. Results show that the execution time of ALBA is less as every time the resource with minimum queue length is selected for execution as compared to the execution time with NALBA. The algorithm is tested under various load conditions in terms of job length varying from 10,000,000 to 750,000,000 (MI). The performance of ALBA is also better when the system is lightly loaded in terms of increasing the resources and keeping the number of user as fixed.
| References|| |
|1.||C. Xu, and F. Lau, "Load Balancing in Parallel Computers: Theory and Practice", Kluwer, Boston, MA, 1997. |
|2.||Y. Li, Y. Yang, and R. Zhu, "A Hybrid Load Balancing Strategy of Sequential Tasks for Computational Grids", International Conference on Networking and Digital Society (ICNDS), 2009. |
|3.||M. Baker, R. Buyya, and D. Laforenza, "Grids and Grid Technologies for Wide Area Distributed Computing", International Journal of Software: Practice and Experience (SPE), Vol. 32, no. 15, 2002. |
|4.||K. Lu, and A. Zomaya, "A Hybrid Policy for Job Scheduling and Load Balancing in Heterogeneous Computational Grids", Proceeding of 6th International Symposium on Parallel and Distributed Computing, pp. 19-26, 5 July 2007. |
|5.||B. Yagoubi, and M. Medebber, "A load balancing model for grid environment", Proceeding of 22 nd International Symposium on Computer and Information Sciences (ISCISC 2007), pp. 1-7, 7 November 2007. |
|6.||M. Dobber, R. Mei, and G. Koole, "Dynamic Load Balancing and Job Replication in a Global-Scale Grid Environment: A Comparison", IEEE Transaction on Parallel and Distributed Systems, Vol. 20, no. 2, pp. 207-218, February 2009. |
|7.||J. Cao, D. P. Spooner, S. A. Jarvi, and G. R. Nudd, "Grid Load Balancing Using Intelligent Agents", Future Generation Computer Systems, Vol. 21, no. 1, pp. 135-149, January 2005. |
|8.||P. K. Suri, and M. Singh, "An Efficient Decentralized Load Balancing Algorithm For Grid", IEEE 2 nd International Advance Computing Conference, pp. 10-13, February 2010. |
|9.||K. Lu, R. Subrata, and A. Zomaya, "An Efficient Load Balancing Algorithm for Heterogeneous Grid Systems Considering Desirability of Grid Sites", Journal of Computer and System Sciences, Vol. 73, no. 8, pp. 1191-1206, December 2006. |
| Authors|| |
Manpreet Singh is presently serving as Professor and Head, Information Technology Department of M. M. Engineering College, Mullana, Ambala. He has about 12 years of experience in teaching and research. He obtained his B. Tech., M. Tech. and Ph.D. from Kurukshetra University. He has published about 25 research papers in international and Indian journals and conferences. His current research interest includes Grid Computing, Cloud Computing, Distributed Databases, MANETs etc.
Sandip Kumar Goyal is presently serving as Assoc. Professor and Head, Computer Engineering Department of M.M. Engineering College, Mullana, Ambala. Sandip Kumar Goyal is in teaching since 2000. He has supervised several M.Tech and M.Phil Dissertations. He received his B.Tech. degree from Kurukshetra University, Kurukshetra, India in 1999, M.Tech. Degree from Kurukshetra University, Kurukshetra, India in 2006 and is currently enrolled as a Ph.D. scholar in the department of Computer Science and Engineering at M.M.University, Haryana, India. His research area is Adaptive and Dynamic Load balancing Methodologies in distributed environment.
Vishal Gupta is presently serving as Lecturer in Department of Computer Engineering at M. M. Engineering College, Mullana, Ambala. He has about 4 years of teaching experience. He obtained his B. Tech. from Kurukshetra University and M. Tech. from Maharishi Markandeshwar University. His current research interest includes Grid Computing and Cloud Computing.
[Figure 1], [Figure 2], [Figure 3], [Figure 4], [Figure 5], [Figure 6]
[Table 1], [Table 2], [Table 3], [Table 4], [Table 5]