CHAPTER 2

2. LOAD BALANCING IN CLOUD COMPUTING

This chapter contains the detail of load balancing, like different method of load
balancing, metrics, challenges and components of load balancing.

2.1 Introduction of Load Balancing

Distribution of workflow to all available computing resources is done in such as way

that no any nodes become overloaded or no any node become under loaded. So process
of such type of distribution is called load balancing. Here resource means cloud data
center, physical machine, VM, or software of application[23]. So sharing of task to all
these types of resources is a load balancing. For load balancing process, mapping of task
and resources should be done.

Figure 14 Different levels of task-resource mapping

In cloud environment cloud provider need some data center to provide cloud services
And every data centre also has some hosting devices. It means some physical devices
are also used. And each physical device contains virtual machine based on policy. The
hosts are getting a lots of virtual machine based on policy of virtual machine allocation.
That policy designed may be designed by the cloud provider. In single virtual machine

31
instance lots of application service is provided, that is known as application
provisioning.

Physical infrastructure is required for data centre. So it is an entity which means a

physical place like hall or building. That building is capable enough to accommodate
the required physical machines. That is called physical computing server. And each
physical machine has fix capacity for processing and that capacity measured in MIPS
(Million instructions per second). In data centre there can be some other resources like
memory, network, storage etc. some other software like application provisioning policy
for allocating processing power to virtual machines.

Using some virtualization technology, some virtual machines is also created on host
machine which are the instance of that host. It is not physical host. But logically created
host to perform some task. After creating that VM machine some application deployed
on that VM as per the requirement of client. So all the processing devices and some
other hardwares are allocated to that virtual machine by following some host allocation
policy. As per the allocation policy, it also consider some hardware distinctiveness like
units of processing power, sharing or processing cores, primary and secondary memory
are also assigned to some Virtual machines. Allocation policy is looked after that how
many virtual machines are allocated with what processing capacity and which
applications are hosted on which virtual machine and what total memory is utilized for
processing particular task or application.

To assign a processing cores to virtual machine mainly two techniques are used first is
space shared and the other one is time shard policy. Before assigning the processing
cores to virtual machine, one thing is considered by the service provider that how many
phical machines are available and what capacity each hardware has. Following figure 15
shows the example of host allocation policy.

Figure 15 Host allocation policy

32
Application specific virtual machines are assigned to different host based on some
Virtual machine sharing policy. It shows creation virtual machine, configuration of
virtual machine and also assignment of virtual machine to host. Following figure 16
represent the virtual machine allocation policy.

Figure 16 Virtual machine allocation

Mainly two issues are needs to be handled while balancing the nodes in distributed
systems. One is resource allocation and other one is task scheduling.

Resource Allocation is the process of mapping resources to entities of cloud based on

demand of customers. Resources are allocated in such a way that no any node should
overload or no any node should overload. Or no any node should be in idle position.
There are again two ways of resource mapping one is VM mapping to host and other
one is task mapping to VM.

VM mapping to host: one physical machine can be mapped with multiple virtual
machines. For assigning a processing power to virtual machine, the responsible entity is
physical machine. A provisioning policy which is installed on that physical machine or
host provides ground to allocate processing power to virtual machine as per the
requirement of customer. Before mapping the allocation policy ensure that the features
of virtual machine and physical machine. It should be match and then it can map.

Task Mapping to VM: Virtual machine is responsible to execute the application and
task. To execute the each application of task on virtual machine it needs certain amount
of processing power. Virtual machine is also responsible to provides necessary
processing feature to the application or task which are need to mapped with that
particular virtual machine. It is mapped based on configuration of VM and availability
for processing the job[24].

33
Task Scheduling: The working of task scheduling is exists after allocating the
resources to the cloud entity. Task scheduling means, how to execute the given task on
virtual machine. In which sequence different task should be executed on VM. So the
resource allocation means which cloud resource are available to fulfill the requirement
of executing the particular task. Where task scheduling in which manner the particular
resources are mapped to various task. It provides capability for multi processing. Task
scheduling is performed in two ways one is using space shared method and other is time
share method.

Space shared: in this method resources are allocated to different task. After mapping,
one by one task performed based on time required of that particular task. So, next task is
performed on particular VM, after completing the precious task which is mapped. So no
time slot is assigned to VM only task is assigned. And other task has to wait till the
completion of precious task.

Time shared: In this method resources are allocated to particular task for some fix
amount of time. If task duration is more than fix allocated time than that task should be
withdraw from that VM and next task should be assigned till the fix timing. So that task
goes into queue , till its next turn for execution[25].

2.2 Strategies for Load Balancing

