路由 TCP/IP 卷一 第四章：Dynamic Routing Protocols 总结

之前的章节讲解了路由器路由所需的信息，这些信息都是网络管理员手动输入进去的静态路由信息。从这章开始，我们将学习自动输入这些路由信息的动态路由协议。路由协议就是路由器之间交换网络可达性和状态的一种共同语言。

动态路由协议不仅进行路径决定和路由表更新，还会在一条路径失效后自动选择次优路径，这是它优于静态路由配置的地方。

显然，为了交流能发生，路由器之间肯定需要用共同语言。自从 IP 路由开始之后，有 8 个主要的 IP 路由协议。后续章节将逐个介绍具体的协议，这章先讲动态路由协议的共同点。

Routing Protocol Basics

所有的动态路由协议都基于某个算法。算法就是解决一个问题的一步步的过程。一个路由算法最少应该明确如下方面：

• 从其他路由器接收路由信息的过程；
• 发送路由信息给其他路由器的过程；
• 基于路由表的信息找出最佳路径的过程；
• 应对、弥补、广播网络变化的过程。

路径决定、度量、收敛和负载均衡是所有路由协议都要考虑的问题。

Path Determination

网络中的所有子网都必须连接到某个路由器，路由器的每个接口必须有一个 IP 地址，这个地址就是可达信息的出发点。路由器之间的消息分享看上去非常简单：

1. 路由器考察自己的 IP 地址，知道它有几个直连网络；
2. 它把直连网络的信息写入路由表中，伴随着一些标志信息表明端口是直连的；
3. 路由器把信息放入一个报文中，我直连的地址是 xxx；
4. 路由器把报文发送给它相邻的路由器。

其余路由器也进行相同的操作，把路由信息发送给它们相邻的路由器中。路由器把接受到的信息写入路由表，并标明信息的来源。这样，网络中的每个路由器都知道了网络中路由的所有信息。

但仔细想想，还是有一些细节问题，这就是为什么路由协议如此复杂。

• 当一个路由器接收到邻居传来的信息后，它要不要把这个信息传给自己的邻居？
• 如果不转发更新，有可能信息共享不完整。比如路由器的两个邻居只能借助它来通信，如果不接力转发，则那两个邻居之间无法通信；
• 如果路由器同时从两个邻居接收到了对同一个网络的路由信息，它会选择哪条路径到那个网络？
• 什么机制确保所有路由器接收到所有路由信息，同时避免更新报文在网络中无限循环？
• 路由器和路由器之间的网络信息，是否要广播？毕竟每个路由器都知道自己的直连网络。

这些问题都是每个路由协议要解决的，这也是它们复杂的原因。

Metrics

当去往同一个目的地有多条路径可选时，一个路由器必须能够选择最佳的路径。度量就是分配给一条路径的变量，用来给路径的好坏排序。

Hop Count

跳数是一个很直白的指标，它表示到达目的地需要经过几跳路由器。跳数少，说明目的地离得更近；反之亦然。不过距离最短的一定是最佳路径吗？万一那条路带宽很小，很可能走的反而更慢。

Bandwidth

基于带宽尺度来选择路由，路由器会选择带宽更大的。带宽当然也不一定是好的尺度，因为有可能高带宽的道路现在很拥堵。

Load

这个尺度反映了当前链路上带宽的多少。从它的定义可以发现，负载指标是一个动态指标，需要定期更新，这就对路由算法提出了新的要求。负载指标必须把更新的时间控制在合理的尺度中，太快可能会增加 CPU 负担，也可能造成路由的翻转；太慢则指标太滞后，无意义。

Delay

延迟表示的是一个包经过路由所需时间。听上去，时间必须要通过实际发包测算，其实不是这样。就像是算法的时间复杂度一样，不需要通过运行程序来计时，延迟指标可以通过链路的一些基本静态信息代入公式计算。

Reliability

可靠性是衡量某条链路失败概率的指标，它可以是动态的，也可以是静态的。动态计算的方法可以是一段时间内链路失败的概率，静态则可以由管理员手动配置。

