Dynamic Load Balancing Algorithms Computer Science Essay

Published:

Decrease in hardware costs and advances in computer networking technologies have led to increased interest in the use of grid computing .Grid computing creates the illusion of a simple but large and powerful self-managing virtual computer out of a large collection of connected heterogeneous systems sharing various combinations of resources which leads to the problem of load balance. The main goal of load balancing is to provide a distributed, low cost, scheme that balances the load across all the processors in the grid. To improve the global throughput of Grid resources, effective and efficient load balancing algorithms are fundamentally important. The focus of this paper is to review different dynamic load balancing algorithms for the grid, identify the comparison metrics for the load balancing algorithms and to carry out comparison between these algorithms based on these identified metrics.

1. INTRODUCTION

Grid computing is the cooperation of distributed

Lady using a tablet
Lady using a tablet

Professional

Essay Writers

Lady Using Tablet

Get your grade
or your money back

using our Essay Writing Service!

Essay Writing Service

computer systems where user jobs can be executed on either local or remote computer systems. It can also be described as a wide area network connecting large equipment to form a parallel computing environment that is much larger than the traditional node distributed computing environment. Three main discussions describes computing grid. Heterogeneity, Scalability and Adaptability. Heterogeneity: is a grid containing various resources that are in different executive areas.

Scalability: resources in grid are growing from low to

high. Adaptability: existing an unsuccessful resource in a gird is normal, there many resources in grid that probability of defied some resources is more.

Resource management and scheduling is the key grid services, but to achieve efficient grid resource management and scheduling, task scheduling and load balancing is one of the key issues that must be addressed.

In grid computing, load balancing is a technique to distribute workload evenly across two or more computers, network links, CPUs, hard drives, or other resources, in order to get optimal resource utilization, maximize throughput, minimize response time, and avoid overload. Using multiple components with load balancing, instead of a single component, may increase reliability through redundancy. The load balancing service is usually provided by a dedicated program or hardware device. Load balancing refers to grid computing system, by some scheduling strategy to ensure that the entire resource node computing the ratio of its own performance as an equal, thereby improving the utilization of resources based on nodes, reducing the overall task completion time. To achieve these goals, the load balancing mechanism should be "fair" distribution of load in the resource node, which indicates the maximum load nodes and the lightest load balance between nodes should be minimized. Load balanced is a collection of servers distributed in a symmetrical way, each server is equally important, providing service to the outside world by its own without any aids of other servers. Through a certain kind of load shared technology, the outside requests can be allocated to a server with symmetrical structure equally, and then the received server will be responded to the clients independently[2].

2. Load Balancing Approaches

2.1 Load Balancing Algorithms

Load balancing mainly deals with distributing a set of independent jobs among all the computing nodes of the grid such that the jobs are uniformly distributed and none of the nodes are overloaded or under loaded. There are two algorithms of performing load balancing(LB) - static and dynamic .

(1)Static LB algorithms

This algorithms assumes that a priori information about all the characteristics of the jobs, the computing nodes and the communication network are known and provided. LB decisions are made deterministically or probabilistically at compile time and remain constant during runtime[figure 2.1]. The static approach is attractive because of its simplicity in both implementation and overhead, since there is no need to constantly monitor the nodes for performing statistics. However, it has two major disadvantages. Firstly, the workload distribution of many applications cannot be predicted before program execution. Secondly, it assumes that the characteristics of the computing resources and communication network are all known in advance and remain constant. Such an assumption may not apply to a grid environment[3].

L4.jpg

(1)Dynamic LB algorithms

Dynamic LB algorithms attempt to use the runtime state information to make more informative decisions in sharing the system load[figure 2.2]. Dynamic LB algorithms can be further classified into a centralized approach and a decentralized approach. In the centralized approach , only one node in the distributed system acts as the central controller. It has a global view of the load information in the system, and decides how to allocate jobs to each of the nodes. The rest of the nodes act as slaves; they only execute the jobs assigned by the controller. The centralized approach is more beneficial when the communication cost is less significant, e.g. in the shared-memory multi-processor environment.

Lady using a tablet
Lady using a tablet

Comprehensive

Writing Services

Lady Using Tablet

Plagiarism-free
Always on Time

Marked to Standard

Order Now

It is now commonly agreed that despite the higher runtime complexity, dynamic algorithms can potentially provide better performance than static algorithms. However, this comes at the additional cost of collecting and maintaining load information, so it is important to keep these overheads within reasonable limits[3].

L5.jpg

2.2 Load Balancing Strategies

There are three major parameters which usually define the strategy a specific load

balancing algorithm. These three parameters answer three important questions:

• who makes the load balancing decision

• what information is used to make the load balancing decision, and

• Where the load balancing decision is made.

