Nature Inspired Load Balancing Algorithms in Cloud : Comparative Study

Nature Inspired Load Balancing Algorithms in Cloud : Comparative Study

Divya Kumawat

Department of Computer Engg. Atharva College of Engineering,

Malad(W), Mumbai, India

Aruna A. Pavate Department of Computer Engg. Atharva College of Engineering,

Malad(W), Mumbai, India

Santosh Dodamani Department of Computer Engg. Atharva College of Engineering, Malad(W), Mumbai, India

Abstract Cloud computing is no more new form of computing. Most of us are using it in our day today life. It is an internet based technology where on demand requests are fulfilled. Load balancing plays a crucial role in clouds performance. The aim of load balancing is to decrease response time, increase throughput and fault tolerance, with the help of proper resource utilization. Many researches are going on in the field of nature inspired load balancing algorithm. This algorithms are also used with other algorithms in order to get better performance .This paper reviews, describes and performs comparative study of nature inspired load balancing algorithm such as ant colony optimization, genetic algorithm etc.

KeywordsCloud Computing,Load Balancing,Nature Inspired Algorithm.

1. INTRODUCTION

   Cloud computing provides on demand computing resources by using distributed servers. The main advantage of cloud computing includes elasticity, pay per use and self- provisioning. The performance of distributed network depends on the load distribution among the participating nodes. As cloud needs to handle changing demand on virtual machines (VM),it needs to perform load balancing among VMs in order to achieve good performance and proper resource utilization. Load balancing algorithm improves the performance in terms of reduced total waiting time, response time and completion time for the resources. Basically there are two types of load balancing techniques: 1) Static 2) Dynamic. In static load balancing algorithm prior information about the system is necessary while in dynamic load balancing algorithm monitors the changed in the system and redistribute the load according to current situation. It has been observed that Dynamic load balancing performs better than static load balancing.[9].There are many load balancing

2. NATURE INSPIRED COMPUTING

   It refers to classes of meta-heuristic algorithms that resembles or are inspired by some natural phenomena explained by natural sciences [10]

   Nature inspired algorithm can be classified into four major categories: bio-inspired algorithm, physics/chemistry-based, and others. This NIA are further sub classified as:

   1. Bio-Inspired algorithm

      Based on Swarm Intelligence (SI)-It is a collection of agents having no central authority to control the behavior. These agents interacts with each other. Interaction between such agents form the basis for intelligence.SI based algorithms are most popular and widely used algorithm. The reason behind

      popularity is that they usually shares information among multiple agents, so that self organization, co-evolution and learning during iterations and another reason is multiple agent can be parallelized easily to get large-scale optimization. Swarm based algorithm includes ant colony optimization, Particle swarm optimization etc. The SIA are based on the idea of collective behaviors of insects living in colonies such as ants, bees, wasps and termites [10]

   2. Bio-Inspired (Not based on SI)-these algorithms are inspired from biological phenomena. Example- Genetic algorithm.

   3. Physics chemistry Inspired [12]: This type of algorithm has physics or chemistry as a source of inspiration. It includes certain physical or chemical laws, related to electrical charges, gravity, river systems etc.

   4. Others [12]: It is difficult to put some algorithms into above given four categories. Those algorithm falls under this category.

