计算机网络——网络层：控制平面

概述

在本文中，我们将研究网络层的控制平面：即路由器如何决定其转发表。 我们知道，计算转发表的方式主要有两种，即让路由器自发决定和通过逻辑集中式控制器计算。 前者需要路由器和其他网络中的路由通信以计算转发表，这是由路由器的控制平面通过OSPF和BGP等路由选择算法完成的，且已经在互联网上使用许久了。 后者需要路由器和逻辑集中式路由选择控制器通信，控制器通过某些协议和数据平面的控制代理（Control Agent）通信，然后由CA配置和管理转发表，这意味着路由器本身不具有控制平面的功能，而是完全交由服务器控制。 这种控制方法还允许转发表进行复杂的动作，正如前文末尾所述。 SDN就是采用的后者的控制逻辑，而且已经在ISP中得到广泛使用。

路由表与转发表

在这里，我们有必要区分一下路由表（Routing Info Base，RIB）和转发表，它们共享相同的信息，但是作用的平面不同。

在上一章中，我们说到，路由器在数据平面使用转发表决定把对应的IP地址转发到哪个物理接口。 这一章，我们将讨论如何计算控制平面的路由表。 路由表保存的是对每个前缀，使用哪个IP地址进行转发，每个IP地址对应一个出口链路； 而转发表保存的是对每个前缀，使用哪个出口链路进行转发，这里使用的是出口链路的物理标号。

路由表还包括一些额外的信息，比如：下一跳的IP地址（网关）和到下一跳的距离（跃点数）¹，这些信息供路由选择协议使用。 本章介绍的内容包括两个方面，这两个方面都是路由选择协议的组成部分：

1. 不同路由器的控制平面如何交互并填充路由表（路由通告）；
2. 路由器的控制平面如何通过路由表计算转发表（路由选择）。

值得注意的是，尽管本章主要讲解路由器如何获得路由表，实际上每台主机内部也有自己的路由表。 这种路由表是必要的，首先，主机也需要知道哪些IP地址对应同一子网的，哪些IP地址不在子网中，与不在子网中的端点通讯时需要哪个网关的协调； 其次，现在的许多主机往往具有多个接口，例如有线网（以太网）、WiFi和蓝牙，主机需要选择使用哪一个接口进行发送。

你可以使用route print（Windows）或ip route list（Linux）检查当前计算机的路由表。 通常这个表含有最重要的两条信息（以Windows为例）：

网络目标        网络掩码          网关       接口   跃点数
          0.0.0.0          0.0.0.0      192.168.0.1     192.168.0.2     1
      192.168.0.0    255.255.255.0            在链路上      192.168.0.2    1

这表示将同一子网内的地址直接发送到对应主机（在链路上），然后把其他地址发送给路由器（网关）。

路由选择算法

在本节中，我们将概述路由选择算法，并介绍两种最简单的算法以明确其思想。 在之后的章节中，我们还将介绍两个实际使用在互联网中的算法：OSPF与BGP。

我们使用无向图$G = (V,E)$来代表网络，其中$V$是顶点（Vertex，也称节点，Node）集合，而$E$是边集合。 图中的顶点表示路由器，而边表示一条物理链路，因此我们假设这个图没有重边与自环。 这个无向图是带有边权的，用来表示开销，这个值可能表示链路的物理长度、金钱开销或速度。 我们用$c(x,y),\, x,y \in V$来表示两个点之间的边的权值或耗费。 特别地，如果两个顶点之间没有边，那么规定$c(x,y) = \infty$； 同时规定$c(x,x) = 0$。 若两个顶点之间存在一条边，那么我们称这两个点为邻居（Neighbor）。

我们规定路径（Path）为一个顶点的有限有序序列$(x_1,x_2,\cdots,x_p)$，其中任意两个相邻的顶点都是邻居，即$(x_i,x_{i+1}) \in E$。 我们称节点$x_1$为起点，$x_p$为终点。 我们额外规定路径必须是简单的，即其顶点序列中不含有重复的顶点。 路径的权值就是其所有边的权值的总和。 对于联通的图，任意两点之间必然存在路径，而这些路径中权值最短者就是最短路径。

路由选择算法就是要求在这样的一张图上选择出给定起点和终点之间的一条路径，当然，我们希望路径的耗费越短越好。

