Proceedings of CCIS2014
AN IMPROVED K-SUBSET ALGORITHM FOR LOAD
BALANCE PROBLEMS IN CLOUD COMPUTING
Linlin Tang, Pingfei Ren, Jengshyang Pan
School of Computer Science and Technology,
Harbin Institute of Technology Shenzhen Graduate School, Shenzhen, China
hittang@126.com
Abstract: Cloud Computing has earned more and more
attention for its important role in the modern network
development process. It can be seen as a new distributed
computing mode based on virtualization process. One of
the problems for Cloud Computing is load balance. An
improved k-subset algorithm is proposed in this paper
for this problem. Good performance in experiments on
CloudSim platform shows its efficiency
Keywords: Cloud Computing; Load balance; k-subset
algorithms; CloudSim.
1 Introduction
Cloud Computing has become more and more popular in
network. Generally speaking, it can be seen developed
from grid computing with some characteristics of utility
computing. It also has basic feature of virtualization [1].
Cloud Computing could can both benefit its users and
providers[2]: For those users, a large number of money
buying IT resources could be saved by using services
provided by the cloud services providers[3]. For those
cloud services providers, money could be earned by
using its machines’ abilities fully. Here the word “users”
could be an end user, an organization or even another
cloud services provider [4].
There are two main opinions on cloud computing [5]:
concreted or distributed. From user’s view their tasks are
submitted to a “cloud”,and thenthe “cloud” returns the
result, just like days in middle 20thcentury. On the other
hand, tasks may be divided into several parts and then
processed by one or more real machines, just like
distributed computing. In fact, tasks users submitted is
processed by many virtual machines installed in one or
more real machines, in another word, in a distributed
method through virtualization.
Both the way cloud serve users and the types of services
affect the way to make load balance decisions. Here we
give some basic type of services [6]:
Infrastructure as a service (IaaS)
IaaS providers provide Process ability, Storage, network
and other fundamental computing ability as services,
hidden details of real machines [7]. Users could deploy
and control all the things in virtual machines except the
real hardware where virtual machines are deployed in.
IaaS providers are: EC2, HP Cloud, Azure Service as a
service, etc.
Platform as s service (PaaS)
PaaS providers provide a kind of platform where OS,
DB, Runtime Environment, web server are already given.
Users could only deploy and control their own software
and the runtime needed.
PaaS providers are: Google App Engine, Windows
Azure Services, AWS Elastic Beanstalk, etc.
Software as a service (SaaS)
SaaS providers provide software for users. Here users
are often referred to as end users, in another word,
people. Users relief themselves from installing software,
resulting in more hard disk space and less load for their
CPU. By using SaaS, device inventors could make
devices smaller faster while have more functionality.
People usually give particular names for some kind of
SaaS by its function: Desktop as a service, Business
Process as a Service, Communication as a service, etc.
SaaS providers are: Google Apps, Microsoft Office 365,
onlive, GT Nexus, etc.
Others
The aforementioned three types of cloud services are
defined by NIST, Nov, 2011. Other organizations have
several different opinions about it. In Feb, 2012, ITU-T
raised network as a service (NaaS), which could be seen
as the same level where IaaS, PaaS and SaaS at. NaaS is
determined by network provider, network user and what
kind of service it provides; take VPN, BoD and MVNOs
for example.
Also ITU-T separates CaaS from SaaS from the view of
its real time attribute.
In this paper we mainly focus on the CPU-bound tasks,
ignoring other attributes of the task such as I/O and
bandwidth needed.
2 Related work
Load balancing problem is studied deeply in traditional
distributed systems. Aim of load balancing is to avoid
some particular processing nodes have heavy load while
others have almost zero load, in another word, to avoid
imbalance. Load balancing try to optimize system
performance within its ability while overload control
mainly focus when and how to determine refusing new
requests, where in cloud computing context it mainly
____________________________________
978-1-4799-4719-5 /14/$31.00 ©2014 IEEE