计算机网络——网络层学习笔记（中）：路由算法

偏执的太偏执、 2022-05-24 13:00 144阅读 0赞

## 路由选择算法 ##

1、路由算法概述

路由算法（协议）确定去往目的网络的最佳路径

转发表确定在本路由器如何转发分组。

网络抽象：图

图：G=(N,E)

N=路由器集合，E=链路集合

关键问题：源到目的的最小费用路径是什么？

路由算法：寻找最小费用路径的算法。

**2、路由算法分类**

**分类方式一：**

静态路由：手工配置、路由更新慢、优先级高

动态路由：路由更新快（定期更新、及时响应链路费用或网络拓扑变化）

分类方式二：

全局式路由选择算法：所有路由器掌握完整的网络拓扑和链路费用信息。例如链路状态算法（LS，Link State）。

分散式路由选择算法：路由器值掌握物理相连的邻居以及链路费用，邻居间信息交换、运算的迭代过程。例如距离向量算法（DV,Distance-Vector）。

**3、链路状态路由算法**

**Dijkstra算法**

所有结点（路由器）掌握网络拓扑和链路费用。

通过链路状态广播。

所有结点拥有相同信息。

计算从一个结点（源）到达所有其他结点的最短路径。

获得该结点的转发表

迭代：K次迭代后得到到达K个目的结点的最短路径。

符号：

c(x,y) 结点x到y的链路费用，不直接相连为记为无穷大

D(v) 从源到目的v的当前路径费用值

p(v) 沿从源到v的当前路径，v的前序结点

N' 已经找到最小费用路径的结点集合

★算法描述：

1 Initialization:  
2 N' = \{u\}  
3 for all nodes v  
4 if v adjacent to u  
5 then D(v) = c(u,v)  
6 else D(v) = ∞  
7  
8 Loop  
9 find w not in N' such that D(w) is a minimum  
10 add w to N'  
11 update D(v) for all v adjacent to w and not in N' :  
12 **D(v) = min( D(v), D(w) + c(w,v) )**   
13 /\* new cost to v is either old cost to v or known  
14 shortest path cost to w plus cost from w to v \*/

15 until all nodes in N'

★算法复杂性：n个结点

每次迭代需要检测所有不再集合N'中的结点w

n(n+1)/2次比较：O(n2)

更高效的实现：O（nlogn）

★存在问题：震荡（oscillations）

![70][]

数据报可能总是路由不到A，随着TTL减少最终被丢包。通常会使用其他机制也避免震荡现象，比如引入随机延时。

**4、距离向量算法**

**Bellman-Ford方程（动态规划）**

Define  
dx(y) := cost of least-cost path from x to y  
Then  
**dx(y) = min \{c(x,v) + dv(y) \}**  
where min is taken over all neighbors v of x

![70 1][]