在上一节中我们介绍了路由算法中的链路状态路由算法，介绍它基于Dijkstra算法来实现，同时分析了其缺点。接下来，我们继续介绍另外两种路由算法：距离向量路由算法和层次化路由算法

距离向量路由算法

距离向量路由算法实际上是基于Bellman-Ford方程（动态规划的思想）来实现的。

同样的，这里先列举出后续算法介绍中会使用到的符号定义：

• 令d_x(y) = 从x到y最短路径的费用（距离）

  则d_x(y) = min_v{ c(x,v) + d_v(y) }

  其中

  • min_v表示 在x节点的所有邻居v中取最小值。
  • c(x,v)表示x到邻居v的费用（距离）。
  • d_v(y)表示从邻居v到目的节点y的费用（距离）。

有了上述公式后，作为x节点就不需要知道整个网络的拓扑结构和路径费用，而只需要知道跟所有邻居节点间的费用，以及每个邻居节点到目的节点的最短路径费用即可。

Bellman-Ford算法举例

如下图所示，假设我们希望计算节点u到节点z的最短路径。

根据图上的路径费用，显然有：

• d_v(z) = 5
• d_x(z) = 3
• d_w(z) = 3

因此， 根据Bellman-Ford算法公式可以得到：

d_u(z) = min{ c(u,v) + d_v(z),

​ c(u,x) + d_x(z),

​ c(u,w) + d_w(z) }

​ = min{ 2+5,

​ 1+3,

​ 5+3}

​ = 4

可以看出，在这种算法中，节点u不需要知道完整的网络拓扑，只需要知道跟所有邻居节点间的费用，以及每个邻居节点到目的节点的最短路径费用即可。

在上面的例子中，当节点u知道到达节点z的最短路径是从邻居节点x中获取的，就会把这个信息记录在转发表中。后续数据报达到需要转发到z节点上时，就会经过路由器的u->x的接口转发出去。

重点：节点获得最短路径的下一跳，该信息用于转发表中

距离向量路由算法

在上述公式：d_x(y) = min_v{ c(x,v) + d_v(y) }中，c(x, v)的距离可以直接由到达邻居节点的路径费用获得，而d_v(y)的获取，则需要其他算法步骤的支持，需要多次迭代计算获取。

我们设定D_x(y) 表示从节点x到节点y的最小费用估计， 因此，对于节点x的所有邻居节点，节点x维护一个距离向量D_x = [ D_x(y), y 属于N]。

此外，节点x还必须维护其所有邻居节点的距离向量：D_v = [ D_v(y): y属于N’]

也就是说，在距离向量路由算法中，每个节点计算得到的到其邻居节点的距离向量，都需要通告给其邻居节点。 相当于每个邻居节点，都有其邻居节点的距离向量D_x的记录。

此时，节点x维护的两个向量为：

• 已知的到达每个邻居节点的费用：c(x, v)
• 维护其所有邻居节点的距离向量：D_v = [ D_v(y): y属于N’]

有了上述两个信息之后，就可以进行核心逻辑的计算了。

核心思想

• 每个节点不定时的将其自身的D_v估计发送给其邻居。

• 当x接收到邻居的新D_v估计时，，即根据Bellman-Ford算法更新其自身的距离向量估计：

  

​ 在更新完自身的距离向量估计后，同样的，会将该距离向量同步给其所有的邻 居节点，邻居节点接收到新的距离向量估计后，同样也会更新自己的。以此类 推地迭代下去。

• D_x(y)将最终收敛于实际的最小费用d_x(y)

算法特点

• 异步迭代

  引发每次局部迭代的因素：

  • 局部链路费用改变
  • 来自邻居的距离向量D_v更新。

• 分布式

  每个节点只有当D_v变化时才通告给其所有邻居。邻居在必要时（其D_v更新后发生改变）再通告它们的邻居。

有了上面的概念后，就可以给出距离向量路由算法的一个大致核心思想的描述：

层次化路由算法

在之前我们介绍的链路状态路由算法和距离向量路由算法，其核心思想都是要将整个网络抽象成一张图，然后借助于图算法来计算得到图中节点间的最短路径，最后映射到实际的网络中。

但是将任意规模网络抽象为一个图计算路由过于理想化，尤其对于大规模的网络，比如Internet网络。

比如，考虑将网络规模6亿多节点的网络抽象成一张图：

• 图算法计算复杂度无法估量
• 计算得到的路由表几乎无法存储
• 路由计算过程中的信息（e.g. 链路状态分组、D_v距离向量）交换量巨大，这些信息在路由器间交换时，本身就会占用链路带宽的。最极端情况可能会把链路带宽都耗尽，导致淹没路由！

同时，单一将整个网络用同一种路由算法来计算，也存在一定缺陷，比如管理自治的问题：

• 每个网络的管理（比如运营商、企业网络管理者）可能都期望自主控制其网内的路由。不能说所有网络都采用一种单一的方式来进行路由设计。
• 正式因为管理自治，像我们现在的网络，将不同自治下的网络互联在一起，构成一个更大的网络，也正是被叫做互联网的原因。

显然，当网络规模较大时，单一抽象成图结构来表示网络结构是不可行的。那么怎么解决大规模网络，管理自治等问题下，设计出更合适的路由算法呢？这就是本节层次化路由算法的由来。

层次化路由

