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