版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領(lǐng)
文檔簡介
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é)點的數(shù)量)LeastcostSeeStallingsappendix10AforroutingalgorithmsExamplePacketSwitchedNetworkDecisionTimeandPlaceTimePacketorvirtualcircuitbasisPlacePlace(referstowhcichnodeornodesinthenetworkareresponsiblefortheroutingdecsion,是指應該由哪一個或者哪一些結(jié)點來負責路由選擇的判決)DistributedMadebyeachnodeCentralizedSourceNetworkInformationSourceandUpdateTiming(網(wǎng)絡信息資源和更新定時)Routingdecisionsusuallybasedonknowledgeofnetwork((notalways,大多數(shù)情況下,路由會要網(wǎng)絡的拓撲結(jié)構(gòu)、通信負荷量和鏈路費用等信息))Distributedrouting(分布式路由)NodesuselocalknowledgeMaycollectinfofromadjacentnodesMaycollectinfofromallnodesonapotentialrouteCentralrouting(集中式路由)CollectinfofromallnodesUpdatetiming(更新定時)WhenisnetworkinfoheldbynodesupdatedFixed-neverupdatedAdaptive-regularupdatesRoutingStrategiesFixed(固定式)Flooding(洪泛式)Random(隨機式)Adaptive(自適應式)FixedRoutingSinglepermanentrouteforeachsourcetodestinationpairDetermineroutesusingaleastcostalgorithm(appendix10A)Routefixed,atleastuntilachangeinnetworktopologyFixedRouting
TablesFlooding(洪泛式路由)NonetworkinforequiredPacketsentbynodetoeveryneighborIncomingpacketsretransmitted(中轉(zhuǎn))oneverylinkexceptincominglinkEventuallyanumberofcopieswillarriveatdestinationEachpacketisuniquelynumberedsoduplicatescanbediscardedNodescanrememberpacketsalreadyforwardedtokeepnetworkloadinboundsCanincludeahopcountinpacketsFlooding
ExampleAnExampleApacketistobesentfromnode1tonode6andisassignedahopcountof3TheFirsthop,3copiesarecreatedTheSecondhop,9copiesarecreatedTheThirdhop,22copiesarecreatedPropertiesofFloodingAllpossibleroutesaretriedVeryrobustAtleastonepacketwillhavetakenminimumhopcountrouteCanbeusedtosetupvirtualcircuitAllnodesarevisitedUsefultodistributeinformation(e.g.routing)RandomRoutingNodeselectsoneoutgoingpathforretransmissionofincomingpacketSelectioncanberandomorroundrobinCanselectoutgoingpathbasedonprobabilitycalculationNonetworkinfoneededRouteistypicallynotleastcostnorminimumhopAdaptiveRoutingUsedbyalmostallpacketswitchingnetworksRoutingdecisions(判決)changeasconditionsonthenetworkchangeFailureCongestion(擁擠)RequiresinfoaboutnetworkDecisionsmorecomplexTradeoff(權(quán)衡)betweenqualityofnetworkinfoandoverheadReacting(反應)tooquicklycancauseoscillation(振蕩)Tooslowlytoberelevant(如果太慢,就沒有多大的意義)AdaptiveRouting-AdvantagesImprovedperformanceAidcongestioncontrol(Seechapter13)ComplexsystemMaynotrealizetheoreticalbenefitsClassification(分類)BasedoninformationsourcesLocal(isolated,孤立式的自適應策略)RoutetooutgoinglinkwithshortestqueueCanincludebiasforeachdestinationRarelyused-donotmakeuseofeasilyavailableinfoAdjacentnodes(相鄰的)nodes(分布式的自適應策略)Allnodes(集中式的自適應策略)IsolatedAdaptiveRoutingARPANETRoutingStrategies(1)FirstGeneration1969Distributedadaptive(分布自適應)Estimateddelay(估計時延)asperformancecriterionBellman-Fordalgorithm(appendix10a)NodeexchangesdelayvectorwithneighborsUpdateroutingtablebasedonincominginfoDoesn'tconsiderlinespeed,justqueuelengthQueuelengthnotagoodmeasurementofdelayRespondsslowlytocongestionARPANETRoutingStrategies(1)ARPANETRoutingStrategies(1)Periodically(every128ms),echonodeexchangesitsdelayvectorwithallofitsneighbore.ARPANETRoutingStrategies(2)SecondGeneration1979UsesdelayasperformancecriterionDelaymeasureddirectlyUsesDijkstra’salgorithm(appendix10a)Goodunderlightandmedium(中等的)loads(負載)Underheavyloads,littlecorrelation(相關(guān)性)betweenreporteddelaysandthoseexperiencedARPANETRoutingStrategies(3)ThirdGeneration1987Linkcost(鏈路費用)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
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責。
- 6. 下載文件中如有侵權(quán)或不適當內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 養(yǎng)老院老人生活照顧人員職業(yè)道德制度
- 養(yǎng)老院老人健康數(shù)據(jù)統(tǒng)計分析制度
- 民航安全管理體系培訓心得
- 新媒體合伙人合同(2篇)
- 承包采摘黃秋葵協(xié)議書范本(2篇)
- 2024年智能化物流設備采購合同
- 《食管癌的治療》課件
- 2025年棗莊貨運資格證安檢考試題
- 2025年廣州貨運從業(yè)資格考試技巧
- 2025年青海貨運從業(yè)資格證考試模擬考試題庫
- 北師大版數(shù)學初二上冊知識點總結(jié)
- 鐵路建設項目施工企業(yè)信用評價辦法(鐵總建設〔2018〕124號)
- 模具報價表精簡模板
- 抽樣檢驗培訓教材(共47頁).ppt
- 時光科技主軸S系列伺服控制器說明書
- 通用帶式輸送機TD75或DT型出廠檢驗要求及記錄
- 高考英語單項選擇題題庫題
- lonely-planet-PDF-大全
- 成人大專畢業(yè)生自我鑒定
- 汽車轉(zhuǎn)向系統(tǒng)設計規(guī)范
- 管鮑之交-歷史劇劇本(共4頁)
評論
0/150
提交評論