计算机网络（23）——路由选择算法概述及层次路由_层次路由系统

路由选择算法概述

Internet 网络层的核心功能为路由选择（routing）和转发（forwarding），转发通过路由器索引其转发表决定某分组被指向的链路接口；路由选择算法在路由器中运行、交换和计算信息，这些信息被用于配置转发表。无论网络层提供的是数据报服务（在给定源和目的地址之间的所有分组可能采用不同的路由），还是虚电路服务（在给定源和目的地址之间的所有分组将采用相同路径），网络层都必须为发送方到接收方的分组确定所采用的路径，这就是路由选择的工作。

主机通常直接与一台路由器相连接，该路由器即为该主机的默认路由器（default router），或称为第一跳路由器（first-hop router）。每当主机发送一个分组时，该分组被传送给它的默认路由器。我们将源主机的默认路由器称作源路由器（source router），把目的主机的默认路由器称为目的路由器（destination router）。一个分组从源主机到目的主机的路由选择问题可归结为从源路由器到目的路由器的路由选择问题。

因此，路由选择算法的目的是：给定一组路由器以及连接路由器的链路，路由选择算法要找到一条从源路由器到目的路由器的“好路径”。通常，一条好路径指具有最低代价的路径（实践中还需关心一些其他问题，这也使得概念简单、性能优秀的算法变得复杂），且通常使用图来形式化路由选择问题。

路由选择算法可以根据算法是静态的还是动态的进行分类：

• 静态路由选择算法：手工配置，随着时间流逝，路由的变化是非常缓慢的，且通常优先级较高。
• 动态路由选择算法：能够当网络流量负载或拓扑发生变化时改变路由选择路径。可周期性地运行或直接响应拓扑或链路费用的变化而运行，路由更新快。

还可以根据算法是全局式的还是分散式的来加以区分：

• 全局式路由选择算法：所有路由器掌握完整的网络拓扑和链路费用信息，如链路状态（Link State, LS）路由算法。
• 分散式路由选择算法：路由器只掌握物理相连的邻居以及链路费用，通过邻居间信息交换，以迭代、分布式的方式计算出最低代价路径，如距离向量（Distance Vector, DV）路由算法。

链路状态路由选择算法

在链路状态路由算法中，网络拓扑和所有链路费用都是已知的，实际中这是通过让每个节点向网络中所有其他节点广播链路状态分组来完成的，即链路状态广播。

可以采用 Dijkstra 算法作为链路状态路由算法，该算法可以计算从某节点（源节点，记为 $u$）到网络中所有其他节点的最低费用路径。Dijkstra 算法是迭代算法，其性质是经过 $k$ 次迭代之后，可找到 $k$ 个目的节点的最低路径费用。用计算得到的最短路径信息来配置转发表，到达某个目的节点要走与当前节点相连的那条链路。

距离向量路由选择算法

距离向量（DV）算法是一种迭代的、异步的、分布式的算法，可以采用 Bellman-Ford 算法的思想。同 Dijkstra 算法，这也是一个单源最短路径算法，采用了动态规划的计算方式，令 $d_x(y)$ 表示从 $x$ 到 $y$ 最短路径的费用，$c(x,v)$ 表示 $x$ 到邻居 $v$ 直接链路的费用，则递归方程为：
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)} 该方程也称为 Bellman-Ford 方程，使用该方程可以获得最短路径的下一跳，该信息用于配置转发表；另一个重要实际贡献是它提出了在 DV 算法中发生的邻居到邻居通信的形式。

算法基本思想

用 $D_x(y)$ 表示每个节点 $x$ 对在 $N$ 中的所有节点 $y$ 最短路径的费用的估计；令 ${\text{D}}_x=[D_x(y),y\in N]$ 表示节点 $x$ 的距离向量（DV），该向量是从 $x$ 到网络中所有其他节点 $y$ 的最低费用估计的向量。每个节点 $x$ 维护下列路由选择信息：

① 对于每个直接相连邻居 $v$，从 $x$ 到 $v$ 的链路费用 $c(x,v)$。
② 节点 $x$ 自身的距离向量，即 ${\text{D}}_x=[D_x(y),y\in N]$，包含了 $x$ 到 $N$ 中所有目的地 $y$ 的费用的估计值。
③ 它的每个邻居的距离向量，即对 $x$ 的每个邻居 $v$，有 ${\text{D}}_v=[D_v(y),y\in N]$。

