计算机网络•自顶向下方法：路由选路算法

路由选路算法

在网络层中，选路是指数据包从源主机到目的主机的传输过程中，如何通过网络中的路由器选择一条合适的路径。路由器根据网络拓扑、路由表、协议规则等来决定如何将数据包转发到下一跳，直到数据包到达目的地。

在这里插入图片描述

选路算法分类

静态算法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)$ 是x 的邻居集合， $c (x, p)$ 为 x 到其邻居 p 的链路代价， $d_x(y)$ 为从 x 到 y 的最小代价路径的代价，则：
$d_x(y) = min_p\{{c(x,p) + d_p(y)}\}，p∈N(x) \\（Bellman-Ford方程）$
在这里插入图片描述

距离矢量（DV）算法

距离矢量算法：

利用Bellman-Ford方程求解任意两个节点之间的最小代价路径
主要贡献在于给出了分布式求解B-F方程的方法

算法的基本思想：

节点 x 测量其到各个邻居 v 的链路代价 $c (x, v)$
节点x 估计其到达各个节点 y 的最小代价 $D_x(y)$ ，这些代价构成了自己的距离矢量 $D_x = [D_x(y): y є N ]$
每个节点x周期性地将它的距离矢量 $D_x$ 发送给邻居
节点x拥有每个邻居v的距离矢量 $D_v = [D_v(y): y є N ]$
当节点 x 从各个邻居收到它们的距离矢量后，利用B-F方程更新自己的距离矢量： $D_x(y) ← min_v\{{c(x,v) +D_v(y)}\}$

距离矢量算法是迭代的、异步的、分布式算法。

RIP（Routing Information Protocol） 是最经典的基于 DV 算法的路由协议

特点

好消息传播快
- 当网络中某个链路代价变小时（例如，某条路径变得更短），节点通过距离矢量算法会迅速更新其路由表并通知邻居。由于每个节点都倾向于采用代价较小的路径，因此这个变化会以最快的方式沿着网络传播。
- 原因：
  - Bellman-Ford 方程： $D_x(y)←min_v\{{c(x,v)+D_v(y)}\}$ 当某个链路代价 $c (x, v)$ 减小时，所有受影响的节点会立刻采用新的较小代价进行更新。
  - 好消息无需额外验证，只需要简单比较，符合 Bellman-Ford 方程即可更新。
坏消息传播慢
- 当网络中某条链路断开或代价增加时，坏消息在距离矢量算法中传播较慢。这是因为距离矢量算法可能导致路由环路
- 原因：
  - 节点在某些情况下无法立即获知链路断开的信息，会继续通过其邻居获取过时的距离矢量，误以为存在有效路径。
  - 更新代价遵循 Bellman-Ford 方程，但算法本身无法快速检测到全局无效路径的存在。

解决方法

水平分割（Split Horizon）：禁止节点将自己学到的信息传播回原来的来源。
毒性逆转（Poisoned Reverse）：若节点通过某个路径获知目标，则将该路径的代价设置为无穷大并通知邻居。

LS算法和DV算法的对比

通信复杂度

链路状态（LS）算法：
- 链路状态信息需要在整个网络中传播
- 每个节点向所有其他节点发送链路状态信息，通信复杂度较高
- 传播范围：全网
距离矢量（DV）算法：
- 距离矢量信息只需要发送给直接邻居。
- 每个节点仅与其邻居交换信息，通信复杂度相对较低
- 传播范围：仅邻居

收敛速度

链路状态（LS）算法：
- 收敛速度快，所有节点在全网链路状态信息收集完毕后，利用 Dijkstra 算法进行路由计算
- 收敛速度大致为 $O (∣ N ∣∣ E ∣)$ 个报文发送，主要取决于网络拓扑规模
距离矢量（DV）算法：
- 收敛速度差异大，特别是在网络发生变化时，可能出现“坏消息传播慢”的现象
- 可能出现路由环路，例如“计数到无穷问题”，导致收敛时间不确定

计算复杂度

链路状态（LS）算法：
- 在链路状态收集完毕后，每个节点独立运行 Dijkstra 算法，计算复杂度为 $O(|N|^2)$
- 适用于规模较小的网络，但对于大型网络计算代价会较高
距离矢量（DV）算法：
- 计算复杂度较低，每个节点仅需简单地利用 Bellman-Ford 方程更新路由表
- 计算复杂度大致为 $\cdot |V|)$ ，其中 $∣ V ∣$ 是直接邻居数

健壮性

链路状态（LS）算法：
- 每个节点仅传播自己测量的本地链路代价，这些信息可靠且不会传播计算错误
- 节点独立计算路由，不依赖邻居的路由信息
- 优点：错误不会扩散
距离矢量（DV）算法：
- 节点依赖邻居的距离矢量进行路由计算，邻居的距离矢量可能包含错误信息（“道听途说”）
- 节点计算的路由信息需要传播给邻居，错误可能扩散
  靠且不会传播计算错误
- 节点独立计算路由，不依赖邻居的路由信息
- 优点：错误不会扩散
距离矢量（DV）算法：
- 节点依赖邻居的距离矢量进行路由计算，邻居的距离矢量可能包含错误信息（“道听途说”）
- 节点计算的路由信息需要传播给邻居，错误可能扩散
- 缺点：网络中的故障可能导致错误快速传播并引发路由环路