As per the application environment, different load balancing technique is used. So,
different environment has different techniques. It can be achieved at different layers
like application layer, server layer, platform layer, protocol layer etc. load balancing can
be achieve by different way like gateway, load control software or some load balancing
tool. The main objective of the load balancing is to improve the throughput, reduce the
response time or optimization of usage of cloud resources. Following are the strategies
of load balancing algorithm[26].

Load testing rule: In this strategy, for load balancing load of each node of system is
calculated. So the workload is allocated to each node based on current load of that
particular node in the system. So the first stage for load balancing algorithm is to find
out the load index of node to find the total load of that particular node.

34
Information Rule: Information rules have right to finalize the procedure of method of
collection of load information of node and also to spread that information to all the
nodes. It also decides to on what time this information is shared or after which slot
period the load information should shared to others. It also based on some event driven.
That means when some event occurs at that time particular information should be
shared. Information used either some periodic manner broadcast mode or it is query by
some user when they need it. That can be managing by two ways centralized or in
distributed manner.

Initiation rule: This rule is helpful for deciding to start the load balancing operation.
That can be used by thresholds or as per event driven.

Operation Rule: This strategy is very important for load balancing. This strategy has
three steps. Location rule, distribution rule and selection rule. Location rules is used to
find the nodes which are used for load balancing. Distribution rule is used to clear the
load of each node in the system and the last selection rule is used to redistribute the task
to the other node which as lower load.

 The primary fraction is the location rule which decides the node involved in the
‘load balancing’ operations.
 The subsequent part is distribution rule which can make each node's load clear in
the ‘load balancing’ system.
 The last part is a selection rule which will redistribute a figure of jobs or resources
in the overfilling node.

2.3 Types of Load Balancing

Cloud computing provides different types of services means heterogeneous services. If

provider wants to use their cloud resources in optimum way than they should confirmed
that no node in the system is overloaded or no any node which are under loaded or no
any node which is idle in the system. So, based on the cloud environment, load
balancing method has different types. The following figure 17 shows the types of load
balancing methods. Mainly all the load balancing methods are divided in to two broad
categories. One is load balancing based on system load and other one is load balancing
based on topology of the system.

35
 Figure 17 Load balancing classification

2.3.1 Based on System Load

Based on mapping of task to resources, we have different load balancing approach as

[12],[37] like distributed approach ,centralized approach and mixed approach
Their details are as follows:

Distributed method has no any scheduler which is work centrally. All the nodes have
its own scheduler. It maintains the load vector which stores the information of load of
other nodes in system. Based on information stored in load vector it takes the decision.
This is more suitable for distributed system like cloud system. In this system there is
less change for failure so system has fault tolerant so no any node is overloaded in the
system.

Centralized method has one scheduler which is responsible for distributing the load to
the system. Time can be reduced here because of centralize management. System is less
tolerant than distributed environment. Recovery is also difficult in this method.

Mixed method is use the advantages of both the methods distributed as well as
centralized. So that method is called mixed method or approach for load balancing.
Decisions are taken at centralized as well as distributed level in this approach. This
method is more suitable method for load balancing. So it is adopted by more cloud
provider for load balancing.

2.3.2 Based on System Topology: Based on the usage of parameter of recent

circumstances and how the technique is designed, different load balancing technique is
used. Like static approach, dynamic approach and adaptive approach.[27],[29],[30]:

36
Static approach is used generally during design or implementation of the system. In
cloud environment different types of environment are used. Like homogeneous,
heterogeneous, stable environment, instable environment etc. so this static approach is
suitable for stable and homogeneous environment. If the algorithm used this approach
for implementation then this approach is called static approach. This is not flexible and
do not support the dynamic change in attributes. This gives the best result only in stable
environment where attributes are stable. But if it is not stable then this approach should
not be used. Here in this approach task is assigned to the node based on capability of the
nodes. So here some prior knowledge is required regarding capability of the nodes or
properties of node. A property means processing power of node, storage capacity,
memory, etc. This approach doesn’t consider the dynamic change of this attribute value
at runtime. Also it is nod adobe run time change in load.

Dynamic Approach is more suitable for distributed system like cloud computing. It is
used at any time in the system not only in the designing or implementation but runtime
also it can be used. It gives good result in heterogeneous environment as well as instable
system. If algorithm used this approach, then this algorithm is dynamic algorithm. This
is flexible and support dynamic change in attribute runtime. This gives the best result in
non stable environment also. It considered numerous attributes of capability of node and
network bandwidth. Mostly this type of algorithm depends on collection of different
information prior gathered information about then nodes and run time properties when
node runs the task. These algorithms assign the work at compile time or dynamically re
assign task to the nodes based on information of attribute at compile time. Constantly
monitoring of nodes and progress of work is required in this type of algorithm.
Implementation is harder than static algorithm. But it gives more accuracy and good
result in load balancing.

Adaptive Approach: is suitable when environment parameters change frequently in