Cost

代价/花费是一个网络管理员配置的反映某个链路偏好程度的一般指标。它的好处在于可以用在不区分协议细节的一般讨论中，比如 RIP 基于跳数选择了最小花费的路径。

另一个一般的术语叫做最短的，比如 RIP 基于跳数选择了最短的路径。

Convergence

根据前面讲解的内容，一个动态路由协议必须定义如下过程：路由器接收邻居传来的路由信息、处理它们，并转发给它的邻居们。此外，还必须定义评价链路的度量。

另外一个对路由协议的评价标准是不同路由器中路由表的一致性。比如两个邻居 A 和 B，对同一个目的地，A 认为下一跳是 B，B 认为下一跳是 A，那遇到一个这个目的地的包，这个包就会在 A B 之间反反复复，形成路由循环。

理想来说，路由循环应该是一种中间状态，是不一致的一种状态。对于所有路由器的路由表达到一致状态的过程叫做收敛，所花费的时间叫收敛时间。

不过，有时候由于一些错误配置，导致收敛状态下也出现了路由循环，这时候就需要网络管理员来进行排错。

Load Balancing

在第三章中，我们讲了，为了充分利用链路，可以进行负载共享。在动态路由协议中，何时、如何进行负载均衡也是需要考虑的事情。负载均衡可以是等代价或者不等代价的，也可以是逐报文的或者逐目的地的。

Distance Vector Routing Protocols

绝大多数的动态路由协议属于以下两种类别之一：距离向量(distance vector)或者链路状态(link state)。

距离向量协议的理论基础是 Bellman, Ford 和 Fulkerson 提出的动态规划算法，是的，就是算法课讲的那个动态规划，0-1 背包问题的那个动态规划。一个例外是 EIGRP，它基于的是 J. J. Garcia Luna Aceves 提出的算法。

动态规划算法的精髓有三：子问题定义、转移方程、记忆列表。可以试着在经典的背包问题上套用这三个组分。在路由问题上，子问题就是到某个结点的最短距离和下一跳，转移方程是考察所有邻居，哪个到达下一跳更近；记忆则体现在路由表中。

不管是哪种路由协议，都涉及到算法，这里的算法指的是针对路由表的信息进行路径确定的算法，比如动态规划、比如 Dijkstra，而不是路由器之间交换涉及的通信协议。通信协议单纯是通信领域的内容，如何开始、交换什么、交换间隔等等。

距离向量协议中，路由器之间交换路由信息的方式是 (距离，方向) 对，这就是这个协议名字的来源。比如，目的地 A 有 5 跳远，方向是路由器 X 作为下一跳的方向。每个路由器从邻居那里知道路由信息，所以距离向量协议也被称为通过谣言进行路由。

距离向量协议包括如下协议：

• RIP for IP
• XNS RIP
• IPX RIP
• IGRP 和 EIGRP
• DNA Phase IV
• RTMP

Common Characteristics

一个典型的距离向量协议采用的寻路算法中，路由器通过把整个路由表广播的形式，周期性地给所有邻居发送路由更新。

上面这句话有许多细节问题，下面逐个解释。

Periodic Updates

周期性更新的意思是，在某个计时器到期，更新会被发送。不同协议规定的周期很可能不同。

周期更新的时间间隔需要谨慎考虑，如果太小，可能会加剧 CPU 负担，同时造成网络拥塞；太大可能会导致收敛时间不可接受。

Neighbors

就路由器而言，邻居指的是共享一条数据链路、或者在更高层次上具有邻居关系的路由器。一个距离向量协议通过把更新发送给邻居，再依靠邻居把消息传递出去。所以距离向量协议也叫逐跳更新。

这和图神经网络(GNN)的消息传递有几分相似，在 GNN 中，消息传递也基于邻居，通过卷积和池化，让一个结点的信息受到局部邻居的影响。不过二者确实有显著的差别。