由于局部链路费用改变或收到来自邻居的 DV 更新，某节点的 DV 估计可能会发生变化，将新的 DV 估计发送给其邻居；当 $x$ 接收到邻居的新的 DV 估计时，即依据 B-F 方程更新其自身的距离向量估计：
D x ( y ) ← m i n v { c ( x , v ) + D v ( y ) } ,   f o r   e a c h   n o d e   y ∈ N D_x(y)\leftarrow min_v\{c(x,v) + D_v(y)\},\ for\ each\ node\ y\in N Dx​(y)←minv​{c(x,v)+Dv​(y)}, for each node y∈N如果节点 $x$ 的距离向量因这个更新步骤而改变，节点 $x$ 接下来将向它的每个邻居发送其更新后的距离向量。只要所有的节点继续以异步方式交换它们的距离向量，每个费用估计 $D_x(y)$ 将最终收敛于实际的最小费用 $d_x(y)$。

上面的算法基本思想体现出该算法是一个异步迭代、分布式的算法，每个节点所要执行的动作可总结如下：

无穷计数问题

当一个运行 DV 算法的节点检测到从它自己到邻居的链路费用发生变化时，它就更新其距离向量，并且如果某最低费用路径的费用发生了变化，向邻居通知其新的距离向量。当链路费用减小时，DV 算法只需要少数轮迭代就可以达到静止状态。即“好消息传播快”。

现在考虑一下当某链路费用增加时发生的情况。如上图所示，$x$ 与 $y$ 之间的链路费用从 4 增加到 60：

1. 在链路费用变化之前，$D_y(x)=4,D_y(z)=1$ 和 $D_z(y)=1,D_z(x)=5$。在 $t_0$ 时刻，$y$ 检测到链路费用变化（4 变为 60），$y$ 计算其到 $x$ 的新的最低费用路径的费用值为
   D y ( x ) = m i n { c ( y , x ) , c ( y , z ) + D z ( x ) } = m i n { 60 , 1 + 5 } = 6 D_y(x)=min\{c(y,x), c(y,z)+D_z(x)\}=min\{60,1+5\}=6 Dy​(x)=min{c(y,x),c(y,z)+Dz​(x)}=min{60,1+5}=6 当然，从网络全局的视角能够看出经过 $z$ 的这个新费用是错误的，但节点 $y$ 仅有的信息是：它到 $x$ 的直接链路费用为 60，且 $z$ 上次已经告诉 $y$，$z$ 能以费用 $5$ 到 $x$。
2. 因为节点 $y$ 的距离向量发生了改变，它在 $t_1$ 时刻将该距离向量通知 $z$。$z$ 收到了 $y$ 的新距离向量，它指示了 $y$ 到 $x$ 的新最低费用是 6，因此计算出到 $x$ 的最低费用 D z ( x ) = m i n { 50 , 1 + 6 } = 7 D_z(x)=min\{50,1+6\}=7 Dz​(x)=min{50,1+6}=7。
3. 以类似的方式，$z$ 的距离向量发生改变，它需要通知 $y$ 其新费用，如下图所示。直到 $z$ 算出它经由 $y$ 的路径费用大于 50 为止，迭代过程才会停止，即“坏消息传播慢”。该现象也称为无穷计数（count to infinity）问题。
   

消除无穷计数问题的方法有很多，其中包括一种称为毒性逆转（poisoned reverse）的技术，其思想较为简单：如果 $z$ 通过 $y$ 路由选择到目的地 $x$，那么 $z$ 将通告 $y$：$D_z(x)=\infty$，我们现在看一下毒性逆转如何解决无穷计数问题。

1. 当 $c(x,y)$ 链路的费用在 $t_0$ 时刻从 4 变成 60 时，$y$ 更新其表：$D_y(x)=60$（由于 $D_z(x)=\infty$，所以 $y$ 选择直接路由选择到 $x$），并将该更新通知 $z$。
2. $z$ 在 $t_1$ 时刻收到更新后，便立即将其到 $x$ 的路由切换到费用为 50 的直接 $(z,x)$ 链路。因为 $z$ 的距离向量发生了更新，且路径不再经过 $y$，所以 $z$ 通知 $y$：$D_z(x)=50$。
3. $y$ 在 $t_2$ 时刻收到更新后，使用 $D_y(x)=51$ 更新其距离向量，并通知 $z$：$D_y(x)=\infty$ 来毒化从 $z$ 到 $x$ 的逆向路径（毒性逆转）。
   

但是更复杂的网络将无法用毒性逆转技术检测到，还需要一些其他的技术，如定义最大跳步数等。

LS 与 DV 路由选择算法的比较

DV 和 LS 采用互补的方法来解决路由选择计算问题。在 DV 算法中，每个节点仅与它的直接相连的邻居交谈，但它为其邻居提供了从它自己到网络中（它所知道的）所有其他节点的最低费用估计；在 LS 算法中，每个节点（经广播）与所有其他节点交谈，但它仅告诉它们与它直接相连链路的费用。记 $N$ 是节点（路由器）的集合，$E$ 是边（链路）的集合：

