https://doi.org/10.31449/inf.v43i3.2944 Informatica 43 (2019) 355–361 355 A Novel Agent Based Load Balancing Model for Maximizing Resource Utilization in Grid Computing Ali Wided and Kazar Okba Department of Computer Science, Mohamed Khider University, Biskra, Algeria E-mail: aliwided1984@gmail.com Keywords: grid computing, load balancing, multi agent system, performance metrics, agent based load balancing Received: July 15, 2019 Grid is the collection of geographically distributed computing resources. For effective management of these resources, the manager must maximize its utilization, which can be achieved by efficient load balancing algorithm, The objective of load balancing algorithms is to assign the load on resources to optimize resource use while reducing total jobs execution time. The proposed agent based load balancing model aims to take advantage of the agent characteristics to generate an autonomous system. It also addresses similar systems drawbacks such as instability, scalability or adaptability. The performance of the proposed algorithms were tested in Alea 2 simulator by using different parameters such as response time, resources utilization and overall queue time. The performance evaluation suggests that the proposed algorithm can enhance the overall performance of grid computing. Povzetek: Predstavljena in s simulatorjem analizirana je agentna metoda razporejanja obremenitev v o mrež ju. 1 Introduction Due to the emergence of grid computing on the Internet, a hybrid load balancing algorithm, which takes into account various factors such as grid architecture, computer heterogeneity, communication delays, network bandwidth, resource availability, unpredictability and job characteristics, is now required. For grids, scalability and adaptability are two major issues. As for the centralized resource scheduling problem, the limitation of scalability and computational performance is inevitable. Moreover, due to resource heterogeneity, resource variations, application diversity and grid environments are dynamic. Therefore, adaptive and robust scheduling techniques are preferred [1][2]. Multi-agent systems offer promising features for resource managers. The reactivity, proactivity, scalability, cooperation, robustness, flexibility and autonomy that characterize agents can help in the complex task of managing resources in dynamic and changing environments. This paper presents a new Agent Based Load Balancing Algorithm, called ABLBA. A hierarchical architecture with coordination is designed to ensure scalability and efficiency. In addition, a multi-agent approach is applied to improve the adaptability. The proposed algorithm aims to reduce the average response time, as much as possible, of jobs submitted to the Grid, and to maximize throughput and resource utilization. 2 Related works Authors in [3] proposed a multi-agent load balancing model by analyzing the load of compute nodes and the subsequent migration of virtual machines from overloaded nodes to underloaded nodes. The proposed system involves multiple nodes that interact to implement MapReduce jobs. The multi-agent system consists of a group of agents: node sensor agent, simulation model sensor agent, analysis agent, migration agent and distribution agent. Analysis and distribution agents are defined as reasoning agents. In [4], a decentralized computing algorithm was proposed to assign and schedule jobs on a distributed grid. Using the properties of multi-agent systems, the proposed distributed resource allocation protocol (dRAP) is described as follows: An agent in the system is simply a node. Each agent has a vector including the number of CPUs in its cluster and the residual time to complete the execution of its current process. Each agent is assured to be in exactly 1 out of 4 cases during the simulation. A main feature of this algorithm is that nodes ask their neighbors to form clusters. This reduces waiting time and communication costs. One optimization to consider would be to delay the disconnection of the cluster in state 4, which would guide learning or memory in the system where the planner would be able to remember the requirements of the past process. The problem with this algorithm is its decentralized nature, it is neither a centralized control nor a precise synchronization on nodes (agents). The study in [5] presented the development of an agent-based model for managing network resources with defined operations so that the user can perform jobs efficiently and effectively and thus significantly improve management by a gLite Grid middleware. The proposed solution provides a platform based on a collection of agents in a virtual organization. The key 356 Informatica 43 (2019) 355–361 A. Wided et al. aspects of this proposal architecture are: resource tracking, load balancing and agent hierarchy. In [6] the authors proposed a new load balancing structure based on the moving agent and a technique for optimizing ant colonies. In the proposed structure, a dispatcher agent is involved in distributing the tasks received to the worker agents according to the right decisions to minimize the overall execution time (makespan). The proposed framework is constructed using three layers which are the producer of user tasks, the scheduling load balancing layer and the workers' layer. This study should be complemented by comparing their results with other methods, minimizing task movements and resulting in additional costs in the migration process. Authors in [7] presented the design and implementation of a priority scheduling and fuzzy load balancing model in a computing grid. In this grid template, the user sends his jobs to the grid agent, after the grid scheduler uses the priority-based scheduling algorithm to schedule jobs from the grid agent to the available resource. Load balancing is done using the fuzzy logic technique Propose, in which a set of fuzzy rules are produced using the resource and the work parameter. As fuzzy control rules are collected using linguistic variables, perceptual knowledge and inspection are easily integrated into the control mechanism. 3 Proposed agent based load balancing model A grid computing was modelled as a set of clusters. Each cluster was composed of nodes and belonged to a LAN local domain (Local Area Network). Every cluster was connected to the WAN global network (World Area Network) by a Switch [8]. The proposed Agent Based load balancing model was based on mapping the Grid architecture into a tree structure. This tree was built by aggreGAtion as follows: first, for each cluster, a two level subtree was created. The leaves of this sub-tree correspond to the cluster nodes, and its root, called cluster manager, represents a virtual node associated with the cluster. Secondly, sub-trees corresponding to all clusters were collected to generate a three level sub-tree whose root is a virtual node designated as a Grid manager. The concluding tree is referred to as C/N, where C is the number of clusters that constitute the Grid and N the number of worker nodes [8]. This study aims to develop a hierarchical load balancing model based on a multi-agent system. There are two key challenges for Grid computing: heterogeneity and scalability. The authors propose a three-layer architecture to address the scalability issue. Connecting or disconnecting resources (worker nodes or clusters) correspond to simple operations in a tree (adding or removing leaves or sub-trees). The proposed agent based load balancing model aims to take advantage of the agent’s characteristics to create an autonomous system. It also addresses similar disadvantages such as instability, scalability, adaptability, etc., and other specific issues related to grid computing. 3.1 Model characteristic The proposed model is characterized as hierarchical; this characteristic facilitates the circulation of information through the tree and defines the flow of messages in the proposed strategy. Three types of load information movements can be identified: • Ascending movement: this movement relates to the load information movement, to get current load state. from Level 2 (node Agents) towards Level 1 (Cluster Agents). or from Level 1(Cluster Agents) towards Level 0 (grid Agents). With this movement, the cluster manager can have a global view of the cluster load or the grid manager can have a glob view of the grid load. • Horizontal movement: it concerns the useful parameters for the execution of load balancing operations. This movement relates to task assignment intra-cluster in Level 2. • Descending movement: this movement allows to take decisions for task assignment or jobs migration, the decisions taken by cluster Agents at levels 1 to the Migration Agents at same level. And from Migration Agents at level 1 to Node Agents at level 2, also from Grid Agent at level 0 to Cluster Agents in level 1. The proposed model: • supports the scalability and heterogeneity of grids: insertion or elimination entities (processing elements, nodes or clusters) are very simple operations in the proposed model (insertion or elimination nodes, subtrees); • is totally independent of any physical structure of a grid: the conversion of a grid into a tree is a unique conversion. Each grid corresponds to one and only one tree; • is based on the exchange of information between Nodes and clusters through their respective agents. Level 0: At this level, Grid Agent is located, the Grid users send their jobs to the Grid Agent, for which it is responsible: • receiving jobs from Grid users • sending jobs for Node Agents • all Cluster Agents are started by Grid Agent • initiating a global load balancing process Level 1: At this level, Cluster Agent is associated with a physical grid cluster; this Agent is responsible for: • the maintenance of the load information relating to each of its Node Agents. • estimating the load of the associated cluster and sending this information to Grid Agent. • the decision to start local load balancing • sending load balancing decisions to Migration Agent A Novel Agent Based Load Balancing Model for... Informatica 43 (2019) 355–361 357 • Migration Agent is started by its associated cluster Agent • all Node Agents are started by their corresponding Cluster Agent Migration Agent is also present at this level, whose role is to: • start the migration process • send the migration decisions to the Node Agents. • wait for an acknowledgement from receiver node and ensure that the migrated jobs are received and successfully resumed at the destination node Level 2: At this level, Node Agent is present; it is necessary to have one Node Agent on each node; every Node Agent at this level is responsible for: • maintaining its load information • sending this information to its associated • Cluster Agent • working in cooperation with the Migration • Agent to execute the migration process • collect information about the jobs (number of jobs queued at node, arrival time, waiting time, submission time, start time, processing time and finish time of each job on the local node) • remove the terminated, leaving or migrated jobs from queue of jobs • calculate the total load of node • receive jobs sent by Grid Agent 3.2 Proposed algorithms According to the proposed model, two levels of load balancing are considered: Intra-cluster Agent based load balancing algorithm and Inter-Clusters Agent based load balancing algorithm. There are certain specific events that change the load configuration in Grid computing and can be classified as follows: • Any new job is arrived • Accomplishment of execution of any job • Any new node is arrived • Any existing node is removed • Failure of Machine at any node • The node become overloaded When any of these events happen, the local load value is changed. Table 1 summarizes the notations used in the proposed algorithms. Parameter Description N Node LoadN Load of Node Qlength Queue length CPU-U CPU utilization of Node Mem Memory utilization of node THH The higher threshold THL The lower threshold OLD-list Overloaded List ULD-list BLD-list Loadavg NBRN C Underloaded List Balanced List Average Load Number of Nodes of cluster Cluster Table 1: Notations used in the proposed algorithms. 3.2.1 Intra-cluster agent based load balancing algorithm Depending on its current load, each Cluster Agent decides to start a Job Migration operation. In this case, the Cluster Agent tries, in priority, to balance its load among its nodes. Load estimation The node load at a given time was simply described by the CPU queue length. It indicates the number of processes awaiting execution. The proposed algorithm considers CPU-U (CPU Utilization), Q length (Queue length) and Mem (memory utilization) as load information parameters to measure the load of a node. These parameters are calculated as follows: Load (CPU-U)= (U1+U2+……+UT)/T, where: U1+U2+……+UT is the value of CPU-U in a previous one second interval. Load (Qlength) = (Q1+Q2+…...+QT)/T, where: Q1,Q2,……...,QT is the value of Qlength in a previous one second interval. Figure 1: Agent based load balancing model in grid. 358 Informatica 43 (2019) 355–361 A. Wided et al. Load(Mem)=(M1+M2+……...+MT)/T Where: M1,M2,……...,MT is the value of Mem in a previous one second interval. T is the number of time intervals. The averaged information of CPU-U, Qlength and Mem are the load parameters used to describe the node load. Algorithm 1. An algorithm for Node Agent 1: T←5 seconds 2: Waiting for jobs; 3: Create jobs queue for related node; 4: In each one second of T intervals do 5: Calculate (CPU-U); 6: Calculate (Qlength); 7: Calculate (Mem); 8: End do 9: Load (CPU-U) = (U 0+U 1+…..U T)/T; 10: Load (Qlength) = (Q 0+Q 1+…..Q T)/T; 11: Load (Mem) = (M 0+M 1+…..M T)/T; 12: Send load information for related Cluster Agent 13: Wait for load change // happening of any of defined events 14: If (events_happens ()=1 or events_happens ()=4) then // Termination or migration of job 15: Remove terminated or migrated job from the waiting queue 16: Subtract their load value from the total local load of node. 17: Send new load to its Cluster Agent associated; 18: End if 19: If (events_happens ()=2 or events_happens ()=3) then // new or incoming job 20: Add the newly created or incoming job for the waiting queue 21: Add their load value for the total local load of node 22: Send new load to its Cluster Agent associated; 23: End if Function events_happens () output Type: integer 1: If (Job.state=Termination) then events_happens () =1; End If 2: If (Job.state=Start) then events_happens () =2; End If 3:If (Job.state=Incoming Migrating) then events_happens ()=3; End If 4: If (Job.state = migrated) then events_happens ()=4; End If 5:If (Arrival of any new resource) then events_happens ()=5; End If 6: If (Cluster.state=saturated )then events_happens ()=8; End If 7:If (Cluster.state=unbalanced) then events_happens ()=9; End If Location policy In the next step, the nodes must be classified according to their load. Three states were used for classification: overloaded, underloaded and balanced. First, Cluster Agent must calculate two threshold values, which are calculated as follows: • cluster Agent calculates load average of each parameter (CPU-U and Qlength) over all related nodes. • Load avg(Qlength)=(load 1+load 2+….load NBRN)/NBR N, where Load avg(Qlength) is the average load of Qlength over all related nodes. • load 1,load 2,….load n are the current Qlength of each node calculated by Node Agent. • Load avg (CPU-U) =(load 1+load 2+….load NBRN)/ NBRN, where Load avg (CPU-U) is the average load of CPU-U over all related nodes. • load 1,load 2,….load NBRN are the current load of CPU-U of each node calculated by Node Agent. Calculation of threshold values The higher and lower threshold values of Qlength and CPU-U of parameters are calculated by multiplying the average load of (Qlength or CPU-U ) and a constant value. • THH(Qlength) =H*Loadavg(Qlength) • THL(Qlength) =L* Loadavg(Qlength) • THH(CPU-U) =H*Loadavg(CPU-U) • THL(CPU-U) =L* Loadavg(CPU-U) where, TH H is the high threshold and TH L is the low threshold. H and L are constants. The next step is to divide the nodes for balanced, overloaded and underloaded nodes using the threshold values as follows: • Overloaded: the node will be added for overloaded list if queue length is high, or CPU utilization is high, or memory usage is greater than 85%, then the node is classified as overloaded node. • Underloaded: the node will be added for underloaded list if queue length is low, or CPU utilization is low. • Balanced: the node is not into the overloaded list or the underloaded list. The node is in a balanced load state. They are considered to be more loaded than the low state and less loaded than the high state. Algorithm 2. An algorithm for Cluster Agent 1: Startup its related Node Agent 2: Startup its related Migration Agent 3: Receive load information(Load N(Qlength), Load N(CPU-U)) from its related nodes. 4: Calculate and send its load information for Grid Agent. 5: somme ←0; somme1←0; 6: For every Node N of cluster C do 7: Somme← Somme+ LoadN(Qlength); 8: Somme1← Somme1+ LoadN(CPU-U); 9: End For 10: Load avg(Qlength)= somme1/NBR-N; 11: Load avg(CPU-U)= somme/NBR-N; 12: TH H(Qlength)= Load avg(Qlength)*H; 13: TH L(Qlength)= Load avg(Qlength)*L; 14: TH H(CPU-U)= Load avg(CPU-U)*H; 15: TH L(CPU-U)= Load avg(CPU-U)*L; 16: Partition Nodes into overloaded list OLD- A Novel Agent Based Load Balancing Model for... Informatica 43 (2019) 355–361 359 list, underloaded list ULD-list and balanced list BLD-list 17: OLD-list← ∅; ULD-list← ∅; BLD-list← ∅; 18: For every Node N of cluster C do 19: If ((Load N(Qlength)>TH H(Qlength)) or (Load N(CPU-U)>TH H(CPU-U))or (Load(Mem)>85%)) then 20: OLD-list ←OLD-list ∪ N; 21: End If 22: Else If ((LoadN(Qlength))< TH L(Qlength))or(Load N(CPU- U)