在 GNN 中，我们不希望过度平滑。如果消息传递次数太多，会导致结点与结点之间没有区分度，无法进行分类；而在路由中，我们希望结点完全一致，这样才能收敛，反映网络的稳定状态。

Broadcast Updates

当一个路由器初次在网络上活跃时，其他路由器如何感知它的存在，它又如何发现其他路由器？最简单的方法是发送一份广播消息，和当前路由器采用同种路由协议的会回应，其他不相关的结点将丢弃这条消息。

Full Routing Table Updates

绝大多数距离向量协议都采用把完整路由表广播出去的这种最简单的方式。接收到完整路由表的其他路由器过滤它们需要的信息，忽略不需要的部分。

Routing by Rumor

这节先是举了个路由信息按时间逐个路由器传递的例子，比较简单，我就不重复了。

进入到比喻时间，距离向量协议就像是迷宫中的路牌——“出口 51，北京，150 公里”。你不知道 150 公里会经历哪些路段，也不知道牌子是否能相信。距离向量协议就是提供了网络的路标，提供了方向和距离，但是不包含路途中的细节信息。与此同时，它们也容易被破坏或干扰。

下面是一些距离向量算法的困难和优化。

Route Invalidation Timers

试想一下，如果某个路由器 A 连接的子网突然坏掉了，这个路由器就会标记当前路径失效，并把信息传递给邻居们——一切正常。

但是如果现在是路由器 A 坏掉了呢？邻居们仍然以为 A 连接的子网可达，照样给 A 发信息，可是得不到响应。网络中形成了一个黑洞。

为了解决这个问题，路由表中的某个记录还伴随着一个路由无效计时器，每当路由器接收到这条记录时，计时器会重置。如果有一段时间（一般是 3 到 6 个更新周期）没有接收到某条记录，则这条路由会标记为失效。之所以不是一个周期没接收到路由便失效，是因为一次丢失可能是延迟或丢包造成的偶然现象。

周期不能特别短，否则路由表会不稳定（明明只是路由可靠性差丢了个包，却把路由标记为不可达）；也不能特别长，否则真出现了网络拓扑改变，收敛时间太长。

网络、通信领域的许多变量都是如此，不能太大也不能太小。

Split Horizon

根据距离向量协议，每次更新，路由器都会把自己路由表中的全体内容广播给邻居。想想，其实不是特别好。比如，路由器 A 从邻居 B 那学到了路由信息，它在广播的时候就没必要把从 B 那学到的信息再返回给 B，因为 B 已经知道这些信息了。这样做不仅会减少流量，也能防止路由循环出现。

第一个好处很好理解，第二个好处的解释可以看下面这个例子。

路由器 A 从邻居 B 那知道了到达子网 X 的下一跳路由器是 B。突然，B 检测到其连接到子网 X 的链路故障了。B 在路由表中记录了这一故障信息，并准备在下一个更新周期中广播给邻居。好巧不巧，在下次更新之前，B 接收到 A 广播的路由信息。A 说它离 X 一跳之隔。B 立马更新了这一信息。

毕竟，B 无法确定 A 给的路标是否正确，它只能无条件相信。好了，现在一个目的地址是 X 的包到达 A，A 查路由表，知道该给 B，B 接收到包后发现应该给 A——于是路由循环造成了。

一个指向报文发送方的路由叫做反向路由，分割地平线技术就是为了避免两个路由器之间的反向路由。

如何理解 split horizon 这个名字呢？Horizon 的意思是地平线、视野，这里指一个路由器了解的全部知识，也就是路由表。Split 表明分割、舍弃某些事物。合起来，指的是路由器在广播信息时，会舍弃一些存放在路由表的路由信息。舍弃的原则是，不会把从某个路由器学习到的路由信息再次返回给那个路由器。

分割地平线有两个类别：简单分割地平线和污染反向内容的分割地平线。前者的思想是，从某个端口发送路由信息时，不发送从这个端口学到的内容；后者则是照样发送从这个端口学到的内容，但对这些内容，把距离设定为无穷远。

