Home | About us | Editorial board | Search | Ahead of print | Current issue | Archives | Submit article | Instructions | Subscribe | Contacts | Advertise | Login 
  Official website of M M University Mullana      
   


 
 
Table of Contents
ARTICLE
Year : 2011  |  Volume : 1  |  Issue : 2  |  Page : 70-73

An Adaptive Load Balancing Algorithm for Computational Grid


Department of Computer Engineering, M. M. Engineering College, M. M. University, Mullana, Ambala, Haryana, India

Date of Web Publication24-Oct-2011

Correspondence Address:
Manpreet Singh
Department of Computer Engineering, M. M. Engineering College, M. M. University, Mullana, Ambala, Haryana
India
Login to access the Email id

Source of Support: None, Conflict of Interest: None


DOI: 10.4103/0976-8580.86636

Rights and Permissions
   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

How to cite this URL:
Singh M, Goyal SK, Gupta V. An Adaptive Load Balancing Algorithm for Computational Grid. J Eng Technol [serial online] 2011 [cited 2019 Nov 14];1:70-3. Available from: http://www.onlinejet.net/text.asp?2011/1/2/70/86636


   1. Introduction Top


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 [1] . 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 [2] 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 [3] , 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 [1] . A lot of research has already been done in the field of grid environment related to load balancing. In [4] 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 [5] . 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 [6] , 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 [7] . In [8] , 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 [9] , 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 Top


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.
Figure 1: Computational grid model

Click here to view


The proposed algorithm for adaptive load balancing in computational grid is as follows:

  1. Input the value of number of Users (NU) and Resources (NR).
  2. Initialize the GridSim toolkit.
  3. Create the gridlength of each User.
  4. Get the availability of all registered Resources.
  5. Initialize the NextUser = 0 and QueueLength of each resource = 0.
  6. Find the resource 'R' with minimum QueueLength.
  7. Allocate the job of NextUser to R and Sub_Time_job = GridSim.Clock().
  8. NextUser = NextUser + 1.
  9. QueueLength_R = QueueLength_R + 1.
  10. Check for the arrival of any job 'J' from Resource 'R' after completing the execution.
  11. If no resource arrival exists then go to step 14.
  12. QueueLength_R = QueueLength_R-1.
  13. ExecutionTime_J = GridSim.Clock()-Sub_Time_J.
  14. If NextUser < = NU then go to step 6.
  15. Print ExecutionTime_J of all jobs.

   3. Sequence Diagram Top


  • Initially all resources register (REG) their information to GIS as shown in [Figure 2].
    Figure 2: Sequence diagram showing working of proposed algorithm

    Click here to view
  • 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 Top


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 1: Simulation parameters

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 5: Execution time at various resources when number of users = 25

Click here to view
Figure 6: Execution times at various resources when number of users = 50

Click here to view
Table 4: Execution time at various resources when number of users = 25

Click here to view
Table 5: 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 Top


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 Top

1.C. Xu, and F. Lau, "Load Balancing in Parallel Computers: Theory and Practice", Kluwer, Boston, MA, 1997.   Back to cited text no. 1
    
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.   Back to cited text no. 2
    
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.   Back to cited text no. 3
    
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.   Back to cited text no. 4
    
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.   Back to cited text no. 5
    
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.   Back to cited text no. 6
    
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.   Back to cited text no. 7
    
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.   Back to cited text no. 8
    
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.  Back to cited text no. 9
    

 
   Authors Top


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.


    Figures

  [Figure 1], [Figure 2], [Figure 3], [Figure 4], [Figure 5], [Figure 6]
 
 
    Tables

  [Table 1], [Table 2], [Table 3], [Table 4], [Table 5]


This article has been cited by
1 Optima l and Queuing Based Approach for Load Balancing In Computational Grid
Prakash Kumar, Pradeep Kumar, Vikas Kumar
International Journal of Computer Trends and Technology (IJCTT). 2013; 4(6): 1975-1980
[Pubmed] | [PDF] | [DOI]
2 Computational Grid System Load Balancing Using an Efficient Scheduling Technique
Prakash Kumar, Pradeep Kumar, Vikas Kumar
International Journal of Computer Trends and Technology (IJCTT). 2013; 4(8): 2501-2504
[VIEW] | [PDF] | [DOI]
3 G rouping - based Scheduling with Load Balancing for Fine - G rained J obs in G rid C omputing
Rabab Mohamed Ezzat,Amal Elsayed Aboutabl and Mostafa Sami Mostafa
(IJACSA) International Journal of Advanced Computer Science and Applications,. 2013; 4(11): 67-75
[VIEW] | [PDF]
4 Enhanced Genetic Algorithm Based Load Balancing in Grid
Sandip Kumar Goyal and Manpreet Singh
IJCSI International Journal of Computer Science Issues. 2012; 9(3)(2): 260-266
[VIEW] | [PDF] | [DOI]
5
. ;
[Pubmed] | [PDF]



 

Top
 
  Search
 
    Similar in PUBMED
   Search Pubmed for
   Search in Google Scholar for
 Related articles
    Access Statistics
    Email Alert *
    Add to My List *
* Registration required (free)  

 
  In this article
    Abstract
   1. Introduction
    2. The Adaptive ...
   3. Sequence Diagram
    4. Simulation Re...
   5. Conclusion
    References
    Authors
    Article Figures
    Article Tables

 Article Access Statistics
    Viewed3560    
    Printed328    
    Emailed1    
    PDF Downloaded1282    
    Comments [Add]    
    Cited by others 5    

Recommend this journal