01-07-2013, 02:35 PM
Ant colony Optimization: A Solution of Load balancing in Cloud
Ant colony Optimization.pdf (Size: 726.43 KB / Downloads: 90)
Abstract
As the cloud computing is a new style of computing over internet. It has many advantages along with some
crucial issues to be resolved in order to improve reliability of cloud environment. These issues are related
with the load management, fault tolerance and different security issues in cloud environment. In this paper
the main concern is load balancing in cloud computing. The load can be CPU load, memory capacity,
delay or network load. Load balancing is the process of distributing the load among various nodes of a
distributed system to improve both resource utilization and job response time while also avoiding a
situation where some of the nodes are heavily loaded while other nodes are idle or doing very little work.
Load balancing ensures that all the processor in the system or every node in the network does
approximately the equal amount of work at any instant of time. Many methods to resolve this problem has
been came into existence like Particle Swarm Optimization, hash method, genetic algorithms and several
scheduling based algorithms are there. In this paper we are proposing a method based on Ant Colony
optimization to resolve the problem of load balancing in cloud environment.
Introduction
Cloud Computing
Cloud computing has become very popular in recent years as it offers greater flexibility and
availability of computing resources at very low cost. The major concern for agencies and
organizations considering moving the applications to public cloud computing environments is the
emergence of cloud computing facilities to have far-reaching effects on the systems and networks
of the organizations. Many of the features that make cloud computing attractive, however, can
also be at odds with traditional security models and controls. As with any emerging information
technology area, cloud computing should be approached carefully with due consideration to the
sensitivity of data. Planning helps to ensure that the computing environment is as secure as
possible and is in compliance with all relevant organizational policies and that data privacy is
maintained.
Cloud Platform as a Service (Paas)
The capability provided to the consumer is to deploy onto the cloud infrastructure consumer
created or acquired applications created using programming languages and tools supported by the
provider. The consumer does not manage or control the underlying cloud infrastructure, but has
control over the deployed applications and possibly application hosting environment
configurations.
Virtualization
It is a very useful concept in context of cloud systems. Virtualisation means ”something which
isn’t real”, but gives all the facilities of a real. It is the software implementation of a computer
which will execute different programs like a real machine. Virtualisation is related to cloud,
because using virtualisation an end user can use differentservices of a cloud. The remote
datacentre will provide different services in a fully or partial virtualised manner.
Load balancing in cloud computing
Load Balancing is a method to distribute workload across one or more servers, network
interfaces, hard drives, or other computing resources. Typical datacenter implementations rely on
large, powerful (and expensive) computing hardware and network infrastructure, which are
subject to the usual risks associated with any physical device, including hardware failure, power
and/or network interruptions, and resource limitations in times of high demand.
Load balancing in the cloud differs from classical thinking on load-balancing architecture and
implementation by using commodity servers to perform the load balancing. This provides for new
opportunities and economies-of-scale, as well as presenting its own unique set of challenges.
Load balancing is used to make sure that none of your existing resources are idle while others are
being utilized. To balance load distribution, you can migrate the load from the source nodes
(which have surplus workload) to the comparatively lightly loaded destination nodes.
Dynamic Load balancing algorithm
In a distributed system, dynamic load balancing can be done in two different ways:
distributed and non-distributed. In the distributed one, the dynamic load balancing algorithm is
executed by all nodes present in the system and the task of load balancing is shared among them.
The interaction among nodes to achieve load balancing can take two forms: cooperative and noncooperative
[4]. In the first one, the nodes work side-by-side to achieve a common objective, for
example, to improve the overall response time, etc. In the second form, each node works
independently toward a goal local to it, for example, to improve the response time of a local task.
Dynamic load balancing algorithms of distributed nature, usually generate more messages than
the non-distributed ones because, each of the nodes in the system needs to interact with every
other node. A benefit, of this is that even if one or more nodes in the system fail, it will not cause
the total load balancing process to halt, it instead would affect the system performance to some
extent.
Policies or Strategies in dynamic load balancing
In non-distributed type, either one node or a group of nodes do the task of loadbalancing. Nondistributed
dynamic load balancing algorithms can take two forms: centralized and semidistributed.
In the first form, the load balancing algorithm is executed only by a single node in the
whole system: the central node. This node is solely responsible for load balancing of the whole
system. The other nodes interact only with the central node. In semi-distributed form, nodes of
the system are partitioned into clusters, where the load balancing in each cluster is of centralized
form. A central node is elected in each cluster by appropriate election technique which takes care
of load balancing within that cluster.
Ant Colony Optimization
Individual ants are behaviorally much unsophisticated insects. They have a very limited memory
and exhibit individual behavior that appears to have a large random component. Acting as a
collective however, ants manage to perform a variety of complicated tasks with great reliability
and consistency.
Although this is essentially self-organization rather than learning, ants have to cope with a
phenomenon that looks very much like overtraining in reinforcement learning techniques.
The complex social behaviors of ants have been much studied by science, and computer scientists
are now finding that these behavior patterns can provide models for solving difficult
combinatorial optimization problems. The attempt to develop algorithms inspired by one aspect
of ant behavior, the ability to find what computer scientists would call shortest paths, has become
the field of ant colony optimization (ACO), the most successful and widely recognized
algorithmic technique based on ant behavior.
Basic principles of trail laying
Depending on the species, ants may lay pheromone trails when travelling from the nest to food, or
from food to the nest, or when travelling in either direction. They also follow these trails with a
fidelity which is a function of the trail strength, among other variables. Ants drop pheromones as
they walk by stopping briefly and touching their gesture, which carries the pheromone secreting
gland, on the ground. The strength of the trail they lay is a function of the rate at which they make
deposits, and the amount per deposit. Since pheromones evaporate and diffuse away, the strength
of the trail when it is encountered by another ant is a function of the original strength, and the
time since the trail was laid. Most trails consist of several superimposed trails from many
different ants, which may have been laid at different times; it is the composite trail strength which
is sensed by the ants. The principles applied by ants in their search for food are best explained by
an example as given in [7].
Related Work
Many researchers have invented different techniques for load balancing and distributing the
workload in a cloud environment. Many tools has been developed like c-meter, Amizone EC-2,
GrenchMark etc.[18]
Many methods likehoneybee Foraging system,had been took place in the area of research. These
methods also inspired by swarm intelligence. This algorithm is derived from the behaviour of
honey bees for finding and reaping food. There is a class of bees called the forager bees which
forage for food sources, uponfinding one, they come back to the beehive to advertise this using a
dance called waggle dance. The display of this dance, gives the idea of the quality or quantity of
food and also itsdistance from the beehive. Scout bees then follow the foragers to the location of
food and then began to reap it. They then return to the beehive and do a waggle dance, which
gives an idea of how muchfood is left and hence results in more exploitation or abandonment of
the food source.
Proposed Work
Ant based control system was designed to solve the load balancing in cloud environment.Each
node in the network was configured with
1) Capacity that accommodates a certain.
2) Probability of being a destination.
3) Pheromone (or probabilistic routing) table.
Each row in the pheromone table represents the routing preference for each destination, and each
column represents the probability of choosing a neighbor as the next hop. Ants are launched from
a node with a random destination.
In this approach, incoming ants update the entries the pheromone table of a node. For instance, an
ant traveling from (source) to (destination) will update the corresponding entry in the pheromone
table in. Consequently, the updated routing information in can only influences the routing ants
and calls that have as their destination. However, for asymmetric networks, the costs from to and
from to may be different. Hence, In thisapproach for updating pheromone is only appropriate for
routing in symmetric networks.