污染反向的分割地平线是更为偏好的选择，毕竟，坏消息总比没消息好。当网络中出现异常时，简单分割地平线无法对错误的路由进行纠错；但污染策略却能够广而告之某些路由是错误的。当然，这可能会造成更大的带宽压力，需要取舍。

Counting to Infinity

不管是哪种分割地平线，都无法解决数到无穷问题。

A -- B
|    |
C -- D

有这样一个情景，四个路由器组成了环。突然，某个路由器 B 连接的子网不可达了，这个路由器给邻居们发送这一消息。不过在一个更新周期，最新消息只能传达给 1-跳邻居，也就是 A 和 D。

此时，对角的那个路由器 C 会广播，不可达的那个子网离它 2 跳之远。A 和 D 一看，原来能从你那到达，赶紧更新路由表。

为什么 C 会广播这一错误信息？一方面，B 传递的消息有滞后性，C 还不知道那个子网不可达；另一方面，C 有两条路径到达 B，它会给 A 发送从 D 那得知的信息，给 D 发送从 A 那得知的信息。所以，分割地平线无法阻止这一广播的发生。

到了下一个更新周期，D（A 也可以，这里假设是 D）告诉 B，它离不可达的那个子网 3 跳远。B 记下了，离那个子网 4 跳远，告诉 A，A 增加到 5 跳，C 增加到 6 跳，以此类推，数到无穷。

解决这个问题的方法是定义无穷，如定义无穷是 16 跳，那么在一段时间后，网络中的所有路由器都知道这个子网是真的不可达了。但这样，收敛的时间很长，需要许多广播周期才能完成收敛。减少收敛时间的方法是触发更新。

Triggered Updates

触发式更新，也叫闪速更新，非常简单。如果一个度量改变了，不等到更新计时器结束，路由器便会广播这一更新。这样收敛的速度就会快很多。数到无穷这一问题被大大缓解，但没有在根本上解决。

一个更好的优化是只在更新中包含触发了触发更新的记录，而不用包含完整的路由表。这样可以减少处理时间和网络带宽的影响。

Holddown Timers

触发更新在一个重新收敛的网络中增加了响应性，限制时钟对于坏的路由信息引入了一定量的怀疑。

当一条路由记录的距离增加了，路由器就会设定一个限制计时器，在这个计时器过期之前，路由器不会接受对这个路由的任何新的更新。

显然，这里也涉及到权衡，要是计时器的时间太小，则发挥不了用处；反过来呢，则对正常路由有负面影响。

Asynchronous Updates

按理来说，使用同一个以太网的路由器应该异步更新，换句话说，不应该在同一时刻广播它们的更新，因为这会导致碰撞，造成链路拥塞。但这确实是共享介质可能造成的问题。因为路由器处理路由所需的时间会导致更新时钟滞后，滞后呀滞后，待到滞后一个周期时，不同路由器的更新时钟便同步了。

详细解释一下这个问题。比如，路由器 A 在 0s, 30s, 60s… 更新；路由器 B 在 10s, 40s, 70s… 更新。0s，路由器 A 广播了更新，链路繁忙。B 的更新时间也到了，但由于链路繁忙无法更新，时钟无法重置。下次 A 的更新还是 30s，但 B 的更新很可能在 15s。

以此类推，要是 B 落后 A 一个周期，A 和 B 的更新时间便同步了。

解决这一问题有两个方案：

• 更新时钟独立于处理时间。但这一方案不是很好，因为这要求网络中的所有路由器不能同时启动，不太现实。
• 每次的更新时间会引入一个小扰动。这一方案要注意扰动的大小，太小了则近乎无效。

Link State Routing Protocols

距离向量协议传递的信息可以类比为路标，那链路状态协议传递的信息就可以类比为一个道路图。一个链路状态路由器不会被错误的路由欺骗，因为它知道完整的图景。

不像通过谣言路由的距离向量协议，链路状态协议从它所有的同伴路由器（采用同种协议的路由器，不仅是邻居）中获取第一手信息。每个路由器发送自己的信息、连接的链路和链路状态（协议名字的来源），以及直连的邻居。