(a) Sender-Initiated vs. Receiver-Initiated Strategies

The question of who makes the load balancing decision is answered based on whether a

sender-initiated or receiver-initiated policy is employed. In sender-initiated policies, congested nodes attempt to move work to lightly-loaded nodes. In receiver-initiated policies, lightly-loaded nodes look for heavily-loaded nodes from which work may be received. Figure [2.3] shows the relative performance of a sender-initiated and receiver-initiated load balancing algorithm. As can be seen, both the sender-initiated and receiver-initiated

policies perform substantially better than a system which has no load sharing.

L6.jpg

The sender-initiated policy performing better than the receiver-initiated policy at low to moderate system loads. Reasons are that at these loads, the probability of finding a lightly-loaded node is higher than that of finding a heavily-loaded node. Similarly, at high system loads, the receiver initiated policy performs better since it is much easier to

find a heavily-loaded node. As a result, adaptive policies have been proposed which behave like sender-initiated policies at low to moderate system loads, while at high system loads they behave like receiver-initiated policies.[4]

(b) Global vs. Local Strategies

Global or local policies answer the question of what information will be used to make a load balancing decision. In global policies, the load balancer uses the performance profiles of all available workstations. In local policies workstations are partitioned into different groups. The benefit in a local scheme is that performance profile information is only exchanged within the group. The choice of a global or local policy depends on the behavior an application will exhibit. For global schemes, balanced load convergence is faster compared to a local scheme since all workstations are considered at the same time. However, this requires additional communication and synchronization between the various workstations; the local schemes minimize this extra overhead. But the reduced synchronization between workstations is also a downfall of the local schemes if the various groups exhibit major differences in performance. if one group has processors with poor performance (high load), and another group has very fast processors (little or no load), the latter will finish quite early while the former group is overloaded.[4]

(c) Centralized vs. Distributed Strategies

A load balancer is categorized as either centralized or distributed(decentralized), both of which define where load balancing decisions are made. In a centralized scheme, the load balancer is located on one master workstation node and all decisions are made there[figure 2.4].

Basic features of centralized approach are:

• a master node holds the collection of tasks to be performed,

• tasks are sent to the execution node

• when a execution process completes one task, it requests another task from the

master node

l2.jpg

In a distributed (decentralized)scheme, the load balancer is replicated on all workstations. There are

different algorithms used in distributed scheme for job selection. These algorithms are Round robin algorithm, Random polling algorithm etc[figure 2.5].

L3.jpg

Once again, there are tradeoffs associated with choosing one location scheme over the other. For centralized schemes, the reliance on one central point of balancing control could limit future scalability. Additionally, the central scheme

also requires an "all-to-one" exchange of profile information from workstations to the balancer as well as a "one-to-all" exchange of distribution instructions from the balancer to the workstations. The distributed (decentralized)scheme helps solve the scalability problems, but at the expense of an "all-to-all" broadcast of profile information

between workstations. However, the distributed scheme avoids the "one-to-all"

Lady using a tablet
Lady using a tablet

This Essay is

a Student's Work

Lady Using Tablet

This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.

Examples of our work

distribution exchange since the distribution decisions are made on each workstation.[4]

2.3 Load Balancing Policies

Load balancing algorithms can be defined by their implementation of the following

Policies.

• Information policy: specifies what workload information to be collected, when it

is to be collected and from where.

• Triggering policy: determines the appropriate period to start a load balancing

operation.

• Resource type policy: classifies a resource as server or receiver of tasks

according to its availability status.

• Location policy: uses the results of the resource type policy to find a suitable

partner for a server or receiver.

• Selection policy: defines the tasks that should be migrated from overloaded

resources (source) to most idle resources (receiver).

3. METRICS FOR COMPARING VARIOUS LOAD BALANCING ALGORITHMS

The various metrics identified for comparing the load

balancing algorithms are[5]:

Communication overhead : Communication

overhead is the status information which each node has to provide to other nodes in the grid.

• Load balancing time : Amount of time that elapses

between the job arrival time and the time at which

the job is finally accepted by a node.

• Scalability : It is the ability of the algorithm to

perform load balancing for a grid with any finite

number of nodes.

• Fault tolerance : It is the ability of the algorithm to

perform uniform load balancing in spite of arbitrary

node or link failure.

• Reliability : It is the ability of the algorithm to

schedule job in predetermined amount of time.

4. DYNAMIC LOAD BALANCING ALGORITHMS

In this section, we will offer an overview for the dynamic algorithms used in the comparison.

