This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.
Abstract- This paper gives a survey on load balancing techniques for distributed systems. Based on the study, we propose different major techniques for load balancing in distributed environment. It gives general classification of distributed load balancing scheme. An important part of distributed system design is the choice of load balancing technique. These methods are used to transfer the load from heavily loaded nodes to lightly loaded nodes in the network.
Keywords- load balancing algorithms, Dynamic load balancing, centralized approach, interrupt service load balancing, DHT, self-aggregation ,distributed stream processing
In large distributed environment one of the major issue is the development of effective technique for proper distribution of load among various processing elements. Load balancing is the process of allocation of work of a single application to multiple processors for minimizing the execution time of the application. Efficient load balancing method can increase performance. The most important criteria for any load balancing algorithm is proper assignment of tasks and optimum utilization of resources.
This paper presents a comparative study on different techniques used for load balancing in distributed systems. Firstly includes the common classification of load balancing algorithms. A primary approach for load balancing , a centralized approach and a modified load balancing with exploitation of interrupt service also included. This survey also includes load balancing technique used in distributed stream processing systems.
Classification of load balancing algorithms
The major classification of load balancing algorithms is local scheduling and global scheduling. Local scheduling is the process of assigning processor time quantum to task as it is done by every traditional operating system. The process of deciding where to execute a task in a multi computer environment is called global scheduling. Global scheduling again classified into two major groups as static load balancing(static scheduling) and dynamic load balancing(dynamic scheduling).
In static load balancing, before the execution begins, the decision of assignment of tasks to processors is taken. Before run time, we assumed that expected execution time and resource requirements are to be known. Task is executed on the processors to which it is assigned at the start of execution. So there is no task migration in SLB. That is static scheduling is processor non-preemptive. The main purpose of the static scheduling is to minimize execution time and communication overhead. One of the advantages of SLB method is that, all the overheads of scheduling processes are eliminated at compile time itself. But this advantage is the main drawback in the case of large distributed environment. So for dynamic and large distributed environment SLB methods are not used.
Dynamic load scheduling is based on redistribution of tasks among available processors during execution time. Here, tasks are transferring from heavily loaded processors to lightly loaded processors. A DLB algorithm is defined by four policies such as transfer policy, selection policy, location policy and information policy.
It determines in what conditions a task should be transferred. This policy includes either both task migration and task re-scheduling or one of them. Suspension of executing task and transfer it to another processor and resumes its execution from the state of suspension is called migration. Re-scheduling means transfer of tasks which are not started its execution .transfer policies are based on 'threshold'. Transfer policy updates the local load information whenever a new task is submitted to any host. Then defines the host as 'sender' or 'receiver' based on predefined threshold values.
After deciding a host as sender, selection policy selects task for transfer. The common method is to select a newly arrived task that just transfers the host into sender. The factors considering in selection policy are
i. There should be minimum overhead incurred by transfer.
ii. Life time of selected task should be long.
iii. There should be minimal number of location dependent system calls made by the selected task. The system calls that must be executed on the host where the task originated is called location-dependent system calls.
Location policy finds a suitable transfer partner(sender or receiver). Important task of location policy is to check the availability of services required to the task the is migrated or re-scheduled.
Information policy decides the time when the information about the states of the other hosts in the system is to be collected.
This section describes three approaches of dynamic load balancing algorithms
Here, load balancing action initiated by overloaded host or
sender(Fig 1). Ie, congested nodes attempt to move workload to lightly-loaded nodes.
1) Transfer policy: Whenever a new job arrives and CPU queue length exceeds predefined threshold value (T), then host is declared as sender. If the new job arrival does not result in the exceeding the system load from T, then the host declared as receiver.
2) Selection policy: Same selection policy is used by all algorithms and only newly arrived jobs are considered for transfer.
3) Location policy: Algorithms differs only in their location policy. Three different location policies are there, such as Random, Threshold, Shortest queue length. In Random policy, task is transferred to randomly selected remote host. No prior information exchange between the hosts. In threshold policy, avoids useless task transfers by polling a host to determine whether transferring a task leads to queue length exceeds T. If not, task is transferred to selected host. Otherwise, next host is selected at random and performs polling. In shortest queue length policy, the host with shortest queue length is selected as the destination for task transfer.
4) Information policy: Information policy is demand driven. Because, if either shortest or threshold location policy is used, polling starts when the transfer policy identifies a host as the sender of a task.
Fig. 1: Sender-initiated load balancing
In this, load distribution activity initiated by the under-loaded host(receiver). Receiver always tries for getting a task from an overloaded host.
1) Transfer policy: In this, depending upon the present value of CPU queue length, threshold value for transfer changes. The host is identified as a receiver if and only if the local queue length falls below the threshold. If its queue length exceeds the predefined threshold value T, then the host is selected as a sender.
2) Selection policy: Receiver initiated algorithms takes all tasks for transfer.
3) Location policy: Selects a random host and polling is performed to determine whether transferring leads to placing its queue length below the threshold level. The polled host transfers the task only if it does not leads to going queue length below threshold. Otherwise, a next random host selected and perform polling. Repeat this procedure until either a eligible host is found or static poll limit number of tries fails to find a sender.
4) Information policy: Polling starts only after a host becomes a receiver. So the information policy is demand driven.
Fig. 2: Receiver-initiated load balancing
In these algorithms, both senders and receivers initiate activities of load distribution for task transfers. It is a combined form of sender-initiated and receiver-initiated algorithms. At finding under-loaded hosts, the sender-initiated component is more successful. But in the case of high system loads, the receiver-initiated component is more successful than sender-initiated. Polling at high system loads by sender-initiated algorithms may result in system instability. A preemptive task transfer policy is necessary for receiver-initiated algorithms. By combining the transfer and location policies described for sender-initiated and receiver-initiated algorithms, we can construct a simple symmetrically initiated algorithm.
IV. one primary approach for dynamic load balancing
Distributed system consists of independent workstations. They are connected usually by a local area network. In dynamic load balancing number of jobs at a station is not fixed. Jobs are allocated to host while other jobs are in execution. Dynamically calculates the load at each node. Sender and receiver approaches are used to find the desired load that should be transferred.
Node 2 222
Fig. 3: Simple dynamic load balancing
Initially processes are stored in queue or process can be allotted as soon as they arrive. If the processes are stored in queue, they are allotted to primary nodes one by one. Processes are migrated to lightly weighted node. Network bandwidth and work load greatly affects this process migration. For reducing the traffic, nodes are grouped into clusters. Firstly within the same cluster search for lightly weighted node. If such a node is not found ,then only nearby cluster is searched. After finding a required lightly loaded node, transfer of load take place.
V. centralized approach for load balancing
Sometimes heavily loaded node don't find lightly loaded node in its cluster or it fails in search a node far away from its cluster due to congestion in network. In this approach one temporary node in same cluster handles the overload. Ie, in each cluster, one centralized node is provided. Whenever a primary node becomes overloaded, firstly searches the light weighted primary node. If such a node exists, load transfers between these nodes and thus load can be balanced. If such a node is not available, the centralized node for that cluster accommodate the overload of a primary node. Initially centralized node is not assigned by any process. Processes are assigned to centralized node only when primary nodes are overloaded. For avoiding network delay, traffic between centralized node and primary nodes kept minimum.
Node 2 222
Fig. 4: Load balancing based on centralized node
VI. a modified approach for dynamic load balancing with interrupt service
In this approach, centralized node is split into small nodes called supporting nodes (SNs). Initially supporting nodes are given some load and SNs maintain a priority list of process or order of execution of process at the SN. Consider the execution of a process Pi by SNi. A primary node Ni is overloaded and it finds a supporting node SNi for transferring its overload . Then Ni will interrupt the SNi and SNi will assign priority to the coming process. And for handling the interrupt, the interrupt service routine is also called.
Interrupt service routine compares the priorities of processes and perform switching between the currently executing process and process coming from the primary nodes.
Each SN Maintains a priority queue in which process to be executed are sorted based on its priority. The coming process are stored in this queue with a priority.
Node 2 222
Fig. 5: Load balancing with interrupt service
VII. self-aggregation technique for load balancing in distributed systems
Balancing work load among all the nodes in a system composed of interconnected nodes is critical. Because loads enter and exit the system without following any rule. For addressing this issue, autonomic self-aggregation techniques can be used. In this techniques, rewire the system in groups of homogeneous nodes, then they become able to balance the load among each others using classical technique. Self-aggregation requires the exchange of a higher number of messages between nodes. Even though this technique does not introduce a significant overhead in terms of execution time.
In heterogeneous networks, we can solve the load balancing problem by modifying the links of the network (rewire) in order to aggregate the domain of the same type. For this we need to aggregate the nodes that can process the same type into unique domains.
The major purpose of a self-aggregation (or clustering) algorithm is to rewire the network. Aim of this rewiring is to reduce the number of links between different type nodes and also add new links between same type nodes. The example of clustering:
Before clustering After clustering
The main concept of self-aggregation is clustering is not executed by a external centralized entity. It is executed in a distributed manner using the ability of each node to autonomously take a simple decision about disconnect or maintain the link. This decision is taken based on type of each neighbour. For overcoming the inherent limitations of classical load balancing algorithms, adaptive clustering algorithm can be used to reconfiguration of network topology. This algorithm runs in parallel with the load balancing algorithm for enhancing its convergence rate. And results in maximizing the throughput of the system. The self-aggregation algorithms works by continuous iterations of themselves on all the nodes of the network. Whenever the network is created, these algorithms will start and active forever. The list of neighbours of each node involved in an iteration is the only information used and modified. When a node has at least a node of same type in its neighbours list and its queue is not empty, then dimension exchange algorithm is activated. Only its queued jobs list and the one of its neighbours is modified. Each algorithm modifies different node properties. So conflicts are not possible. The main advantage of using this approach are scalability and efficiency.
VIII. load balancing technique of distributed stream processing systems
In stream processing applications data are usually unbounded, continuous, large amount, fast arriving, time various and out bursting. Because of the outbursting of data incoming and the unpredictable pattern of resource consumption, delays in data stream processing are very difficult to handle. A scalable, efficient, dynamic load balancing technique for distributed data stream processing system is vRing. It is a hierarchical DHT- based proximity network. Distributed hash table (DHT) network is a content-addressable overlay network because based on a consistent hashing function it maps files to network nodes. Nodes are distributed in the logical space in a DHT network. So actual network topology information and the capacity of node are not known. The logical proximity abstraction derived from DHTs and the physical proximity information in reality does not necessarily match. DHT network are heterogeneous.
vRing:proximity -aware architecture
Migrate or transfer workload between physically close nodes is the important step in proximity-aware load balancing. In distributed data stream processing system it is very important because the high cost of transferring streams. The vRing is a hierarchical proximity-aware architecture. It generates a resilient auxiliary network in which nodes are divided into main nodes and sub nodes. Each main node has the information about its sub nodes. Each sub node points to a physically closest main node. This network can save communication cost in load balancing and increase the speed of load balancing.
1) Node IDs generation algorithm: In vRing node generated using one algorithm. The main node ID is generated by hashing. When a sub node SN1 joins into vRing, it sends probe messages to the main nodes for getting delay between this sub node and the main nodes. MN1 is the nearest main node and take it as father node. Minimal delay main node is MN2. Let d1 is delay between SN1 and MN1 and d2 denotes the delay between SN1 and MN2. ID1 and ID2 are the Ids of MN1 and MN2.
2) Load balance of operators: In distributed data stream processing system operators are never ended. The data stream will traverse a series of operators which may not locate on the same node. So the communication between operators is big problem in distributed stream processing system.
B. Load balancing algorithm
In a time vary stream processing system load balancing algorithm is very important. For a good load balancing algorithm the optimal goal is critical. In the global load balancing algorithm, assuming there are M main nodes in the vRing system. The load of each main node is represented by L(Si). The aims of this algorithm are
L(Si) < C * P(Si), 1<= i <= M;
Minimize ∑ ( T (Si) -T (Si))2 .
IX. . conclusion
Various techniques for load balancing in distributed systems are studied and explained. New effective ways to deal with the increasing complexity of distributed computing systems is included. Challenges of scalability and load balancing in supporting distributed stream processing applications also presented. Balancing worked load among all nodes in a system composed of interconnected nodes that enter and exit the system without following any rule can be done by a self-aggregation technique. This technique rewire the system in groups of homogeneous nodes.