消息在路由器之间传播，每个接收到消息的路由器都会留存一份拷贝，但不会改变它。最终的目标是网络中的每个路由器都有相同的网络信息，独立地计算最短路线。

链路状态协议，有时候也叫最短路或者分布数据库协议，基于大名鼎鼎的图论中的 Dijkstra 算法，也叫最短路算法。链路状态路由协议有如下的几个例子：

• OSPF
• IS-IS
• DNA Phase V
• NLSP

即使相较于距离向量协议来说，链路状态协议看起来比较复杂，但基本原理一点都不复杂：

1. 每个路由器它们的每个邻居建立邻接关系；
2. 每个路由器给邻居发送一个数据单元(Link State Advertisements, LSA)，表明其链路、链路状态、度量以及连接接口。接收到信息的每个邻居也会把信息转发给自己的邻居(floods)；
3. 每个路由器在数据库中存储了所有它见过的 LSA，正常来说，所有路由器的数据库都应相同；
4. 完成了的拓扑数据库，也叫做链路状态数据库。Dijkstra 算法利用这个数据库计算出到达每个路由器的最短距离。随后，链路状态协议就能够从数据库中找到每个路由器连接的子网，并把这份信息写入路由表中。

Neighbors

邻居发现是建立链路状态环境的第一步，这一步用到了 Hello 协议。Hello 包至少会包含路由器的 ID 和包发送的地址。路由器 ID 应该是每个路由器唯一的。除此之外，Hello 包还会包含子网掩码、Hello 间隔和假设邻居存活的最大时间、电路类型等等。

当两个路由器发现对方是邻居后，会进入同步数据库的过程。它们交换数据库中的信息，直到数据库完全相同。具体的同步细节在 OSPFv2 和 IS-IS 的章节中会讲解。

为了进行数据库同步，邻居必须是相邻的——也就是它们必须在协议规定的参数中保持一致，诸如计时器等参数。通过 Hello 包建立邻接关系，链路状态协议以一种受控的方式交换信息，这和距离向量协议迥然不同，后者不需要沟通，直接把路由表广播出去。

除了建立邻接关系，Hello 包还可以用来确认一个邻居是否可达，充当心跳包的作用。要是超过某些周期不可达，比如 4 个 Hello 周期都没有接收到邻居的响应，则认为邻居 dead 了。

Link State Flooding

在邻接关系建立后，就可以发送 LSA 了。像 flooding 这个术语暗示的那样，这个广告是发送给每个路由器的。一步步地，LSA 被复制并发送给每个邻居，除了 LSA 的发送方。由此可见，这是链路状态协议优于距离向量协议的地方，它快。

每个路由器接收到 LSA 后立刻就可以传送出去，不像距离向量协议那样还需要运行动态规划算法。所以在拓扑改变时，链路状态协议收敛的更快。

Flooding 过程是一个链路状态协议中最复杂的部分，有许多让 flooding 更高效、可靠的地方，比如单播或者组播、校验和以及积极 ACK 等等。那些都会在具体的协议中介绍。不过有两个机制是至关重要的：定序和老化。

Sequence Numbers

泛洪的一个难点是，何时停止呢？用序列号来表示一次泛洪。还是以一个路由器环举例。

F - E - D
|       |
A - B - C

假如 A 连接的链路突然失效了，A 会把消息传递出去。假如现在 C 通过 A-B-C 这个链路接收到了消息，它会把新的网络状态记录到数据库中，并传递给 D。

过了一段时间，从更远路径 A-F-E-D-C 的同样消息到达了 C，问题是，C 要不要把消息传递给 B 呢？答案是不，因为这次通知和之前通知的序列号相同。

看上去好像不用序列号也没问题？只需要看新通知和现有通知的内容是否相同就好了。NO。假如现在 A 连接的链路又好了，A 又发送了个消息。接收到链路 up 的路由器 C 记录了消息。过了一段时间，链路 down 的消息由于延迟，才从 D 传来。要是没有序列号，C 就无法得知原来 down 是之前过期的消息。

