WilliamStallings

DataandComputerCommunications

7thEditionChapter12Routing內(nèi)容12.1RoutinginCircuit–switchingNetworks12.2RoutinginPacket-SwitchingNetworks12.3Least-CostAlgorthms12.1RoutinginCircuitSwitchedNetworkManyconnectionswillneedpathsthroughmorethanoneswitchNeedtofindarouteEfficiencyResilience(回彈力)PublictelephoneswitchesareatreestructureStaticroutingusesthesameapproachallthetimeDynamicroutingallowsforchangesinroutingdependingontrafficUsesapeerstructurefornodesAlternateRoutingPossibleroutesbetweenendofficespredefinedOriginatingswitchselectsappropriaterouteRouteslistedinpreferenceorderDifferentsetsofroutesmaybeusedatdifferenttimesAlternate

Routing

Diagram12.2RoutinginPacketSwitchedNetworkComplex,crucial(至關(guān)重要的)aspectofpacketswitchednetworksCharacteristics(特性)requiredCorrectness(正確性)Simplicity(簡潔行)Robustness(穩(wěn)健性)Stability(穩(wěn)定性)Fairness(公平性)Optimality(最優(yōu)性)Efficiency(高效性)PerformanceCriteriaUsedforselectionofrouteMinimumhop(跳數(shù),途徑結(jié)點(diǎn)的數(shù)量)LeastcostSeeStallingsappendix10AforroutingalgorithmsExamplePacketSwitchedNetworkDecisionTimeandPlaceTimePacketorvirtualcircuitbasisPlacePlace(referstowhcichnodeornodesinthenetworkareresponsiblefortheroutingdecsion,是指應(yīng)該由哪一個(gè)或者哪一些結(jié)點(diǎn)來負(fù)責(zé)路由選擇的判決)DistributedMadebyeachnodeCentralizedSourceNetworkInformationSourceandUpdateTiming(網(wǎng)絡(luò)信息資源和更新定時(shí))Routingdecisionsusuallybasedonknowledgeofnetwork((notalways，大多數(shù)情況下，路由會(huì)要網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)、通信負(fù)荷量和鏈路費(fèi)用等信息))Distributedrouting(分布式路由)NodesuselocalknowledgeMaycollectinfofromadjacentnodesMaycollectinfofromallnodesonapotentialrouteCentralrouting(集中式路由)CollectinfofromallnodesUpdatetiming(更新定時(shí))WhenisnetworkinfoheldbynodesupdatedFixed-neverupdatedAdaptive-regularupdatesRoutingStrategiesFixed(固定式)Flooding(洪泛式)Random(隨機(jī)式)Adaptive(自適應(yīng)式)FixedRoutingSinglepermanentrouteforeachsourcetodestinationpairDetermineroutesusingaleastcostalgorithm(appendix10A)Routefixed,atleastuntilachangeinnetworktopologyFixedRouting

TablesFlooding(洪泛式路由)NonetworkinforequiredPacketsentbynodetoeveryneighborIncomingpacketsretransmitted(中轉(zhuǎn))oneverylinkexceptincominglinkEventuallyanumberofcopieswillarriveatdestinationEachpacketisuniquelynumberedsoduplicatescanbediscardedNodescanrememberpacketsalreadyforwardedtokeepnetworkloadinboundsCanincludeahopcountinpacketsFlooding

ExampleAnExampleApacketistobesentfromnode1tonode6andisassignedahopcountof3TheFirsthop,3copiesarecreatedTheSecondhop,9copiesarecreatedTheThirdhop,22copiesarecreatedPropertiesofFloodingAllpossibleroutesaretriedVeryrobustAtleastonepacketwillhavetakenminimumhopcountrouteCanbeusedtosetupvirtualcircuitAllnodesarevisitedUsefultodistributeinformation(e.g.routing)RandomRoutingNodeselectsoneoutgoingpathforretransmissionofincomingpacketSelectioncanberandomorroundrobinCanselectoutgoingpathbasedonprobabilitycalculationNonetworkinfoneededRouteistypicallynotleastcostnorminimumhopAdaptiveRoutingUsedbyalmostallpacketswitchingnetworksRoutingdecisions(判決)changeasconditionsonthenetworkchangeFailureCongestion(擁擠)RequiresinfoaboutnetworkDecisionsmorecomplexTradeoff(權(quán)衡)betweenqualityofnetworkinfoandoverheadReacting(反應(yīng))tooquicklycancauseoscillation(振蕩)Tooslowlytoberelevant(如果太慢,就沒有多大的意義)AdaptiveRouting-AdvantagesImprovedperformanceAidcongestioncontrol(Seechapter13)ComplexsystemMaynotrealizetheoreticalbenefitsClassification(分類)BasedoninformationsourcesLocal(isolated,孤立式的自適應(yīng)策略)RoutetooutgoinglinkwithshortestqueueCanincludebiasforeachdestinationRarelyused-donotmakeuseofeasilyavailableinfoAdjacentnodes(相鄰的)nodes(分布式的自適應(yīng)策略)Allnodes(集中式的自適應(yīng)策略)IsolatedAdaptiveRoutingARPANETRoutingStrategies(1)FirstGeneration1969Distributedadaptive(分布自適應(yīng))Estimateddelay(估計(jì)時(shí)延)asperformancecriterionBellman-Fordalgorithm(appendix10a)NodeexchangesdelayvectorwithneighborsUpdateroutingtablebasedonincominginfoDoesn'tconsiderlinespeed,justqueuelengthQueuelengthnotagoodmeasurementofdelayRespondsslowlytocongestionARPANETRoutingStrategies(1)ARPANETRoutingStrategies(1)Periodically(every128ms),echonodeexchangesitsdelayvectorwithallofitsneighbore.ARPANETRoutingStrategies(2)SecondGeneration1979UsesdelayasperformancecriterionDelaymeasureddirectlyUsesDijkstra’salgorithm(appendix10a)Goodunderlightandmedium(中等的)loads(負(fù)載)Underheavyloads,littlecorrelation(相關(guān)性)betweenreporteddelaysandthoseexperiencedARPANETRoutingStrategies(3)ThirdGeneration1987Linkcost(鏈路費(fèi)用)calculationschangedMeasureaveragedelayoverlast10secondsNormalizebasedoncurrentvalueandpreviousresultsARPANETRoutingStrategies(3)12.3LeastCostAlgorithmsBasisforroutingdecisionsCanminimizehopwitheachlinkcost1CanhavelinkvalueinverselyproportionaltocapacityGivennetworkofnodesconnectedbybi-directionallinksEachlinkhasacostineachdirectionDefinecostofpathbetweentwonodesassumofcostsoflinkstraversedForeachpairofnodes,findapathwiththeleastcostLinkcostsindifferentdirectionsmaybedifferentE.g.lengthofpacketqueueDijkstra’sAlgorithmDefinitionsFindshortestpathsfromgivensourcenodetoallothernodes,bydevelopingpathsinorderofincreasingpathlengthN

