《计算机通信网 》第5章 网络层part2

《《计算机通信网 》第5章 网络层part2》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、5.3.4几种动态路由算法动态路由算法根据网络动态变化计算路由，形成路由表路由表自动形成并根据拓扑变化自动更新适应于网拓扑变化的网络、大网如广域网、互联网涉及的问题节点之间交换路由信息快速适应拓扑变化感知拓扑变化快速传递变化信息快速形成新的稳定的路由（无环路、不震荡，快速收敛）★5.3.4几种动态路由算法中心路由算法逆向学习法分布式路由算法（重点）距离矢量法链路状态法中心路由算法（集中路由）原理各个节点定期将本节点的信道及相邻节点信息报告给中心路由计算机由中心路由计算机计算出各节点到其他节点的最佳路由，然后分配到各个节点特点理论上讲可以得到全网最优路由（因算法考虑了流量、节点等

2、全网信息）但实现困难，很难在大网中使用，适应于小网，原因有三：信息上传困难（各节点定期上传信息会造成中心路由计算机附近节点及线路的拥塞）同步困难（节点很多，中心反馈新路由时，各节点接收时间不同，可能会导致同一网里有的节点使用新路由，有的使用老路由）路由更新过时（可能会出现路由更新到达时，节点情况已变）21345中心路由计算机★逆向（反向）学习法原理根据接收分组中的源地址和接收端口号，形成转发表，以便下次作为目的节点时的转发路径特点能动态适应新节点的加入对线路故障、节点损坏反应迟钝适应拓扑结构相对稳定、小网目标节点端口距离………………AnDnCA收到从A送来的分组路由表中记录从该

3、接口可以到达A★分布式动态路由算法基本原理节点之间需相互交换路由信息节点单独计算路由基本特点局部最优，全局不一定最优相互交换信息越具体、越频繁，路由优化越好，但造成的额外开销也越大。需要在额外开销和路由更新的频率之间进行折中优点动态反映网络变化，路由表自动形成与更新（不需人工干预）局部最优，路由开销少缺点局部最优路由，不是全局最优路由可能出现不一致（矛盾）的路由可能出现路由震荡（路由表变化太快）可能出现路由发散（不能收敛）★分布式路由算法要点交换路由信息：分布式计算：节点根据交换的路由信息，采用最优路由计算方法计算最佳路由哪些信息？与谁交换？边交换信息边计算可达、距离、费用、负

4、载、延时……与邻居、与所有节点何时交换？定时、拓扑变化时★两种典型的分布式路由算法基于网络距离的分布式路由算法---矢量距离法基于信道状态的分布式路由算法---链路状态法矢量距离法（V-D：VectorDistance）根据协议的设计者命名，也称为Bellman-Ford路由算法Ford-Fulkerson路由算法基本思想每个节点都保持一张到其他节点的路由表（目的节点，下一节点，距离）“距离”的度量标准可以是跳数或时延等邻居之间交换路由信息（目的节点，距离）根据收到相邻节点的信息，判断并决定是否更新路由算法涉及的内容初始的路由表如何建立？邻居交换哪些信息?如何根据邻居信息计算并

5、更新自己的路由表？★矢量距离法算法的几个步骤初始化建立初始路由表扩散向邻居扩散自己的路由表信息计算根据收到相邻节点的信息，计算最短路径，更新路由表再扩散、再计算这样就逐渐形成了全网的拓扑结构使每个节点都计算出了到其他节点的路径信息值得注意的是：何时向邻居扩散路由信息？定期拓扑发生变化时★距离矢量算法1）初始路由表建立（目的节点，下一节点，距离）=（V0，G0，D0）2）路由表向邻居扩散21345611211111146532133311224444655注意：度量值可以是节点跳数、时延等度量参数★距离矢量算法各节点的初始路由表：直接相连节点的路由信息21345611111111

6、2目的节点下一节点距离221331目的节点下一节点距离111331441目的节点下一节点距离442551目的节点下一节点距离331441661目的节点下一节点距离111221441551目的节点下一节点距离221331551662★距离矢量算法3）节点计算并更新本节点的路由表相邻节点定期交换信息（目的节点，距离）=（V，D）当某节点A收到相邻节点j的信息（Vx，DjX）时（Vx表示目的地为X节点，Djx为j到X节点的距离）A节点更新情况如下：如A路由表中无此项，则添加表项（Vx，j，D0+DXj）（D0为A与邻居j的距离）如A路由表中有Vx项，（Vx，k，DAx）若k≠jDAx

7、>D0+Djx，则表项更新为（Vx，j，D0+DjX）（新、短路径）DAx≦D0+Djx，则此表项保持不变若k=j无论DAx大小如何，都应更新为（Vx，j，D0+DjX）（原路径可能变化，需更新）★距离矢量算法目的节点下一节点距离221331信息发布者2目的节点距离113141节点1路由表初始值收到节点3路由信息目的节点下一节点距离221331更新后发布者3目的节点距离11214151收到节点2路由信息目的节点下一节点距离221331422距离更新=到邻居节点的距离+邻居节点到目的节点的距离