3. COMPARISON OF DIFFERENT NATURE INSPIRED LOAD BALANCING ALGORITHM

   1. Ant Colony optimization:

      Ant Colony optimization algorithm is a biological inspiration from real ant colonies. At the core of this behavior is the indirect communication between the ants by means of chemical pheromone trails [1].Ant finds the shortest path between their nest and food sources with the help of chemical pheromone trails. When ant explores the area randomly they leave a chemical pheromone trail on the ground. During the ants return journey, the quantity of pheromone left may depend on the quality and quantity of the food. Ant chooses the path with strong pheromone concentrations. Ekta Gupta and Vidya Deshpande have proposed ACO based load balancing algorithm in which load is migrated on the basis of threshold value. If the current node has lesser load as compared to threshold, it will search for neighboring overloaded node and perform load balancing [2].

   2. Artificial Bee Colony Algorithm:

      This algorithm is based on foraging behavior of honey bee. In bees colony there is scout bees and forage bees. Scout bees searches for food source, on finding source they return to hive and perform a waggle dance. This waggle dance informs hive forage bees about the food quantity source and its distance. Then Scout bees lead the forage bees to the location and forage bees begins to reap honey. The food

      sources are selected randomly. Same Behavior is applied in the field of cloud computing where honey bees will represent task and food source will be represented as virtual machine. These virtual machines can be overloaded (representing depletion of food source) or under loaded. So in order to achieve better performance load balancing is performed where the task having lowest priority is moved to under loaded node(represents new food source has been obtained)[3].

   3. Ozmos Load Balancing algorithm:

      This algorithm is inspired from osmosis. Osmosis is a self-regulatory process where a solvent moves across a semi-permeable membrane separating two solutions with different solute concentration. The ozmos algorithm dynamically reallocates tasks among participating nodes. The balancing process is completely decentralized, supported by the activity of ant-like agents that are executed by nodes on a Chord overlay. Each node manages a batch scheduling queue and can execute one or more tasks concurrently with different performance characteristics. Here it is assumed that tasks are independent, non-divisible, and non preemptive.

      A node identifier is divided into class id & Chord identifier. Nodes belonging to the same class are connected to adjacent to form a ring. A unique identifier having same class prefixes is allocated to the task. Each node calculates osmotic pressure periodically. Osmotic pressure is the difference between It uses osmosis agent to perform load balancing. Osmosis agent migrates task from high concentration to a low concentration node.

   4. Genetic Algorithm:

   Genetic Algorithm is a Non-SI based Nature Inspired (NI) algorithms inspired from the genetic phenomena of nature. According to Jingyi Ma [11] heuristic genetic load balancing algorithm (HGLBA) reduces overall response time of the tasks.

   The Genetic Algorithm generates a initial population P(0) which is a initial solution coded in the form of chromosomes. Generate step is followed with evaluation step where fitness value of the initial population is calculated. Fitness function calculation is followed by selection, crossover and mutation [5].

   • Selection:

     Chromosomes are selected from the population to be parents to crossover. To select a chromosome roulette whel selection, Boltzman selection, tournament selection, rank selection, steady state selection and some others method can be used [4].

   • Crossover:

     In crossover, the new chromosome will take the best characteristics from each of the parents. Here two selected parental individuals S1 and S2 will be combined to form a new individual solution S0 which keeps the same individuals (VMs) in two parental selections and discards the different ones. Different VMs in two parental individual distribute load to smallest loaded nodes in the physical machine until good load balancing is achieved. [4].

     • Mutation:

   Physical machines are selected according to mutation probability. One or more virtual machines are swapped between these selected physical machines to form a new solution.[4].

   Table 1: Comparision of different nature Inspired load balancing algorithm

   Characteristics/Load Balancing Algorithm	Ant Colony optimization [7]	Artificial Bee Colony Algorithm [7]	Genetic Algorithm	Ozmos load balancing algorithm
   Dynamic	YES	YES	YES	YES
   Distributed	YES	YES	YES	YES
   Scalability	YES	NO	YES	YES
   Synchronization	YES	NO	NO	YES
   Heterogeneous	YES	YES	YES	YES

4. CONCLUSION

Cloud computing is a utility based computing where resources can be requested/released on the basis of requirement. The major issues of cloud computing is Load Balancing and process migration. Overloading of a system may degrade the performance the system. For proper utilization of resources, the efficient load balancing algorithm is implemented.. In this paper, we have surveyed different nature inspired load balancing algorithms used in a cloud environment proposed by different researchers.

REFERENCES

1. Christian Blum Ant colony optimization: Introduction and recent trends ,Elsevier 2005

2. Ekta Gupta, Vidya Deshpande, A Technique Based on Ant Colony Optimization for Load Balancing in Cloud Data Center, 13th International conference on Information Technolog, 2014 IEEE

3. Load Balancing Of Tasks In Cloud Computing Environment Based On Bee Colony algorithm 2015 Fifth International Conference on Advances in Computing and Communications.

4. Chandrasekaran K., Usha Divakarla Load Balancing of Virtual Machine Resources in Cloud Using Genetic Algorithm ICCN 2013, pp. 156168. © Elsevier Publications 2013.

5. Ritu KapurReview of Nature Inspired Algorithms in Cloud Computing

6. Amos Brocco ozmos: Bio-Inspired Load Balancing in a Chord-based P2P Grid ACM 978-1-4503-0733-8/11/06,BADS11, June 14, 2011, Karlsruhe, Germany.

7. Mahendar , Dr. Shahu Chatrapati K , A Comparative Nature Inspired Load Balancing Algorithms in a Cloud Computing Environment , International Journal of Conceptions on Computing and Information Technology ,Vol. 3, Issue. 1, April 2015; ISSN: 2345 – 9808

8. Amos Brocco The grid, the load and the gradient A bio-inspired approach to load balancing, Natural Computing March 2013, Volume 12, Issue 1, pp 6985

9. L.D. Dhinesh Babua,P. Venkata Krishna b aHoney bee behavior inspired load balancing of tasks in cloud computing environments.

10. Siddique N, Adeli H. Nature Inspired Computing: An Overview and Some Future Directions, Published online 2015 Nov 30. Cognit Comput. 2015; 7: 706714.

11. G. Guo-Ning and H. Ting-Lei, Genetic Simulated Annealing Algorithm for Task Scheduling based on Cloud Computing Environment , in Proc. of International Conference on Intelligent Computing and Integrated Systems, pp. 60-63, 2010

12. Iztok Fister Jr., Xin-She Yang , Iztok Fister , Janez Brest , Dusan Fister

,A Brief Review of Nature-Inspired Algorithms for Optimization, Elektrotehniski Vestnik 80(3): 17, 2013 English Edition