路由选路算法
在网络层中，选路是指数据包从源主机到目的主机的传输过程中，如何通过网络中的路由器选择一条合适的路径。路由器根据网络拓扑、路由表、协议规则等来决定如何将数据包转发到下一跳，直到数据包到达目的地。
选路算法分类
静态算法or 动态算法
- 静态算法：路由随时间不变或缓慢变化 (手工配置)
- 动态算法：路由器根据拓扑及链路代价的变化而自动更新路由
全局算法 or 分布式算法
全局算法：
- 所有路由器具有关于拓扑和链路代价的全部信息
- 集中式计算
分布式算法：
- 路由器仅知道邻居节点以及到邻居节点的链路代价
- 通过与邻居交换信息，进行迭代计算
链路状态（LS）选路算法
链路状态选路算法为全局算法，其基本思想为：每个节点利用可靠方法获得全网拓扑信息，抽象成一个带权拓扑图，计算到各个节点的最短路径
最常见的链路状态路由协议是 OSPF（Open Shortest Path First）
链路状态选路算法包括五个步骤：
- 发现邻居：有链路直接相连的节点为邻居
- 探测链路代价：探测到每个邻居的代价
- 构造链路状态（LS）分组：利用邻居及链路代价信息
- 扩散LS分组：向网络中所有节点发送LS分组
- 计算路由：利用收到的LS分组构造网络拓扑，计算从本节点到其它各个节点的最短路径
一旦路由器有了完整的网络拓扑图，它就可以使用 Dijkstra 最短路径算法 来计算到每个目标的最短路径。
Dijkstra算法
1 Initialization:
2 N’ = {u} // N’为已找到最短路径的节点集合，初始时只有u
3 for all nodes v //标记源节点u到各个节点v的路径代价D(v)
4 if v adjacent to u
5 then D(v) = c(u,v) //c(u,v)为链路(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’ //将找到最短路径的节点加入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 until all nodes in N'
Bellman-Ford 方程
假设 x 和 y 分别为源节点和目的节点，
N
(
x
)
N(x)
N(x)是x 的邻居集合，
c
(
x
,
p
)
c(x,p)
c(x,p)为 x 到其邻居 p 的链路代价，
d
x
(
y
)
d_x(y)
dx(y)为从 x 到 y 的最小代价路径的代价，则：
d
x
(
y
)
=
m
i
n
p
{
c
(
x
,
p
)
+
d
p
(
y
)
}
，
p
∈
N
(
x
)
（
B
e
l
l
m
a
n
−
F
o
r
d
方程）
d_x(y) = min_p\{{c(x,p) + d_p(y)}\}，p∈N(x) \\（Bellman-Ford方程）
dx(y)=minp{c(x,p)+dp(y)}，p∈N(x)（Bellman−Ford方程）
距离矢量（DV）算法
距离矢量算法：
- 利用Bellman-Ford方程求解任意两个节点之间的最小代价路径
- 主要贡献在于给出了分布式求解B-F方程的方法
算法的基本思想：
- 节点 x 测量其到各个邻居 v 的链路代价 c ( x , v ) c(x,v) c(x,v)
- 节点x 估计其到达各个节点 y 的最小代价 D x ( y ) D_x(y) Dx(y)，这些代价构成了自己的距离矢量 D x = [ D x ( y ) : y є N ] D_x = [D_x(y): y є N ] Dx=[Dx(y):yєN]
- 每个节点x周期性地将它的距离矢量 D x D_x Dx发送给邻居
- 节点x拥有每个邻居v的距离矢量 D v = [ D v ( y ) : y є N ] D_v = [D_v(y): y є N ] Dv=[Dv(y):yєN]
- 当节点 x 从各个邻居收到它们的距离矢量后，利用B-F方程更新自己的距离矢量： D x ( y ) ← m i n v { c ( x , v ) + D v ( y ) } D_x(y) ← min_v\{{c(x,v) +D_v(y)}\} Dx(y)←minv{c(x,v)+Dv(y)}
距离矢量算法是迭代的、异步的、分布式算法。
RIP（Routing Information Protocol） 是最经典的基于 DV 算法的路由协议
特点
- 好消息传播快
- 当网络中某个链路代价变小时（例如，某条路径变得更短），节点通过距离矢量算法会迅速更新其路由表并通知邻居。由于每个节点都倾向于采用代价较小的路径，因此这个变化会以最快的方式沿着网络传播。
- 原因：
- Bellman-Ford 方程： D x ( y ) ← m i n v { c ( x , v ) + D v ( y ) } D_x(y)←min_v\{{c(x,v)+D_v(y)}\} Dx(y)←minv{c(x,v)+Dv(y)}当某个链路代价 c ( x , v ) c(x,v) c(x,v) 减小时，所有受影响的节点会立刻采用新的较小代价进行更新。
- 好消息无需额外验证，只需要简单比较，符合 Bellman-Ford 方程即可更新。
- 坏消息传播慢
- 当网络中某条链路断开或代价增加时，坏消息在距离矢量算法中传播较慢。这是因为距离矢量算法可能导致路由环路
- 原因：
- 节点在某些情况下无法立即获知链路断开的信息，会继续通过其邻居获取过时的距离矢量，误以为存在有效路径。
- 更新代价遵循 Bellman-Ford 方程，但算法本身无法快速检测到全局无效路径的存在。
解决方法
- 水平分割（Split Horizon）：禁止节点将自己学到的信息传播回原来的来源。
- 毒性逆转（Poisoned Reverse）：若节点通过某个路径获知目标，则将该路径的代价设置为无穷大并通知邻居。
LS算法和DV算法的对比
通信复杂度
- 链路状态（LS）算法：
- 链路状态信息需要在整个网络中传播
- 每个节点向所有其他节点发送链路状态信息，通信复杂度较高
- 传播范围：全网
- 距离矢量（DV）算法：
- 距离矢量信息只需要发送给直接邻居。
- 每个节点仅与其邻居交换信息，通信复杂度相对较低
- 传播范围：仅邻居
收敛速度
- 链路状态（LS）算法：
- 收敛速度快，所有节点在全网链路状态信息收集完毕后，利用 Dijkstra 算法进行路由计算
- 收敛速度大致为 O ( ∣ N ∣ ∣ E ∣ ) O(|N||E|) O(∣N∣∣E∣) 个报文发送，主要取决于网络拓扑规模
- 距离矢量（DV）算法：
- 收敛速度差异大，特别是在网络发生变化时，可能出现“坏消息传播慢”的现象
- 可能出现路由环路，例如“计数到无穷问题”，导致收敛时间不确定
计算复杂度
- 链路状态（LS）算法：
- 在链路状态收集完毕后，每个节点独立运行 Dijkstra 算法，计算复杂度为 O ( ∣ N ∣ 2 ) O(|N|^2) O(∣N∣2)
- 适用于规模较小的网络，但对于大型网络计算代价会较高
- 距离矢量（DV）算法：
- 计算复杂度较低，每个节点仅需简单地利用 Bellman-Ford 方程更新路由表
- 计算复杂度大致为 O ( ∣ N ∣ ⋅ ∣ V ∣ ) O(|N| \cdot |V|) O(∣N∣⋅∣V∣)，其中 ∣ V ∣ |V| ∣V∣ 是直接邻居数
健壮性
- 链路状态（LS）算法：
- 每个节点仅传播自己测量的本地链路代价，这些信息可靠且不会传播计算错误
- 节点独立计算路由，不依赖邻居的路由信息
- 优点：错误不会扩散
- 距离矢量（DV）算法：
- 节点依赖邻居的距离矢量进行路由计算，邻居的距离矢量可能包含错误信息（“道听途说”）
- 节点计算的路由信息需要传播给邻居，错误可能扩散
靠且不会传播计算错误 - 节点独立计算路由，不依赖邻居的路由信息
- 优点：错误不会扩散
- 距离矢量（DV）算法：
- 节点依赖邻居的距离矢量进行路由计算，邻居的距离矢量可能包含错误信息（“道听途说”）
- 节点计算的路由信息需要传播给邻居，错误可能扩散
- 缺点：网络中的故障可能导致错误快速传播并引发路由环路