Load Balancing Optimization Based on Enhanced Genetic Algorithm in Cloud Computing

Abstract

Load imbalance tends to occur in cloud computing due to dynamics and complexity. Load Balancing ensures that all the nodes and machines in the network does exactly same amount of work. To address the Load Balancing in the application of task scheduling, we put forward an approach based on improved Genetic multitask scheduling algorithm which has assigning function on multiple schedules. Then improved Genetic Algorithm is applied to re-assign the cloudlets to virtual machines and obtain minimum completion time. The aim of this project is to satisfy the demand for load balancing under cloud computing and to improve the resource utilization, compared to traditional algorithms.

Introduction

I. INTRODUCTION

In today's scenario, most of the business-like social media, IT sector and many other applications are leaning towards Cloud computing. Cloud computing uses high-performance mechanism to utilize resources from anywhere in the world with the help of cloud. Maximum use of utilization of resources is important and it increases system level performance. Popular companies like Google, Microsoft and IBM are achieving a great progress in cloud computing. However, we opt for a cloud service provider and with the help of credentials, we run our applications which can be referred to as task assigned to cloud or as a request for one of the cloud services. When a request is received, virtual machine will be allocated to the task with the help of some scheduling algorithms. There are number of virtual machines supporting this kind of system but problem is, how, where and on which machine the request has to be sent. For example, if all request has been sent to one or two machine and other machines are free then overall system performance will be down. Therefore, load balancing term arrive in cloud computing to enhance overall system performance which is a big challenge for industry and researcher.

A. Load Balancing

Load balancing is equal to the distribution of processing between two or more computers and / or processors, networks, communication channels, and storage devices, which in the end will result in faster delivery of services with a higher level of efficiency. Load balancing can be carried out with the aid of computer software, hardware, or that of any other, and it's widely used by several of the servers that appear to be one and the same machine (also known as computer clustering). This is the process of improving the performance of parallel and distributed systems, by applying the load among the processors. The allocation of resources is a benefit of all the communication systems that allows for better reliability and performance than any other system in a similar situation.

One of the most important research problems in parallel and distributed systems is the most effective and efficient methods, the development of the workload distribution of the number of nodes. The main goal is to, in order to distribute the tasks between the processors, capacity, stability, support, resources, and ensuring fault- tolerance in the wild. The local scheduling is performed by the operating system, it consists of the assignment of processes over a period of time slices of the CPU. In Global scheduling, on the other hand, is the process of deciding whether to run in a multiprocessor system. The Global scheduling can be carried out in a central, or master, the processing element, which is also known as an operating system, or it can be achieved between the processing elements.

A simple cloud architecture defines set of virtual machines connected to each other in a form of parallel and distributed system. It performs the dynamic provision of resources based on service level agreement (SLA) or policy that inculcates to ameliorate one or more objectives.

To assign the tasks as load to virtual machines several challenges are being faces from start of usage of cloud, And the Load balancing is one of them, which aim at equalizing the workload among all the virtual machines by minimizing execution time, minimizing communication delays between the machines, maximizing resource utilization and throughput.

II. RELATED WORK

This paper mainly focusses on Dynamic Load Balancing and the system uses distributed computational approach. Henceforth we put forth detailed work that is carried on Cloud with the help of Dynamic Load Balancing Algorithms.

