A dynamic and adaptive load balancing strategy for

J.ParallelDistrib.Comput.72(2012)1254–1268ContentslistsavailableatSciVerseScienceDirectJ.ParallelDistrib.Comput.journalhomepage:∗,XiuqiaoLi,QimengWu,LiminXiao∗,LiRuanStateKeyLaboratoryofSoftwareDevelopmentEnvironment,SchoolofComputerScienceandEngineering,BeihangUniversity,Beijing100191,ChinaarticleinfoArticlehistory:Received1July2011Receivedinrevisedform2May2012Accepted14May2012Availableonline23May2012Keywords:DistributedloadbalancingParallelfilesystemsOn-lineloadpredictionLoadcollectionDynamicfilemigrationAdaptivealgorithmabstractManysolutionshavebeenproposedtotackletheloadimbalanceissueofparallelfilesystems.However,allthesesolutionseitheradoptcentralizedalgorithms,orlackconsiderationsforboththenetworktransmissionandthetradeoffbetweenbenefitsandside-effectsofeachdynamicfilemigration.Therefore,existingsolutionswillbeprohibitivelyinefficientinlarge-scaleparallelfilesystems.Toaddressthisproblem,thispaperpresentsSALB,adynamicandadaptiveloadbalancingalgorithmwhichistotallybasedonadistributedarchitecture.Tobealsoawareofthenetworktransmission,SALBontheonehandadoptsanadaptivelyadjustedloadcollectionthresholdinordertoreducethemessageexchangesforloadcollection,andontheotherhanditemploysanon-lineloadpredictionmodelwithaviewtoreducingthedecisiondelaycausedbythenetworktransmissionlatency.Moreover,SALBemploysanoptimizationmodelforselectingthemigrationcandidatessoastobalancethebenefitsandtheside-effectsofeachdynamicfilemigration.ExtensiveexperimentsareconductedtoprovetheeffectivenessofSALB.TheresultsshowthatSALBachievesanoptimalperformancenotonlyonthemeanresponsetimebutalsoontheresourceutilizationamongtheschemesforcomparison.ThesimulationresultsalsoindicatethatSALBisabletodeliverhighscalability.©2012ElsevierInc.Allrightsreserved.1.IntroductionThedisparitybetweentherateatwhichscientificapplicationscancalculateresultsandtherateatwhichtheapplicationscanstoretheirdataontopersistentstorage(i.e.,harddisks)isanunavoidableissueforhigh-endcomputersystems[32].Asanattractivesolution,theparallelI/Osystemallowsdatatobeconcurrentlytransferredbetweenthememoryandthepersistentstoragedevice.Theparallelfilesystem,oneoftheimportantcomponentsofaparallelI/Osystem,isresponsibleforstripingdataontoI/Oserversandthenpermitstheaccessesforthesedataexecutingconcurrently.Hence,parallelfilesystemsplayanimportantroleindatamanagementandhavereceivedalotofattentionintherecentpast[25,7,13].InordertofullyreaptheperformanceofparallelI/Osys-tems,theloadamongtheI/Oserverssituatedinparallelfilesystemsshouldbedistributeduniformly[33].EvenlydistributedloadacrosstheI/Oserverscaneliminateperformancebottlenecks,therebyoptimizingthemeanresponsetimeandtheresourceuti-lization.However,somefactorssuchasunsuitablefilestriping∗Correspondingauthors.E-mailaddresses:[e-mail](B.Dong),[e-mail](L.Xiao).sizes[45],improperfileallocations[56,60],applicationcompeti-tions[27,6]andheterogeneouscomputingenvironments[54]mayleadtoloadimbalanceamongtheI/Oservers.Consequently,thevarianceoftheresponsetimeofparallelfilesystemsisenlargedandthereforethewholeparallelI/Osystemisunderutilized[38].Manysolutions[38,46,31,35]havebeenproposedtotackletheloadimbalanceissueoftheI/Oservers.However,withthegrowthoftheparallelI/Osystemscale,parallelfilesystemsarenowfacingsignificantchallengescausedbythemanagementoflarge-scaleI/Oservers.Asaresult,theloadbalancingalgorithmforparallelfilesystemsneedstodealwiththefollowingthreenewchallenges.ThefirstchallengefortheloadbalancingalgorithmishowtoprovidethescalabilityandtheavailabilityrequiredbythesteadilygrowingparallelI/Osystem.High-performancecomputingisintheeraofthepetabyte-scaleandisexpectedtoachievetheextrabyte-scaleinthe2018–2020timeframe[22].Accordingly,itisestimatedthattheI/Orequirementofscientificapplicationswillincreasefrom0.2TB/sto20TB/s[29].SincetheparallelI/Osystemprovidesthehigh-speeddatatransferratethroughaggregatingindividualdeviceperformance,inordertomatchsuchfastdatatransferrates,thescaleoftheparallelI/Osystemmustbeenlarged[1].High-scalableandhigh-availablesoftwaresaretheenablingtechnologiesthatallowsuchsystemstofullydelivertheirperformance.However,mostexistingloadbalancingsolutions[38,46,31]employcentralizedalgorithms,thescalabilityofwhichislimitedbyfixedmemorysize,CPUpower,andnetwork0743-7315/$–seefrontmatter©2012ElsevierInc.Allrightsreserved.doi:10.1016/j.jpdc.2012.05.006B.Dongetal./J.ParallelDistrib.Comput.72(2012)1254–12681255bandwidth[35].Moreover,ifthecentralservercrashes,thewholeloadbalancingalgorithmmaybedown.AscalableandavailableloadbalancingmethodisrequiredforparallelfilesystemswhichmaymaintainhundredsoreventhousandsofI/Oservers.Thesecondchallengefortheloadbalancingalgorithmishowtotakethenetworktransmissionintoaccount.Ontheonehand,themessageexchangesfortheloadcollectionshouldbeconsideredbytheloadbalancingalgorithm.Onereasonisthattheloadbalancingdecisionshouldbemadebasedontheloadconditionofthewhol