Load Balancing on Virtual Machines Using Ant Colony Optimization In Cloud Seminar Report submitted in partial fulfillment of the requirements for the award of degree ofMaster of Engineering Computer Science and Engineering Submitted ByName: Jasleen Kaur(Roll No. 801632014)Under the supervision of: Dr. Neeraj Kumar Associate Professor,Computer Science and Engineering DepartmentDr. Mukesh SinghAssociate ProfessorElectrical and Instrumentation Engineering Department,COMPUTER SCIENCE AND ENGINEERING DEPARTMENTTHAPAR UNIVERSITY PATIALA – 147004December 2017 CERTIFICATEI hereby certify that the matter which is being presented in the seminar report titled, “Seminar topic”, in partial fulfillment of the requirements for the award of degree of Master of Engineering Computer Science and Engineering submitted in Computer Science and Engineering Department of Thapar University, Patiala, is a survey carried out by me. Name : Jasleen Kaur Roll No. 801632014 ME(CS) ABSTRACT The development of the internet has given birth to many technologies. Cloud computing is a latest trend in large scale data processing. It aids in providing shared resources. It gives support to the distributed parallel processing. However, providing an efficient response time is a major challenging issue in the distributed systems. Cloud computing provides data on the pay per use basis and eliminates the need of having one’s own device. As cloud computing grows, more users get attracted towards it. Lesser response time is needed for distributed computing and effective load balancing is one of the major issues that can improve response time. Improving the dynamic nature of load balancing algorithms in order to improve the performance of the cluster is the first and foremost requirement. In the proposed algorithm, load balancing is done by using Ant Colony Algorithm. Probability calculation is done by considering hardware parameters including CPU utilization and bandwidth utilization which helps to avoid the overloading and under loading of Virtual Machines. Algorithm is executed on cloud analyst. The results show the effectiveness of the proposed algorithm. ACKNOWLEDGEMENT First of all I would like to thank the Almighty, who has always guided me to work on the right path of the life. This work would not have been possible without the encouragement and able guidance of my supervisor Dr. Neeraj Kumar and Dr. Mukesh Singh I thank my supervisor for her time, patience, discussions and valuable comments. Her enthusiasm and optimism made this experience both rewarding and enjoyable.I am also thankful to the entire faculty and staff members of Computer Science Department, Thapar University, for their direct-indirect help, cooperation, love and affection.Last but not the least, I would like to thank my parents for their wonderful love and encouragement, without their blessings none of this would have been possible. I would also like to thank my close friends for their constant support. LIST OF CONTENTS PAGE NO. Certificate iAbstract iiAcknowledgement iiiTable of Contents ivList of Figures viList of Tables viiiChapter 1. Introduction 11.1. Introduction to Cloud Computing 11.1.1. Advantages of Cloud Computing 21.2. Introduction to Load Balancing 31.2.1. Load Balancing Algorithms 31.3. Ant Colony Optimization 51.3.1. Applications of ACO algorithm in various problems 6Chapter 2. Literature Survey 72.1. Related Work 7Chapter 3. Status of the Work 93.1. Status 93.1.1 Experimental Results 9Chapter 4. Conclusion and Future Scope 134.1. Conclusion 134.2. Future Scope 13References 14 LIST OF FIGURES PAGE NO. Figure 1.1: Cloud Computing 1Figure 3.1: Comparison between Load Balancing Policies 10Figure 3.2: Round Robin Load Balancer 11Figure 3.3: Equally Spread Current Execution Load Balancer 11Figure 3.4: Throttled Load Balancer 11Figure 3.5: Ant Colony Load Balancer 12Figure 3.6: Response time analysis 12 LIST OF TABLES PAGE NO. Table 1: Comparison of various Load Balancing Algorithms 4Table 2: Comparative Analysis of Various Ant Colony Optimization 7Table 3: Parameters used for Execution 9 Chapter 1 INTRODUCTION 1.1. Introduction to Cloud ComputingCloud computing is the ability of using various computing resources through the internet including applications and storage services. The shared pool of the resources is hosted by the cloud provider. According to the National Institute of Standard and Technology 1, Cloud Computing is defined as a model for providing convenient and on demand access to the shared pool of resources including networks, storage, services etc. These services require minimal effort. The main attribute of the cloud computing is the elasticity, means its tendency to grow and reduce the computation as per the requirements 2. The other attribute is it is scalable, means its ability to balance the increased demands of the CPU storage, bandwidth etc. Cloud Computing provides the secure access to the applications as shown in the Figure. Figure 1.1: Cloud Computing 3 To meet the user needs, Cloud Computing provides the virtual environment. It is based on Service Oriented Architecture (SOA) to provide hardware support and it moves the data, processing and service delivery away from the desktop transform to the data centers 5. The main aim of the cloud computing is to make use of the distributed resources to increase the overall throughput.1.1.1. Advantages of Cloud ComputingI. Ease in management- A person needs only internet connection and the web browser to access the services without the need for installing any other application for the computation. The maintenance of the infrastructure requires less time and the cost. The applications can also make easier access to the storage services through the cloud.II. Reduction in the cost- It reduces the cost because costly infrastructure does not require here- Most of the applications deployed on the cloud does not need any man power and can be setup freely like emails, Google Apps. Also these applications are reliable and the main advantage of such applications is availability.III. No interruption in the services- Cloud computing provides uninterrupted services to the user 6.IV. Disaster Management- Cloud computing is also efficient in the disaster recovery. Keeping the backup of an important data is need of the organizations. An offsite backup is helpful to recover the data. Cloud storage not only keep the back up of the data offsite but also ensures that they have system provided for disaster recovery in terms of the failure.V. Green Computing- Energy consumption is the main concern in the today scenario including electronic waste with the advancement in time, extensive use of the system resources. This can be reduced with the help of the cloud computing to some extent. Less e-waste generated results in environment preserving.VI. Easy to scale- The cloud resources are managed by the software and thus if new requirement arises then it is easy to scale up the cloud. The scalability process can be done in less time. Similarly the resources can also scale down with the requirements.1.2. Introduction to Load BalancingLoad Balancing is a technique to distribute the workload across various nodes, or other resources like central processing units, network links, etc. The main aim is to achieve efficient resource utilization, increase in the throughput, decrease the response time and minimize the overhead. It also helps to achieve the fairly distribution of the workload.Cloud load balancing: Cloud load balancing is the process of distributing workloads across multiple computing resources in a cloud computing environment. To balance load distribution, we can migrate the load from the heavy loaded nodes to the comparatively lightly loaded destination nodes.The load balancing is achieved by the relevant hardware/software, for example multilayer switch helps in load balancing. It is also one main issue of cloud computing as there may occur a situation in which some nodes are busy and at the same time some nodes are idle. So this increases the overall response time. A mechanism is needed to ensure that the workload across the nodes is evenly distributed. Different algorithms are there to serve the efficient load balancing.1.2.1. Load Balancing AlgorithmsBasically load balancing algorithms are divided into two types i.e Static an Dynamic Algorithms.a) Static Load Balancing AlgorithmsThe static load balancing algorithms are based on the prior knowledge of the properties of the nodes and its ability to process the new requests. This also includes the processing power of the node. This only takes into consideration the static properties of the node and is not adaptable to any changes.b) Dynamic Load Balancing AlgorithmsDynamic load balancing algorithms depend on the run-time information collected of the selected nodes. In this approach, workload is assigned and may reassign to the nodes based on the computation. These algorithms also require continuous monitoring of the tasks. This is also more accurate approach of load balancing in comparison with the static approach.a. Comparison of various Load Balancing AlgorithmsTable 1 shows the comparison with various Load Balancing Algorithms. This table covered various advantages and limitations of these algorithms.Techniques Advantages LimitationsRound Robin It selects the first node randomly and then allocates jobs to all other nodes in a round robin manner Some nodes might be heavily loaded and some are not. Since the running time of any process is not known prior to execution, there is a possibility that nodes may get heavily loaded.Weighted Round Robin In this algorithm, a weight is assigned to each node and depends on the weight, the requests are processed. As precise prediction of execution time is not possible, therefore this algorithm isn’t preferred.Ant Colony Optimization 7 • Under loaded node is found at the beginning of the search• It is Decentralized, so there is no single point of failure.• Ants can collect the information faster. • Due to large number of ants, network may be congested.• The status of the nodes after the ant’s visit is not taken into consideration.Load Balancing Min-Min (LBMM) 11 Job with the smallest time is executed first. The drawback of this algorithm is that some jobs may experience starvation.Honeybee Foraging Behavior 12 Achieves global Load Balancing through local server and used for large scale cloud systems. The computation of profit may cause an additional overhead which results in overall decrease in the throughput. Equally Spread Active Execution (ESAE) algorithm 13 In the ESAE algorithm, as the tasks are submitted, they are queued. If the task size and the size of the virtual machine match, the job is assigned. This is done by the job scheduler based on the priority. Power consumption caseIsn’t considered.Weighted Least Connection (WLC) 14 It finds out the node with the least number of the connections. If the node with the least number of connections is found, the task is assigned to it. It does not takes into consideration important factors including the processing speed, bandwidth etc.Throttled Algorithm15 Assign the workload on the virtual machines for effective resource utilization Failed to distribute load uniformly, overloading initial VMs and leaving others underutilized.1.3. Ant Colony Optimization Ant Colony Optimization is basic foraging behavior of an ant that encouraged them to find the optimal shortest path from their nest to food introduced by Dorigo. M .When ants are moving from their nest to food or vice versa they deposit a chemical substance called pheromone on their path. Paths are randomly chosen by ants initially. Chance of an isolated ant to follow a particular path among several possibilities always based on previously laid trail .High concentrated pheromone helps an ant to choose a path and more ants are also attracted due to this high pheromone. By this way trail are reinforced with its own pheromone. Probability of an ant can separate the best optimal path from different set of paths is proportion to the concentration of way’s pheromone. As a result denser pheromone attracts more ants. It’s a basically positive feedback mechanism that helps ants to find an optimal path finally.1.3.1 Application of ACO algorithm in various problems1. Travelling salesman problems2. Quadratic assignment problems3. Scheduling problems4. Vehicle routing problems5. Sequential ordering problems6. Shortest common super sequence7. problems8. Graph coloring problems9. Frequency assignment problems10. Bin packing and multi-knapsack problems11. Constraint satisfaction problems Chapter2 LITERATURE SURVEY 2.1. Related Work Table2 Comparative Analysis of Various Ant Colony Optimization Title Purpose Techniques Used Advantages DisadvantagesCloud task Scheduling based on Load balancing ACO.6 To minimize the task completion time that are distributed among different virtual Machines. Load BalancingACO Algorithm is used to find the optimal resourceallocation for each task in dynamic cloudsystem. 1. Nodes are balancedDynamically.2. LBMM Balanced the entire system whether the entire task are the same or not that can handle all type of conditions. 1. The task aremutually independent as No precedenceconstraints betweendifferent task.2. The task areComputationallyintensive which isnot realistic for cloudsystem.3. It is not Heterogeneity of system.Load balancing ofnode in cloudusing Ant colonyoptimization(ACO)7. 1. Aim is to Efficiently distribution of load among nodes such that ant never dead.2.It provide the bettersynchronization of ants.3. It is best case thatfinds the node is underloaded or not. 1.Centralized approach . Ant Collect the information faster.2.Two types movement of ant that is forward movement and backward movement. 1. It gives optimumsolution of load.2. It is centralizedno single point of failure .3. the ant updatedthe single result setrather thanupdating their own result set. It iscompiled only onceduration ofmovement of ant 1. Network overheadbecause of the largenumber of ants2. Points of initiationof ants and numberof ants are not clear3. Nodes statuschange after antsvisits to them is notaken into account4..full replication ofdataDynamic Load Balancing Strategy for Cloud Computing with Ant Colony Optimization8. 1.Present anovel approach on load balancing via ant colony optimization (ACO), for balancing theworkload in a cloud computing platform dynamically. Two strategies, forward-backward ant mechanism and max-min rules, are introduced to quickly find out the candidate nodes forload balancing. Better speed of convergence and canbe used in the cloud computing platform with a huge number of slave nodes. 1.Overhead increases.Effective SchedulingAlgorithm for Loadbalancing using AntColony Optimizationin Cloud Computing.9 1.To develop an effective load balancing algorithmusing ACO . 1.SchedulingAlgorithm for LoadBalancing(SALB) 1.Efficient to finding the overloaded node in minimum time.2. To balance the node with efficiency and maximum utilization ofresources. 1.Less performance(canbe increased by varyingdifferent parameters)Cloud computinginitiative usingmodified ACOFramework.10 To minimize the make span (throughput ofheterogeneouscomputing system) . Based onheuristics algorithmuses modified ACO. The main modification in pheromoneFormula. 1.Better utilizationof resources.2. It is not dynamic in nature.3.Probability ofservicing the request also has been converged using modified Scheduling. 1. Fault tolerance isnot good.2. overheadIncreases.Chapter 3 STATUS OF THE WORK In cloud computing, there is an issue regarding overloading of the tasks due to the random arrival of the tasks. Due to the random utilization of the CPU, resources are sometimes heavily loaded whereas the other resources are idle. Load Balancing is a way to distribute the entire load over the network across a large number of virtual machines or CPU. This helps to achieve the balanced utilization which maximizes the performance and minimizes the response time. So there is an important issue to balance the load efficiently among the resources.3.1. Status of the Work• Up to now we have setup the CloudSim environment and Cloud Analyst with Eclipse IDE and common math library has been integrated.• Creation of Data centre, assigning properties, creation of Virtual machines, hosts, cloudlets has been simulated using system given classes.• The inbuilt broker object is invoked which is responsible for assignment of cloudlets into VMs.• The default allocation policies are being examined.• Ant Colony Optimization algorithm implementation.3.1.1. Experimental Results Following is the cloudsim based toolkit parameters configured for the execution of the algorithm as shown in Table 3.Number of Datacenter 1Architecture X86Operating System LinuxVMM XenAvailable Bandwidth per VM 1000Number of Virtual machines in a datacenter 8Data size per request (in bytes) 10000Number of requests 60Image Size 10000Physical Hardware Units 4Instruction length per request(in bytes) 10000Memory per Host(in Mb) 2048Storage per Host(in Mb) 100000Bandwidth per Host(in Mbits/sec) 100000Table 3: Parameters used for executionTo test the efficiency of the ACO algorithm, it is compared with the other algorithms using cloud analyst tool. Cloud analyst tool is an extension to the cloudsim. Screenshot of the existing algorithms in the tool has shown in the Figure3.1. Figure 3.1: Comparison between Load Balancing Policies Round robin processes the request by selecting the virtual machines randomly and then the workload gets allocated in the circular manner. However it doesn?t consider the processing time. A request has to wait in queue if no virtual machine is available. So, this increases the overall response time. Response time of this algorithm with the assigned configuration has shown in the Figure.3.2. Figure 3.2: Round Robin Load BalancerEqually Spread current Execution distributes the workload equally to all the virtual machines. So in this way equal numbers of the tasks are assigned to each virtual machine. No virtual machine is underutilized. Figure 3.3 shows the response time execution of this algorithm with the configuration as shown in the Table 3. Figure 3.3: Equally Spread Current Execution Load BalancerThrottled algorithm assigns the workload uniformly to the virtual machines. It takes care of the predefined amount of the tasks are allocated to the virtual machine. Figure3.4 shows the response time execution of this algorithm with the configuration as shown in the Table 3. Figure 3.4: Throttled Load Balancer An Ant Colony algorithm is implemented in cloudsim and its toolkit. This algorithm takes care of the different hardware parameters of the virtual machines. So a Probability value is calculated based on the hardware parameters. The result shows that response time has improved as shown in Figure 3.5. Figure 3.5: Load Balancing based on Resource Utilization Figure 3.6: Response Time AnalysisThe comparison between round robin, equally spread current execution, throttled, and Ant colony algorithm has shown in the Figure 3.6. From the analysis of the results, it is proved that the proposed algorithm has better response time as compared to the other algorithms. So this algorithm is response time efficient. Chapter 4 CONCLUSION AND FUTURE SCOPE 4.1.ConclusionThe existing work considered several load balancing techniques that manage the load distribution among various virtual machines and assigns load corresponding to their priority and states. There is an issue of overloading which means the resources may be over utilized and hence there increases the response time. There is also an issue of under loading means the resources may underutilize and hence there may increase in the power consumption. According to the ACO Algorithm, the workload is distributed to the virtual machine based on Pheromone valueof virtual machines. The analysis of the results shows that response time of the algorithm is reduced as compared to the other algorithms. 4.2.Future ScopeIn future, the load balancing can be more dynamic and efficient by making some changes in the already implemented ACO algorithm .During the work also try to overcome the problem of fault tolerance which is also an issue in cloud computing. REFERENCES1 P. Mell and T. Grance, “The NIST Definition of Cloud Computing”, National Institute of Standards and Technology, Sept. 2011.2 E. J. Qaisar, “Introduction to Cloud Computing for Developers: Key concepts, the players and their offerings”, in proc. of IEEE Information Technology Professional Conference (TCF Pro IT), pp. 1-6, 2012.3 M. B. Mollah, K. R. Islam and S. S. Islam, “Next Generation of Computing through Cloud Computing Technology”, in proc. of 25th IEEE Canadian Conference on Electrical and Computer Engineering (CCECE), pp.1-6, 2012.4 J. Harauz, L. M. Kaufinan and B. Potter, “Data Security in the World of Cloud Computing”, in proc. of IEEE Security & Privacy, co published by IEEE Computer and Reliability Societies, pp. 61-64, July 2009.5 M. D. Dikaiakos, G. Pall, et al. “Cloud computing: Distributed Internet Computing for IT and Scientific Research”, in proc. of IEEE Internet Computing, pp. 10-13, 2009.6 Kun Li, Gaochao Xu, Guangyu Zhao, Yushuang Dong, Dan Wang, “Cloud Task scheduling based on Load Balancing Ant Colony Optimization”, 2011 Sixth Annual China Grid Conference, 978-0-7695- 4472-4/11, 2011 IEEE.7 N. Kumar, P. Sharma, et al. “Load Balancing of Nodes in Cloud Using Ant Colony Optimization”, in IEEE proc. of 14th International Conference on Modeling and Simulation, pp. 3-8, 2012. 8 http://www.mdpi.com/1999-5903/7/4/465.9 Shagufta Khan, Niresh Sharma, “Effective Scheduling Algorithm for Load balancing using Ant Colony Optimization in Cloud Computing”, International Journal of Advanced Research in Computer Science and Software Engineering, Volume 4, Issue 2, February 2014.10 Soumya Banerjee, Indrajit Mukherjee, and P.K. Mahanti, “Cloud computing initiative using modified ACO framework”, World Academy of Science, Engineering and Technology Vol:3 2009-08-27. 11 S. Wang, K. Yan, W. Liao and S. Wang, “Towards a load balancing in a three- level cloud computing network,” in the proc. of IEEE 3rd International Conference on Computer Science and Information Technology (ICCSIT), pp. 108-113, July 2010. 12 M. Randles, D. Lamb and A. Bendiab, “Experiments with Honeybee Foraging Inspired Load Balancing”, in IEEE proc. of 2nd International Conference on Developments in eSystems Engineering(DESE), pp. 240-247, 2009. 13 J. kaur, “Comparison of load balancing algorithms in a Cloud”, in International Journal of Engineering Research and Applications (IJERA), vol. 2, issue 3, pp. 169-173, 2012. 14 R. Lee and B. Jeng, “Load-balancing tactics in cloud,” in IEEE proc. of International Conference on Cyber-Enabled Distributed Computing and Knowledge Discovery (CyberC), pp. 447-454, October 2011. 15 M. Sharma and P. Sharma, “Efficient Load Balancing Algorithm in VM Cloud Environment”, M.Tech. Dissertation, Information Technology Department, Dharmsinh Desai University, 2012.