• 报文复杂性。LS 算法要求每个节点都知道网络中每条链路的费用，这就要求无论何时一条链路的费用改变时，必须向所有节点发送新的链路费用；而 DV 算法仅当在新的链路费用导致与该链路相连节点的最低费用路径发生改变时，才传播已改变的链路费用。
• 收敛速度。LS 算法采用 Dijkstra 算法的时间复杂度为 $O(|N{|}^2)$（堆优化的话为 $O(|E|log|N|)$）；DV 算法收敛较慢，且在收敛时还会遭遇无穷计数的问题。
• 健壮性。在 LS 算法下，路由计算在某种程度上是分离的，提供了一定程度的健壮性；而在 DV 算法中，一个不正确的节点计算值会扩散到整个网络。

层次路由

在前面介绍的 LS 和 DV 算法的研究中，都将网络抽象为一张图。但是将任意规模的网络抽象为一个图来计算路由过于理想化，因为至少有以下两个重要原因：

• 网络规模：随着路由器数目变得很大，涉及路由选择信息的计算、存储及通信的开销将高的不可实现。在公共因特网上的所有路由器中广播 LS 更新所需的开销将导致没有剩余的带宽来发送数据分组；在如此大量的路由器中迭代的 DV 算法讲课顶永远无法收敛。显然必须采取一些措施以减少公共因特网这种大网络中的路由计算的复杂性。
• 管理自治：每个网络的管理可能都期望自主控制其网内的路由，或对外隐藏其网络的内部组织面貌。在理想情况下，一个组织应当能够按自己的愿望运行和管理其网络，还要能将其网络与其他外部网络相连接。

这些问题都可以通过将路由器聚合为自治系统（Autonomous System, AS）来解决，每个 AS 由一组通常处在相同管理控制下的路由器组成（例如，由相同的 ISP 运营或属于相同的公司网络）。在相同的 AS 中的路由器全都运行同样的路由选择算法（如一种 LS 或 DV 算法），称为自治系统内部路由协议（intra-autonomous system routing protocol），不同自治系统内的路由器可以运行不同的 AS 内部路由协议。当然，将 AS 彼此互联是必须的，因此在一个 AS 内的一台或多台路由器负责向在本 AS 外的目的地转发分组，这些路由器被称为网关路由器（gateway router），它们通过链路连接其他 AS 的网关路由器。

可以仅通过 AS 内部路由协议为在 AS 内部的源和目的对决定路由选择路径，但是如何将数据分组路由选择到位于其 AS 外部的目的地呢？

• 当源 AS 仅有一条通向外部 AS 的链路时（仅有一台网关路由器），直接将数据分组转发到其网关路由器即可；
• 如果源 AS 具有多条链路通往外部 AS，那么对于一个 AS 来说，它首先需要解决的问题是：从相邻 AS 获取可达性信息和向该 AS 中的路由器传播可达性信息，这正是自治系统间路由选择协议（inter-autonomous system routing protocol）所负责的，此外还需要从多个网关中进行选择，这也是 AS 间路由选择协议的任务。

因为自治系统间路由协议涉及两个 AS 之间的通信，这两个通信的 AS 必须运行相同的自治系统间路由选择协议。事实上，因特网中的所有 AS 中都运行相同的 AS 间路由选择协议，该协议称为 BGP4。如下图中，假设 AS1 内的某路由器收到一个目的地址在 AS1 之外的数据报，那么 AS1 必须知道哪些目的网络可以通过 AS2 到达，哪些可以通过 AS3 到达，且需要向 AS1 中的所有路由器传播这些可达性信息，以配置它们的转发表来处理外部 AS 目的地。

以路由器 1d 为例，看一下它的转发表如何配置。假设 AS1 通过 AS 间路由协议学习到：子网 $x$ 可以通过 AS3（网关 1c）到达，但不能通过 AS2 到达，AS1 则向它的所有路由器传播这个信息。当路由器 1d 知道从 AS3 并因此从网关 1c 可达子网 $x$ 时，根据 AS1 内部路由选择协议提供的信息，确定其到达 1c 的最小费用路径接口 $I$，并将表项 $(x,I)$ 放入其转发表中。

接着上面的例子，假设 AS1 通过 AS 间路由协议学习到：子网 $x$ 通过 AS3 和 AS2 均可到达，AS1 将向它的所有路由器传播该信息。为了配置转发表，路由器 1d 必须确定通过哪个网关路由器来转发目的地址为 $x$ 的数据分组，这个任务也是由 AS 间路由选择协议来完成。在实践中经常使用的一种方法是热土豆路由：将分组发送给最近的网关路由器。下图总结了路由器 1d 对转发表增加用于 $x$ 的表项所采取的动作。