DCN-FatTreeAdvanced Computer Networking完整原版课件

AdvancedComputerNetworkingScopeCuttingedgetechnologicaltrendsincomputernetworkinginthepastafewyears.Time:Tuesday3,4,5(9:45-12:10,week1-16)Thursday1,2(7:50-9:25,week8-12)Venue:Online:Offline:3B202Score:60%:~3courseprojects40%:finalexam(USTCmandatoryrequirement)AScalable,CommodityDataCenterNetworkArchitectureMohammadAl-Fares,AlexanderLoukissas,AminVahdatSIGCOMM2008PresentedbyYeTianforCourseCS05112OutlineBackgroundFattreebasedsolutionImplementationandevaluationReviewDatacentersClustersofthousandsofcomputersWheretheInternetlivesGoogledatacenter/about/datacenters/inside/streetview/Microsoft

underwaterdatacenter腾讯贵安七星数据中心阿里巴巴千岛湖数据中心DatacenterracksWhatisdatacenter?DCCommunicationsPlentyofM2Mcommunications,theprinciplebottleneckinlarge-scaleclustersisofteninter-nodecommunicationbandwidth.MapReduce:mustperformsignificantdatashufflingtotransporttheoutputofitsmapphasebeforeproceedingwithitsreducephase.Websearchengine:oftenrequiresparallelcommunicationwitheverynodeintheclusterhostingtheinvertedindextoreturnthemostrelevantresultsManagedbyonesingleauthorityTwoapproachesforDCnetworkApproach1:SpecializedhardwareandcommunicationprotocolsForexample:InfiniBand,MyrinetDonotleveragecommodityparts,expensiveNotcompatiblewithTCP/IPapplicationsApproach2:LeveragescommodityEthernetswitchesandrouterstointerconnectclustermachines.Unmodifiedapplications,OS,andhardwareButhow?DesiredPropertiesforaDCNetworkArchitectureScalableinterconnectionbandwidth:anarbitraryhostinthedatacentercancommunicatewithanyotherhostinthenetworkatthefullbandwidthofitslocalnetworkinterface.Economiesofscale:makecheapoff-the-shelfEthernetswitchesthebasisforlargescaledatacenternetworks.Backwardcompatibility:theentiresystemshouldbebackwardcompatiblewithhostsrunningEthernetandIP.CurrentDataCenterNetworkTopologiesCurrentDataCenterNetworkTopologiesThreetiers:core,aggregation,edge(ToRswitch)Twotypesofswitches:48-portGigEswitch,withfour10GigEuplinks,usedattheedgeofthetree128-port10GigEswitchforhigherlevelsofacommunicationhierarchyProblemsoftheTopologyOversubscription:theratioofthetotalbisectionbandwidthofaparticularcommunicationtopologytotheworst-caseachievableaggregatebandwidthamongtheendhosts.Ideal:1:1,allhostsmaypotentiallycommunicatewitharbitraryotherhostsatthefullbandwidthoftheirnetworkinterfaceTypicaldesignsareoversubscribedbyafactorof2.5:1to8:1ProblemsoftheTopologyMulti-pathRouting:Deliveringfullbandwidthbetweenarbitraryhostsinlargerclustersrequiresa“multi-rooted”treewithmultiplecoreswitchesECMPperformsstaticload-splittingamongflows.Limitthemultiplicityofpathsto8–16ProblemsoftheTopologyCost:保证一定的oversubscription，cost会随规模急剧增加。ProblemsoftheTopologyCost:Usingthelargest10GigEandGigEswitchestobuildadatacenterwith1:1oversubscriptionAclustercanbeupto27,648hostsOutlineBackgroundFattreebasedsolutionImplementationandevaluationReviewFat-treeFat-treekpods,eachcontainingtwolayersofk/2switches.Eachk-portswitchinthelowerlayerisdirectlyconnectedtok/2hosts.Eachoftheremainingk/2portsisconnectedtok/2ofthekportsintheaggregationlayer.Fat-tree(k/2)2

