- based on the previous works, we used the job migration technique for hierarchical load balancing. In this paper the authors propose a novel job migration algorithm for dynamic load balancing (JMADLB), in which parameters(such as CPU queue length) have been considered which is used for the selection of overloaded resources (or underloaded ones) in grid. . In dynamic load balancing state, the system will change dynamically until it reaches a balance. In a grid environment, efficiency of resources varies with time. Thus, the allocation of jobs must be adjusted dynamically in according with the variation of the resources status. The proposed algorithm has been verified through Alea2 simulator and the simulation results validate that the proposed algorithm allow us to reach our objectives.
I. INTRODUCTION
A computational Grid is a hardware and software
infrastructure that gives dependable, consistent, pervasive, and
cheap access to high-end computational capabilities [
The authors[
In the study of [
In this paper [
III. PROPOSED LOAD BALANCING ALGORITHM
The proposed Load Balancing implements three policies: Information Policy, selection Policy and location Policy. For implementation of Information Policy we use activity based approach. We use FIFO strategy For implementing the Selection Policy, for implementation of location policy We use as Load Index Queue Length. On the basis of Load Index Load Balancer decides to activate Load Balancing process.
Notations used in our algorithms are summarized and shown in Table I:
Depending on its current load, each cluster manager decides to start a Job Migration operation. In this case, the cluster manager tries, in priority, to balance its Load among its nodes. To implement this local load balancing, we propose the following algorithms:
We considered the load of node at given time was described simply by CPU queue length. it denotes the number of processes which are waiting to be executed.
Load (Qlength) = (Q1+Q2+……...+QT)/T Where:Q1,Q2,……...,QT is the value of Qlength in a previous one second interval.
gathering information algorithm
T 5 seconds Waiting for jobs; Create jobs queue for each node; For every Node N and in each one second of T intervals do
Calculate (Qlength); End For Load (Qlength)=(Q0+Q1+…..QT)/T; According to its period cluster manager receives Load informations from all nodes and compute load of cluster C associated.
Cluster manager Sends Load information of C to Grid manager
wait for load change // happening of any of defined events if (events_happens ()=1 or events_happens ()=4) then begin Remove terminated or migrated job from the waiting queue Subtract their load value from the total local load of node. Send new load to its cluster manager associated ; End if (events_happens ()=2 or events_happens ()=3) then begin Add the newly created or incoming job for the waiting queue Add their load value for the total local load of node Send new load to its cluster manager associated; End If ((events_happens () =6) and (events_happens () =7)) then begin ask the slowest resource to send a portion of its load to the idle resource .
End
output Type: integer begin If (Job.state=Termination) then events_happens () =1; If (Job.state=Start) then events_happens () =2; If (Job.state=Incoming Migrating ) then events_happens ()=3; If (Job.state = migrated) then events_happens ()=4; If (Arrival of any new resource) then events_happens ()=5; If(resouce.state= idle) then events_happens () =6; if(resource.state= slowest) then events_happens ()=7; if(cluster.state=saturated then events_happens ()=8; if (cluster.state=unbalanced) then events_happens ()=9; end
This algorithm classifies the nodes according to their load. it used three states for classifying: overloaded, underloaded and balanced. In the first time, we must calculate two threshold values for Qlength parameter.
The calculation of these thresholds is done as follow: Calculate load average of Qlength parameter over all nodes Loadavg(Qlength)=(load1+load2+….loadn)/nbr; Where Loadavg(Qlength) is the average load of Qlength over all nodes. load1,load2,….loadn are the current load of Qlength of each node calculated by Load estimation algorithm. nbr is the number of nodes.
The higher and lower threshold values of Qlength parameter are calculated by multiplying the average load of Qlength and a constant value.
THH=H*Loadavg THL=L* Loadavg
Where THH is the high threshold and THL is the low threshold
The next step is to partition the nodes for balanced, overloaded and underloaded nodes by using the threshold values as follow:
Overloaded : the node will be added for overloaded list if Qlength is high, that is mean if the number of jobs in the queue of node is high then the node is classified as overloaded node.
Underloaded: the resource will be added for underloaded list if Qlength is low. balanced :the node are not into overloaded list and underloaded list are the node in the balanced load state they are considered as more loaded than the low state and less loaded than the high state.
If(events_happens ()=8) then Inter-cluster load balancing algorithm somme 0; For every Node N of cluster C do
Somme Somme+ LoadN(Qlength) ; End For Loadavg(Qlength)= somme1/NBR-N; THH(Qlength)= Loadavg(Qlength)*H; THL(Qlength)= Loadavg(Qlength)*L; Partionning Nodes into overloaded list OLD-list , underloaded list ULD-list and balanced list BLD-list OLD-list ; ULD-list← ; BLD-list← ; For every Node N of cluster C do If (LoadN(Qlength) )>THH(Qlength) then
OLD-list ←OLD-list N; Else If (LoadR(Qlength) )< THL(Qlength)) then ULD-list ULD-list N
Else BLD-list BLD-list N; End If End For Sort OLD_list by descending order relative to their LoadN. Sort ULD_list by ascending order relative to Their LoadN. End.
After classifying the nodes, in the next step cluster manager decide to migrate jobs from overloaded to under-loaded nodes, it applies the following algorithm:
While (OLD-list ≠ .AND. ULD-list ≠ ) do For i = 1 To ULD-list.Size() do
Select job from queue of first node belonging to OLD-List by FCFS algorithm Migrate the selected job from first Sender node of OLD-List to ith receiver node of ULD-list; Update the current LoadN of receiver and sender nodes; Update OLD-list, ULD-list and BLD-list; Sort OLD-list by descending order of their LoadN;
End For End
This algorithm applies a global load balancing among all clusters of the Grid. The Inter-cluster load balancing at this level is made if a cluster manager fails to balance its Load among its associated nodes. In this case the grid manager migrates Jobs from overloaded clusters to under loaded clusters. We propose the following algorithms:
begin According to period T do Grid manager receives Load informations of clusters from its Cluster Managers .
Grid manager collect related informations of its clusters in the clusters information table; Grid manager partitions grid into overloaded (OLD), underloaded (ULD) and balanced (BLD) clusters; Create OLD_clusters_table; Create ULD_clusters_table; Sort clusters Cj of OLD_clusters_table by Descending order of their Load; For Every cluster Cj of OLD_clusters_table Do begin
Sort clusters Cr of ULD_clusters_table by Ascending order of their Load
Sort nodes of Cj by descending order of their Load While (OLD_clusters_table ≠ Φ AND ULD_clusters_table ≠ Φ) Do Begin
Sort the clusters Cr of ULD_clusters_table by ascending order of inter clusters (Ci-Cr) WAN bandwidth sizes.
Sort the nodes of Ci by descending order of their load Sort Jobs of first node of Ci by FCFS algorithm and communication cost Migrate the selected job from the first node of Ci to jth cluster of ULD_clusters_table Update the current Load of receiver cluster
Update ULD_clusters_table, and OLD_clusters_table End
In order to evaluate the feasibility and the performance of our algorithms we have tested them in Alea 2 Grid simulator. We utilized the following parameters:
Resource parameters: these parameters give information about available resources during load balancing period such as: 2. job parameters: these parameters include:
number of Clusters number of resources in each Cluster size of memory (RAM) date to send load information from resources tolerance factor. number of jobs queued at every resources; arrival time, waiting time, submission time ,start time , processing time and finish time job length job priority
4. Load index: we have used CPU queue Length Where CPU queue Length denotes number of waiting jobs in queue of resource.
We have focused on the following parameters:
Average response time: the response time is the time a job spends in the system which means the time from its arrival to its termination. 2. Slowdown: denotes as the ratio of response time to processing time . Slowdown= Max (response time/processing time) of all jobs. 3.
The proposed algorithm provides better Job Migration mechanism with DLBA. The important performance factors in estimating our proposed algorithm are decreasing response time, reducing slowdown and maximizing resource utilization. We performed some experiments for evaluating efficiency and performance of the proposed algorithm.
In the first experimentation, we have focused on the average response time (in sec), according to various numbers of jobs and clusters. We have supposed different numbers of clusters and we considered that each cluster is composed of various numbers of resources. The results showed that proposed algorithm surpassed other algorithms by decreasing the average response time. In FCFS (first come, first served) algorithm, if the resource demanded by the first job in the queue is not available, the remaining jobs cannot schedule even if the demanded resources are available. In the proposed algorithm, it works as FCFS in the job selection but when the first job in the queue cannot be scheduled directly the proposed algorithm estimate the earliest probable starting time for the first job using the processing time calculated of running jobs. Then, it makes a reservation to run the job at this pre-estimated time. Next, it examines the queue of waiting jobs and directly schedules every job not intervening with the reservation of the first job.
From figure 1 and 2, we can perceive that the proposed algorithm works much better than FCFS and EDF(Earliest deadline first ) since jobs are equally distribute over available clusters. The average response time and average slowdown are slightly better for the proposed algorithm. we have tried solving the problem of staturation by preventing the overloaded resources and we don’t permit receiving more jobs. Evidently, simple solution is not enough for more complex problems. We will try to fully comprehend this phenomenon in the future since it is outside the focus of this paper.
Fig 1. Comparison of avg response time(in sec), between FCFS, EDF and JMADLB with 20 clusters Fig 2.Comparison of avg slowdown(in sec) between FCFS, EDF and JMADLB with 20 clusters
In the second experimentation, we have focused on the resource utilization (%). We have supposed number of clusters is 14, and we considered that each cluster is composed of various numbers of resources. Number of jobs is 3000. Figure 3 shows the cluster utilization of different algorithms.
Examination of the cluster utilization showed that FCFS and EDF did not perform well. It shows that the cluster-11 which is having the highest processing resources is over utilized, while clusters 2, 4, 5, 8 and 9 are idle in FCFS and EDF scheduling algorithms. The reason behind improvement is even utilization of all clusters which is achieved because JMADLB balances the load between clusters at the time of scheduling. It shows that the JMADLB is better performed compared to traditional scheduling algorithms, also because load balancing is used to make sure that none of existing clusters are idle while others are being utilized. The load balancing effects are caused by under-loaded clusters. In the proposed algorithm there is an increase of utilization of cluster 2 from 0% (before JMADLB algorithm) to 8% (after) and cluster 4 from 0% to 2.5% and cluster 8 from 0% to 4% and cluster 9 from 0% to 30%. In this case, the different utilizations of the participating clusters are balanced. On the other hand, jobs with specific requirements have to wait until the suitable resources become available. This in fact generates higher system utilization on particular clusters. We have tried solving that by migrate the jobs for idle resources for load balancing and preventing the overloaded clusters. Moreover the JMADLB algorithm permits the scattering of the job on the most available resources when there was no appropriate resource, unlike the other scheduling algorithms that try to select the best resource resembling to the job requirements; otherwise, the job will stay in the global queue, which indicates an under-utilization of the resources.
Fig 3. Comparison of Cluster Utilization (%) between FCFS, EDF and JMADLB with 14 clusters
In the third experimentation, we have focused on waiting job in queue and we have compared it with running job. We have supposed the number of clusters is 20 and we considered that each cluster is composed of various numbers of resources. Number of jobs is 3000.
Fig 4 . Comparison of running jobs and waiting jobs of JMADLB algorithm with 20 clusters Fig 5 . Comparison of running jobs and waiting jobs of EDF algorithm with 20 clusters Fig 6. Comparison of running jobs and waiting jobs of FCFS algorithm with 20 clusters
The horizontal axis represents time (units of days) while the vertical axis indicates that the number of jobs. The red curve shows waiting job who says that a job in the waiting jobs queue, the green curve shows running job which say that a job is running or executing. EDF and FCFS are not able to schedule jobs easily, generating greatest waiting jobs during the time. For 3000 jobs and with 20 clusters JMADLB, is capable of a higher resource utilization and there is no waiting jobs in the queue through the time as can be seen in figure 4.
In this paper we have presented a load balancing algorithm in grid computing environment. To validate the proposed algorithm, we have used a Grid simulator in order to measure its performance. The first experimentation results are very promising and lead to a better load balancing between nodes of a Grid without high computing overhead. We have obtained good results especially for resource utilization. In the future, the authors want to develop the proposed algorithm by adding the multi-agent systems and we will run our algorithm in decentralized manner. Nevertheless, our algorithm has some limitation that the authors intend to address in the future. In this work, the authors did not study the effect of increasing the number of Job Migration and the performance degradation due to the migration in addition to the drawback of the centralized system. So for the future work, the authors will be interested by these directions.