资源描述：
《《路由协议》ppt课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、RoutingGraphabstractionforroutingalgorithms:graphnodesareroutersgraphedgesarephysicallinkslinkcost:delay,$cost,orcongestionlevelsinglecostGoal:determine“good”path(sequenceofrouters)thrunetworkfromsourcetodest.RoutingprotocolAEDCBF2213112535“good”path:typicallymeansminimu
2、mcostpathotherdef’spossible1NetworkLayerALink-StateRoutingAlgorithmDijkstra’salgorithmnettopology,linkcostsknowntoallnodesaccomplishedvia“linkstatebroadcast”allnodeshavesameinfocomputesleastcostpathsfromonenode(“source”)toallothernodesgivesroutingtableforthatnodeiterativ
3、e:afterkiterations,knowleastcostpathtokdest.’sNotation:c(i,j):linkcostfromnodeitoj.costinfiniteifnotdirectneighborsD(v):currentvalueofcostofpathfromsourcetodest.Vp(v):predecessornodealongpathfromsourcetov,thatisnextvN:setofnodeswhoseleastcostpathdefinitivelyknown2Network
4、LayerDijsktra’sAlgorithm1Initialization:2N={A}3forallnodesv4ifvadjacenttoA5thenD(v)=c(A,v)6elseD(v)=infty78Loop9findwnotinNsuchthatD(w)isaminimum10addwtoN11updateD(v)forallvadjacenttowandnotinN:12D(v)=min(D(v),D(w)+c(w,v))13/*newcosttoviseitheroldcosttovorknown14shortest
5、pathcosttowpluscostfromwtov*/15untilallnodesinN3NetworkLayerDistanceVectorRoutingAlgorithmIterative(重复）:continuesuntilnonodesexchangeinfo.Asynchronous异步:nodesneednotexchangeinfo/iterateinlockstep!Distributed分布:eachnodecommunicatesonlywithdirectly-attachedneighborsDistanc
6、eTabledatastructureeachnodehasitsownrowforeachpossibledestinationcolumnforeachdirectly-attachedneighbortonodeexample:innodeX,fordest.YvianeighborZ:D(Y,Z)XdistancefromXtoY,viaZasnexthopc(X,Z)+min{D(Y,w)}Zw==4NetworkLayerDistanceVectorRouting:overviewIterative,asynchronous
7、:eachlocaliterationcausedby:locallinkcostchangemessagefromneighbor:itsleastcostpathchangefromneighborDistributed:eachnodenotifiesneighborsonlywhenitsleastcostpathtoanydestinationchangesneighborsthennotifytheirneighborsifnecessarywaitfor(changeinlocallinkcostormsgfromneig
8、hbor)recomputedistancetableifleastcostpathtoanydesthaschanged,notifyneighborsEachnode:5NetworkLayerDist
