第五章 网络层 ： 控制平面

本章中 ， 我们将通过包含网络层的控制平面组件来完成我们的网络层之旅 。 控制平面作为一种网络范围的逻辑， 不仅控制沿着从源主机到目的主机的端到端路径间的路由器如何转发数据报 ，而且控制网络层组件和服务如何配置和管理 。

5.1 概述

网络层是OSI参考模型中的第三层，介于传输层和数据链路层之间，它在数据链路层提供的两个相邻端点之间的数据帧的传送功能上，进一步管理网络中的数据通信，将数据设法从源端经过若干个中间节点传送到目的端，从而向传输层提供最基本的端到端的数据传送服务。主要内容有：虚电路分组交换和数据报分组交换、路由选择算法、阻塞控制方法、X.25协议、综合业务数据网（ISDN）、异步传输模式（ATM）及网际互连原理与实现。【来源：百度百科】

我们通过回顾图 4-2 和图 4-3, 迅速建立起学习网络控制平面的环境 。 在这里， 我们看到了转发表（ 在基于目的地转发的场景中 ） 和流表（ 在通用转发的场景中 ） 是链接网络层的数据平面和控制平面的首要元素 。 我们知道这些表定义了一台路由器的本地数据平面转发行为。 我们看到在通用转发的场景下 ， 所采取的动作 （ 4.4.2 节） 不仅包括转发一个分组到达路由器的每个输出端口 ，而且能够丢弃一个分组 、 复制一个分组和/ 或重写第2 、 3 或 4 层分组首部字段 。 在本章中 ， 我们将学习这些转发表和流表是如何计算 、 维护和安装的 。 在 4.1 节的网络层概述中 ， 我们已经学习了完成这些工作有两种可能的方法 。

• 每路由器控制。 图 5-1 显示了在每台路由器中运行一种路由选择算法的情况 ， 每台路由器中都包含转发和路由选择功能 。 每台路由器有一个路由选择组件 ，用于与其他路由器中的路由选择组件通信 ， 以计算其转发表的值。 这种每路由器控制的方法在因特网中已经使用了几十年 。
• 逻辑集中式控制。 图 5-2 显示了逻辑集中式控制器计算并分发转发表以供每台路由器使用的情况。 如我们在 4.4 节中所见，通用的 “匹配加动作” 抽象允许执行传统的 IP 转发以及其他功能（负载共享、 防火墙功能和 NAT） 的丰富集合 ，而这些功能先前是在单独的中间盒中实现的 。

该控制器经一种定义良好的协议与每台路由器中的一个控制代理 （ CA） 进行交互，以配置和管理该路由器的转发表 。 CA — 般具有最少的功能， 其任务是与控制器通信并且按控制器命令行事。与图 5-1 中的路由选择算法不同 ，这些 CA 既不能直接相互交互 ， 也不能主动参与计算转发表 。 这是每路由器控制和逻辑集中式控制之间的关键差异 。

“ 逻辑集中式 ” 控制意味着就像路由选择控制服务位于单一的集中服务点那样获取它们 ， 即使该服务出于容错和性能扩展性的原因 ， 很可能经由多个服务器实现 。 正如我们将在 5-5 节中所见， SDN 采用了逻辑集中式控制器的概念 ，而这种方法在生产部署中得到了越来越多的应用 。

5.2 路由选择算法

在本节中 ， 我们将学习路由选择算法 （ routing algorithm ） , 其目的是从发送方到接收方的过程中确定一条通过路由器网络的好的路径 （等价于路由） 。 通常 ， 一条好路径指具有最低开销的路径 。 然而我们将看到 ， 实践中现实世界还关心诸如策略之类的问题（例如 ， 有一个规则是 “ 属于组织 Y 的路由器 X 不应转发任何来源于组织 Z 所属网络的分组 ” ） 。 我们注意到无论网络控制平面采用每路由器控制方法 ，还是采用逻辑集中式控制方法 ， 必定总是存在一条定义良好的一连串路由器 ， 使得分组从发送主机到接收主机跨越网络 “ 旅行 ”。 因此 ，计算这些路径的路由选择算法是十分重要的， 是最重要的 10 个十分重要的网络概念之一。

可以用图来形式化描述路由选择问题 。 我们知道图( graph ) $G = (N, E) $是一个 N个节点和 E 条边的集合 ， 其中每条边是取自N的一对节点 。 在网络层路由选择的环境中 ， 图中的节点表示路由器 ，这是做出分组转发决定的点; 连接这些节点的边表示这些路由器之间的物理链路 。 这样一个计算机网络的图抽象显示在图 5-3 中。

如图 5-3 所示， 一条边还有一个值表示它的开销 。 通常 ， 一条边的开销可反映出对应链路的物理长度 （ 例如一条越洋链路的开销可能比一条短途陆地链路的开销高）， 它的链路速度 ， 或与该链路相关的金钱上的开销 。为了我们的目的， 我们只将这些链路开销看成是给定的，而不必操心这些值是如何确定的 。 对于 E 中的任一条边$(x,y)$，我们用 $c(x,y)$ 表示节点$x$和 $y$ 间边的开销 。 如果节点对 $(x,y)$ 不属于 E，则置 $c(x,y)=\infty $ 此外 ， 我们在这里考虑的都是无向图 （ 即图的边没有方向 ）， 因此边$(x,y)$与边 $(y,x)$ 是相同的并且$c(x,y)=c(y,x)$ 然而， 我们将学习的算法能够很容易地扩展到在每个方向有不同开销的有向链路场合。同时 ， 如果$(x,y)$属于 E,，节点$y$也被称为节点$x$的邻居 （ neighbor） 。