既然是序列号，就一定有个界限。如果序列号到达了上界，该如何处理呢？

Linear Sequence Number Spaces

一个解决方案是使用一个足够大的序列号空间，比如 32 位的。如果每 10s 发送一次 LSA，则序列号可以使用 1361 年，看上去万无一失了。

但现实世界是残酷的，很可能有个路由器不知道怎么回事，把序列号很早就用完了。那它就必须关机，等网络中其他邻居的路由信息老化过期后才能再次启动。

此外，一个路由器重启之后，它该从哪个序列号开始呢？很可能是 1。不过，此时邻居路由中存放的序列号比 1 大多了，邻居们会认为序列号为 1 的信息是旧的信息，不理睬。这样，路由器似乎又得关机，等邻居的路由信息老化。可能要一个小时之多。

一个更好的解决方案是添加一个规则，如果邻居接收到了一个比数据库中序列号更小的序列号，邻居会把自己数据库中的序列号返回，这样路由器就知道该从哪里继续了。

还是要注意，要是原来的序列号接近上界，重启仍然不可避免。嗨，扯了这么久，还是没解决这上界的问题。一个可能的方案是增加一条规则，序列号的一般增长不能超过全部序列空间的一半。要是超过了一半，就认为小的序列号是更新的。

Circular Sequence Number Spaces

另一种解决方案是采用循环地址空间，这样不就没有边界了吗。学习了数字逻辑后，这是很好理解的，相当于一个循环计时器。最大数的下一个是 0。当然了，一个重启的路由器照样会遇到上面线性序列号的问题。

循环序列号有点反逻辑，对于上界和下界之间的每个数 $x$，有 $0 < x < 0$。这个问题在运转正常的网络中可以通过定义以下两个规则来解决。对于地址空间 $n$，$a$ 比 $b$ 更新需要满足两条之一，核心思想是大，但不要大的太多：

• $a > b$，且 $(a - b) \le n/2$;
• $a < b$，且 $(b - a ) > n/2$

但如果网络不是良好运转的，很可能有大问题发生。假如在一个最大值为 32 的空间中，有个路由器发生异常，抖擞精神，发送了 3 个 LSA，序列号都是 44。碰巧邻居也不正常，丢失了一些位数，让这三个包的序列号分别变成了 44，40 和 8。

DEC	BIN
44	101100
40	101000
8	001000

哇，现在 44 比 40 新，40 比 8 新，但 8 又比 44 新。一个新中新的循环出现了。网络中的路由器会持续更新最新的 LSA 信息，直到 CPU 过载，直到整个网络垮掉。

看上去很荒谬，但这确实发生了。在 1980 年的 10 月 27 日，ARPANET 中的两个路由器就发生了上文描述的情况。

Lolipop-Shaped Sequence Number Spaces

棒棒糖形状的序列号空间是由 Radia Perlman 提出的，它是线性空间和循环空间的结合，兼具二者的优点。循环空间的问题是，没有一个最小的数用作初始化标记；线性空间的问题是，它的空间不是循环的，是有界的。

线性空间部分组成了棒棒糖的棍。当路由器刚启动的时候，它会发出一个比所有循环空间的数字都小的序列号作为 LSA 的编号。邻居们如果发现数据库中的编号比这个编号更新，则会把数据库中的编号返回给 LSA 的发出者，这样发出者就知道启动前编号到了哪个数字。

怎样构建出满足比所有循环空间数字都小的数呢？方法是，采用负数作为线性空间的数字，非负数作为循环空间的数字。启动路由器后，它会发送最小的负数，随后数值逐渐增大到 0。此后，序列号进入循环部分，在 0 和最大正数之间循环，不会再返回负数部分。

有点像某些数字电路的计数器，一开始是全 0，但计数循环中的状态机却不包含全 0 这个状态。