总的来说，路由选择算法有三种分类方式：

1. 集中式和分散式：
   1. 集中式路由选择算法使用完整的、全局性的信息计算从源到目的地之间的最短路径，这种算法可以在路由器的路由选择处理器中执行，也可以在某个集中的设备上进行。这种算法也叫链路状态（Link State，LS）算法。
   2. 分散式路由选择算法以迭代、分布式的方法计算最短路径。单个路由器并不具有整个网络的状态信息，相对地，仅仅需要其邻居的信息即可工作。最常见的分散式算法为距离向量（Distance Vector，DV）算法。
2. 静态和动态： 静态路由选择算法计算出的结果，即路由，随时间的变化较慢，通常仅由人工进行调整； 而动态路由选择算法在进行路由时会因网络的流量负载或拓扑变化而快速做出反应。
3. 负载敏感与负载迟钝： 负载敏感算法中的链路开销会考虑到底层链路的拥塞水平，从而趋向于避开拥塞的链路； 负载迟钝算法中的链路开销不会动态考虑链路的拥塞水平。 早期互联网采用负载敏感算法，但是产生了许多问题，因此当前流行的算法都是负载迟钝的。

链路状态算法

链路状态算法有许多，此处我们介绍最常见的Dijkstra算法。

在链路状态算法之中，路由选择处理器必须知晓网络拓扑和所有链路开销。 实践中，这通常是通过让每个节点向网络中其他所有节点广播自己的状态分组来完成的，这种算法称为链路状态广播算法。 之后我们要研究的OSPF就是基于这种算法。

简单回忆一下未加任何优化的Dijkstra算法：

记N'表示已发现最短路的顶点集合
将起点u加入N'
初始化从起点到所有顶点v的距离D(v)为c(u,v)

重复：
    寻找不在N'中且D(v)最小的节点w
    将w加入N'中
    对w的每个邻居v：
        若 D(w) + c(w,v) < D(v)：
            D(v) = D(w) + c(w,v)
            将到达v的最短路径的前驱结点更新为w
直到 N' = N

这个算法的时间复杂度为$\mathcal{O}(n^2)$。

路由振荡

这个算法虽好，但在拥塞敏感的路由选择情况下会发生路由震荡。 我们假设如果一条链路出现拥塞，那么将其边权增加以反应耗费的增加。

现在，假设路由选择算法选择了两个节点之间的最短路，然后把分组通过这条路径路由。 如果大量的分组通过这条路径，就会导致拥塞，从而耗费增加。 当增加耗费达到一定程度后，这条路径就不再是最短路了，从而算法会选择其他路径路由。 但是，选择其他路径后，这条链路上的负载就下降了，因此它又可能变回最短路。

任何拥塞敏感或基于时延的路由算法都可能遭遇这个问题。 尽管固定边权就不会发生这种振荡，但这对于拥塞敏感算法是不可能的，因为没有其他办法可以绕开拥塞链路。 为此，另一种解决方案是避免让所有路由器同时运行LS算法，这样可以让不同的路由器选择不同的路径，从而避免大规模的路由振荡。 有趣的是，因特网上的路由器具有一定的自同步特性，即尽管起始时间不同，相同周期的算法执行会自发的变成同一时间执行。 通过让发送链路通告的时间随机化可以解决这个问题。

距离向量算法

距离向量算法本质上是分布式的Bellman-Ford算法，基于经典的Bellman-Ford方程： \(d_x(y) = \min_{c(x,v) < \infty}\left( c(x,v) + d_v(y) \right)\) 即从$x$到$y$的最短距离等于从$x$到其邻居$v$的距离加上从$v$到$y$的最短距离的最小值。

这个方程不仅给出了计算最短路的方法，还给出了从$x$到$y$的最短路在起点处的后继，换句话说就是给出了转发表的表项。 \(\text{令} v^* = \arg \min_{c(x,v) < \infty}\left( c(x,v) + d_v(y) \right) \text{，那么，} v^* \text{就是最短路在} x \text{处的后继}\)

接下来我们将介绍距离向量（Distance Vector，DV）算法，就是基于这个方程的。 这个算法需要每个节点$x$保存以下三种信息：