N.Malarvizhi,Dr. V. Rhymend Uthariaraj reduce the Average Response Time (ART) for the grid application in their Hierarchical Based Load Balancing algorithm[6].This load-balancing algorithm is dynamic, decentralized and it handles load balancing strategy by mapping of any Grid architecture into a hierarchical structure. In this structure each cluster consists of nodes (Processing Elements (PE's)) and its root is called Cluster Manager (CM) whose role is to manage the workload of the associated cluster. CM maintains the neighboring set of each PE within its control and also performs load balancing within the neighbor set only. To build a next level in the hierarchy, all clusters are aggregated and its root is designated as Grid Manager (GM) which maintains the workload information about the cluster managers and performs load balancing within the neighboring clusters only.

4.1.1.jpg

According to the proposed model, there are

two load balancing strategies: Intra-Cluster (Inter PE), IntraGrid (Inter Cluster)

a ) Intra- Cluster (Inter PE ) Load Balancing : In this approach, based on the current workload of cluster, which are estimated from its own PE's, each CM decides whether to start a local load balancing operation or not. If it decides to start a balancing operation, then it tries to distribute its workload among its PE. Hence, we can proceed C parallel local load balancing, where C is the number of Clusters.

b) Intra - Grid ( Inter Cluster ) Load Balancing: The load balancing at this level is performed only if some CM fails to balance their workload among their associated PE's. The local balancing failure may be due to saturation of the cluster. In this case, jobs of overloaded clusters are transferred to underloaded ones according to the selection criteria. The chosen underloaded clusters are one which needs minimal job transfer cost.

Usually, the jobs are independent of each other in the grid, but different tasks of a job may have some precedence constraints. However, this algorithm assume that there is no precedence constraint among different jobs or different tasks of a job.

Prof. E. Saravanakumar ,Gomathy Prathima. E minimize the response time for small-scale grid environment in their Load Balancing on Arrival (LBA) algorithm[7]. This load-balancing algorithm is dynamic, decentralized and uses a Grid system consisting of M heterogeneous processors, P1, P2, …, PM, connected via communication channels assuming an arbitrary topology.

GGG.jpg

Each processor has an infinite capacity buffer to store jobs waiting for execution. This assumption eliminates the possibility of dropping a job due to unavailability of buffer space. Each processor saves information about its neighbors including the network bandwidth available between the local resource and its neighbor; job arrival rate, CPU processing rate , load on each processor and expected finish time. This status information is exchanged periodically. The load balancing strategy used states that when a job arrives LBA computes system parameters. Then it determines whether any of its buddy set members can execute the job earlier than itself. If it finds such a member, then the job will be migrated to that processor. This algorithm also considers job transfer cost, resource heterogeneity and network heterogeneity while making migration decision.

Ashish Revar,Malay Andhariya,Prof. Madhuri Bhavsar,Dharmendra Sutariya collect data and generate the rules using machine learning method in their Load Balancing in Grid Environment using Machine Learning algorithm[1]. This algorithm propose a technique which dynamically balances the load. The rules generated by data mining techniques are used for migrating jobs for load balancing.To achieve load balancing in Grid environment, this system uses examples related to job distribution for providing initial knowledge to the system. Based on some predefined information and new generated rules, this system can take decisions to balance load.

G4.jpg

Kai Lu, Riky Subrata, Albert Y. Zomaya present an efficient desirability-aware load balancing algorithm to tackle the new challenges in heterogeneous grid systems in their Load Balancing Algorithm for Heterogeneous Grid Systems Considering Desirability of Grid Sites[8]. This load-balancing algorithm is dynamic, decentralized ,and handle a hierarchical architecture that is divided into three levels: the Grid-Level, the Site-Level and the Node-Level. The Grid-Level scheduler is responsible for load control among grid sites. The Site-Level consists of a collection of computing nodes. The Site-Level scheduler can fully control the computing nodes within the site, but cannot operate the computing nodes in other sites directly. The Node-Level is a computing node.

G1.jpg

The algorithm take a novel approach by considering site desirability, which is how site characteristics will affect the performance of future load balancing. The LB algorithm (considering heterogeneity of sites) makes more powerful sites carry more loads, as jobs executed at fast sites are more likely to execute at high speed. This LB scheme take into account that different network communication delay between sites can reduce the cost of load movement, and enable quick response to load imbalances. In other word, the desirability-aware approach is "greedy" in the sense that it tries, at each step, to make jobs assignments at lightly loaded site. Rather than using the conventional state-broadcast or state-polling approaches, state information exchange in the algorithm is done via mutual information feedback to reduce the communication overheads.

4.2.jpg

David S. Acker, Sarvesh Kulkarni propose a new decentralized dynamic job dispersion algorithm[9] that is capable of dynamically adapting to changing operating parameters.This distributed load-balancing algorithm is dynamic, decentralized, and it handles systems that are heterogeneous in terms of node speed, architecture and networking speed. The algorithm allows individual nodes to leave and join the network at any time and have jobs assigned to them as they become available. Each node saves information about its neighbors including the network bandwidth available between the local resource and its neighbor; the current CPU utilization; and the current I/O utilization. This status information is exchanged periodically. Knowing the status information

