=Paper=
{{Paper
|id=Vol-1203/EES-paper5
|storemode=property
|title=Load Balancing to Save Energy in Cloud Computing
|pdfUrl=https://ceur-ws.org/Vol-1203/EES-paper5.pdf
|volume=Vol-1203
|dblpUrl=https://dblp.org/rec/conf/ict4s/PertsasW14
}}
==Load Balancing to Save Energy in Cloud Computing==
https://ceur-ws.org/Vol-1203/EES-paper5.pdf
Load Balancing to Save Energy in Cloud Computing
Theodore Pertsas Usman Wajid
University of Manchester University of Manchester
United Kingdom United Kingdom
tpertsas@gmail.com usman.wajid@manchester.ac.uk
Abstract— While load balancing techniques have been designed implementation and testing of the load balancing algorithms. In
and evaluated for efficient resource utilization in cloud the proposed system, cloud applications are decomposed into
computing, achieving energy efficiency as a consequence of load independent but interrelated tasks, each of which can be
balancing often does not get direct attention. In this paper we deployed and executed on Host Agents that are tightly coupled
describe two load balancing algorithms that focus on balancing
with a physical hosts or servers in the cloud infrastructure. Host
workload distribution among physical hosts in the cloud
infrastructure. The test results presented in this paper reveal the agents implement the load balancing algorithms and interact
strength and weaknesses of the algorithms. In future work we with each other to perform load balancing operations.
aim to analyze the impact of our load balancing on energy The definition and testing of load balancing algorithms,
consumption in the cloud infrastructure. reported in this paper, will lead to further investigation about
their potential impact on energy consumption within the cloud
Index Terms—energy efficiency, load balancing, cloud infrastructure. The comparative evaluation of the algorithms
reveals their strengths and weaknesses and more importantly
I. INTRODUCTION provide motivation for further work in the area of energy
Cloud computing offers a scalable and economical solution efficient and environmentally aware cloud computing.
for addressing rapidly increasing computational needs of ICT The structure of the paper is as follows, Section II presents
applications. Increasing popularity and widespread adaptation the preliminary details about the load balancing algorithms.
of cloud computing is resulting in continual growth in terms of Section III presents the design details of the system, where the
numbers and size of cloud facilities, raising questions about load balancing algorithms were implemented and tested.
effective management of workloads as well as long term Section IV describes the two load balancing algorithms.
environmental implication of cloud computing model. In fact, Section V presents the results of testing the algorithms in a
management of cloud applications with the view to achieve cloud environment. The paper ends with a summary in Section
energy efficiency is now being considered a critical challenges IV.
to be dealt with in cloud computing. II. PRELIMINARIES
Existing techniques for achieving energy efficiency in
cloud computing focus on strategic power management This section describes the preliminaries concerning the
operations e.g. by suggesting the use of low powered machines cloud infrastructure and load balancing algorithms.
[1] and deploying applications on fewer machines or spreading Task is an application component which is either executed
them evenly across available resources/machines [2]. or stored in a virtual machine (VM) with specific CPU,
Typically, such techniques are applied at the initial deployment memory and disk space. A cloud application can have several
stage i.e. while deploying new applications on cloud. In the tasks each running on a VM.
work presented in this paper we address the load balancing and Host is a physical server capable of hosting several VMs.
energy efficiency issues at post-deployment stage. Particularly, Load can be considered to be a number of tasks which
we focus on load balancing as a way to ensure effective and currently exist at a host
efficient utilization of cloud resources and consequently to find As tasks arrive at a host, the load of the host is increasing.
alternative deployment configurations that can contribute Due to the heterogeneity of the system tasks can be completed
towards saving energy in the cloud infrastructure. at different time intervals and therefore some hosts will be
The two load balancing algorithms we describe in this more loaded than the others at any given time. Thus load
paper aim to minimize wastage of cloud resources as a result of balancing, as the name implies, is a method to distribute the
under-utilization of some resources; and minimize lengthy load to the hosts in the system.
response times as a result of over-utilization, where both cases A load balancing algorithm needs to consider various
contribute towards excess energy consumption. We adopt an factors in order to decide if the system needs balancing and
agent-based system development approach for the how to perform it. Depending on how these decisions are
taken, where they are taken, how they are performed and what
additional benefit is being sought (e.g. energy efficiency in our
© Copying permitted only for private and academic purposes.
This volume is published and copyrighted by its editors
perspective), we can identify different types of heuristics and host supports this type. Otherwise, it remains in the waiting list
policies for load balancing. of the host.
Before we delve into more technical details about our load
B. Host
balancing algorithms it is worth noting our reasons for its
importance: A host is a central entity in the cloud infrastructure and is
Reduces overloading of certain resources e.g. hosts the place where the load balancing happens in our system.
Energy efficiency by virtue of minimizing the overall
execution time of tasks in cloud infrastructure
Maximises the amount of work done by the cloud
infrastructure (throughput).
In a cloud infrastructure, we assume that tasks can be
migrated between hosts and new tasks can arrive at any host at
any time. In a cloud infrastructure, there can be N number of
hosts, which form the set H. Each host , has a load at
any time . The load depends on the used CPU, memory, Figure 2: Internal structure of host Agent
disk capacity, etc. of the host. Denoting the set of
values for CPU, memory, capacity, any other quantity that Each host is represented by an agent that runs individually
affects the load of a host, we define the load function from other host agents in the cloud infrastructure. The internal
, for each host i. structure of a host agent is composed of five components, the
network component, the processor, the task manager, the
Following the utility-based optimization approach [1] the
logger and the load balancer as shown Figure 2.
utility of each task is defined as the inverse of its load. Hence,
we define the utility function for a host i as Network Component: each host agent is able to interact
with other host agents by sending and receiving messages in a
reliable manner. In this respect, a host agent acts as both a
server and a client. As a server, it runs continuously in the
The utility function is a metric for the load of a host. background, in order to accept messages and tasks.
Depending on the load balancing heuristic, we need to Processor: The component that represents the running tasks
minimise or maximise . Below we denote the system utility in a host is the processor component. In this respect, the
function, which represents the overall optimisation problem at processor is responsible for creating or setting up the VMs
the system level. We are trying to find solutions that will end where tasks can be deployed and executed. The processor starts
up minimizing over time. the creation of VMs and subsequently execution of tasks by
picking them from a waiting list, which is basically a
temporary storage space in the host agent where new task
(request) arrives. New tasks wait in the waiting list until their
required resources are allocated (e.g. a VM is setup).
Task Manager: The task manager is the component of host
III. SYSTEM DESIGN agent that is responsible for receiving and analysing new tasks,
Here we describe the design features of the different and loading tasks from waiting list to the processor.
modules which contribute towards the design of a system that Logger: The logger component (as shown in Figure 3)
allow us to implement and test our load balancing algorithms receives messages from the load balancer about the state of the
and give a solution that is applicable in cloud computing. host and any requests that are received from other hosts. The
logger can log messages, as list of events, either locally or
A. Tasks receive messages from other hosts in the cloud infrastructure.
A task is executed at the host and has certain requirements.
In our system each new task has certain characteristics or
structure, as shown in Figure 1.
Figure 3: Logger component and format of a Log
Figure 1: Task agent structure
Load Balancer: The most important and decision making
Each task has a certain type and can only be executed if the entity in the host agent is the load balancer. Depending on the
algorithm that will be used, the decisions for the load balancing system is the host in which the task arrives, and the candidates
operation will be taken here. The load balancer is able to are the other hosts in the network.
communicate with the processor, in order to get latest load This algorithm is triggered when a host reaches the high
information. It will use the network component to send
threshold, which sets the host in high load state. Before we start
messages to other hosts. The network component will pass any
received messages to the load balancer for evaluation. If a task the discussion on the load balancing algorithm, we need to set
is received, then the load balancer uses the task manager to the following policies for host agents:
check the task details/structure. The load balancer has an a) Transfer policy: We use a preset ‘High’ threshold value,
address book that holds the addresses of other host agents in above which the host agent triggers the load balancing
the system. The decision making about load balancing operation. The host agent starts looking for candidate host
operation is based on the notion of state transitions. In this agents to send tasks. If a host is below this value, then it
respect, each host agent, can be in one of the following states at
may be able to receive more tasks.
any time:
b) Selection policy: Host agents follow a two-step process to
choose tasks to send. In the first step, tasks are selected
based on type e.g. small, medium or large VM instances.
On the second step, hosts randomly choose from the set of
tasks of the same type. We receive tasks of the type that
we can execute in the respective hosts.
c) Location policy: Host agents can send requests to all the
A host agent can determine the state by checking its current hosts in their address book and then wait for an answer. If
load (in the Processor component) against the more than two answers are received at the same time, then
thresholds in a local statistical the hosts choose randomly from the two. Host agents wait
table. The following table shows the relation between the for a period of time before they resend any requests, to
thresholds and the states. avoid flooding the network with unnecessary messages.
d) Information policy: Host agents follow a demand-driven
approach, since the requests are sent only when there is
change in state of the host agent.
Algorithm 1: Secretaries (Stage 1)
Each host agent determines its state independently from the
Initialise a statistics table
others and takes the appropriate action depending on the load
balancing algorithm. while cancellation has not been requested do
get host waiting list load
IV. LOAD BALANCING store the values in the statistics table
Here we describe two algorithms for load balancing and if the statistics table has adequate size then
energy efficiency. The algorithms are based on heuristics and calculate average waiting list size
their main focus is to achieve efficient utilization of available determine the state of the host
resources and consequently lower the energy consumption, if the state is High then
while having a minimal overhead in the system. Decide number and type of tasks to send out
A. Secretaries Send load balancing request to hosts in the
This heuristic is inspired by the swarm intelligence address book
approaches and the reality of an office environment. For
example, in a company, when a manager wants a task done, he If the algorithm decides that the host has high load, then it
delegates it to a secretary. The secretary in her part, makes a proceeds to ask for help. The “ask for help” operation will be
couple of phone calls, or goes around the office, and finds a referred as Load Balancing Request (LBR). As mentioned
suitable person to execute the task. If we imagine a situation, in before, a host is in high state when it is over the high threshold.
which there is more than one secretary, then we can have the In this algorithm, host agents follow the strategy that they need
necessary background for a swarm intelligence approach. Each to send as many tasks as they can to other hosts, in order to fall
one of the secretaries will perform their quest, independently of under the high threshold. In this case, this will happen when the
the others and once they find a candidate they either pass-over hosts send the excessive items of the waiting list.
their task, or move to the next candidate. The manager in our
Once a host agent sends the LBR, the next stage happens in Once a suitable candidate is found that is willing to accept
the load balancing algorithm of the host agent that receives it. excess load of the initial requester (host agent), the first step at
this stage is to stop the load balancer. The final number of tasks
to send out is the maximum number that the other host agent
Algorithm 2: Secretaries (Stage 2) can accept. The next step is to pick up the tasks that will be
Check host state sent out. To perform this step we choose the tasks randomly
if host state is not High or High Average then without adding further complexity to the algorithm.
Check if the types of tasks (within LBR) can be B. Eager Worker
executed on this host This algorithm is inspired by the epidemic protocols; a
if they can be executed then relatively new approach to load balancing by spreading
Decide number of tasks to ask for information around the system in a similar way that a virus (or
Accept the LBR and send the number of tasks gossip) spreads. In this scenario, the central role is played by a
back to the sender worker who does not have any work to do. However, since he
else is eager to work, he goes to all the people that he knows and
Forward the LBR to host agents in the address book announces his availability (“infects”). Since he cannot do
anything else, he waits for someone to call him. The people
The receiver host agent, checks its status looking at the who know this fact now have the option to either use him, or
local statistics table. If the state is Low or Low Average, then it spread the rumor around that there is an available worker
can accept the LBR. The host agent asks for as many tasks as it (“spread the infection”). In our case, worker is a host agent
is needed to reach the High threshold, or just over it, thus who goes under the average threshold and is in either Low
setting its state at High Average or High. The main criterion for Average or Low state. The algorithm has following policies:
this to happen is the local queue size, because this determines a) Transfer policy: Host agents use the Average threshold
the size of the batch. After receiving the tasks, the host agent value in order to trigger the load balancing operation.
can still accept more tasks until an acceptable state is reached. Below this value the hosts will be able to receive tasks.
Once the host accepts the LBR message, it sends back to b) Selection policy: This policy is the same as in the
the initial host agent the number of tasks that it can receive, in “Secretaries” algorithm.
order to help the initial sender/requester host agent. This leads
c) Location policy: Host agents are selected for sending a
us to the third and last stage of the algorithm.
load balancing request. After sending the requests, the
sender host agent waits for a reply. Requests are sent in
Algorithm 3: Secretaries (Stage 3)
an interval, to avoid flooding the system. If a request for
if suitable candidate was found after sending LBR then
help arrives from two or more host agents, then host
Stop load balancing
agents operate in a “first-come, first-served” manner.
Pick up the desired number of tasks from the
d) Information policy: Host agents follow a demand-driven
waiting list policy. The requests are sent, when the host is in Low or
Send tasks Low Average state.
This algorithm follows a more opportunistic model: if there
is help, the host agent will make use of it without considering
the overall state of the system.
The algorithm has a two-stage execution, contrary to the
three stages in “Secretaries” algorithm. At the first stage a host
agent determines the state of the host and then sends the LBRs.
Algorithm 4 includes the pseudo-code for this stage.
Algorithm 4: Eager Worker (Stage 1)
Initialise a statistics table
while cancellation has not been requested do
get host waiting list load
store the values in the statistics table
Figure 4: Some of the possible states of host agents. Load
balancing starts when the host agent is in High load state. if the statistics table has adequate size then
The numbers represent the stages of the algorithm. calculate average waiting list size
determine the state of the host The choice of tasks to send follows a similar pattern to the
if the state is Low or Low Average then “Secretaries” algorithm. In this initial design, we decided to
Decide number and type of tasks to send choose the tasks in a random way.
Send load balancing request to host agents in If there is no need for load balancing, then the LBR is
the address book forwarded to other hosts of the network. If the LBR arrives
back to the original host agent, then it is rejected automatically,
Most of the steps in this algorithm are similar to the thus, avoiding duplicate requests going through the network.
“Secretaries” algorithm. When deciding for the number of tasks
and types to send, we base our calculations on the waiting list
of hosts, since this is what determines the amount of tasks to
delegate. The host agents in this algorithm ask for as many
tasks as needed, in order to remain under the High threshold.
When the number and types of tasks to ask is decided, a
LBR is sent to either a random number of host agents in the
address book or to all of them. If the LBR is sent to all of them
then this might lead to an overflow of messages in the system. Figure 5: Possible states of host agents. Load balancing
Since this algorithm follows an epidemic approach, the LBRs starts when the host agent is in Low or Low Average state. The
will reach to all the host agents in the system.. numbers represent the stages of the Eager Worker algorithm
V. RESULTS
Algorithm 5: Eager Worker (Stage 2) The algorithms were tested in a single site cloud environment.
if load balancing request was received then The message exchanges between host agents happen in a
Check host state round-robin format. A host agent “knows” only one other host
If host state is High or High Average then agent. The reasoning behind this scenario, compared to
Check if the sender host agent can execute the broadcasting or n-to-n interactions, was to minimize the
tasks of this host complexity of managing multi-agent interactions (which was
if they can be executed then not the focus of the work presented here) and more importantly
Stop load balancing to see if the algorithms develop any behavior. We used
Decide number of tasks to send and choose ZeroMQ (http://zeromq.org/) technology to realize message
tasks exchange between host agents. Command messages travel in
Accept the LBR and send the tasks one direction starting from one host agent to the last but task
Start load balancing transfer can happen between any two host agents.
else We ran our experiments for each algorithm five times and
Forward LBR to host agents in the address book we get averages of the number of tasks at each host after an
interval. We create a set of 75 tasks in individual VMs and
The next stage of the algorithm is executed by the host deployed them in the first host. Our aim was to observe how
agent that receives the request. the algorithms handle spikes of load and energy consumption at
This time the host agent accepts the LBR if its state is in a host. Furthermore, we monitored the number of messages
High Average or High. The High Average state is included as exchanged between the host agents every minute.
well, because the host agent at this stage needs tasks to finish The results of testing both algorithms are shown in Figure
execution. Since the algorithm follows an opportunistic model, 76 and Figure 7.
if there is an idle worker, then it sends tasks across. The For Eager Worker load balancer, Table 1 shows the
number of tasks depends on the total size of the waiting list. It average messages per minute circulating in the network.
sends either the maximum tasks that can be executed in the
Table 1: Eager Worker: Number of messages (avg. five runs)
other hosts, or in the case of High Average state, enough tasks
so as to get close to the Average threshold. Total transferred tasks 60
The load balancing operation needs to stop for the same LBRs per minute 32,8
reasons as before and it is restarted after the host agent finishes
Messages per minute 234
the transfer of tasks.
On average there were around 33 LBR messages every minute other hand, due to the formation of neighborhoods and slower
since a number of host agents with low or low-average states distribution of load, the execution finished almost 2 minutes
were asking for tasks. later than Eager Worker.
Table 2: Secretaries: Number of messages (avg. five runs)
Total transferred tasks 49
LBRs per minute 0,5
Messages per minute 191
For Secretaries load balancer, the first host agent sends a
LBR every time it needed load balancing – as shown in Table
12, hence the very low number of LBRs in the network.
As shown in Figure 6, it is obvious that Eager Worker
achieves a better overall performance at the expense of Figure 7: Distribution of tasks on each node after approximately 10
increased network traffic. The load is distributed uniformly minutes of operation (averaged and rounded)
among the nodes. In particular, Host B did not get as many
VI. SUMMARY AND FUTURE WORK
tasks due to the preset MaxRetransmits value that restricts host
agents to transmit only 5 messages during the testing period. This paper presents two heuristics-based algorithms for
load balancing. The results of testing both algorithms reveal
their advantages and disadvantages as one might be performing
better than the other in any given context. By tweaking the
various parameters, we can achieve better performance, but
there is always a trade-off. The work presented in this paper
focuses on testing the load balancing aspect of the algorithm. In
future work, we aim to analyze the impact of these algorithms
on the energy consumption of cloud infrastructure within the
context of ECO2Clouds project (www.eco2clouds.eu).
ECO2Clouds allows quantification of energy consumption
and environmental impact (CO2 emissions) at three different
levels of cloud infrastructure. These include testbed, physical
Figure 6: Distribution of tasks on each node after host and VM levels. The ability to quantify the energy
approximately 5 minutes of operation (averaged and rounded) consumption at testbed and physical host level will allow us to
investigate the use of our load balancing heuristics as runtime
Whereas, in the case of secretaries algorithm, as shown in adaptation mechanisms that can balance resource utilization
Figure 7, Host A was 7 hops away from Host H, hence its LBR with reduction in energy consumption.
messages never arrived that far. Due to the design of the
REFERENCES
algorithm, LBRs are always trying to find overloaded hosts.
[1] G. Luigi Valentini, W. Lassonde, S. U. Khan, N Min-
Overall, Eager worker generates approximately 28% more Allah, S. A. Madani, J. Li, L. Zhang, L. Wang, N. Ghani,
traffic than Secretaries, but converges faster to an overall load J. Kolodziej. H. Li, A. Y Zomaya, C. Z. Xu, P. Balaji, A.
Bishnu, F. Pinel, J. E. Pecero, D. Kliazovich. P. Bouvry.
balanced state. On the other hand, Secretaries tend to form An overview of energy efficiency techniques in cluster
“neighbourhoods” e.g. host agent A visits first its closest computing systems. In Cluster Computing. March
2013, Volume 16, Issue 1, pp 3-15
neighbor and gives them work to do and then slowly spreads its [2] P. Lindberg, J. Leingang, D. Lysaker, S. U. Khan, J. Li.
load to the rest. For this reason the further hosts seldom receive Comparison and analysis of eight scheduling heuristics
any tasks. Even if there were more tasks, Host H would have for the optimization of energy consumption and makespan
in large-scale distributed system. In Journal of
never been reached due to the preset MaxRetransmits value. Supercomputing. January 2012, Volu. 59. Issue 1, pp.
Removing the MaxRestransmits constraint or increasing its 323-360.
[3] L. Skorin-Kapov, et al., "Approaches for Utility-Based
preset value may allow spreading the tasks to further hosts. QoE-Driven Optimization of Network Resource
However, the advantage of secretaries algorithm is lower Allocation for Multimedia Services," in Data Traffic
Monitoring and Analysis. vol. 7754, E. Biersack, et al.,
network traffic: LBRs are sent only when it is needed. On the Eds., ed: Springer Berlin Heidelberg, 2013, pp. 337-358.