路由算法
# 路由算法
- 路由算法(协议)确定去往目的网络的最佳路径
- 转发表确定在本路由器如何转发分组
# 网络抽象
图
- 路由器被抽象为结点
- 路由器之间有物理链路相连,则抽象为边
图中的权值
- 费用
- 广义上可称为距离
- 费用
关键问题
- 源到目的(如u到z)的最小费用路径是什么
# 路由算法分类
静态路由与动态路由
静态路由
- 手工配置
- 路由更新慢
- 优先级高
动态路由
- 定期更新
- 及时响应链路费用或网络拓扑变化
全局信息 与 分散信息
基于全局信息的路由算法
- 所有路由器掌握完整的网络拓扑和链路费用信息
- 例如:链路状态(LS)路由算法
基于分散信息的路由算法
- 路由器只掌握物理相连的邻居以及链路费用
- 邻居间信息交换、运算的迭代过程
- 例如:距离向量(DV)路由算法
# 链路状态路由算法
Dijkstra
算法
- 所有结点(路由器)掌握网络拓扑和链路费用
- 通过"链路状态广播"
- 所有结点拥有相同信息
- 计算从一个结点("源")到达所有其他结点的最短路径
- 获得该结点的转发表
- 迭代:
k
次迭代后,得到到达k
个目的结点的最短路径
相关符号
c(x,y)
- 结点
x
到结点y
链路费用 - 如果
x
和y
不直接相连,则=∞
- 结点
D(v)
- 从源到目的
v
的当前路径费用值
- 从源到目的
p(v)
- 沿从源到
v
的当前路径,v
的前序结点
- 沿从源到
N’
- 已经找到最小费用路径的结点集合
算法描述
初始化:
N' = {u}
for 所有结点 v
4 if v毗邻u
5 then D(v) = c(u,v)
6 else D(v) = ∞
7
8 Loop
9 找出不在 N’中的w ,满足D(w)最小
10 将w加入N'
11 更新w的所有不在N’中的邻居v的D(v) :
12 D(v) = min( D(v), D(w) + c(w,v) )
13 /*到达v的新费用或者是原先到达v的费用,或者是
14 已知的到达w的最短路径费用加上w到v的费用 */
15 until 所有结点在N’中
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
2
3
4
5
6
7
8
9
10
11
12
13
14
15
- 最短路径树
存在震荡(oscillations)可能
# 距离向量路由算法
Bellman-Ford 方程(动态规划)
- 路由器不需知道整个网络拓扑
- 结点获得最短路径的下一跳, 该信息用于转发表中
算法实现
异步迭代
分布式
计算示例
链路费用变化
- 结点检测本地链路费用变化
- 更新路由信息,重新计算距离向量
- 如果DV改变,通告所有邻居
- 好消息与坏消息
- 对坏消息, 环路中可能存在 "无穷计数" 的问题
- 错误的认为通过
z
到达x
的距离为5
- 会持续震荡, 收敛较慢
- 错误的认为通过
- 对坏消息, 环路中可能存在 "无穷计数" 的问题
无穷计数问题的消除方法
毒性逆转
定义最大度量
- 跳步,在有限的交换过程中达到收敛
# 层次路由
- 聚合路由器为一个区域:自治系统AS(autonomous systems)
- 同一AS内的路由器运行相同的路由协议(算法)
- 自治系统内部路由协议("intra-AS" routing protocol)
- 不同自治系统内的路由器可以运行不同的AS内部路由协议
编辑 (opens new window)