1. 到每个邻居所需的划分$c(x,v)$；
2. 该节点自己的距离向量$\vec{D}_x = \left[ D_x(y), y \in V \right]$；
3. 每个邻居的距离向量$\vec{D}_v$。

距离向量就是某个节点到所有其他节点的最短距离的估计值，可以证明使用DV算法可使这个估计值收敛至准确值。 节点自己的距离距离向量用来保存结果并向其他节点转发； 每个邻居的距离向量是从其邻居处接收的，用于计算自己的距离向量。

算法的工作流程非常简单： 每个节点定时向其邻居发送自己的距离向量； 每个节点收到邻居的距离向量时，检查其是否和保存的副本不同，如果不同则根据Bellman-Ford方程重新计算自己的距离向量； 如果节点在计算距离向量后发现自己的距离向量也更新了，那么它也向其邻居发送新的距离向量。

这个算法的伪代码如下：

将自己的距离向量初始化为c(x,y)，若y不是邻居则值为正无穷
将邻居的距离向量初始化为无穷大
向每个邻居v发送自己的距离向量Dx

永远重复：
    等待 收到邻居的距离向量或发现到邻居的链路权值变化

    对每个结点y：
        对x的每个邻居v：
            Dx(y) = min(c(x,v) + Dv(y), Dx(y))
    
    若Dx(y)发生变化：
        向每个邻居v发送Dx

无穷计数与毒性逆转

现在让我们考虑边权的动态变化。 假设现在有三台路由器$x, y, z$构成的网络，其中x - y、y - z和x - z的边权分别为4、1、50。 我们此后仅考虑计算从y到x的最短路，忽略x路由器上运行的算法，并假设边权变化之前已经完成了DV算法。

假设x - y的边权变为1，那么会依次发生以下事件：

1. y检测到边权变化，更新自己的距离向量并发送之；
2. z收到y更新的距离向量，因此也更新自己的距离向量，即$D_z(x)$变为2；
3. y收到z更新的距离向量，但自己的距离向量不再更新，因此不再发送距离向量。

不难发现边权的减少非常容易在网络之中传播。

现在假设x - y的边权变为60，此时从y到x的最短路变为y - z - x。 此时会发生大量的事件：

1. y检测到边权变化，$D_y(x)$ 现在变为 $c(y,z)+D_z(x) = 1+5 = 6$，然后发送其距离向量；
   • 值得注意的是，现在出现了路由环路，即y将分组路由至z，而z将仍分组路由至y。
2. z收到更新的距离向量，然后更新自己的距离向量，现在$D_z(x) = c(z,y)+D_y(x) = 1+6 = 7$，然后发送距离向量……

这个过程将不断重复，直到最终算出距离大约50为止。 显然这将浪费大量的时间，尤其是在更新前的次短链路非常长，而增量又非常小的情况。 这种问题被称为无穷计数（Count-to-infinity，数到无穷大）问题。

我们可以通过引入毒性逆转（Poisoned reverse）来缓解这个问题。 其思想相当简单：如果z选择通过y路由到x，那么在广播的距离向量中，其将设$D_z(x) = \infty$。

在最多只经过两个结点的无穷计数问题中，在第一步时，由于y选择路由至z，因此其将通报$D_y(x) = \infty$。 然后当z接收到这个通报后，因为从y到x的距离为无穷大（被毒化了），就不会选择将分组路由至y了。

如果环路涉及三个或更多结点，那么这个算法就不起作用了。

总结

我们从以下三个方面总结这两个算法：

1. 报文复杂性：LS要求每个结点知道每条链路的状态，因此需要$\mathcal{O}\left(\left| E \right| \left| V \right|\right)$个报文；相对地，DV在每次迭代时才会在邻居之间交换报文。
2. 收敛速度：如果使用未优化的Dijkstra算法，那么LS算法的时间复杂度为$\mathcal{O}\left( \left| V \right|^2 \right)$；相对地，DV算法的收敛速度具有很大的不确定性，且容易遭遇路由回路和无穷计数问题。
3. 健壮性：LS算法使用全局信息，但是只计算自己的路由表，而且计算结果不会相互影响，因此健壮性较好；相对地，DV算法会向整个网络传播错误的计算结果。

1. 实际上记录的是路由权值（Metrics），这一权值通常是由跃点数、时延和带宽等数据综合而成的。 ↩