版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
WilliamStallings
DataandComputerCommunications
7thEditionChapter12Routing内容12.1RoutinginCircuit–switchingNetworks12.2RoutinginPacket-SwitchingNetworks12.3Least-CostAlgorthms12.1RoutinginCircuitSwitchedNetworkManyconnectionswillneedpathsthroughmorethanoneswitchNeedtofindarouteEfficiencyResilience(回弹力)PublictelephoneswitchesareatreestructureStaticroutingusesthesameapproachallthetimeDynamicroutingallowsforchangesinroutingdependingontrafficUsesapeerstructurefornodesAlternateRoutingPossibleroutesbetweenendofficespredefinedOriginatingswitchselectsappropriaterouteRouteslistedinpreferenceorderDifferentsetsofroutesmaybeusedatdifferenttimesAlternate
Routing
Diagram12.2RoutinginPacketSwitchedNetworkComplex,crucial(至关重要的)aspectofpacketswitchednetworksCharacteristics(特性)requiredCorrectness(正确性)Simplicity(简洁行)Robustness(稳健性)Stability(稳定性)Fairness(公平性)Optimality(最优性)Efficiency(高效性)PerformanceCriteriaUsedforselectionofrouteMinimumhop(跳数,途径结点的数量)LeastcostSeeStallingsappendix10AforroutingalgorithmsExamplePacketSwitchedNetworkDecisionTimeandPlaceTimePacketorvirtualcircuitbasisPlacePlace(referstowhcichnodeornodesinthenetworkareresponsiblefortheroutingdecsion,是指应该由哪一个或者哪一些结点来负责路由选择的判决)DistributedMadebyeachnodeCentralizedSourceNetworkInformationSourceandUpdateTiming(网络信息资源和更新定时)Routingdecisionsusuallybasedonknowledgeofnetwork((notalways,大多数情况下,路由会要网络的拓扑结构、通信负荷量和链路费用等信息))Distributedrouting(分布式路由)NodesuselocalknowledgeMaycollectinfofromadjacentnodesMaycollectinfofromallnodesonapotentialrouteCentralrouting(集中式路由)CollectinfofromallnodesUpdatetiming(更新定时)WhenisnetworkinfoheldbynodesupdatedFixed-neverupdatedAdaptive-regularupdatesRoutingStrategiesFixed(固定式)Flooding(洪泛式)Random(随机式)Adaptive(自适应式)FixedRoutingSinglepermanentrouteforeachsourcetodestinationpairDetermineroutesusingaleastcostalgorithm(appendix10A)Routefixed,atleastuntilachangeinnetworktopologyFixedRouting
TablesFlooding(洪泛式路由)NonetworkinforequiredPacketsentbynodetoeveryneighborIncomingpacketsretransmitted(中转)oneverylinkexceptincominglinkEventuallyanumberofcopieswillarriveatdestinationEachpacketisuniquelynumberedsoduplicatescanbediscardedNodescanrememberpacketsalreadyforwardedtokeepnetworkloadinboundsCanincludeahopcountinpacketsFlooding
ExampleAnExampleApacketistobesentfromnode1tonode6andisassignedahopcountof3TheFirsthop,3copiesarecreatedTheSecondhop,9copiesarecreatedTheThirdhop,22copiesarecreatedPropertiesofFloodingAllpossibleroutesaretriedVeryrobustAtleastonepacketwillhavetakenminimumhopcountrouteCanbeusedtosetupvirtualcircuitAllnodesarevisitedUsefultodistributeinformation(e.g.routing)RandomRoutingNodeselectsoneoutgoingpathforretransmissionofincomingpacketSelectioncanberandomorroundrobinCanselectoutgoingpathbasedonprobabilitycalculationNonetworkinfoneededRouteistypicallynotleastcostnorminimumhopAdaptiveRoutingUsedbyalmostallpacketswitchingnetworksRoutingdecisions(判决)changeasconditionsonthenetworkchangeFailureCongestion(拥挤)RequiresinfoaboutnetworkDecisionsmorecomplexTradeoff(权衡)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(相关性)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结束条件: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结束条件:表格中最后两行的值相同,不再变化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. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2024至2030年中国微电流放大器数据监测研究报告
- 2011-2015年太子参行业市场研究与竞争力分析报告
- 2024至2030年中国客车有无人标示锁数据监测研究报告
- 2024至2030年中国全铜升降式防臭地漏行业投资前景及策略咨询研究报告
- 自然科学如何撰写和发表高水平的科研论文
- 2024年中国木醋液市场调查研究报告
- 2024年中国冰箱用石英管加热器市场调查研究报告
- 高中语文摹形传神千载如生第13课滑稽列传课件苏教版选修史记蚜
- 理发美容店租赁合同三篇
- 轮胎市场开发与步骤
- 2023年05月北京师范大学基础教育发展管理部招聘笔试题库含答案详解
- 外刊阅读-英语资料
- 胎心监护(妇产科)-课件
- 2023版押品考试题库必考点含答案
- book3-unit5公开课一等奖市赛课一等奖课件
- 2000-2023年全国中学生生物学联赛试题和答案解析(生物化学部分)
- 数理统计(第三版)课后习题答案
- 世界读书日知识竞赛参考题库250题(含答案)
- 急性颅脑损伤急诊科诊治流程-
- 【市场营销(互联网营销)专业案例分析报告1700字】
- 高等工程数学知到章节答案智慧树2023年南京理工大学
评论
0/150
提交评论