在图抽象中为各条边指派了开销后 ，路由选择算法的天然目标是找岀从源到目的地间的最低开销路径 。为了使问题更为精确， 回想在图 $G = （N, E）$ 中的一条路径 （ path） 是一个节点序列 $(x_1,x_2,\cdots,x_p )$，这样每一个对 $(x_1, x_2)，(x_2, x_3)，\cdots，(x_{p-1}, x_p)$是E 中的边 。 路径 $(x_1,x_2,\cdots,x_p )$的开销只是沿着路径所有边的开销的总和 ， 即$c(x_1, x_2)+c(x_2, x_3)+\cdots +c(x_{p-1}, x_p)$。 给定任何两个节点$x$和$y$， 通常在这两个节点之间有许多条路径 ， 每条路径都有一个开销 。 这些路径中的一条或多条是最低开销路径（ least-cost path ） 。因此最低开销路径问题是清楚的： 找出源和目的地之间具有最低开销的一条路 。例如 ， 在图 5-3 中 ， 源节点$u$和目的节点$w$建之间的最低开销路径是 $(u,x,y,w)$， 具有的路径开销是 3 。 注意到若在图中的所有边具有相同的开销， 则最低开销路径也就是最短路径 （ shortest path ） ，即在源和目的地之间的具有最少链路数量的路径 。

作为一个简单练习 ，试找出图 5-3 中从节点 $u$到节点 $z$ 的最低开销路径 ， 并要反映出你是如何算出该路径的 。 如果你像大多数人一样 ，通过考察图 5-3，跟踪几条从$u$到$z$的路由， 你就能找出从$u$到$z$的路径 ， 然后以某种方式来确信你所选择的路径就是所有可能的路径中具有最低开销的路径 。 （ 你考察过从$u$到$z$之间的所有 17 条可能的路径吗 ？ 很可能没有 ！）这种计算就是一种集中式路由选择算法的例子 ， 即路由选择算法在一个位置（ 你的大脑中 ）运行，该位置具有网络的完整信息 。一般而言，路由选择算法的一种分类方式是根据该算法是集中式还是分散式来划分。

• 集中式路由选择算法 （centralized routing algorithm） 用完整的 、全局性的网络知识计算岀从源到目的地之间的最低开销路径 。也就是说，该算法以所有节点之间的连通性及所有链路的开销为输入。 这就要求该算法在真正开始计算以前 ，要以某种方式获得这些信息。 计算本身可在某个场点 （ 例如 ， 图 5-2 中所示的逻辑集中式控制器 ）进行， 或在每台路由器的路由选择组件中重复进行（ 例如在图 5-1中 ） 。 然而，这里的主要区别在于 ，集中式算法具有关于连通性和链路开销方面的完整信息 。具有全局状态信息的算法常被称作链路状态 （ Link State, LS） 算法，因为该算法必须知道网络中每条链路的开销 。 我们将在 5.2. 1 节中学习 LS 算法 。
• 在分散式路由选择算法 （ decentralized routing algorithm ） 中 ，路由器以迭代、分布式的方式计算出最低开销路径 。 没有节点拥有关于所有网络链路开销的完整信息 。相反 ， 每个节点仅有与其直接相连链路的开销知识即可开始工作。 然后 ，通过迭代计算过程以及与相邻节点的信息交换 ， 一个节点逐渐计算出到达某目的节点或一组目的节点的最低开销路径 。 我们将在后面的 5.2.2 节学习一个称为距离向量（Distance-Vector, DV） 算法的分散式路由选择算法 。之所以叫作 DV 算法 ， 是因为每个节点维护到网络中所有其他节点的开销（距离） 估计的向量 。 这种分散式算法 ，通过相邻路由器之间的交互式报文交换 ， 也许更为天然地适合那些路由器直接交互的控制平面， 就像在图 5-1 中那样 。

路由选择算法的第二种广义分类方式是根据算法是静态的还是动态的进行分类 。 在静态路由选择算法 （static routing algorithm） 中 ，路由随时间的变化非常缓慢 ，通常是人工进行调整 （ 如人为手工编辑一条链路开销） 。动态路由选择算法 （ dynamic routing algorithm ）随着网络流量负载或拓扑发生变化而改变路由选择路径 。一个动态算法可周期性地运行或直接响应拓扑或链路开销的变化而运行 。 虽然动态算法易于对网络的变化做岀反应 ， 但也更容易受诸如路由选择循环 、 路由振荡之类问题的影响。

路由选择算法的第三种分类方式是根据它是负载敏感的还是负载迟钝的进行划分。 在负载敏感算法 （ load-sensitive algorithm） 中 ，链路开销会动态地变化以反映出底层链路的当前拥塞水平 。 如果当前拥塞的一条链路与高开销相联系， 则路由选择算法趋向于绕开该拥塞链路来选择路由 。 而早期的 ARPAnet 路由选择算法就是负载敏感的 ， 所以遇到了许多难题 。当今的因特网路由选择算法 （ 如 RIP 、OSPF 和 BGP） 都是负载迟钝的 （ load insensitive）, 因为某条链路的开销不明确地反映其当前 （ 或最近）的拥塞水平 。