对于棒棒糖地址空间，衡量两个序列号 $a$ 和 $b$ 新旧关系的规则如下。$b$ 比 $a$ 更新当且仅当：

• $a < 0$, 且 $a < b$, 或
• $a > 0$, $a < b$, 且 $(b - a) < n/2$, 或
• $a > 0$, $b > 0$, $a > b$, 且 $(a - b) > n/2$

有些实现会将最大的数和最小的数设置为保留位，不使用。

棒棒糖地址空间作为 OSPFv1 的序列号实现，但是 OSPFv1 从来就没走出过实验阶段。实际投入使用的 OSPFv2 采用了有符号数的序列号形式，但仍然是线性地址空间。当到达序列号上界时，需要对所有路由器中相关序列号进行刷新重置。

说了这么多种编号方式，有些乱，列个表格总结一下它们的优缺点。

方式	优点	缺点
线性		有上界
循环	无上界	没有比所有数都小的数，可能导致循环更新
棒棒糖		循环更新问题仍然存在

看上去发展的思路是，线性序列号有界，希望通过引入循环序列号实现无界的特性。然而循环序列号会出现更为严重的问题。集两家之长的棒棒糖策略仍然无法避免循环序列号的问题。

Aging

老化和距离向量协议的 Invalidation Timer 充当的功能类似，提高路由信息的可靠性。

如果两个具有相同序列号的报文先后到达，如果时间差小于 MaxAgeDiff，则认为是正常的网络延迟，不会再次 flood 给邻居；否则，说明网络中可能出现了异常：一个新的 LSA 发出，但序列号没增加。此时，新的 LSA 会被 flood。OSPF 使用的 MaxAgeDiff 是 15 分钟。

LSA 的 age 在数据库中也会增长，如果超过了 MaxAge，则说明这个链路信息过时了，会被删除，同时通知邻居们记录过期。

为了避免链路信息因超时被删除，有一个刷新机制，即 LSRefreshTime，当这个时间到期，一个新的 LSA 会发出给邻居们，重置 age。OSPF 的 MaxAge 是 1 小时，LSRefreshTime 是 30 分钟。

Link State Database

除了泛洪 LSA 和发现邻居外，另一个链路状态协议的主要工作是链路状态数据库。为了寻路，LSA 应该广播如下两种信息：

• 路由链路信息，用三元组 (路由器 ID，邻居 ID，花费) 的形式广播一个路由器的邻居信息；
• 连接的子网信息，用三元组 (路由器 ID，网络 ID，花费) 的形式广播一个路由器直连的子网信息。

记录了这些信息，接下来需要运行最短路算法，从而判断到达每个路由器的最短路。最后，再把每个路由器连接的子网补充上去，就能确定如何到达每个子网。

路由器构成的图可以是一个有向图，也就是 A -> B 和 B -> A 的代价很可能不同。这一不同可能是人为规定的，也可能是链路上行下行的负载不同所导致的。

SPF Algorithm

这节讲的就是 Dijkstra 的最短路算法了，算法课和离散数学课上都讲过，就不再赘述了。不过，可以看看 Dijkstra 的原文是怎么描述这个算法的。

在构造过程中，树枝（边）被分为以下三个类别：

I. 已经被分配给建造中的树的树枝；
II. 待选入集合 I 中的树枝；
III. 剩下的树枝（被拒绝或者暂未考虑）。

同时，结点可以被分为两种类别：

A. 被集合 I 中的树枝连接起来的点；
B. 剩余结点（有且只有一个集合 II 中的树枝会连接这些点）。

一开始，任意选择一个点作为集合 A 中唯一的成员，并且把这个点连接的所有树枝都放入集合 II。之后，重复进行如下两个步骤：

Step 1: 集合 II 中最短的树枝被移动到集合 I 中。这也会导致集合 B 中的一个结点被移动到集合 A；
Step 2: 考虑所有连接刚刚被挪到集合 A 的结点和仍然在集合 B 中结点的连边。如果考虑中的连边比集合 II 中的更长（这里的长度比较的是到根的距离，而不单纯是这条边的长度），则它被拒绝（进入集合 III）；如果它更短，则它替代集合 II 中对应的连边，后者被拒绝。

