外文翻译基于哈希模式的负载均衡性能研究Word文档格式.docx
《外文翻译基于哈希模式的负载均衡性能研究Word文档格式.docx》由会员分享,可在线阅读,更多相关《外文翻译基于哈希模式的负载均衡性能研究Word文档格式.docx(21页珍藏版)》请在冰点文库上搜索。
专业网络工程
班级
学生姓名xx
学号xx
指导教师
PerformanceofHashing-BasedSchemesforInternetLoadBalancing
ZhiruoCao,ZhengWang,EllenZegura
CollegeofComputing
GeorgiaInstituteofTechnology
Atlanta,GA30332-0280
BellLabs
LucentTechnologiesHolmdel,NJ07733
Abstract—LoadbalancingisakeytechniqueforimprovingInternetperformance.Effectiveuseofloadbalancingrequiresgoodtrafficdistributionschemes.Westudytheperformanceofseveralhashingschemesfordistributingtrafficovermultiplelinkswhilepreservingtheorderofpacketswithinaflow.Althoughhashing-basedloadbalancingschemeshavebeenproposedinthepast,thisisthefirstcomprehensivestudyoftheirperformanceusingrealtraffictraces.
Weevaluatefivedirecthashingmethodsandonetable-basedhashingmethod.Wefindthathashingusinga16-bitCRCovertheFivetuplegivesexcellentloadbalancingperformance.Further,load-adaptivetable-basedhashingusingtheexclusiveORofthesourceanddestinationIPaddressesachievescomparableperformancetothe16-bitCRC.Table-basedhashingcanalsodistributetrafficloadaccordingtounequalweights.Wealsoreportonfourotherschemeswithpoortomoderateperformance.
Keywords—Loadsharing,hashing.
I.INTRODUCTION
Loadbalancing(alsoknownasloadsharing)isakeytechniqueforimprovingtheperformanceandscalabilityoftheInternet.Forexample,manylargeenterprisenetworksareconnectedtomultipleInternetServiceProviders(ISPs)toachieveredundantconnectivityandtodistributetrafficloading.InsidetheInternet,thebackbonesareoftenengineeredtohavemultipleparalleltrunksbetweenmajorPointsofPresencetoensurehighavailability.Typically,theseparalleltrunksareconfiguredasequal-costpathsandallowloadbalancingoverthem.
TheparalleltrunksmaybecomeevenmoreubiquitouswhenthepromisingDenseWavelengthDivisionMultiplexing(DWDM)technologyisdeployedinthefutureInternetback-bone.DWDMexpandsthecapacityofcommunicationtrunksbyallowingagreaternumberofchannelstobecarriedonasingleopticalfiber.WithpotentiallytensorevenhundredsofDWDMchannelsbetweenmajorpoints,loadbalancingisessentialinbestutilizingthemultipleparallelchannels.
ParallelarchitectureshavebeenusedforpacketprocessingforcopingwithexponentialgrowthinInternettraffic,Insteadofoneprocessingengine,packetsaredispatchedtomultipleparallelenginesinsidearoutertoincreasetheoverallprocessingthroughput.Thesametechniqueisalsousedinscalingwebservers.PopularwebserversoftenoperateafarmofmachinesandtheroutersconnectedtothemsplittheHTTPrequeststodifferentmachines.
Foralloftheseexamples,effectiveuseofloadbalancingrequiresgoodschemesforsplittingtrafficovermultiplelinks.Inaddition,sincethemajorityofthetrafficontheInternetisTCP-based[1],trafficsplittingschemesneedtoavoidpacketmisorderingwithinaTCPflow,whichcanfalselytriggercongestioncontrolmechanismsandcauseunnecessarythroughputdegradation[2],[3].
Inthispaper,weproposeandevaluateaclassofhashingbasedtrafficsplittingalgorithmswhichpreserveper-flowpacketordering.Weconsiderfivehashfunctionsthatare“direct,”meaningthatthehashfunctionproducesavalueintherangeof0...N-1,whereNisthenumberofoutgoinglinks.Wealsoconsideratable-basedgeneralizationthatinvolveshashingtoMbins,thenassigningtheMbinstotheNoutgoinglinks.Tablebasedhashingrequiresmorestatethandirecthashing,buthastheflexibilitytosupportunequalloaddistributionanddynamicadaptation.
Ourresultsareobtainedbysimulatingtheperformanceofatrafficsplitter,usingpackettracestakenfromtwotrunksofamajorInternetbackboneprovider.WefindthatdirecthashingwiththedestinationIPaddresscausessignificantimbalanceacrosstwolinks.UsingtheInternetchecksumortheexclusiveORofboththesourceIPaddressanddestinationIPaddressimprovestheperformanceconsiderably,thoughmoderateimbalancepersists.Themorecomputationallycomplex16-bitCRCofthefive-tuple(sourceaddress,destinationaddress,sourceport,destinationportandprotocolid)givesexcellentloadbalancingperformance,keepingtheloadandqueuelengthsverysimilarontwolinks.Equallygoodloadbalancingcanbeachievedusingtable-basedhashingwithadaptation,whichrequireslesscomputationthantheCRCbutnecessitatesmonitoringthelinkloadsandstoring(andadjusting)themappingfromtablebinstolinks.
Table-basedhashinghastheadditionaladvantagethatitcandistributetheloadaccordingtounequalweights.Further,anindex-basedversionofthisschemecanaltertheweightdistributionwithminimaldisruptiontoexistingflows.Ourresultsconfirmthattheindex-basedhashingcanaccuratelyachieveaweighteddistributionwhenadaptationisalsoused.
Therestofthispaperisorganizedasfollows.InSectionIIwediscussrelatedworkintrafficsplittingandloadbalancing.SectionIIIdescribesthebehaviorofanidealtrafficsplitter,explainstherequirementsforapracticalsystem,anddefinestheperformancemetricsthatwillbeusedtoassessvarioushashing-basedschemes.ThesetofschemesthatweconsideraredescribedinSectionIV.TheresultsofourstudyaredescribedinSectionV,andincludeanalysisoftherandomnessinherentinthetracedata(SectionV-A).WeconcludeandmentionareasforfutureworkinSectionVI.
II.RELATEDWORK
Loadbalancinghasbeenusedintelecommunicationnetworksintheformofinversemultiplexing[4].Inversemultiplexingallowsserviceproviderstoofferwidebandchannelsbycombiningmultiplenarrowband56kbpsand64kbpstrunks[5].Theloadbalancingininversemultiplexingistypicallybasedonroundrobindistributionofpacketsorbytes[6],[7].
Ourworkdiffersfrominversemultiplexingintwoimportantdimensions.First,inversemultiplexingisdesignedforuseoverpoint-to-pointlinks;
itstechniquesarenottypicallyapplicablefornetworklayerloadbalancing.Internetloadbalancing,however,makesuseofthenaturalredundancyinthenetworktopology.Thepathsforloadbalancing,forexample,equal-costmulti-paths,arediscovereddynamicallybyroutingprotocols,suchasOSPF[8],ratherthanthroughconfiguration.Second,inordertomaintainsynchronizationandper-flowFIFOpacketorderingininversemultiplexing,itisnecessarytoaddextrapacketheaderswithsequencenumbersortokeepstateatbothendsofthechannel.But,implementingtheseadditionalmechanismsfornetworkloadbalancingrequiresanewnetworkprotocol.Incomparison,thehashing-basedschemescanmaintainper-flowpacketorderingandcanbeimplementedwithoutrequiringanyadditionalprotocolsupport.
Hashinghasbeenwidelyusedinindexingandsearching[9].Inthenetworkingcontext,hashing-basedalgorithmsforaddresslookup[10],flowidentification[11]andpacketdemultiplexing[12]havebeenproposedinthepast.Theuseofhashingfornetworkloadbalancingisnotnew.SomecommercialrouterproductshaveimplementedsimplehashingovertheIPdestinationaddresstodistributetraffic[13].IntheOSPFOptimizedMultipathprotocol(OSPF-OMP)[14],anumberofpossibleapproachesforloadbalancingovermultiplepathsarementioned,includingper-packetroundrobin,dividingdestinationprefixesamongavailablenexthopsintheforwardingtable,anddividingtrafficaccordingtoahashfunctionappliedtothesourceanddestinationpair.However,theproposedschemesarenotevaluatedwithsimulationorrealnetworkmeasurement.InthestudyofloadbalancingwithOSPF-OMP,perfecthashingisassumed[15].
Atrafficsplittingschemeusingrandomnumbersisproposedin[16].Itappliesthename-basedmappingsapproachtoloadbalancing[17].Inthisscheme,eachnext-hopisassignedwithaweightbasedonasimplepseudo-randomnumberfunctionseededwiththeflowidentifierandthenext-hopidentifier.Whenapacketarrives,theweightsaregenerated,andthenext-hopreceivingthehighestweightisusedforforwarding.Theschemeisapproximatelytimesasexpensiveasahashing-basedscheme,whereisthenumberofoutgoinglinks.Again,noperformancestudyontheproposedschemeispresented.
Itisclearthatalthoughhashing-basedschemesfortrafficsplittinghavebeenproposedinthepast,andsomesimpleschemeshaveevenbeenimplementedincommercialproducts,theperformanceofsuchschemeshasnotbeenadequatelyevaluated.Thispaperpresentsthefirstcomprehensiveperformancestudyonawiderangeofhashing-basedschemes,usingrealpackettracesfrombackbonenetworks.
III.FRAMEWORK
Inthissection,wedescribethebehaviorofanidealtrafficsplitter,explaintherequirementsforapracticalsystem,anddefinetheperformancemetricsforassessingvariousschemes.
A.ReferenceModel
AloadbalancingsystemtypicallycomprisesatrafficsplitterandmultipleoutgoinglinksasshowninFigure1.Insuchasystem,thetrafficsplitterreceivesanincomingpacketfromahigher-speedlinkandforwardsittooneofthelower-speedoutgoinglinks.Agoodloadbalancingsystemshouldbeabletosplitthetraffictothemultipleoutgoinglinksevenlyorbysomepre-definedproportion.
In[7],ithasbeenobservedthatthereisacloserelationshipbetweenfairqueuingandloadbalancing.Wenowextendtheirobservationtoamathematicalmodeltoobtaintheconstraintsforidealtrafficsplitting.
Letusfirstlookatanidealfluidmodelwherethetrafficisinfinitelydivisible.Supposethatthereareoutgoinglinksintheloadbalancingsystem,andthecapacityoflinkIisui.LetSi(T,t)be