Transcription
International Journal of Scientific and Research Publications, Volume 3, Issue 3, March 2013ISSN 2250-31531Improved Hybrid Dynamic Load Balancing Algorithmfor Distributed EnvironmentUrjashreePatil*, RajashreeShedge***Department of Information Technology, ThadomalShahani Engineering College**Department of Computer Engineering, R. A. I. T.Abstract- With the rapid development of high-speed andComputational resources Load Balancing has become anecessity in emerging distributed environment to address theinherit heterogeneity in computing resources. From two loadbalancing strategies static and dynamic, dynamic strategy isefficient for these systems. In dynamic also the centralizeddynamic approach limits the scalability with the load balancingunit itself becoming a bottleneck. Conversely, thedecentralized dynamic approach though overcomes the aboveproblems, suffers from increased communication overhead.The hybrid dynamic approach which uses centralized anddecentralized strategy suffers from bottleneck andcommunication overhead problem for large number of system.In this paper we propose the design of a simple yet effectiveimproved hybrid dynamic load balancing algorithm thatovercomes the limitations of hybrid dynamic algorithm andperforms competitively for heterogeneous system having largenumber of heterogeneous nodes.Index Terms-Bottleneck, Communication Overhead,Distributed Environment, Heterogeneous System, LoadBalancing.I. INTRODUCTIONLoad balancing is an operation that involves redistribution ofthe system workload, as evenly as possible, among theprocessing elements of a distributed system based on prioranalysis of the existing load. Load balancing is to ensure thatevery processor in the system does approximately the sameamount of work at any point of time. Load balancing is one ofprerequisites to utilize the full resources of parallel anddistributed system [1]. Load balancing is basically to dofollowing benefits as optimal resource utilization, maximumthroughput, reduce mean job response time under job transferoverhead, increase the performance of each host, removestarvation that causes to small job[2]. In parallel anddistributed system more than one processors processingparallel programs, the amount of processing time needed toexecute all processes assigned to a processor is calledworkload of processor [3]. Processes may migrate from onenode to another even in the middle of execution to ensure equalworkload. A distributed system provides the resource sharingas one of its major advantages, which provide the betterperformance and reliability than any other traditional system inthe same condition [4].A load balancing has two strategies Static Load Balancing(SLB) and Dynamic Load Balancing (DLB) depending onthe freshness of the input parameters used for determining theload distribution. An associated aim is to avoid systemoverload by using the processing power of the entire systemevenly to smooth out periods of high congestion at individualnodes and network. Dynamic load balancing is moreresponsive to changes in the system workload and hence ismore suitable to heterogeneous environment [5][6]. A DLBalgorithm is further based on either centralized ORdecentralized (distributed) approach. Centralized DLBalgorithm approach limits the scalability [6] because the loadbalancing unit itself becomes a bottleneck and susceptible tofailures so Decentralized DLB algorithm is preferred [7][8].The critical issue here is the inter-node communication andsynchronization required – that involves an all-to-all broadcastas compared to that in the centralized approach (all-to-one andone-to-all)[9].Thus, though the decentralized approachovercomes the limitations of the centralized approach, it raisesthe number of messages used for information exchanges.Therefore, the development of an efficient DLB algorithm isreally critical design issue – one that must ensure a tradeoffbetween the scalability and efficiency. In this backdrop, thehybrid dynamic algorithm is designed which uses bothcentralized and decentralized strategy but which is also lesseffective in case of large number of nodes in the system [10].Therefore we propose the design of a simple yet effectiveimproved hybrid dynamic load balancing algorithm. Ourapproach typically sits between the two extremes mentionedabove.The report proceeds with what other related work we havedone before in sectionII. SectionIII The new improved hybridload balancing approach which is overcoming the drawbacksof hybrid algorithm work that we have done. After that insection IV Analysis of the improved algorithm is done withhybrid system showing that how proposed method is efficient,finally conclusion is produced in chapter V and references thatwe have taken for whole work in section 6.II. RELATED WORKThere are many sources available to write literature for theparametric analysis of static and dynamic load balancingalgorithm and the design of load balancing algorithm that try toaddress one or another design issues, but no one of themaddressed efficiency concern as per my observation.Loadbalancing involves the distribution of jobs throughout anetworked computer system, thus increasing throughputwithout having to obtain additional or faster computerhardware [1]. Load balancing policies may be either static ordynamic.A.Static Load Balancing(SLB)Static load balancing policies are generally based on theinformation about the average behavior of system; transferdecisions are independent of the actual current system state.SLB algorithm collects no information and makes probabilisticwww.ijsrp.org
International Journal of Scientific and Research Publications, Volume 3, Issue 3, March 2013ISSN 2250-31532balancing decisions[2]. Processes are assigned to theprocessors before the execution starts.BDynamic Load Balancing(DLB)Dynamic load balancing algorithm collect varying amount ofstate information to make their decisions. DLB can reassign theprocesses. Dynamic policies, on the other hand, react to theactual current system state in making transfer decisions. Thismakes dynamic policies necessarily more complex than staticones, and truly optimal dynamic policies are known only forspecial systems.Load balancing algorithms vary in theircomplexity where complexity is measured by the amount ofcommunication used to approximate the least loaded node andcost of transferring a job from one node to another. Potentiallythe more information an algorithm can collect the betterdecision it will make [3]. Figure 1 shows the general dynamicload balancing system [5].Figure2:Centralized node based load balancingFigure2 shows the centralized node based balancing in whichone central node handles all the load distribution of theoverloaded node [6].2) Decentralized DLB AlgorithmIn decentralized algorithm all nodes participate in loadbalancing. Decentralized dynamic approach though overcomesthe above problems, suffers from increased communicationoverhead.The project work shows that efficiency can beimproved by replacing the centralized node with a number ofnodes added with interrupt service which is shown in figure 3[6]. The scheme can reduce the waiting time by significantamount of time [7]. This approach supports scalability and hasbetter fault tolerance [8].The decentralized approach ispreferred for the heterogeneous system for balance allocation[9][10].Figure 1: Simple dynamic load balancingThe problem with the complex load balancing algorithm is thatthey cannot keep up with the rapidly changing stateinformation of the system. An associated aim is also to avoidsystem overload by using the processing power of entiresystem evenly to smooth out periods of high congestion atindividual nodes and network [4].In a distributed network of computing hosts, the performanceof the system can depend crucially on dividing up workeffectively across the participating nodes. Dynamic loadbalancing is still very effective when a large portion of theworkload is immobile. All hosts, even those with light loads,benefit from load balancing. Similarly, all types of jobs seeimprovements in their response times, with larger jobsbenefiting more. System instability is possible, but can beeasily avoided. The random arrival of tasks at each processor islikely to bring about uneven processor loads in a distributedsystem [5]. Dynamic Load balancing can be improved byhaving one centralized node to handle the uneven load.DLBcan be centralized or decentralized.1) Centralized DLB AlgorithmA central node acts as the load balancing node, working on thejobs from different nodes in the system. However, thisapproach limits the scalability because the load balancing unititself becomes a bottleneck and susceptible to failures.Figure3: Centralized node replaced by number ofsupporting nodes3) Hybrid DLB algorithm:To overcome the problem of centralized and decentralizedDLB the hybrid load balancing algorithm is developed whichgives greater performance over decentralized approachincreasing response time[11].In figure 4, the MasterNode MSN are replaced by multiplesupporting nodes S1, S2, S3, , Sp. Each node in the system isallowed to access any supporting node. When a node becomesoverloaded, it first queries the member nodes of its group andcollects the load information in a decentralized fashion. Thereis a high probability that the Overloaded node will find alightly loaded node in the same group Here, when a highlyloaded node does not find a lightly loaded node in the samegroup, it randomly selects one supporting node and nowsupporting node follows the same procedure as pursued byMSN. The algorithm gives very high performance with largereduction of response time for large system having largenumber of processes.www.ijsrp.org
International Journal of Scientific and Research Publications, Volume 3, Issue 3, March 2013ISSN 2250-3153 3maximummemory utilizationmaximumI/O queue lengthmaximumI/O utilizationmaximumcontext switch rateAn appropriate combination of these parameters is used toconstitute the load index. Considering maximum loadmeasurement matrices over short interval improvesinstantaneous values, and overcome the use of too longaveraging interval that reduces the responsiveness of the indexto load changes[11]. Hence, we use maximum load ofresources over an interval of 4 seconds.Figure 4: View of groups in simplified distributed systemwith supporting nodesThe disadvantage of the system is that communicationoverhead will be very large in case of large number of nodessince the nodes are directly connected to the supporting nodeof master node in this algorithm [11]. So Here, we propose thedesign of a simple yet effective improved hybrid dynamic loadbalancing algorithm that overcomes limitations of hybridapproach performs competitively for heterogeneous system.Under this new hybrid approach, a highly loaded node isexpected to discover lightly loaded node in lesser time ascompared to hybrid dynamic approach, minimizes thecommunication overhead, and is also expected to produceimproved performance under variety of workloads.III. PROPOSED APPROACHA.Design issuesThere are various factors pertaining to design of a loadbalancing algorithm. For the proposed hybrid approach, allthese factors are discussed in the following1) HeterogeneityThe proposed algorithm is designed to consider systemheterogeneity that is to be associated with varied hardware andsoftware resources of the nodes. We address heterogeneitywith respect to diverse set of CPUs, memories, and disksmachine platform. Specifically, we characterize each node nibyits CPU speed Ci, the storage capacity Miand the disk speedDi.2) Target applicationsA real distributed system can have workload consisting ofapplications that may be using significant amount of CPU,memory, and/or I/O. Therefore, to prevent performance fallunder variety of applications, it is essential to make a decisionupon intended applications while designing a DLB algorithm.3) Metrics for load measurementOur design takes into account the following parameters tomeasure the load at each node in the system; based on whichthe decision for further distribution is done. maximum CPU queue lengthmaximumCPU utilizationmaximummemory queue lengthB. Components of proposed algorithmVarious kinds of components exist, and they should be chosenaccording to the desired environment, such as application typesor system environment. The improved hybrid dynamicalgorithm uses same component as that of hybrid dynamicalgorithm with little changes named as follows,1) Information PolicyThe proposed information policyuses an effective mechanismto exchange state information that considerably reduces thecommunication overhead while quickly updating the stateinformation in large system environment. We use traditionaldemand-driven information policy same as hybrid approach.When any node becomes highly loaded, initially, loadinformation of local nodes from any one supporting node thatresides within the same group is collected. If a lightly loadednode is not found within the same group, other groups aresearched to find a lightly loaded node. In former case, lessernumber of messages will be used while in latter case, thenumber of messages will increase gradually.2) Transfer policyWe use a threshold policy as the transfer policythat is dynamicin nature. However, for simplicity single threshold policy isconsidered. Defining a suitable threshold value for a particularcomputing environment is a challenging task. Therefore, onenode in each group is selected as a MasterNode. TheMasterNode periodically collects the load information of othernodes in the group to compute the average load of the group.This average load is set as a new threshold value T and isbroadcast to other nodes in the group.3) Selection policySelection policy is same which is used in hybrid dynamic loadbalancing algorithm[13].4) Location policyLocation policyconsidered is polling (or probing). Under thispolicy, a MasterNode polls all the nodes in the same group tofind out a lightly loaded node. The node whose load is lowesttaking into account all the parameters is considered as thedestination node. Thus, this approach makes an effort tochoose the best node for the process transfer. The destinationnode executes the process regardless of its resource usage atthe time of arrival of the transferred process.C. Working of Proposed ApproachThe proposed algorithm is designed for a system in which N { n1, n2, n3, ., nn } nodes are connected via a high speedwww.ijsrp.org
International Journal of Scientific and Research Publications, Volume 3, Issue 3, March 2013ISSN 2250-31534communication network. Each node in the system is composedof a combination of various resources including processor,memory, disk, network connectivity and every node differs inits capacity of processor, memory and disk. A system isdivided into m groups, where 1 m n/2. For simplicity, staticgroups are created. Moreover, each group can have differentsize where a number of nodes in each group can be minimum 2and maximum n/2. In each group one node is selected asMasterNode and which is also divided into p number ofMasterSupportingNode(MSN) where 1 p m/2, which is thecentral node for that group that periodically collects the load ofthe other nodes in the group to set new threshold value.Communication between groups is possible via number ofsupporting node SN.Table 1:Definition of notationsNotationsDefinitionNNumber of nodes in distributed systemNi where1 i nDifferent nodes in systemMNumber of groupsMNMaster nodeMsnMasterSupportingNodeSNSupporting nodeLiLoad of the node niPiOverload of the node niTThreshold value to decide status of the nodeFigure 5 shows groups created for simplified distributedsystem. Here, system consists of n 13 nodes that are dividedinto m 4 groups, where group1 and group 3 has 4 nodes,group2 has 4 nodes, and group4 has 2 nodes. Nodes 3, 7, 8,and 12 are MasterNode. Each MN is divided into Msn. EachMsn node has access to SN. Msn is responsible for monitoringavailable resources of other nodes in the group.When a node becomes overloaded, it first queries any one ofthe Msn of its group and Msn collects the load information in acentralized fashion. There is a high probability that the Msnwill find a lightly loaded node in the same group for largesystem (unlikely if the majority of nodes in group are highlyloaded).Figure 5:View of groups in simplified distributed systemwith supporting nodesHowever, when the Msn does not find a suitable destinationnode in the same group to transfer its overload, it requests toone of the supporting nodes to search for the lightly loadednode in the other groups. The SN randomly selects one groupand collects the load status of all nodes in this group from Msnto ensure the availability of destination node. If any lightlyloaded node is found, the overload will be transferred to thisnode, otherwise Msn selects another supporting node andprocess will be repeated until either a lightly loaded node isfound or all groups are searched. In the latter case, the overloadwill be executed on the original node.Since the groups containsvery large number of nodes so there is no possibility that Msnbecomes a bottleneck and a single point of failure occur due topresence of number of Msn. Each Msn in the group is allowedto access any supporting node. We will see algorithm utilizedby highly loaded, Master supporting and supporting node.Algorithm utilized by a highly loaded nodeAssumption: Each node is having some loadInput: load Li of the node and threshold TOutput: destination node to transfer overloadAlgorithm LoadBalancingProcedure (Li, T)1. if Li T for any node Ni2. Consult Msn (or randomly selected MasterSupportingNode)to find lightly loaded node within the group3. if (destination node found)4. dispatch Pi Li – T load to this node5. exitAlgorithm utilized by MasterSupportingNodeAssumption: Each node is having some loadInput: load Li of the node and threshold TOutput: destination node to transfer overloadalgorithm LoadBalancingProcedure Msn(Li, T)1. if Li T for any node Ni2. collect the load status of all nodes in the same group3. take out lightly loaded nodes4. destination node most lightly loaded node5. if (destination node found) send ID of the destination nodeto overloaded node6. transfer overload to destination nodewww.ijsrp.org
International Journal of Scientific and Research Publications, Volume 3, Issue 3, March 2013ISSN 2250-31537. exit8. else9. Consult SN (or randomly selected supporting node) to findlightly loaded node in other groupAlgorithm utilized by SupportingNodeAssumption: Each node is having some loadInput: load Li of the node and threshold TOutput: destination node to transfer overloadAlgorithm LoadBalancingProcedureSN (Li, T)1. while (destination node is not found OR all groups are notsearched)2. FOR each group in the system3. obtain value of threshold T for the selected group from Msn4. take out lightly loaded nodes6. destination node most lightly loaded node7. if (destination node found)8. send ID of destination node to Msn9. Transfer overload to destination node10. exit11.else12. Execute overload on the original nodeIV.PERFORMANCE ANALYSISThe proposed improved hybrid algorithm is evaluated usingfollowing two parameters: Communication overhead andResponse time for large system having node in of largenumber.Table 2: Comparison of decentralized approach andproposed approachCommunication OverheadHybrid dynamicProposedApproachImproved Hybriddynamic approachBest Case75Average Case18 or 2616 or 22Worst Case3030Table 2 summarizes the number of messages utilized by hybridand improved hybrid approaches in order to achieve loadbalancing for the given example.Consider figure 5, let’s assume that node 4 in group-1 hasbecome overloaded. As per the proposed approach, initialnumber of messages used to collect the load information fromthe same group is equal to 7 (4 request messages and 4response messages). If lightly loaded node is found in thisgroup, then 1 message will be used to transfer overload todestination node. Thus, the number of messages is limited to 9if lightly loaded node is found in the same group. However, if adestination node is not found in the same group, the highlyloaded node sends a request to Msn to locate lightly loadednode from the other group. Msn will consult with SN1 andSN1 will search group2, group3, and group4 until lightlyloaded node is found with 18, 26, and 30 messagesrespectively.This analysis shows that proposed approach has higherprobability of lesser communication overhead. For the abovementioned example, it takes only 9 messages to transferoverload in best case while the same communication indecentralized approach would have taken 31 messages. Inaverage case, it takes 18 or 26 messages. However, in worst5case, it may need 30 messages to transfer the overload, but thelikelihood of worst case is less. Moreover, it has been reportedin literature that lesser communication overhead minimizesresponse time. Thus, proposed approach is expected to improveperformance of system in terms of communication overheadand response time. Thus, from all the above study we willcome to conclusion which is explained in next chapter.V. CONCLUSIONWith increasing number of nodes in the system due to largenumber of resources used by user the previous load balancingalgorithms failed to perform efficiently to provide greaterperformance with efficient work distribution. We havedesigned an effective improved hybrid dynamic load balancingalgorithm that fulfills main objectives to overcome severallimitations of hybrid load balancing method, provides Loadmeasurement policy that gives load status of major affectingparameters using Effective information policy. This improvedhybrid load balancing approach significantly minimizes thecommunication overhead along with demand-driveninformation policy for system containing large number ofnodes.Our algorithm is expected to perform efficiently forCPU-intensive, memory-intensive, I/O intensive applications,and any combination of these because we have defined the loadindex utilizing load information of critical resources viz. CPU,I/O, memory to measure the load in large system.REFERENCESMd. Abdur Razzaque and Choong Seon Hong.―Dynamic Load Balancingin Distributed System: An Efficient Approach‖; T.N.Anitha et al / IndianJournal of Computer Science and Engineering (IJCSE) Vol. 3 No. 2 AprMay 2007.[2] Pawandeep Kaur, Harshpreet Singh, “Adaptive dynamic load balancingin grid computing an approach‖; International Journal of EngineeringScience & Advanced Technology(IJESAT),112-125,May-Jun 2012.[3] Ali M. Alakeel. ―A Guide to Dynamic Load Balancing in DistributedComputer Systems‖; International Journal of Computer Science andNetwork Security, Vol. No.10, Issue No. 6, 153—160, Jun 2010.[4] Belabbas Yagoubi, and Yahya Slimani. ―Dynamic Load BalancingStrategy for Grid Computing‖; Transactions on Engineering, Computingand Technology (World Academy of Science), Vol. No. 13, 260—265,May 2006.[5] Sandip Kumar Goyal, R.B. Patel, Manpreet Sing, ―Adaptive andDynamic Load Balancing Methodologies For Distributed Environment:A Review‖; International Journal of Engineering Science andTechnology , Vol.3 No. 3,2011.[6] Parveen Jain, and Daya Gupta. ―An Algorithm for Dynamic LoadBalancing in Distributed Systems with Multiple Supporting Nodes byExploiting the Interrupt Service‖; International Journal of Recent Trendsin Engineering (Academy Publisher), Vol. No. 1, Issue No. 1, 232—236,2009.[7] Sunita Bansal, Divya Gupta, and Chittaranjan Hota, ―AdaptiveDecentralized Load Sharing Algorithms with Multiple Job Transfers InDistributed Computing Environments‖; International Journal of RecentTrends in Engineering, Vol 2, No. 2, November 2009.[8] Issam Al-Azzoni, and Douglas G. Down. ―Decentralized Load Balancingfor Heterogeneous Grids‖; Proceedings of the Computation World:Future Computing, Service Computation, Cognitive, Adaptive, Content,Patterns, IEEE Computer Society, 545—550, 2009.[9] P.Neelakantan, ―Decentralized load balancing in Heterogeneous systemsusing diffusion Approach‖; International Journal of Distributed andParallel Systems (IJDPS) Vol.3, No.1, january 2012.[10] Sunita Bansal, Divya Gupt1, and Chittaranjan Hota, ―AdaptiveDecentralized Load Sharing Algorithms with Multiple Job Transfers InDistributed Computing Environments‖; International Journal of RecentTrends in Engineering, Vol 2, No. 2, November 2009.[11] Mayuri Mehtaand Devesh Jinwala, ―A Hybrid Dynamic Load BalancingAlgorithm for Heterogeneous Environments‖ ; International Journal ofComputer Science & Emerging Technologies(IJCSET), Vol-2 No 5October, 2011[1]www.ijsrp.org
International Journal of Scientific and Research Publications, Volume 3, Issue 3, March 2013ISSN 2250-31536[12] r0m0/index.jsp?topic %2Fcom.ibm.cicsuc600.doc%2Fccllaa0270.htm[13] Pradeep Kumar Sinha, ―Didtributed operating system‖; IEEE Press, 1997- 743 pages,2011.AUTHORSFirst Author – UrjashreePatil., M.E.(Computer Pursuing),Department of Information Technology, ThadomalShahaniEngineering College.Email: hedge,M.E.(Computer)Department of Computer Engineering, R. A. I. T.Email: rajashree.shedge@gmail.comwww.ijsrp.org
Load balancing is an operation that involves redistribution of the system workload, as evenly as possible, among the . March 2013 2 ISSN 2250-3153 www.ijsrp.org balancing decisions[2]. Processes are assigned to the processors before the execution starts. BDynamic Load Balancing(DLB) Dynamic load balancing algorithm collect varying amount of .