each node can choose when to send jobs to its neighbors.

This algorithm is fault tolerant and takes job size into account. It is scalable but at the cost of increased communication overhead. Large buffer space is required on each node to store status information of all nodes.

P. K. Suri,Manpreet Singh improve the system

performance in their Efficient Decentralized Load Balancing Algorithm[10]. This load-balancing algorithm is dynamic, decentralized that considers load index as a

decision factor for scheduling of tasks within a cluster and among clusters (grid). This decentralized grid system provide load balancing in grid comprising of clusters,

where clusters server are treated as Coordinator Nodes(CN).Each cluster has multiple Worker Nodes (WN) with different processing powers. In addition, there is a Grid Information Centre (GIC) that maintains the memory and CPU utilization value along with registration

information of each CN in the grid.

grid.jpg

If a new job arrives at CN which is already overloaded i.e. the utilization value of all resources of its cluster has reached a threshold value then GIC is contacted.GIC will provide list of other clusters which are underutilized. On receiving this information, task will be transferred to one of the selected cluster.

Malarvizhi Nandagopal, K.Gokulnath, V.R. Uthariaraj propose Sender Initiated Decentralized Dynamic Load Balancing for Multi Cluster algorithm[11] to improve the average response times of jobs among clusters in distributed heterogeneous computational grid environments. A decentralized job scheduling and load balancing approach is used since the jobs generated by users are submitted to the scheduler where the job originates. The scheduler determine whether to send the jobs to the local cluster(resource) or to a neighboring cluster according to the load information of local and neighboring clusters. The clusters in the grid system may have different processing power. The processing power of a cluster is measured by the average CPU speed across all computing nodes within. GIS is responsible for collecting and maintaining the details of memory, CPU utilization and load value along with registration information of the resources. The remote manager in each cluster queries each other periodically to collect instantaneous load information of other clusters and updates GIS dynamically. Each cluster also saves information about its neighbors including the transfer delay available between the local cluster and its neighbor and the current CPU utilization. Knowing this, each cluster can choose the neighbor to which the scheduler has to send job. Load balancer interacts with scheduler and provides load control among computational nodes in the cluster.

GIS.jpg

Belabbas Yagoubi, Yahya Slimani propose a dynamic load balancing strategy based on a tree model representation of a grid architecture[12]. Based on a tree model, the algorithm presents the following main features: (i) it is layered; (ii) it supports heterogeneity and scalability; and, (iii) it is totally independent from any physical architecture of a grid. The model allows the transformation of any grid architecture into an unique tree with at most four levels where each level has specific functions.

• Level 0: In this first level (top level of the tree), we

have a virtual node that corresponds to the root of

the tree. It is associated to the grid and performs two

main functions: (i) manage the workload information of

the grid; (ii) decides, upon receiving tasks from users,

where these tasks can be launched, based on the user

requirements and the current load of the grid.

• Level 1: This level contains G virtual nodes, each one

associated to a physical cluster of the grid. In our load

balancing strategy, this virtual node is responsible to

manage workload of its sites.

• Level 2: In this third level, we find S nodes associated

to physical sites of all clusters of the grid. The main

function of these nodes is to manage the workload of

their physical computing elements.

• Level 3: At this last level (leaves of the tree), we find

the M Computing Elements of the grid linked to their

respective sites and clusters.

gg.jpg

The load balancing strategy of the algorithm is also hierarchical. Hence, we distinguish between three load balancing levels:

1) Intra-site load balancing: In this first level, depending on its current load, each site decides to start a load balancing operation. In this case, the site tries, in priority, to load balance its workload among its computing elements.

2) Intra-cluster load balancing: In this second level, load balance concerns only one cluster, Ck "rewrite", among the clusters of a grid. This kind of load balance is achieved only if some sites Sjk fail to load balance its workload among their respective computing elements. In this case, they need the assistance of its direct parent, namely cluster Ck.

3) Intra-grid load balancing: The load balance at this level is used only if some clusters Ck's fail to load balance their load among their associated sites.

The main advantage of this strategy is to prioritize local load balancing first (within a site, then within a cluster and finally on the whole grid).

5.CONCLUSION

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. This paper presents eight dynamic load balancing algorithms. They are all decentralized, scalable, fault tolerant, and reliable. They all seek for minimizing the average response time and total execution time for jobs that arrive at a Grid system for processing. Each algorithm adopt different methodology for load balancing ,but they share the same objective which is performing uniform load balancing with minim response time and communication overhead.