分布式系统中一种有效的扩散负载均衡算法(IJITCS-V6-N8-9)

I.J.InformationTechnologyandComputerScience,2014,08,65-71PublishedOnlineJuly2014inMECS()DOI:10.5815/ijitcs.2014.08.09Copyright©2014MECSI.J.InformationTechnologyandComputerScience,2014,08,65-71AnEfficientDiffusionLoadBalancingAlgorithminDistributedSystemRafiqulZ.KhanDepartmentofComputerScience,AligarhMuslimUniversity,Aligarh,IndiaEmail:[e-mail]cience,AligarhMuslimUniversity,Aligarh,IndiaEmail:[e-mail]—Indistributedcomputingsystemsomenodesareveryfastandsomeareslowandduringthecomputationmanyfastnodesbecomeidleorunderloadedwhiletheslownodesbecomeoverloadedduetotheunevendistributionofloadinthesystem.Indistributedsystem,themostcommonimportantfactoristheinformationcollectionaboutloadsondifferentnodes.Thesuccessofloadbalancingalgorithmdependsonhowquicklytheinformationabouttheloadinthesystemiscollectedbyanodewillingtotransferoracceptload.Inthispaperwehaveshownthatthenumberofcommunicationoverheadsdependsonthenumberofoverloadednodespresentinthedomainofanunderloadednodesandvice-versa.WehavealsoshownthatcommunicationoverheadforloadbalancingisalwaysfairlylessthanKNbutinworstcaseouralgorithm’scomplexitybecomesequaltoKN.IndexTerms—DistributedSystem,LoadBalancing,UnderLoaded,Overloaded,OverheadsI.INTRODUCTIONAdistributedcomputingsystem(DCS)isasetofprocessors(nodes)connectedthroughanetwork.Distributednetworkismainlyheterogeneousinnatureinthesensethattheprocessingnodes,networktopology,communicationmedium,operatingsystemetc.maybedifferentindifferentnetworkwhicharewidelydistributedovertheglobe[1-4].Presentlyseveralhundredcomputersareconnectedtobuildthedistributedcomputingsystem[3,5-7].Inordertogetthemaximumefficiencyofasystemtheoverallworkloadhastobedistributedamongthenodesaccordingtotheirperformanceoverthenetwork.Sotheissueofloadbalancingbecamepopularduetotheexistenceofdistributedmemorymultiprocessorcomputingsystems[8].ThemainpurposeoftheDCSistosharetheresourcesinabestwayavailableinthenetwork.Sooneofthebestwaytoutilizeandtosharethenetworkresourcesisthroughtheloadbalancingamongtheprocessors.InDCSgenerallysomeprocessorsmayhavemorenumbersofjobsandsomeothersmayhavelessnumbersofjobsorevenidlecausinginequalityofjobdistributionondifferentprocessorsresultinglowperformanceofthesystem.Andtheperformanceofasystemisconsideredtobetheperformanceoftheslowestnodeinthenetwork.Sometimeitisobservedinthenetworkthatatpeaktimethefastestprocessorsareidleorlightlyloadedandtheslowernodesareheavilyloaded.Soloadbalancingcanbedonebytransferringexcessloadfromtheheavilyloadednodestothelightlyloadednodessothattheloadoneachnodebecomesapproximatelythesame.Theloadbalancingalgorithmsimprovetheoverallperformanceofthesystembyexploitingmaximumpoweroftheprocessorsandminimizingtheaverageresponsetime.Thedistributionofloadstotheprocessingelementsissimplycalledtheloadbalancingproblem.Inasystemwithmultiplenodesthereisaveryhighchancethatsomenodeswillbeidlewhiletheotherwillbeoverloaded.Thegoaloftheloadbalancingalgorithmsistomaintaintheloadtoeachprocessingelementsuchthatalltheprocessingelementsbecomeneitheroverloadednoridlethatmeanseachprocessingelementideallyhasequalloadatanymomentoftimeduringexecutiontoobtainthemaximumperformance(minimumexecutiontime)ofthesystem[9-13].Sotheproperdesignofaloadbalancingalgorithmmaysignificantlyimprovetheperformanceofthesystem.Inthenetworktherewillbesomefastcomputingnodesandslowcomputingnodes.Ifwedonotaccounttheprocessingspeedandcommunicationspeed(bandwidth),theperformanceoftheoverallsystemwillberestrictedbytheslowestrunningnodeinthenetwork[13].Thusloadbalancingstrategiesbalancetheloadsacrossthenodesbypreventingthenodestobeidleandtheothernodestobeoverwhelmed.Furthermore,loadbalancingstrategiesremovestheidlenessofanynodeatruntime.Theneedofloadbalancingarisesfromtheconceptthatthereisaverylittleprobabilitythattheloadtoasystemwillbedistributedaccordingtotheprocessingpowerofthenodes.Inthenetworksomenodeswillbehighlyloadedandsomewillbelightlyloadedoridlesometimesasaresulttheperformanceofthesystemwillbeconsiderablydegradedwhichcanberesolvedinanoptimizedwaythroughtheloadbalancingstrategieswhichdealswithassigningthetaskstoeachprocessoraccordingtothespeedandbandwidthofthecommunicationlinktoobtainthemaximumperformance(minimumexecutiontime)ofthesystem[8,14-16].66AnEfficientDiffusionLoadBalancingAlgorithminDistributedSystemCopyright©2014MECSI.J.InformationTechnologyandComputerScience,2014,08,65-71Duringthedesignofadynamicloadbalancingalgorithmthefollowingissuesareconsidered[11,15]:Assignmentwhichassignsthejobstotheprocessorsaccordingtothesituationinasystem;loadCalculationwhichtellshowtocalculatetheworkloadofaparticularnodeinasystem;jobtransferwhichdetermineswhetherajobistobeexecutedlocallyorremotely,thisalsodefineswhenanodebecomesoverloaded;systemStatewhichtellswhetheranodeisoverloadedorlightlyloaded;priorityassignmentwhichtellsthepriorityofexecutionoflocalandremoteprocessesataparticularnodeandinformationexchangewhichtellshowtoexchangethesystemloadinformationamongthenode