Path Selection Algorithm The Strategy for Designin

PathSelectionAlgorithm:TheStrategyforDesigningDeterministicRoutingfromAlternativePathsMichihiroKoibuchia,1AkiyaJourakua,HideharuAmanoaaDepartmentofInformationandComputerScience,KeioUniversity3-14-1Hiyoshi,Kohoku-ku,Yokohama223-8522,JapanAbstractSystemAreaNetworks(SANs),whichusuallyacceptirregulartopologies,havebeenusedtoconnectnodesinPC/WSclustersorhigh-performancestoragesystems.AlthoughroutingalgorithmsforSANsusuallyfindoutalternativepaths,SANsusuallyacceptonlydeterministicroutings.Thus,pathselectionalgorithm,whichchoosesasinglepathfromalternativepaths,becomesessentialforadvancedroutingsinSANs.However,afewstudiesofithavebeendoneonlyforSANswithoutvirtualchannels,anditsimpactisnotwellanalyzed.Inthispaper,(1)weproposefourpathselectionalgorithmswhichhavedifferentconceptstodistributepathsinSANswithvirtualchannels,and(2)weinvestigatetheperformanceinfluencesofvariouspathselectionalgorithmsthroughaflit-levelsimulation.Simulationresultsshowthatoneofthefouralgorithmsimprovesupto92%ofthroughputagainstsimplepathselectionalgorithms,andpoliciestoremovepathscrossingthebottleneckchannelsaremoreefficientthanonestokeeppathscrossingchannelsthatarenotcrowded.Keywords:Deterministicrouting,SystemAreaNetworks,pathselectionalgorithm,interconnectionnetworks,virtualchannels1IntroductionNetwork-basedparallelprocessingusingcommoditycomponents,suchasper-sonalcomputers,hasreceivedattentionasanimportantparallel-computingenvironment[1][2][3][4].SystemAreaNetwork(SAN),whichconsistsof1CorrespondingAuthor.Address:DepartmentofInformationandComputerScience,KeioUniversity,3-14-1Hiyoshi,Kohoku-ku,Yokohama223-8522,JapanEmailaddress:[e-mail](MichihiroKoibuchi).PreprintsubmittedtoElsevierScience16November2004switchesconnectedwithpoint-to-pointlinks,isoneofthecrucialcomponentsofsuchanenvironment.UnlikeLocalAreaNetworks(LANs),wormhole[5]orvirtualcut-through[6]isusedinSANsforlow-latencydirect-communication.Whensuchmethodsareused,deadlock-freeroutingsarerequired.Ontheotherhand,unlikeinterconnectionnetworksusedinmassivelyparallelcom-puters[7][8],SANsusuallyacceptirregulartopologies,becauseconnectionflexibilityandrobustnessarepreferredovertheuniformityofinterconnectionnetworks.Theirregularityofinterconnectionintroducesdifficultyonguaranteeofconnectivityanddeadlock-freepackettransfer.Thus,thefollowingsimpleroutingshavebeenreceivedattentionaspracticalsolutions:(1)spanning-treebasedroutings,whichusetheconnectivityandacyclicityoftreestructure(e.g.Up*/Down*[9],L-turn/R-turn[10]);(2)methodsusingvirtualchannelstoeliminatedeadlocks(e.g.structuredbufferpools[11],LASH[12],descendinglayers(DL)[13]).Mostofthemoriginallyhavealternativepaths(adaptivity)becausetheyinitiallysearchalternativeshortestpathsundertheconditionsenoughtoavoiddeadlocks.Onthecontrary,eveninrecentswitchingfabrics,deterministicroutings,whichhaveasinglepathbetweeneachpairofswitches,arepreferredoveradap-tiveroutingsbecauseofthefollowingadvantages:(1)theyguaranteein-orderpacketdelivery,whichmessagepassinglibrariesusuallyrequire,withoutsort-ingpacketsatthedestinationhost;(2)high-speedswitchingfabricscanbeimplemented,becausedynamicalchoiceofanoutputpathisnotneeded.Thus,apolicy,whichchoosesasinglepathfromalternativepaths,becomesessen-tialforadvancedroutingsinSANs,andwecallsuchapolicy“pathselectionalgorithm”.However,afewresearchesonpathselectionalgorithmshavebeendoneonlyforSANswithoutvirtualchannels[14],andtheirimpacttotheperformancehasnotbeenwellanalyzed.Inthispaper,(1)weproposefourpathselectionalgorithmswhichhavedif-ferentconceptstodistributepathsinSANswithvirtualchannels,and(2)weinvestigatetheinfluencesofvariouspathselectionalgorithmsonthroughputandlatencythroughaflit-levelsimulation.TheproposedbasicconceptscanbeappliedtomodernSANs,suchasRHiNET-2[2]orQsNET[4]whichhavevirtualchannels.Therestofthepaperisorganizedasfollow.Section2showstraditionalpathselectionalgorithms.InSection3,weproposefourpathselectionalgorithms,whichhavedifferentconceptstodistributepathsuniformly.InSection4,sim-ulationresultsunderaflit-levelsimulationareshown.InSection5,relatedresearchesonpathchoicearedescribedandcomparedwiththepathselectionalgorithm,andinSection6,theconclusionispresented.22PathSelectionAlgorithmRoutingalgorithmsforSANsusuallyhavealternativepaths(adaptivity)orig-inally,becausetheyinitiallysearchalternativeshortestpathsunderthecondi-tionsenoughtoavoiddeadlocks.However,itcannotbedirectlyimplementedonSANsthatonlyallowdeterministicroutings.Thus,apathselectionalgo-rithm,whichstaticallyselectsasinglepathfromalternativepaths,isrequiredforsuchSANs2.Sinceitcannotdynamicallyavoidnetworkcongestion,itseemsthatitsimpactislimited.Nevertheless,apathselectionalgorithmbe-comesessentialforadvancedroutingsinSANsbecauseperformanceofeachdeterministicroutingisseriouslyinfluencedbythedistributionofpaths.Thesimplestpathselectionalgorithmisrandomselection.Anothersimpleoneselectsapathfortheoutputportwithsmallerport-UID(uniqueidentifier)whenmorethantwooutputportsareavailableataswitch.Inthispaper,thisiscalled“lowportfirst”.Ifapathselectionalg