动态路由算法与拥塞控制

《动态路由算法与拥塞控制》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、主要内容（2）7.1网络层概述7.2路由算法7.2.1最优化原则7.2.2最短路径路由算法7.2.3洪泛算法7.2.4基于流量的路由算法7.2.5距离向量路由算法7.2.6链路状态路由算法7.2.7分层路由7.2.8移动主机的路由7.2路由算法（28）7.2.5距离向量路由算法（DV：DistanceVectorRouting）属于动态路由算法,也称Bellman-Ford路由算法和Ford-Fulkerson算法，最初用于ARPANET，被RIP(RoutingInformationProtocol)协议采用。基本思想每个路由器维护一张表，表中给出了到每个目的地的已知最佳距离和线

2、路，并通过与相邻路由器交换距离信息来更新表；以子网中其它路由器为表的索引，表项包括两部分：到达目的结点的最佳输出线路，和到达目的结点所需时间或距离；7.2路由算法（29）每隔一段时间，路由器向所有邻居结点发送它到每个目的结点的距离表，同时它也接收每个邻居结点发来的距离表；邻居结点X向路由器Y发来的表中，X到路由器Zi的距离为Li，路由器Y到X的距离为m，则路由器Y经过X到Zi的距离为Li+m。根据不同邻居发来的信息，计算Li+m，并取最小值，更新Y路由器的路由表；注意：Y路由器中的老路由表在计算中不被使用ABCDEFGHIJKL路由器ABCDEFGHIJKL012254014231

3、8172192429ABCEDFGHIJKLA2436182772031200112233I2031198301960147229H2128362422403119221009K新估计从J出发的延时J到A的延迟为8J到I的延迟为10J到H的延迟为12J到K的延迟为6J从它的四个邻居路由器上收到的向量J的新路由表A820A28I20H17I30I18H12H10I0—6K15K7.2路由算法（30）无限计算问题算法的缺陷：对好消息反应迅速(好消息：网络上加入一个路由器）对坏消息反应迟钝（坏消息：网络上减少一个路由器）ABCDE初始时1第一次交换后12第二次交换后12

4、3第三次交换后1234第四次交换后对好消息反应迅速ABCDE1234初始时3234第一次交换后3434第二次交换后5454第三次交换后5656第四次交换后7676第五次交换后7878第六次交换后………………对坏消息反应迟钝：引起无穷计算问题7.2路由算法（31）为什么会出现无穷计算问题：因为路由器A通过路由器B才能到达路由器C，虽然路由器A已经下线，C仍然向B报告了以前C到A的距离。解决无穷计算问题的方法：水平分裂算法工作过程与距离向量算法相同，区别在于到X的距离不向真正通向X的邻居结点报告，使得坏消息传播的也快。7.2路由算法（32）ABCDE234第一次交换后3

5、4第二次交换后4第三次交换后第四次交换后123初始时47.2路由算法（33）虽然广泛使用，但有时候会失败。主要内容（2）7.1网络层概述7.2路由算法7.2.1最优化原则7.2.2最短路径路由算法7.2.3洪泛算法7.2.4基于流量的路由算法7.2.5距离向量路由算法7.2.6链路状态路由算法7.2.7分层路由7.2.8移动主机的路由7.2路由算法（34）7.2.6链路状态路由算法（LS：LinkStateRouting）距离向量路由算法的主要问题选择路由时，没有考虑线路带宽；路由收敛速度慢(无穷计算)。7.2路由算法（35）链路状态路由算法发现邻居结点，并学习

6、它们的网络地址；测量到每个邻居结点的延迟或开销；将所有学习到的内容封装成一个包；将这个包发送给所有其它路由器；每个路由器独立计算到其它路由器的最短路径。返回7.2路由算法（36）发现邻居结点，并学习它们的网络地址；路由器启动后，通过发送HELLO包发现邻居结点；两个或多个路由器连在一个LAN时,引入人工结点；7.2路由算法（37）7.2路由算法（38）测量到每个邻居结点的延迟或开销；一种直接的方法是：发送一个要对方立即响应的ECHO包，来回时间除以2即为延迟。7.2路由算法（39）将所有学习到的内容封装成一个包；包以发送方的标识符开头，后面是序号、年龄和一个邻居结点列表；列表中对应

7、每个邻居结点，都有发送方到它们的延迟或开销；链路状态包定期创建或发生重大事件时创建。7.2路由算法（40）7.2路由算法（41）将这个包发送给所有其它路由器；基本思想：洪泛链路状态包，为控制洪泛，每个包包含一个序号，每次发送新包时加1。路由器记录信息对(源路由器，序号)，当一个链路状态包到达时，若是新的，则分发；若是重复的，则丢弃；若序号比路由器记录中的最大序号小，则认为过时而丢弃；7.2路由算法（42）第4步中存在的问题序号循环使用会混淆路由器崩溃；序号出错；7.2