Transcription
International Journal of Computer Applications (0975 – 8887)Volume 97– No.2, July 2014Juxtaposition of Load Balancing Algorithms in CloudComputing using Cloud Analyst SimulatorIndresh GangwarPoonam RanaComputer Science & EngineeringKrishna Institute of Engineering & TechnologyGhaziabad, IndiaComputer Science & EngineeringKrishna Institute of Engineering & TechnologyGhaziabad, IndiaABSTRACT1.2 Metrics for Load BalancingCloud Computing is a term which is generally used inreference to Internet. The whole Internet can be viewed as acloud. The cloud is quickly changing a worldwide network ofcomputers into the largest single, "virtual" computer in theworld. This includes sharing of resources which increases theload on single machine. Thus the overall performancedegrades and this problem is named as load balancing. LoadBalancing is one of the challenging issues now a day. Toovercome from this problem be reassign the load byimplementing various algorithms introduced for this problem.In this paper we study and compare various algorithms,techniques used to solve the problem of Load Balancing andDistributed Load Balancing. Throughput: It is used to compute the no. of tasks for agive time. The performance of any system is improved ifthroughput is maximised. Fault Tolerance: It is defined as to recover from failure.The load balancing should be a best fault tolerantmethod. Migration time: During execution of a job, for reducingload it is need to migrate the jobs or resources from onenode to other nodes and the time required is migrationtime which should be minimised to improve theperformance of the system. Response Time: It is the time required to response atask for a specific load balancing algorithm in a system.It should minimum for better performance of a system. Scalability: It is the capability of an algorithm toperform Load balancing in a system for any determinednumber of nodes. This parameter should be improved.KeywordsLoad Balancing; Round Robin; Throttled Load BalancingAlgorithm; Equally Spread Current Execution Algorithm.Cloud analyst.1. INTRODUCTIONCloud computing is most popular technique that is defined as“A dummy for on-demand network access to a common poolof configurable computing resources that can be rapidlyprovisioned and released with minimal management effort orservice provider Interaction” Cloud Computing is specializedscalable entity that delivers different level of services to thethird party. These services are Platform as a service( PaaS ),Software as a service(SaaS) & Infrastructure as aService(IaaS) [1, 11]. Cloud Computing involves variousdistributed technologies to share resources, softwareinformation via internet to reduce the cost, increasecomputation and performance and satisfy the needs ofcustomer. While providing various benefits it has some sideeffects or it has various issues like security, load managementetc. Load Balancing was identified as a major concern toallow Cloud computing to scale up to increasing demands[2].Load balancing performances is shown by using cloudanalyst simulator for different algorithms.1.3 Policies of Load Balancing1.1 Goal of load balancingLoad Balancing is a technique in which workload isdistributed over a number of nodes to decrease the traffic andincrease the efficiency and throughput of the cloud. There arevarious parameters which will improve the load balancing ifwe properly utilizing the resources. Some of these parametersare reliability, waiting time, adaptability, load rejection,stability, response time, turnaround time, throughput,processor thrashing, execution time, resource utilization, faulttolerant, process migration, etc[3].There are many algorithmsthat are used to distribute the load. Different algorithms havedifferent criteria and environment to improve theperformance. Following are the algorithms used fordistributing the load among several nodes.It main aim is to give best performance by balancing orreassigning the load among various resources. It is newtechnique that facilitates resources by providing evendistribution of load, minimum response time and maximumthroughput. One of the best example related to load balancingare websites [5]. As while using website users couldexperience delays, possible long system responses andtimeouts due to traffic and overloading. Load balancingresolve this problem. It provides better distribution of thecommunication traffic so that website availability isconclusively settled. Information policy: It defined that what information isrequired and how this information is collected. This isalso defined that when this information is collected. Triggering policy: In this we explain that time periodwhen the load balancing operation is starting to managethe load. Selection policy: This policy is used to find out the taskwhich transfers from overloaded node to free node. Resource type policy: It explains all types of resourceswhich are available during the load balancing. Location policy: This uses all the results of the resourcetype policy. It is used to find a partner for a server orreceiver.2. LITERATURE REVIEW21
International Journal of Computer Applications (0975 – 8887)Volume 97– No.2, July 2014Fig no. 1 Implementation of polices of Load Balancing Min-Min Algorithm: First, Minimum completion timefor all tasks are found and among these tasks minimumvalue is chosen and corresponding task is scheduled oncorresponding machine. Assigned task is removed fromthe list of tasks that are assigned to machine. Thisalgorithm has a drawback i.e. Starvation [7, 8]. Max-Min Algorithm: It is similar to min-min algorithmexcept after finding out minimum execution times andselecting task having the maximum value or havingmaximum time among all the tasks on any resources[5,8] Biased Random Sampling: Achieves load balancingacross all system nodes using random sampling of theSystem domain to accomplish self-organization thusstabilize the load among nodes. A virtual graph isconstructed to represent the load on serve andconnectivity among them [8, 9]. Equally Spread Current Execution Algorithm: Ithandles processes with Priorities. It distribute the loadrandomly by checking the size and transfer the load tothat virtual machine which is lightly loaded or handlethat task easy and take less time , and give maximizethroughput. It is also Known as Spread Spectrumtechnique as the entire load is distributes among nodes byload balancer [7, 8]. A Task based Scheduling Algorithm on LoadBalancing: It has two level task scheduling processing.In first level it maps tasks to virtual machines and thenvirtual machines to host resources. It provides maximumthroughput or maximize resource utilization withminimum task response time [5, 10]. Throttled Load Balancing Algorithm: In this algorithmthe client first compete to find a suitable Virtual Machinewith the help of load balancer to perform the requiredoperation. Virtual machines are designed to handlespecific task. The load balancer on the request of userassigns virtual machine on the basis of the requirement oftask. Ant Colony Optimization: This technique take the ideafrom the ant behaviour, how they collect information andleave the liquid(pheromone) in the path to inform othersthe about the path of food. This algorithm maintains apheromone table on the basis of resource utilization andnode selection method. The ants searches for overloadednode and then traverse it and then go back to fill theOn the basis of who initiated the process, load balancingalgorithms can be of classified as [3, 4]: Sender Initialized: Initialized by the sender. Receiver Initiated: In this load balancing algorithm isinitiated by the receiver. Symmetric: It is hybrid of both sender initiated andreceiver initiated.On the basis of the current state of the system, load balancingalgorithms can be classified as [3, 4]: Static: It doesn’t depend on the current state of thesystem Prior knowledge of the system is needed. Itbasically evenly distributes the load between servers[12]. Dynamic: Decisions on load balancing are based oncurrent state of the system. Thus it does not require anyprior knowledge. Thus it is improved version of staticapproach. In this we search the lightest load node orserver to balance the load [12].2.1 Distributed Load BalancingDistributed Load Balancing is used to distribute the work loadover multiple networks. For this many distributed solutionhave been identified. Comparison of different algorithms isshown in table no. 1.There are different algorithms used for it. Some of them are asfollows: Honey Bee Algorithm: Achieves global load balancingthrough local serve actions. Its whole concept is based onthe idea honey bee, how they search their food and theninform others for the same by waggle dance. Thestrength or power of waggle dance gives idea about theamount of food present. In the same way the loadbalancing is done. As virtual machine is overloaded theuser request is forwarded to next less loaded virtualmachine [5]. Round Robin: In this algorithm the processes aredivided between all processors in a round robin order andeach processor having equal work load but differentprocesses have different job completion time. Thus somenodes are idle for much of time and some are heavilyloaded. Thus it is not a good algorithm [6].22
International Journal of Computer Applications (0975 – 8887)Volume 97– No.2, July 2014under loaded node so as to make balance or evenlydistribute the load[13]LoadBalancingDepending on thecurrent state ofthe systemDepending uponwho intiated ativeCooperativeCentralizedSemiDistributedFig no. 2 Hierarchy of Load Balancing Algorithms3. SIMULATION TOOL: CLOUDANALYSTparameters or by changing parameters and also save yoursimulation in a different file [15].Cloud computing relieved the IT companies from theheadache of setting basic hardware and softwareinfrastructure. Thus it also reduces the setting cost of anyproject or even the setting any IT business. Also they canfocus on new technology invention or quality of the servicethey provide. Some recently emerging application serviceswhich are based on cloud technology include content delivery,social networking, real-time instrumented data processing andweb hosting. All of these applications have different feature,configuration, and composition and deployment requirements.Thus to check or test the performance of policies likescheduling and allocation in real environment of cloudcomputing is very difficult and facing many challenges.Because cloud shows dynamic demands, system size, supplypatterns and also varying resources. Another challenge is dueheterogeneous user requirement of varying quality of serviceand also dynamic workloads and varying performances. It isreally very difficult to use real time application on varying ordynamic requirement and it’s also having manybenchmarking. Thus it is impossible to perform benchmarkingexperiments in repeatable, scalable and dependableenvironments using real-world Cloud environments. To do sowe use various simulation tools. One of them is CloudAnalyst .It is a modified version of CloudSim simulator.Cloud analyst is a GUI based simulator which is very easy touse and having ability to define simulations with a higherdegree of flexibility and configurability [15]. It providesgraphical output and you can easily change the parametersfocus on parameters without focusing on programming. Youcan perform experiments in repeated manner for same4. EXPERIMENTAL ANALYSISWe analysis three algorithms Round Robin, Throttled LoadBalancing Algorithm and Equally Spread Current ExecutionAlgorithm. We assume some parameters for analysis on cloudanalyst.For Round Robin I Time Overall response time: Avg(291.61ms) Min(38.26ms)Max(482.02ms). Data Processing time: Avg(0.18 ms)Max(0.75ms)Min(0.00ms)For Throttled Load Balancing I time Overall response time: Avg(291.51ms) Min(40.26ms)Max(482.02ms). Data Processing time: Avg(0.18 ms)Max(0.75ms).Min(0.00ms)For Equally Spread Current Execution Algorithm I time Overall response time: Avg(291.41ms) Min(40.26ms)Max(482.02ms). Data Processing time: Avg(0.81 ms)Max(0.75ms).Min(0.00ms)Table 2 contains the assumed parameters and table 3 givesinformation about user bases. Fig. no. 3 is the output of theround robin algorithm performance.23
International Journal of Computer Applications (0975 – 8887)Volume 97– No.2, July 2014Table No. 1 Comparison of various Load Balancing AlgorithmsALGORITHMNAMEPARAMETERS USEDTYPE OFALGORITHMMERITSDEMERITSHoney BeeAlgorithms[14]Throughput, Job completiontime, OverheadDynamicAchive Global LoadBalancing, Maximizeresource utilization, lowoverheadLow Priority loadRound Robin[6]Completion timeStaticEvery process get equalweight age so no process willgo under starvation.Most of the timeprocessorremains idle.Min- MinAlgorithm[8]Execution timestaticJob with smallest executiontime is executed.StarvationMin-MaxAgorithm[8]Execution timeStaticImproved version of MinMin algorithmTask Schedulingalgorithm[5]Response time, ThroughputDynamicMinimize the response timeand maximizeresource utilization.Performancedegrades as no.of serveincreased.Less prioritesprocess need towait too long.Based RandomSampling[5]Threshold value or maximumwalk lengthDynamicStablilize load among nodesEqually SpreadCurrentExecution[13]Response time,DynamicMaximize throughputThrottled LoadBalancer[5]Communication cost,NetworkDelay,Load Movement FactorDynamicHigh Load Movement FactorAnt ColonyOptimization[13]Fault gh fault tolerance andresource utilization,goodscalabilityHighcommunicationcost and NetworkComplexdelaynetwork and needto managephenome table5. CONCLUSIONTable No. 2 Factors Assumed For Performance AnalysisDay-by-day use of cloud computing is increasing whichincrease the load on the servers providing services to thirdparty. Due to this the overall performance degrades and thereis poor resource utilization. This problem is referred as loadbalancing which is a major issue now days. To solve thisproblem various algorithms are proposed. In this paper bestudy the various algorithms, their advantages anddisadvantages and the parameters which improve the loadbalancing problem. Cloud analyst is tool or simulator onwhich we analyze the performance of various parameterswhich improves the load balancing problem thus improvingoverall performance and maximize the resource utilization.Future scope in this field is to find an algorithm and theparameter which best reduces the load balancing problem.Factor assumedI timeII timeUser group factor in user base110Request grouping factor indata center110Execute instruction perrequest110Simulation time3 min3 min24
International Journal of Computer Applications (0975 – 8887)Volume 97– No.2, July 2014Table No. 3 User bases for simulationNameRegionRequestsper userper hrData Size MT)Avg PeakUsersAvg 3480100391000100UB4560100391000100Fig No. 3 Output of round robin algorithm having 4 users and datacenter6. REFERENCES[1] Bhaskar Prasad Rimal, Eunmi Choi and Ian Lumb, “ATaxonomy and Survey of Cloud Computing Systems” in2009 Fifth International Joint Conference on INC, IMSand IDC.[2] Ian Foster, Yong Zhao, Ioan Raicu and Shiyong Lu,“Cloud Computing and Grid Computing 360-DegreeCompared” in Grid Computing Environments Workshop,2008, IEEE.[3] Abhijit A. Rajguru and S.S. Apte, “ComparativePerformance Analysis of Load Balancing Algorithms inDistributed System using Qualitative Parameters” inInternational Journal of Recent Technology andEngineering (IJRTE) ISSN: 2277-3878, Volume-1,Issue-3, August 2012.[4] Michael Armbrust, Armando Fox, Rean Griffith,Anthony D.Joseph, Randy H.Katz, AndrewKonwinski, Gunho Lee, David A. Patterson, ArielRabkin, Ion Stoica, Matei Zaharia, “Above the Clouds: ABerkeley View of Cloud Computing” ElectricalEngineering and Computer Sciences University ofCalifornia at Berkeley, Technical Report No.UCB/EECS-2009-28.[5] Rajwinder Kaur1 and Pawan Luthra , “Load Balancing inCloud Computing” in ACEEE, Proc. of Int. Conf. onRecent Trends in Information, Telecommunication andComputing, ITC.[6] Subasish Mohapatra, Subhadarshini Mohanty and K.Smruti Rekha “Analysis of Different Variants in RoundRobinAlgorithms for Load Balancing in CloudComputing” in International Journal Of ComputerApplications(0975-8887) Volume 69 – No. 22, May2013.[7] Amandeep Kaur Sidhu, Supriya Kinger ,“Analysis ofLoad Balancing Techniques in Cloud Computing” inInternational Journal of Computers & TechnologyVolume 4 No. 2, March-April, 2013, ISSN 2277-3061.[8] Shanti Swaroop Moharana , Rajadeepan D. Ramesh &Digamber Powar, “Analysis of Load Balancers in CloudComputing” in International Journal of ComputerScience and Engineering (IJCSE), ISSN 2278-9960 Vol.2, Issue 2, May 2013, 101-108 IASE.[9] Sheeja S. Manakattu ad S.D. Madhu kumar,“Animproved biased random sampling algorithm for loadbalancing in cloud based systems” in ACM ICACCI '12Proceedings of the International Conference onAdvances in Computing, Communications andInformatics.[10] Ruhi Gupta, “Review on Existing Load BalancingTechniques of Cloud Computing” in InternationalJournal of Advanced Research in Computer Science andSoftware Engineering.[11] M. Armbrust, et al., A view of cloud computing.Commun. ACM. vol. 53 (2010), pp. 50-58.25
International Journal of Computer Applications (0975 – 8887)Volume 97– No.2, July 2014[12] Zenon Chaczko, Venkatesh Mahadevan , ShahrzadAslanzadeh and Christopher Mcdermid, “Availabilityand Load Balancing in Cloud Computing” in 2011International Conference on Computer and SoftwareModeling IPCSIT vol.14 (2011) (2011) IACSIT Press,Singapore.[13] M Dorigo, G.D. Caro, and L.M. Gambardella, "Antalgorithms for discrete optimization," Artif. Life, vol.5,no.2, pp.137-172, 1999.IJCATM : www.ijcaonline.org[14] Dhineshhh Babu L.D and P. Venkata Krishna, “Honeybee behavior inspired load balancing of tasks in cloudcomputing environments” in Applied Soft ComputingVolume 13, Issue 5, May 2013, Pages 2292-2303[15] Bhathiya Wickremasinghe,“CloudAnalyst: A CloudSimbased Tool for Modelling and Analysis of Large ScaleCloud Computing Environments” in433-659DISTRIBUTED COMPUTING PROJECT, CSSEDEPT., UNIVERSITY OF MELBOURNE.26
Throttled Load Balancing Algorithm: In this algorithm the client first compete to find a suitable Virtual Machine with the help of load balancer to perform the required operation. Virtual machines are designed to handle specific task. The load balancer on the request of user assigns virtual machine on the basis of the requirement of task.