层次化路由实际上就是把我们的网络结构再进行一层抽象，比如我们之前的路由算法是将整个网络抽象成一张图，在图中计算节点间的最短路径，而在层次化路由中，将整个网络结构，依据管理自治性的要求，把一个区域内的或者是一个组织内的路由器聚合在一起。为这个区域定义一个唯一性的标识就是：自治系统 （autonomous systems），对应的自治系统的编号是一个16位的编号，称为自治系统号。

有了这种层次后，我们的路由就可以分成两类，一类是自治系统内部，可以按照前面介绍的路由算法（e.g. 链路状态路由、距离向量路由算法等）进行计算。另一类相当于把自治系统看作一个整体，考虑跨自治系统之间的路由要怎么处理。

按照上述的层次路由思想：

• 同一个AS内的路由器运行相同的路由协议（算法）。自治系统内部路由协议也叫做：”intra-AS" routing protocol。
• 不同自治系统内的路由器可以运行不同的AS内部路由协议。每个自治系统内的路由协议只知道它自治系统内网络拓扑结构和相关信息

有了层次的概念后，在一个AS内部可以运行相同的路由协议，但是不同的AS之间需要如何来进行路由呢？为了解决这个问题，就需要引入网关路由器（gateway router） 的概念

网关路由器的特点：

• 位于AS“边缘”
• 通过物理链路连接其他AS的网关路由器
  • 因为该路由器跟其他自治区域相连接，所以可以根据该路由器与其他自治区域进行路由信息交换。
  • 自治系统内的路由器解决自治系统内的路由信息交换，而网关路由器可以实现更高一层的，跨越自治区域的路由信息交换。

有了网关路由器的概念后，后续我们分析路由，就可以分为自治区域内部的路由交换和自治区域间的路由交换两种不同的层次来考虑。

AS示例

如上图所示，这里有3个自治系统AS1、AS2、AS3互联在一起。可以想象，作为层次化路由来说，任何一个自治区域内的路由器，它的转发表要靠两层协议来进行确定：

• 一方面，在自治区域内部，根据区域内部的路由协议（算法）来确定区域内部路由信息的转发表。
• 另一方面，在自治区域间，当我们的数据需要发往自治区域外，且需要经过多个自治系统到达目的系统时，就需要路由器根据自治区域间的路由协议（算法）来确定自治系统间的路由转发信息。
• 因此，如上图所示，区域内的路由器转发表由两部分路由算法决定。

作为跨自治系统间的路由信息，实际上需要自治系统内部的路由算法和自治系统间的路由算法共同来确定。

自治系统间（Inter-AS）路由任务

如上图所示，有三个自治系统互联在一起。

假设AS1内某路由器收到一个目的地址在AS1之外的数据报，此时需要考虑：

• 路由器应该将数据报转发给哪个网关路由器呢？
  • 比如上图AS1中路由器1c和1b分别连接着另外两个网络AS3和AS2，那么AS1的路由器就需要根据目的地址，判断应该转发给哪个网关路由器。

为了让AS1的路由器拥有这些信息，AS1的路由器必须学会：

• 学习到哪些目的网络可以通过AS2到达，哪些可以通过AS3到达。

而这些信息怎么获取到呢？我们上面介绍过，网关路由器负责通过自治系统间的路由协议，来与不同自治系统间进行路由信息的交换。因此，为了让自治系统内的其他路由器也拥有该信息，就需要网关路由器在自身获取到自治系统间的路由转发信息后，广播给自治系统内的其他路由器。

概括来说，只要涉及到跨自治系统间的目的网络的传输、获取数据等都是自治系统间的路由任务。

接下来，我们以路由器1d的转发表为入口，看看该转发表在跨自治系统间时如何设置。

假设AS1学习到（通过AS间路由协议）某一子网X可以通过AS3（网关1c）到达，但不能通过AS2到达。

对于上午自治系统间的路由信息，对于自治系统AS1来说，需要通过路由器1c向所有内部路由器传播该可达性信息。在有了上层自治系统间的路由信息后，接下来需要解决的就是自治系统内的路由信息计算了。

对于AS1的路由器1d来说，需要利用AS1的内部路由协议（算法），计算出其到达路由器1c的最小费用路径接口，比如此时是接口l。

计算得到这个信息后，就可以将该转发信息添加到转发表中：

• 在转发表中添加记录：（x, l）

另一种场景，如果AS1可以通过多个自治系统到达子网x的话，此时为了配置转发表，路由器1d必须确定应该将去往子网x的数据报转发给哪个网关，也就是应该送到AS3自治系统的3a还是AS2自治系统的2a。

这里就涉及到自治系统间路由的另外一个任务：实现在多个网关间进行选择最短路径。 实现上述选择的协议就是热土豆路由协议：

热土豆路由协议：将分组发送给最近的网关路由器。

从名字不难看出，热土豆算法应该是一种自私的算法，就是将烫手的山芋赶快扔出去。

理解：热土豆路由选择会使用AS内部选择协议（如OSPF），用于计算最低开销路径。当存在多条最低开销路径时，就会根据NEXT-HOP的开销选择路由。

目前层次化路由的策略，尤其是在比较大规模的网络结构中，是一种比较有效的路由策略。事实上，像我们现在使用最广泛的Internet网络，使用的正是这种层次化路由的策略。接下来我们会继续介绍Internet网络路由以及Internet网络按照层次化的方式，自治系统内和自治系统间采用什么样的路由协议。