= setofnodesinthenetworks= sourcenodeT

= setofnodessofarincorporatedbythealgorithmw(i,j)

= linkcostfromnodeitonodejw(i,i)=0w(i,j)=ifthetwonodesarenotdirectlyconnectedw(i,j)0ifthetwonodesaredirectlyconnectedL(n)

=

costofleast-costpathfromnodestonodencurrentlyknownAttermination,L(n)iscostofleast-costpathfromstonDijkstra’sAlgorithmMethodStep1[Initialization]T={s}SetofnodessofarincorporatedconsistsofonlysourcenodeL(n)=w(s,n)forn≠sInitialpathcoststoneighboringnodesaresimplylinkcostsStep2

[GetNextNode]FindneighboringnodenotinTwithleast-costpathfromsIncorporatenodeintoTAlsoincorporatetheedgethatisincidentonthatnodeandanodeinTthatcontributestothepathStep3

[UpdateLeast-CostPaths]L(n)=min[L(n),L(x)+w(x,n)]

foralln

?TIflattertermisminimum,pathfromstonispathfromstoxconcatenatedwithedgefromxton AlgorithmterminateswhenallnodeshavebeenaddedtoT結(jié)束條件：allnodeshavebeenaddedtoTDijkstra’sAlgorithmNotesAttermination,valueL(x)associatedwitheachnodexiscost(length)ofleast-costpathfromstox.Inaddition,Tdefinesleast-costpathfromstoeachothernodeOneiterationofsteps2and3addsonenewnodetoTDefinesleastcostpathfromstothatnodeExampleofDijkstra’sAlgorithmResultsofExample

Dijkstra’sAlgorithmIteration

TL(2)PathL(3)PathL(4)PathL(5)PathL(6)Path1{1}21–251-311–4

--2{1,4}21–241-4-311–421-4–5-3{1,2,4}21–241-4-311–421-4–5-4{1,2,4,5}21–231-4-5–311–421-4–541-4-5–65{1,2,3,4,5}21–231-4-5–311–421-4–541-4-5–66{1,2,3,4,5,6}21-231-4-5-311-421-4–541-4-5-6Bellman-FordAlgorithmDefinitionsFindshortestpathsfromgivennodesubjecttoconstraintthatpathscontainatmostonelinkFindtheshortestpathswithaconstraintofpathsofatmosttwolinksAndsoon

s= sourcenodew(i,j)

=

linkcostfromnodeitonodejw(i,i)=0w(i,j)=ifthetwonodesarenotdirectlyconnectedw(i,j)0ifthetwonodesaredirectlyconnectedh= maximumnumberoflinksinpathatcurrentstageofthealgorithmLh(n)

=

costofleast-costpathfromstonunderconstraintofnomorethanhlinksBellman-FordAlgorithmMethodStep1[Initialization]L0(n)=,forallnsLh(s)=0,forallhStep2[Update]Foreachsuccessiveh0Foreachn≠s,computeLh+1(n)=minj[Lh(j)+w(j,n)]ConnectnwithpredecessornodejthatachievesminimumEliminateanyconnectionofnwithdifferentpredecessornodeformedduringanearlieriterationPathfromstonterminateswithlinkfromjton結(jié)束條件：表格中最后兩行的值相同，不再變化Bellman-FordAlgorithmNotesForeachiterationofstep2withh=Kandforeachdestinationnoden,algorithmcomparespathsfromstonoflengthK=1withpathfrompreviousiterationIfpreviouspathshorteritisretainedOtherwisenewpathisdefinedExampleofBellman-FordAlgorithmResultsofBellman-FordExamplehLh(2)PathLh(3)PathLh(4)PathLh(5)PathLh(6)Path0

-----121-251-311-4--221-241-4-311-421-4-5101-3-6321-231-4-5-311-421-4-541-4-5-6421-231-4-5-311-421-4-541-4-5-6ComparisonResultsfromtwoalgorithmsagreeInformationgatheredBellman-FordCalc