之后，回到步骤 1，重复这段过程，直到集合 II 和集合 B 为空。集合 I 中的连边就构成了所求的树。

具体到寻路这个例子中，也有对应的术语和推演流程，之前的课程都做过这种事，不赘述。

Areas

区域指的是组成一片网络的路由器的子集。把一个网络分解成许多区域是为了处理链路状态协议的三个问题：

• 链路状态协议的数据库相较于距离向量协议需要用到更多内存；
• 复杂的寻路算法需要更多的 CPU 时间；
• 泛洪链路状态报文会对网络带宽造成负面影响，尤其是不稳定的网络。

许多链路状态协议和运行它们的路由器都致力于减轻上述影响，但无法消除。上一节讲解了 8 个路由器的网络中寻路算法的运行流程，这还没考虑每个路由器连接的子网呢。要是 8,000 个路由器，那还了得，可以想见，会对 CPU、带宽、内存有显著的影响。

不过呢，使用区域可以极大地减少上述影响。当一个网络被分成许多区域，LSA 报文只需要在某个区域中传送。这样，数据库更小了，需要的内存更小。当链路的拓扑状态改变时，报文限制在了某个区域中。

连接两片区域的路由器同时属于两片区域，就需要为每个区域单独维护数据库。就像是一个网络中的主机只需要知道网关地址就能上网一样；一片区域的路由器只需要知道边界路由器在哪就能连接到其他区域。道理是相通的。

像 RIP 或者 IGRP 这样的距离向量协议并不使用区域这一概念，所以可以想象，它们必须对大型网络中的每个路由器单独设立一条记录，内存压力很大。同时，定期广播路由表也会造成太大的带宽压力。所以这样来看，链路状态协议更胜一筹。

Interior and Exterior Gateway Protocols

区域引入了网络结构中的一种等级结构。把区域组成为更大的区域则引入了另一层结构——自治系统，也叫路由域。

自治系统原来的定义是，在统一管理下、运行同一种路由协议的路由器组。不过后者在当今快速变化的网络结构中已经不适用了，随着公司合并、拆分，使用不同路由协议的路由器很可能一起工作。所以当代的自治系统的定义就是在统一管理下的网络。

在一个自治系统中运行的协议叫内部网关协议(Interior Gateway Protocols, IGP)。这章给出的所有路由协议都是 IGP。

在自治系统之间的路由协议叫外部网关协议(Exterior Gateway Protocols, EGP)。常见的 EGP 有：

• BGP
• EGP
• IDRP

自治系统这个定义并没有那么绝对，不同的文档有赋予了它不同的含义。不过这本书只在两种情况下使用它：

• 自治系统就是一个路由域，就像上面定义的那样。IGP 是自治系统颞部的路由协议，EGP 是自治系统之间的路由协议；
• 自治系统指处理域，或者一个独立于其他 IGP 进程的 IGP 进程。比如所有运行 OSPF 协议的路由器可以叫做 OSPF 自治系统，同理，EIGRP 自治系统等等。再分配是在这些自治系统中路由的方式。

Static or Dynamic Routing

这章讲了那么多内容，似乎会造成一种动态路由协议比静态协议更好的错觉。但需要留意的一点是，动态协议存在的价值是自动应对网络拓扑变化。这一自动化的代价是带宽、内存和处理时间。

另一个动态路由的代价是缺乏对路由选择的控制。毕竟，路由协议决定了去往一个目的地的最好路线，而不是你。如果对网络的精细控制是重点，尤其是动态协议和你想要的路线不同时，静态路由协议是更好的选择。

一个对静态路由的常见反对是其难于管理，这对于中大型网络是正确的，不过一个就小型网络而言，静态协议往往就够了。

总之，设计网络的时候，最简单的解决方案往往就是最好的。当静态路由无法满足实际需求时，再使用动态协议才是最佳实践。