T. Kokilavani and Dr. D.I. George Amalarethinam (2011) has proposed an approach based on Min-Min scheduling algorithm. This project is based on the failure of the Min-Min algorithm that it gives a large makespan and there is no proper load balancing, so this project is mainly focused on two stages. First stage is simply the implementation of Min-Min algorithm and their concern on the second phase that is rescheduling of the tasks to increase resource utilization and efficiency [1]. Dhinesh Babu L. D., and P. Venkata Krishna (e) (2013) proposed an algorithm, which is called the honey bee behavior inspired load balancing (HBB-LB), to achieve a balanced load among VMs (vessel monitoring system, for maximum throughput. In the proposed algorithm, which is a part of the priority tasks of the machines, so that the sum of the waiting time of the tasks in the queue was minimal [2]. Paulin, Florence V. Shanti (2013) propose the algorithm, which is based on the load index and load balancing operations are carried out with the help of firefly algorithm. The performance of the analysis yielded the expected results, and, thus, to prove the effectiveness of the proposed design graphic approach to optimize the load balance. The average acquisition time of the proposed approach is 0.934 ms [6]. Bo Xu Zhiping Peng Antonio Marcel Gates [2014] proposed a multi-objective comprehensive evaluation model for the dynamic deployment of virtual machines. We then use an improved     multi-objective    particle  swarm optimization (IMOPSO) to optimize the resource use and migration times [7]. Hussain A Makasarwala et al. [2016] In this paper, GA is used for better human implementation, application capture is based on their time, based on the process of measuring the load in the cloud space. In the real world the priorities are considered and the status applications have a certain value, with the help of a proposed algorithm for a different approach to improve the population. Cloud-Analyst simulation is used,

III. LOAD BALANCING OPTIMIZATION MODEL UNDER CLOUD COMPUTING

Load balancing in the first level is completed in task distribution. Task request will be evenly distributed to various physical servers according to the needed resources so that cloud computing server operates task during keeping high efficiency state. Load balancing in the second level is completed by physical server distribution virtual machine. Server sets up an independently operating virtual machine for each task after it receives task request. When there is a server is in overload operation, virtual machine will be transferred to physical machine in light load in order to maintain system load balancing.

Task scheduling-based computing resource balance plays an important role in load balancing and many load balancing strategies are effective to computing resources balance. The model established in this paper is based on computing resources balance of task scheduling. First, task loading and computing resources ability will be measured. Loading and computing resources ability will be abstracted to form optimized mathematical models. Those in loading balance will be distributed to computing resources so that resources utilization ratio of computing resources on each physical machine will not be large and relatively balanced. Task loading measurement will be determined by the predicting time and task load but computing ability of physical machine will comprehensively consider CPU type, frequency, core number, CPU quantity, etc.

The computing resource occupancy rate of physical machine j is computed as [1].

IV. IMPROVED GA- BASED MODEL FOR LOAD BALANCING OPTIMIZATION

Fig.2 represents the steps that are described below and are followed for obtaining the sequence of instructions that are taken for execution of tasks that are assigned to virtual machines.

A. Coding and Decoding of Chromosomes

Binary coding has the defects of continuous function discretization mapping error and individual coding string sometimes may not meet the accuracy requirements in a short time. Also, with the increase of number of tasks, space complexity increases. Thus, we have employed number representation of chromosomes in number format and each chromosome consists of an arrangement of virtual to each of the cloudlets and can be modifies in the following phases to get the chromosome with best fitness.

B. Population Initialization and fitness function

When starting genetic algorithm, h individuals will be randomly generated to form initial population and then operate individual coding. Coding process is the distribution that T virtual machine will be scheduled to M physical machines. We initially generate h scheduling schemes: we initialize population size as h=20, number of cloudlets as 40 and virtual machines as T=15. In addition, we also initialize loading on each virtual machine and computing capability on each physical machine. Since target function is larger than 0 and seeks the minimal value of function, target function seeks reciprocal value to be taken as fitness function. That is to say, to compute reciprocal value of variance in resources occupancy is taken as fitness function. The equation of fitness function is:

C. Selection, Crossover and Mutation

Based fitness of different individuals, each individual will be solved the selected probability. Supposing the individual fitness and selection probability appear direct proportion distribution. The better the fitness, the larger the selected probability. The selected individuals in selecting operation will be randomly performed pairs to exchange some genes of two individuals and form new chromosomes. Crossover operation refers to recombine advantages so that newly combining individuals display stronger advantages. Its individual fitness enhances. Crossover probability Pc is usually set from 0.4 to 0.9. Larger probability is usually chosen. Crossover operation performing optimization processing in global search to avoid local optimal solution and clarify local range of optimal solution. When mutation operation performs local search optimization, it slowly closes to the optimal solution. Mutation probability usually chooses smaller value from 0.001 to 0.1.

Genetic algorithm tends to increase diversity in each stage of mutation and crossover so the probability is selected as shown in diagram. The fmax represents the maximum fitness value in each generation population, the favg represents the average fitness value in each generation population, f' represents the fitness value of the larger one of the two individuals to be crossed, f represents the fitness value of the individual to be changed, k1, k2, k3, k4 take the value of the interval (0,1).

V. IMPLEMENTATION AND RESULTS

CloudSim is used to implement the proposed improved Genetic Algorithm. Cloudsim is a stretchy framework for modeling and simulation of any application's performance in cloud environment on large scale. CloudSim can be seen as a library of cloud simulation scenarios. It uses Java for cloud simulation.

In this implementation of this project we consider only one Data Center to allocate the cloudlets to the virtual machines. Cloudsim can be used to implement the following configurations. Data Center id divided into 15 Virtual Machines that are used to run the cloudlets that are assigned by the user and virtual machines start with 1000 MIPS and reach up to 1140 MIPS with each having a difference of 10 MIPS. This simulation considers 40 tasks or cloudlets each with a file size of 300 and outputs as 300 MIPS and the cloudlets vary in the length where first cloudlet has 1000 MIPS and reach 1380 MIPS with difference of 20 MIPS. The difference is maintained so that the algorithm doesn’t show any bias to a particular model.

The performance of above algorithms i.e. FCFS, RR and SJF are compared with the proposed improved Genetic Algorithm with the help of bar graphs. This helps us to understand the effectiveness of our model compared to other algorithms. Two main factors Makespan (Completion time) and average response time are taken in the given two bar graphs and our algorithm works good compared to other algorithms.

The improved genetic algorithm is compared with traditional algorithms and are shown in the graphs to show the efficiency of the proposed improved genetic algorithm. The proposed algorithm is able to show less makespan and average response time compared to other algorithms. The load on virtual machines is said be reduced as the resources are used effectively in completing the tasks.

Conclusion

On the basis of Improved Genetic algorithm, our project quantifies the satisfaction of resource scheduling by improving the execution process of genetic algorithm, aiming at the completion time of scheduling tasks. We chose Cloudsim as final simulation platform to simulate data center, virtual resources and user’s task under cloud environment. From user’s task completion time and response time, we compare the improved genetic algorithm with traditional algorithms such as SJF, RR, FCFS. The experiment result shows our scheme is better and it can be taken as one of the effective loading balancing algorithms under cloud environment. It is suggested to explore the maximum number of cloudlets or tasks that can be implemented with the help of the encoding and decoding scheme proposed in this project. It would be efficient if we calculate the space complexity that is required to hold the chromosomes as the tasks increases. It is advised to work on efficiency of the algorithm by implementing it on multiple data centers for a large set of virtual machines and also consider the network delays between them.

References

[1] L. Tang, \"Load Balancing Optimization in Cloud Computing Based on Task Scheduling,\" 2018 International Conference on Virtual Reality and Intelligent Systems (ICVRIS), 2018, pp. 116-120, doi: 10.1109/ICVRIS.2018.00036. [2] Kokilavani T, George Amalarethinam D I 2011 Load balanced minmin algorithm for static metatask scheduling in grid computing. Int J Comput Appl. 20(2) 43–9 [3] Dhinesh B L D, Krishna P V. Venkata Krishna, P.: Honey bee behavior inspired load balancing of tasks in cloud computing environments. Applied Soft Computing 13(5), 2292-2303 [4] Florence A P, Shanthi V. A load balancing model using firefly algorithm in cloud computing. Journal of Computer Science, 2014, 10(7):1156- 1165 [5] Bo Xu Zhiping Peng. Deployment method of VM cluster based on graph theory for cloud resource management. https://doi.org/10.1049/iet- com.2016.0071 [6] Vhansure, Fulrani & Deshmukh, Apurva & Subramanain, Sumathy. (2017). Load Balancing in Multi Cloud Computing Environment with Genetic Algorithm. IOP Conference Series: Materials Science and Engineering. 263. 042010. 10.1088/1757-899X/263/4/042010 [7] Dave S, Maheta P 2014 Utilizing round robin concept for load balancing algorithm at virtual machine level in cloud environment Int J Comput Appl [Internet] 94(4) 23–9 [8] Makasarwala .A.H.; Hazari Prasun. (2016) : Using Genetic Algorithm for Load Balancing in Cloud Computing. International Conference -8 th Edition Electronic Computers and Artificial Intelligence. [9] Bhosale KK, Jadhav VD. A review of genetic algorithm for metal cutting processes and a research agenda. International Journal for Research in Applied Science & Engineering Technology (IJRASET). 2015;3(V). [10] Durairaj M, Kannan P. Improvised Genetic Approach for an Effective Resource Allocation in Cloud Infrastructure. International Journal of Computer Science and Information Technologies. 2015;6(4):4037-46.

Copyright

Copyright © 2022 P. Shyam Sunder, P. Satya Shekar Varma. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.