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

路由选路算法

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

选路算法分类

静态算法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 ) = 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)$
• 节点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 ) ← 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)$ 减小时，所有受影响的节点会立刻采用新的较小代价进行更新。
    • 好消息无需额外验证，只需要简单比较，符合 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 方程更新路由表
  • 计算复杂度大致为 $O(|N|\cdot |V|)$，其中 $|V|$ 是直接邻居数

健壮性

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