distributed environment. The main difference in this approach and previous two
approaches is that here algorithm itself can be change if the need is change with change
in environment. Implementation is hard then previous two approaches but give better
performance for frequent change environment scenario.

37
2.4 Load Balancing Metrics

To check the performance of load balancing algorithm, we have different parameters

that can be quantitative as well as qualitative as given below[31].

Response Time: it is a time which specified the total time required to execute the user
query. So how much time it takes to give response to the user is called response time.

Scalability: it is a measure of ability of algorithm to scale as per the change in

requirement. How efficiently algorithm manages the demand change of customer is a
measure of scalability.

Throughput: it is a measure of number of task have completed in unit time period. If

the throughput is high then the performance of algorithm is considered as a good.

Resource utilization: This value shows the degree to which the resources are utilized
in the system. Utilization of those resources should be maximum.

Extra overhead: Extra overhead is generated because of task are migrated from one
node to other. Also by inter process communication extra overhead is generated. It
should be minimized.

Migration time: it is the time required to transfer task from one virtual machine to
other virtual machine in the system. Performance of algorithm can be improved if
migration time is reduced.

Fault Tolerant: it is the capability of algorithm to act correctly when there is some
nodes are fail in the system. How algorithm is handling the failing situation. How it is
recover from the failure. How it prevent the failure situation etc. All this points helps to
decide the fault tolerance of algorithm.

2.5 Issues and Challenges in Load Balancing

Issues and challenges in cloud load balancing are discussed bellow[32], [33].

Spatial Distribution of Nodes: The challenges of spatial distribution of nodes are the
geographical location of nodes. Nodes for what we want to balanced the load. That may
be in any location of world for cloud environment. Issue is there because when we

38
design the algorithm that time we don’t know the location of that particular node. It
means that how far the nodes are. So we need to develop an efficient load balancing
algorithm which can be able to solve this type of problem.

Storage: cloud environment is very big environment. And also it has a distributed
nature. Because of these characteristics of cloud, it has to stores a lot of information on
cloud related to load balancing. Also that information is updated regularly as a when
required. So that is a overhead. So we need to design an algorithm which should
efficient without so much overhead.

Complexity: complexity should be less for designing any algorithms. Cloud

environment is very vast network and it is also multilevel and distributed. So it required
lots of information to store and maintain for load balancing at different location
worldwide. So it increases the complexity. But it is also require. So designing a efficient
algorithm with low complexity is a challenging for load balancing algorithm.

Type of Algorithm: if we have a centralize algorithm that is efficient for most of the
case but at the same time such algorithm fails then whole system is also fail. So,
distributed algorithms are not efficient enough, but that can avoid the failure of whole
system when single point failure. So, selection of algorithm type is a challenging task
for designing algorithm for efficient load balancing.

2.6 Components of Load Balancing Algorithm

Different components are used when we design a load balancing algorithm. And it is
different from algorithm to algorithm. But following four common components which
are used in any algorithm , and interaction between shows in following figure 18 [2],
[34], [35].

Transfer Policy: The roll of node can be sender, receiver or neutral. This roll is
decided by transfer policy. If threshold limit is increase when node has assign some load
then node becomes sender. So load should be transfer to another node. If the threshold
limit of the node is not exceeded and the system becomes balanced, then that node will
work as a receiver.

39
Selection Policy: once transfer policy is decided by transfer policy, selection policy
comes in picture. The main objective behind this selection policy is to decide the task
which needs to be transfer from overloaded node. The easiest selection policy is to
transfer a last arrival node that causes a overload situation. There are some other
selection policy is also exists. In another selection policy, select that task whose
removal will change the status of node from sender to receiver.

Figure 18 Component Interaction for load balancing

Location Policy: location policy decides for location where the load has to be transfer
after selection of task. Responsibility of location policy is, it ensure that migrated task
should satisfy all requirement on the new node. And also ensure that threshold limit
should not be exceeded. Broadcasting and polling is used to find appropriate node.

Information Policy: During execution of the system some information should be

collect and store it. This is maintaining by information policy. This policy is decide that
which information should be collect, when and how it should be collect and finally
where it should be store that this decided by this policy. Following are important
information policy which used for load balancing in cloud computing.
40
  Demand-Driven: this is dynamic in nature. If nodes become sender or receiver
then it can collect the information of another node. That should be sender or
receiver initiated.

 Periodic: nodes are exchanging their load information irrespective of its state in
this information policy. This collected information is used by transfer policy.

 State-change-driven: when state is change node disseminates it load

information in this policy. Demand driven is different than this policy. Here
node disseminates its information while node collects information of other nodes
in demand driven policy.

Summary

This chapter has discussed detail about load balancing, also goes in detail about
the types of load balancing, its different strategies, challenges, different
components, metric with respect to cloud computing at last components of load
balancing and interaction between them is also discussed in detail in this
chapter.

41