k-portcoreswitches.Eachhasoneportconnectedtoeachofkpods.Theithportofanycoreswitchisconnectedtopodisuchthatconsecutiveportsintheaggregationlayerofeachpodswitchareconnectedtocoreswitcheson(k/2)strides.Fat-treeFocusondesignsuptok=48.Useidentical48-portGigEswitches.Thenetworksupports27,648hosts,madeupof1,152subnetswith24hostseach.Thereare576equal-costpathsbetweenanygivenpairofhostsindifferentpods.Thecostofdeployingsuchanetworkarchitecturewouldbe$8.64M,comparedto$37Mforthetraditionaltechniques.ArchitectureDesignMotivationThereare(k/2)2shortest-pathsbetweenanytwohostsondifferentpods,butonlyoneischosen.Eachpathhas5hopsProtocolslikeOSPFselectspathbasedonhopcounts.itispossibleforasmallsubsetofcoreswitches,perhapsonlyone,tobechosenastheintermediatelinksbetweenpods.Needasimple,fine-grainedmethodoftrafficdiffusion.AddressingAllIPaddressesinthenetworkwithintheprivate/8block.Thepodswitchesaregivenaddressesoftheform10.pod.switch.1,poddenotesthepodnumber(in[0,k−1]),switchdenotesthepositionofthatswitchinthepod(in[0,k−1],startingfromlefttoright,bottomtotop).Givecoreswitchesaddressesoftheform10.k.j.i,jandidenotethatswitch’scoordinatesinthe(k/2)2coreswitchgrid(eachin[1,(k/2)],startingfromtop-left).Two-levelRoutingTableEachentryinthemainroutingtablewillpotentiallyhaveanadditionalpointertoasmallsecondarytableof(suffix,port)entries.Afirst-levelprefixisterminatingifitdoesnotcontainanysecondlevelsuffixes,Asecondarytablemaybepointedtobymorethanonefirst-levelprefix.Two-levelRoutingTableEntriesintheprimarytableareleft-handed(i.e.,/mprefixmasksoftheform1m032−m),entriesinthesecondarytablesareright-handed(i.e./msuffixmasksoftheform032−m1m).Ifthelongest-matchingprefixsearchyieldsanon-terminatingprefix,thenthelongest-matchingsuffixinthesecondarytableisfoundandused.Two-levelRoutingTableTheroutingtableofanypodswitchwillcontainnomorethank/2prefixesandk/2suffixes.RoutingAlgorithmPodswitchesIfahostsendsapackettoanotherhostinthesamepodbutonadifferentsubnet,thenallupper-levelswitchesinthatpodwillhaveaterminatingprefixpointingtothedestinationsubnet’sswitch.RoutingAlgorithmPodswitchesForallotheroutgoinginter-podtraffic,thepodswitcheshaveadefault/0prefixwithasecondarytablematchinghostIDs.EmploythehostIDsasasourceofdeterministicentropy;theywillcausetraffictobeevenlyspreadupwardamongtheoutgoinglinkstothecoreswitches.RoutingAlgorithmAggregationswitchesOnceapacketreachesitsdestinationpod,thereceivingupper-levelpodswitchwillalsoincludea(10.pod.switch.0/24,port)prefixtodirectthatpackettoitsdestinationsubnetswitch,whereitisfinallyswitchedtoitsdestinationhost.Generatingupperaggregationswitchroutingtable;Forlowerswitches,omitline3-5.RoutingAlgorithmCoreswitchesOnceapacketreachesacoreswitch,thereisexactlyonelinktoitsdestinationpod,andthatswitchwillincludeaterminating/16prefixforthepodofthatpacket(10.pod.0.0/16,port).AnExampleSource:;destination:Atthegatewayswitch(),matcheswiththe/0first-levelprefix,thenmatcheswiththe/8secondary-levelsuffix,thenforwardtoport2,androutedtothepodswitch.(i=3,z=1)AnExampleAtthegatewayswitch(),matcheswiththe/0first-levelprefix,thenmatcheswiththe/8secondary-levelsuffix,thenforwardtoport2,androutedtothepodswitch.(i=3,z=2)AnExampleAt,matchesaterminating/16prefix,whichpointstopod2onport2,andswitch.At,matchesaterminatingprefix/24,whichpointstotheswitchresponsibleforthatsubnet,onport0.Howaboutthedestinationbecomes?Centralizedalgorithm,notadistributedone.Whyfeasible?FlowClassificationThetwo-levelroutingtechniqueisstatic,buttrafficsarenotevenlydistributedamongthehosts.EdgeswitchRecognizesubsequentpacketsofthesameflow,andforwardthemonthesameoutgoingport.(packetsofsame<srcIP,dstIP,srcport,dstport,proto>belongtoasameflow)Periodicallyreassignaminimalnumberofflowoutputportstominimizeanydisparitybetweentheaggregateflowcapacityofdifferentports.FlowSchedulingTrafficsaredominatedbyfewlargelong-livedflowsEdgeswitchAdditionallydetectanyoutgoingflowwhosesizegrowsaboveapredefinedthreshold,andperiodicallysendnotificationstoacentralschedulerspecifyingthesourceanddestinationforallactivelargeflows.FlowSchedulingCentralSchedulerMaintainsbooleanstateforalllinksinthenetworktheiravailabilitytocarrylargeflows.Whentheschedulerreceivesanotificationofanewflow,itlinearlysearchesthroughthecoreswitchestofindonewhosecorrespondingpathcomponentsdonotincludeareservedlink.Uponfindingsuchapath,theschedulermarksthoselinksasreserved,andnotifiestherelevantlower-andupper-layerswitchesinthesourcepodwiththecorrectoutgoingportthatcorrespondstothatflow’schosenpath.PowerandHeatIssues不同Switch的能耗效率，后三个是10GigE的switchEmploysmoreindividualswitches,issuperiortothoseincurredbycurrentdatacenterdesigns,with56.6%lesspowerconsumptionand56.5%lessheatdissipation.OutlineBackgroundFattreebasedsolutionImplementationandevaluationReviewImplementationImplementrouterprototypewithClick.Supportthetwo-levelroutingtable4-portsTheClickModularRouterProjectAsoftwarearchitectureforbuildingflexibleandconfigurablerouters/kohler/clickExperimentDescriptionImplementa4-portfat-tree(k=4):thereare16hosts,fourpods(eachwithfourswitches),andfourcoreswitches.Multiplexthese36elementsontotenphysicalmachines,interconnectedbya48-portProCurve2900switchwith1GigabitEthernetlinks.Eachpodofswitchesishostedononemachine;eachpod’shostsarehostedononemachine;andthetworemainingmachinesruntwocoreswitcheseach.ExperimentDescriptionForthecomparisoncaseofthehierarchicaltreenetwork,fourmachinesrunningfourhostseach,andfourmachineseachrunningfourpodswitcheswithoneadditionaluplink.BenchmarkSuiteRandom:Ahostsendstoanyotherhostinthenetworkwithuniformprobability.Stride(i):Ahostwithindexxwillsendtothehostwithindex(x+i)mod16.StaggeredProb(SubnetP,PodP):Whereahostwillse