文档介绍：关于路由算法补充知识
第一张，共四十八张，创建于2022年，星期一
1. 路由算法需要考虑的基本因素
1）路由算法的设计目标
2）选择最佳路由的度量参数
第二张，共四十八张，创建于2022年，星期一
1）路由算法的设计
第十六张，共四十八张，创建于2022年，星期一
距离向量法的计算举例
A
D
E
C
B
7
1
8
2
2
1
计算从E经相邻站点A、B和D到达信宿A、B、C和D的最小代价D (destination,neighbor)
得从E到达信宿的最佳路径（最小代价）路由表
最小代价D (des,nei)
E的路由表
第十七张，共四十八张，创建于2022年，星期一
距离向量路由算法
原路由不经过N但距离大
新路由不一定最优，但，原路由可能故障
原路为无穷大，则取代为经N、长度为C的路由
第十八张，共四十八张，创建于2022年，星期一
D-V网络发现过程剖析
1 1
A
C
B
up
如果网络中的最长路径为N，则算法经过N次迭代计算后收敛。即第N步之后，。
第十九张，共四十八张，创建于2022年，星期一
D-V发现链路断开
1 1
A
C
B
down
C与B之间的对话：
，你能告诉我如何到达信宿吗？
我可以到达信宿，距离为1。（传播了一条过时的错误信息）
既然如此，我选择经过你到达信宿的路径，距离为2。
第二十张，共四十八张，创建于2022年，星期一
距离向量法的收敛性问题及解决办法
问题
逐站传递更新信息，算法的收敛速度慢
有可能出现各站路由信息不一致
后果
在站点间构成更新路由的路径环（Routing Loops）
计数至无穷大（Count to Infinity）
解决办法
定义路径代价的最大值（Maximum）
提高收敛速度
第二十一张，共四十八张，创建于2022年，星期一
1 1
A
C
B
down
路径环（Routing Loop）问题
这条错误的路由信息在C与B之间不断复制和修改，并在网络中传播（殃及A），形成路径传播的环路。
第二十二张，共四十八张，创建于2022年，星期一
1 1
A
C
B
down
严重后果：计数至无穷大
第二十三张，共四十八张，创建于2022年，星期一
1 1
A
C
B
down
（定义Hop最大值为16）
解决办法：定义距离的最大值
收敛！
第二十四张，共四十八张，创建于2022年，星期一
加速收敛的方法
水平分割（Split Horizon）
毒性逆转（Poison Reverse）
保持计时（Hold-Down Timers）
触发更新（Triggered Updates）
加速方法的综合应用举例
第二十五张，共四十八张，创建于2022年，星期一
距离向量算法小结
路径选择采用最短路径准则，计算D信宿(距离，下站)；
每个站点只知道自己和邻居的局部信息，在自己的刷新周期到来时，根据邻居的路由变化重新启动算法；
算法的收敛速度慢（特别是对网络崩溃）造成全网信息的不一致，导致产生路径环，使计数至无穷大；
当路径环产生时，定义距离的最大值可防止算法进入死循环，解决计数至无穷大问题；
各种加速收敛方法的目的在于避免路径环的形成，但不能从根本上杜绝这一现象的发生；
在具体的路由协议中，各种加速收敛方法往往综合使用。
第二十六张，共四十八张，创建于2022年，星期一
4）链路状态（Link-State）算法
L-S算法的基本概念
L-S算法的动态特性
L-S算法的性能分析
L-S算法与 D-V算法的比较
OSPF协议
第二十七张，共四十八张，创建于2022年，星期一
链路状态算法的基本概念
链路状态算法的基本概念
链路状态法的计算举例
Dijkatra算法计算结果
第二十八张，共四十八张，创建于2022年，星期一
每个路由器周期性地收集和发送信息
主动测试其到所有邻居的链接状态（度量值）
向所有的路由器发送（广播）自己拥有的状态信息
得到一个全网的、动态的逻辑链路状态（L-S）图
每个路由器刷新自己的路由表
当L-S变化时，用最短路径优