路由算法补充知识.ppt

文档介绍：路由算法补充知识
2）静态路由
静态路由的概念
静态路由工作原理
路由配置举例
故障举例（网络拓扑结构变化）
用人工修改配置排除故障
静态路由的概念
由网络管理员设置路由表
简单、有效，适于结构简单的网络
不适于拓扑结构和传择采用最短路径准则，计算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图）中两个结点之间的最短路径
对每结点赋以标注{D(v),NP(v)}
链路状态法的计算举例
F
3
5
5
2
其中
自变量v：无向图中的结点
函数D(v)：到目前为止，从源点到结点v的最短路径（边长之和）
函数NP(v)：沿源点到结点v的最短路径中与V相邻的前一结点
Dijkatra算法计算结果
A
E
D
C
B
2
1
2
1
1
3
源点A到所有结点的最短路径
F
3
5
5
2
D
F
E
A
B
C
1
1
2
1
2
L-S图
SPF树


L-S算法的动态特性
建立路由表的初始过程
发现新的网络
路由表的维护
发现拓扑变化
修改拓扑数据库
计算SPF树
修改路由表
A
C
B




a0 a1 b0 b1 c0 c1
L-S建立路由表的初始过程
A
C
B

L-S网络发现过程剖析

构造包含发现信息的L-S报文(LSP)向全网广播
接收全网的其他路由器发来的L-S报文
根据收集的信息建立拓扑数据库
启动SPF算法以C为源点计算SPF树
建立到达所有信宿的路由表（端口和代价）
c1
LSP

c0
（1）发现拓扑变化
A
E
D
C
B
F

Net X
Net X Down
Net X Down
LSP
LSP
发现网络X不可达
构造LSP
向全网广播
发现网络X不可达
构造LSP
向全网广播
（2）修改拓扑数据库
A
E
D
C
B
F

Net X
全网具有相同的L-S逻辑图。
A
E
D
C
B
F

Net X
（3）各自重新计算SPF树
2
2
3
3
1
1
5
2
5
1
A
E
D
C
B
F

Net X
根据各自计算的SPF树刷新路由表
（4）修改各自的路由表
a0
a1
a2
Net Y
路由表
路由表
路由表
路由表
路由表
2
2
1
L-S算法的性能分析
优点
代价
路由刷新问题
线路传输速率不同
网络运行状态不同
解决办法
L-S算法的优点
所有路由器具有相同的网络拓扑知识（L-S图）
一次性、无修改地向全网广播LSP
路由器根据全局信息维护各自的路由表
保证链路状态信息的单向传播
保证算法的收敛性
L-S算法的代价
SPF算法计算和拓扑数据库需要更多的CPU和内存资源
网络启动时的扩散路由信息（flood）需要