CS168

距离矢量协议

算法概述

在本节中，我们将设计一种距离矢量协议，它是三类路由算法之一（另外两类是链路状态协议和路径矢量协议）。

距离矢量协议在互联网和 ARPANET（互联网的前身）中有着悠久的历史。典型的距离矢量协议是路由信息协议（RIP），我们将要设计的距离矢量协议与 RIP 有很多相似之处。

为了对我们将要学习的路由协议有一些直观认识，考虑以下网络。

起初，每个路由器的转发表都是空的。我们的目标是填充每个路由器的转发表，以便数据包可以从任何地方路由到目的地 A。

首先，A 可以告诉 R1：“我是 A。” 现在，R1 知道如何将数据包转发到 A 了。

既然 R1 有了到 A 的路径，它就可以告诉它的邻居 R2 和 R3：“我是 R1，我可以到达 A。”

现在，R2 和 R3 知道它们可以通过将数据包转发给 R1 来到达 A。

R2 现在可以告诉它的邻居 R4 和 R5：“我是 R2，我可以到达 A。” 同样，R3 可以告诉它的邻居 R6 和 R7：“我是 R3，我可以到达 A。”

现在，R4 和 R5 知道发往 A 的数据包可以转发给 R2，R6 和 R7 知道发往 A 的数据包可以转发给 R3。

这个过程会继续下去：R4、R5、R6 和 R7 各自告诉它们的邻居自己是谁，以及它们可以到达 A。最终，所有路由器的转发表都会被填充，我们就可以从网络中的任何地方将数据包路由到 A。

总结一下：当你收到某人的通告，说他们可以到达 A 时，你应该记下是谁发送了这个通告。现在，你就可以通过那个人发送发往 A 的消息了。

而且，既然你有了发送消息到 A 的方法，你就应该向所有邻居发布通告，这样它们也可以通过你发送发往 A 的消息。

如果有多个目的地呢？我们可以为每个目的地重复运行这个算法。这样，转发表就会包含多个条目，每个条目对应一个目的地。

在这些笔记中，为了简单起见，我们将专注于单个网段，但我们设计的协议可以扩展到多个目的地。

对于每个目的地：

如果你听说了一条到该目的地的路径，就更新表格。
然后，告诉所有邻居。

通告和消息的方向

在这个协议中，很容易混淆通告和消息的发送方向。

关于如何到达 A 的通告从 A 开始，向外传播。例如，B 向 D 发送一个通告，说 “我是 B，发往 A 的消息可以通过我发送。”

相比之下，实际发往 A 的消息是向内发送的，朝着 A 的方向。例如，一条消息可能从 D 开始，在前往 A 的途中被发送到 B。

通告的方向与消息本身的方向完全相反。注意不要把通告和实际消息混淆！

规则 1：贝尔曼 - 福特更新

如果有多个路径可以到达 A，该怎么办？

在这种情况下，R3 和 R4 都会通告它们可以到达 A。R5 应该选择将数据包转发给 R3 还是 R4 呢？

回想一下，我们的目标是找到网络中代价最小的路由。为了让路由器能够从多个被通告的路径中选择代价最小的路径，我们需要在通告中包含代价信息。

R3 的通告现在是：“我是 R3，我可以到达 A，代价是 3。”

R4 的通告现在是：“我是 R4，我可以到达 A，代价是 2。”

现在，R5 注意到 R4 提供的路径更短，于是决定通过 R4 转发数据包。

我们将使用转发表来记录到目的地的已知最佳代价（以及相应的下一跳）。转发表的每个条目会告诉我们：目的地、该目的地对应的下一跳，以及通过该下一跳到达目的地的代价。

注意：形式上，转发表存储键值对，将每个目的地映射到一个包含下一跳和距离的二元组。为了简单起见，我们会用三列来绘制表格。

R5 可能不会同时收到两条路径的信息，所以我们需要更精确地说明当收到一条新路径时会发生什么。收到一条路径时，有三种可能：

如果表格中没有到该目的地的路径，就接受这条路径。如果我没有到达 A 的方法，我应该接受任何提供的路径。

如果（我们收到的）新路径比已知的最佳路径（来自转发表）更好，我们应该接受新路径，并替换表格中的旧路径。

如果（我们收到的）新路径比已知的最佳路径（来自转发表）更差，我们应该忽略新路径，继续使用表格中的路径。

对于每个目的地：

如果你听说了一条到该目的地的路径，在以下情况更新表格：
- 目的地不在表格中。
- 通告的代价比已知的最佳代价更好。
然后，告诉所有邻居。

我们如何知道一条新路径是更好还是更差呢？我们必须小心，因为并非所有链路的代价都是相同的。当有人通告一条路径时，通过该路径的代价实际上是两个数的总和：你到邻居的链路代价，加上邻居到目的地的代价（来自邻居的通告）。

举个具体的例子，假设我们听到：“我是 R1，A 离我有 5 个单位远。” 这条新路径的代价实际上是 1（我们到 R1 的链路代价）加上 5（来自通告的 R1 到 A 的代价），也就是 6。

之后，我们可能会听到：“我是 R2，A 离我有 3 个单位远。” 只看通告中的代价是不正确的。在这种情况下，新路径的代价实际上是 10（我们到 R2 的链路代价）加上 3（来自通告的 R2 到 A 的代价），也就是 13。这个代价并不比我们已知的最佳代价 6 更好，所以我们不会更新表格。数据包仍然会转发给 R1。

对于每个目的地：

如果你听说了一条到该目的地的路径，在以下情况更新表格：
- 目的地不在表格中。
- 通告的代价加上到邻居的链路代价比已知的最佳代价更好。
然后，告诉所有邻居。

对于我们收到的每个通告，我们都要比较两个数。一个数是表格中的已知最佳代价。另一个数是到邻居的链路代价加上邻居到目的地的通告代价。如果后一个数更小，我们就使用新路径，放弃旧路径。

规则 1：分布式贝尔曼 - 福特算法

这个操作看起来熟悉吗？事实证明，这正是迪杰斯特拉最短路径算法中的松弛操作！

贝尔曼 - 福特是另一种依赖松弛作为关键操作的最短路径算法。贝尔曼 - 福特甚至比迪杰斯特拉算法更简单：反复遍历所有边，对每条边进行松弛，直到我们得到所有最短路径。

你可能在数据结构课程中（比如加州大学伯克利分校的 CS 61B）实现过迪杰斯特拉算法或贝尔曼 - 福特算法。不幸的是，你写的代码对我们的路由协议来说可能不是很有用。请记住，路由协议必须是分布式的，因为路由器没有网络的全局视图（没有中央控制者）。此外，路由器是异步运行的。没有人强制规定路由器执行松弛操作的顺序，或者路由器发送通告的顺序。

相反，我们一直在设计的路由协议是贝尔曼 - 福特算法的分布式、异步版本。该协议是分布式的，因为我们不是让一台计算机运行整个算法。相反，每个路由器都在计算自己部分的答案（填充自己的转发表），而不需要看到整个图。该协议是异步的，因为路由器可以同时运行算法，不需要控制操作的顺序。

注意：虽然为了简单起见我们只展示了一个目的地，但不要忘记我们的路由协议能够找到到所有目的地的最短路径，就像集中式（单计算机）的迪杰斯特拉算法或贝尔曼 - 福特算法一样。

贝尔曼 - 福特演示

术语说明：当我们向邻居发送像 “我是 R1，我可以到达 A，代价是 5” 这样的消息时，这通常被称为通告或广告一条路由。注意，通告包含三个值：目的地、你的标识（以便邻居可以转发给你），以及从你到目的地的总代价。

再重申一下到目前为止的算法：

当你收到另一个路由器的通告时，你要把目的地到该路由器的代价（这个代价在通告中）加上该路由器到你的链路代价。如果这个总和小于你表格中到目的地的已知最佳距离，你就用新的下一跳（来自通告的另一个路由器的标识）和新的距离（你刚刚计算的总和）替换你转发表中该目的地的条目。

如果你收到另一个路由器的通告，而目的地不在你的转发表中呢？你没有到这个目的地的已知最佳距离，因为你还不知道如何到达这个目的地。在这种情况下，你可以在转发表中添加一个新条目，包含新的目的地，以及来自通告的下一跳和代价。

当你更改转发表时，这意味着你发现了到目的地的一条新路径。为了将这条新路径传播到网络的其他部分，你需要向相邻的路由器通告这条新路径（目的地、你的标识，以及通过你到达的代价）。

有了这个算法，让我们来看一个例子。在这个网络中，我们假设所有边的代价都是 1，因为边没有标记。我们想要在转发表中填充到唯一目的地 A 的路由。

首先，使用静态路由，我们在 R1 的转发表中硬编码一个条目。要到达目的地 A，下一跳是 A 本身，这条路径的代价是 1。

R1 的转发表发生了变化，所以 R1 会创建一个新的通告，包含 3 个值：目的地（A）、路由器的标识（R1），以及通过该路由器到目的地的代价（1）。这个通告会发送给 R1 所有的相邻路由器，即只有 R2。

R2 收到这个通告，并在其转发表中查找与目的地 A 对应的条目。转发表是空的，所以不存在这样的条目。因此，R2 会添加一个新条目，包含 3 个值：目的地（A）、下一跳（来自通告的 R1），以及通过 R1 到目的地的代价（通告中的代价加上到 R1 的链路代价，即 2）。

R2 的转发表发生了变化，所以 R2 会发布一个通告，包含 3 个值：目的地（A）、路由器的标识（R2），以及通过该路由器到目的地的代价（2）。这个通告会发送给 R2 所有的相邻路由器，即 R3 和 R1。

注意，在我们目前的协议中，路由器会向所有邻居发送通告。这意味着 R2 的通告也会发送给 R1。如果你觉得这有问题，请继续关注，我们稍后会重新讨论。

R1 收到这个通告。根据 R1 的转发表，到达 A 的已知最佳方式的代价是 1。通过 R2 的路径代价是 2（来自 R2 的通告）加上 1（到 R2 的链路代价），总共是 3。这是到达 A 的更差方式，所以 R1 会忽略这个通告，保持其转发表不变。

R3 也收到了同样的通告。R3 的转发表是空的，所以 R3 会安装一个新条目，包含 3 个值：目的地（A）、下一跳（来自通告的 R2），以及通过 R2 到目的地的代价（通告中的代价加上 R3-R2 链路的代价，即 3）。

根据我们到目前为止的规则，如果你更新了转发表，你需要向所有邻居发送通告。尽管我们可以看到下一个通告不会改变任何东西，但 R3 没有我们所拥有的网络全局视图，所以 R3 会向所有邻居（即 R2）发送一个通告。通告包含：目的地（A）、下一跳（R3），以及通过该下一跳的代价（3）。

R2 收到这个通告。R2 从转发表中知道到达 A 的方式代价是 2。该通告提供的路径代价是 3（来自通告）加上 1（R2-R3 链路的代价），总代价是 4。这比转发表中的代价更差，所以 R2 忽略该通告。

R2 没有更新其转发表，所以它不会发布通告。此时，不会再发布更多通告，我们可以看到每个路由器都在其转发表中填充了关于如何到达 A 的信息。我们还可以看到，这些转发表一起形成了一个有效的、代价最小的交付树，包含到达 A 的最短路由。

规则 2：来自下一跳的更新

回想一下上一节中的一个路由挑战：网络拓扑可能会发生变化。

假设我们收到 R2 的一个通告，说 A 距离 R2 有 3 个单位。如果我们的表格中没有任何信息，我们会接受这个通告，并记录代价为 1+3=4。

之后，我们可能会收到 R2 的另一个不同通告，说 A 距离 R2 有 8 个单位。根据之前的规则，我们会拒绝这个通告，因为通告的代价（1+8=9）比我们当前的代价（4）更差。

然而，我们必须小心是否要拒绝这个通告。发布通告的路由器（R2）正是我们正在使用的下一跳路由器。R2 试图说：“如果你把我当作下一跳，我到 A 的距离不再是 3，而是 8。” 但我们忽略了这个消息，因为我们没有考虑路径可能发生变化的可能性。

为了修正这一点，我们必须修改我们的更新规则。如果我们收到来自下一跳路由器（我们正在通过其转发数据包的已知最佳路径的路由器）的通告，我们应该将该通告视为更新，并编辑我们的转发表。即使该通告产生了一条更差的路径，我们也应该这样做，因为下一跳可能在告诉我们路径代价已经发生变化并且变得更差了。

注意，当这个新规则适用时，我们不会更新转发表中的目的地或下一跳，只更新距离。在这个例子中，R3 中发往 A 的数据包仍然转发给 R2（相同的目的地，相同的下一跳），但通过 R2 的代价发生了变化。

对于每个目的地：

如果你收到关于该目的地的通告，在以下情况更新表格：
- 目的地不在表格中。
- 通告的代价加上到邻居的链路代价比已知的最佳代价更好。
- 通告来自当前的下一跳。
然后，告诉所有邻居。

为了支持变化的拓扑，路由器会无限期地运行路由协议。

假设我们无限期地运行该协议，且拓扑没有变化。最初，一些松弛操作会成功，转发表会发生变化。最终，当我们找到网络中所有代价最小的路由时，算法会收敛。此时，如果我们继续对边进行松弛，转发表将不会改变。每次松弛都会被拒绝，因为到目标的已知最佳路径都是最短路径，我们永远不会找到更好的路径来替代当前的最短路径。网络在收敛时的状态称为稳态。

之后，假设我们改变拓扑（例如，某个路由器发生故障）。当我们继续运行协议时，由于我们改变了底层图，一些松弛操作可能会再次成功。一段时间后，交付树将再次收敛到新的代价最小的路由，并停止变化，直到下一次拓扑变化。

打个比方，考虑一潭水。在稳态下，没有干扰时，水面是完全平静的。如果你往水里扔一块石头，会有一些涟漪，因为环境在适应你刚刚做出的改变，但一段时间后，水面会再次变得完全平静。

规则 3：重发

回想一下上一节中的另一个路由挑战：数据包可能会被丢弃。

例如，让我们回到 earlier 例子的最开始。R2 和 R3 的转发表是空的，R1 被硬编码了到 A 的路由。如果 R1 发布了一个通告，但数据包被丢弃了怎么办？R2 永远不会收到通告，协议就会失败。

你可以尝试设计一个更复杂的方案来确保可靠性（例如，强制接收者发送确认），但让我们使用一个简单的方法：如果你有要发布的通告，每隔几秒钟重发一次。事实证明，这种简单的方法与我们后来的一些设计选择配合得很好，不需要更复杂的方法。

形式上，协议会定义一个通告间隔。在实践中，30 秒是一个常见的间隔。如果间隔是 X 秒，那么每个通告必须每 X 秒重发一次。

只要我们等待足够长的时间并足够多次地重发数据包，只要链路在某些时候是正常的，链路最终会成功发送通告。如果链路丢弃了每一个数据包，那么通告就无法发送（而且一个成功率为 0% 的链路可能不应该存在于图中）。最终，通过足够的重发，这个协议仍然会收敛。

对于每个目的地：

如果你收到关于该目的地的通告，在以下情况更新表格：
- 目的地不在表格中。
- 通告的代价加上到邻居的链路代价比已知的最佳代价更好。
- 通告来自当前的下一跳。
在表格更新时以及定期（按照通告间隔）向所有邻居发布通告。

注意，间隔重发可以与我们 earlier 的规则结合使用，即每当转发表发生变化时就发送通告。表格变化后立即发送的通告称为触发更新。

如果我们只在间隔时间发送通告，协议仍然会收敛。表格发生变化，我们等待间隔时间结束，然后发送通告。然而，除了间隔更新之外再添加触发更新是一种优化，可以帮助协议更快地收敛。一旦我们知道了更新，我们不妨立即发布，而不必等待间隔时间。

有了这个新规则，一旦网络收敛，每个路由器将继续定期重发通告，但所有通告都会被拒绝，因为我们处于稳态，并且每个人都已经拥有代价最小的路由。

在 earlier 的例子中，网络收敛后，R3 可能会决定重发其通告，目的地为 A，下一跳为 R3，通过 R3 的代价为 3。但 R2 会忽略这个通告，因为其转发表中已经有一条代价为 2 的更优路由（该通告路径的代价为 3 + 1 = 4）。

规则 4：过期

回想一下我们 earlier 的路由挑战：网络拓扑可能会发生变化。特别是，链路和路由器可能会发生故障。如果网络中的某个路由器发生故障，我们的路由可能会变得无效。发生故障的路由器不会告诉我们这个问题（因为它已经故障了），所以我们会被这个无效的路由所困扰。

为了解决这个问题，我们会给每个路由（即每个表条目）一个有限的生存时间（TTL）。这是一个倒计时器，告诉我们这个转发条目还能保留多久。

定期更新帮助我们确认路由仍然存在。如果我们收到来自下一跳的通告，我们可以将 TTL 重置（“重新充电”）到其原始值。

如果网络中出现故障，我们将停止收到定期更新。最终，TTL 会过期。如果 TTL 过期，我们会从表格中删除该条目。直观地说：我们不再收到更新，所以这条路由可能不再有效。

下面是 TTL 工作的一个例子。在这个例子中，我们是 R3。在 t=0 时，我们听到一个通告：“我是 R2，A 距离我有 5 个单位。” 我们的表格中没有 A 的条目，所以我们会接受这条路径，并将其 TTL 设置为 11。注意，这个 TTL 与特定的表条目相关联。如果我们有多个表条目，它们会各自有自己的 TTL。

TTL 为 11 告诉我们，R2 必须在接下来的 11 秒内再向我们确认一次这条路由。否则，这个表条目将被删除。（注意：初始 TTL 为 11 是任意选择的。在实践中，这个数字会由协议或路由器的操作人员设置。）

时间流逝。在 t=1 时，TTL 现在是 10。在 t=2 时，TTL 是 9。在 t=3 时，TTL 是 8。在 t=4 时，TTL 是 7。

在 t=5 时，R2 按周期重发通告：“我是 R2，A 距离我有 5 个单位。” 我们查看表格，意识到 R2 是到 A 的当前下一跳，所以我们应该接受这个通告（根据规则 2）并更新表格。

因为我们收到了这条路由仍然存在的确认，所以 TTL 可以重置回其初始值 11。我们需要在接下来的 11 秒内从 R2 收到这条路由的另一次确认。

假设在 t=6 时，一条链路中断，A 现在无法到达。R2 删除了其到 A 的静态路由，不再发送任何定期更新。

在 t=16 时（距离上次更新 t=5 已经 11 秒），我们表条目中的 TTL 已经减少到 0，所以我们会从表格中删除该条目。

对于每个目的地：

如果你收到关于该目的地的通告，更新表格

并重置 TTL

如果：
- 目的地不在表格中。
- 通告的代价加上到邻居的链路代价比已知的最佳代价更好。
- 通告来自当前的下一跳。
在表格更新时以及定期（按照通告间隔）向所有邻居发布通告。
如果一个表条目过期，删除它。

注意不要混淆路由器必须维护的各种计时器。

通告间隔告诉路由器何时向邻居发布路由。这通常是整个表格的一个单一计时器，所以每当通告间隔计时器过期时，路由器就会发布表格中的所有路由。在上面的例子中，通告间隔计时器是 5 秒，因为 R2 在 t=0 和 t=5 发送了通告。

相比之下，TTL 告诉路由器何时删除一个表条目。每个表条目都有自己独立的 TTL，为该特定条目倒计时。在上面的例子中，初始 TTL 是 11 秒（当我们接受一个通告时重置为 11），并为每个表条目倒计时。

到目前为止，我们有了一个功能基本完整的路由协议！让我们添加一些优化以加快收敛速度。

规则 5：毒化过期路由

等待路由过期是很慢的。为了理解原因，让我们再看一遍 earlier 的演示。

在这个例子中，我们是 R3。假设到 t=5 时，我们已经知道了一条到 A 的路由，通过 R2，这条路由的 TTL 还剩 11 秒。

在 t=6 时，A 到 R2 的链路中断了！这个表条目现在是无效的，因为如果我们将数据包转发给 R2，它们实际上无法到达 A。然而，我们还不知道这个条目是无效的。我们必须再等 10 秒，这条路由才会过期。

同样在 t=6 时，我们收到一个新的通告：“我是 R1，A 距离我有 1 个单位。” 我们查看表格，我们已经有了一条到达 A 的路径，所以我们拒绝这个通告。（注意：对于这个演示来说不重要，但这里我们假设不接受等代价路径。）

要是我们知道我们现有的路由是无效的，我们现在就可以接受这个新的通告了。但相反，我们注定要再等 10 秒使用这条无效的路径。

时间流逝。到 t=11 时（5 秒后），这条无效的路由还有 5 秒的 TTL 剩余。

在 t=11 时，我们收到另一个通告：“我是 R1，A 距离我有 1 个单位。”R1 在重发 earlier 的通告。我们再次查看表格，我们仍然有 A 的条目，所以我们再次拒绝这个通告。

再一次，如果我们能以某种方式知道我们现有的路由是无效的…… 那么我们就可以接受这个新的通告。然而，按照我们当前的方法，我们注定要在剩下的 5 秒内继续使用这条无效的路径。

时间流逝。到 t=16 时（又过了 5 秒），无效路由的 TTL 终于达到 0，我们可以从表格中删除这个条目了。

同样在 t=16 时，R1 再次重发其通告：“我是 R1，A 距离我有 1 个单位。” 最后，我们的表格中没有到 A 的路由了（无效的路由刚刚被删除），所以我们可以接受这个通告。

刚才发生了什么？在 t=6 时，故障发生，我们表格中的条目变得无效。然而，因为这条无效路由的 TTL 还剩 10 秒，我们注定要在接下来的 10 秒内继续使用这条无效的路径。在此期间，所有发往 A 的数据包都会丢失，因为我们会沿着一条无效的路径转发数据包。此外，我们可能会向其他人通告这条无效的路由，导致他们的数据包也丢失。最后，正如我们所看到的，我们可能会拒绝新的路径，认为无效的路径仍然有效。

关键问题是：当出现故障时，故障没有被报告，所以我们被迫依靠超时来删除无效路径。这很慢。有没有办法让我们更早地检测到故障呢？

解决方案是毒化：当出现故障时，如果可能，明确通告一条路径是无效的。

用通俗的话来说，R2 发送的新毒化通告会说：“我是 R2，我不再有到达 A 的方法。” 在协议中，我们通过通告一条代价为无穷大的路径来编码这个消息：“我是 R2，A 距离我无穷远。” 这条无穷大代价的路径代表一条无效的路径。

毒化路径的传播方式与其他任何路径相同。如果我们正在通过 R2 转发数据包，并且收到了来自 R2 的毒化消息，我们会更新我们的转发表，并将代价替换为无穷大（根据规则 2）。我们也可以向我们的邻居通告这条无穷大代价的毒化路径，这样他们也会意识到这条无效的路径。这使得无效路径能够在网络中传播，这比等待路径超时要快得多。

让我们再看一遍 earlier 的演示，但这次对过期路由进行毒化。和之前一样，假设到 t=5 时，我们已经知道了一条到 A 的路由，通过 R2，这条路由的 TTL 还剩 11 秒。

在 t=6 时，A 到 R2 的链路中断了！这个表条目现在是无效的。然而，我们还不知道这个条目是无效的。

根据我们的修改，R2 不会什么都不说，而是向我们发送一个毒化通告：“我是 R2，A 距离我无穷远。” 根据规则 2（接受来自下一跳的通告），我们注意到 R2 是我们的下一跳，所以我们接受这个通告并更新我们的表格。

我们的表条目现在表明，通过 R2 实际上无法到达 A。这个条目和其他任何表条目一样有一个 TTL。此外，我们可以像通告其他任何条目一样，向我们的邻居通告这条无穷大代价的路径。这告诉我们的邻居，我们也无法到达 A 了。

同样在 t=6 时，在我们更新表格后，我们收到一个新的通告：“我是 R1，A 距离我有 1 个单位。” 使用这条路由的距离是 2（1 来自链路，1 来自通告），这比表格中的无穷大更好。我们接受这个通告并更新表格。现在，发往 A 的数据包将通过 R1 而不是 R2 进行路由。

在我们 earlier 的演示中，在 t=6 时，我们被迫等待 10 秒让无效路由过期。多亏了毒化通告，我们能够在 t=6 时立即使那条无效路由失效，并接受新的路径。

有了毒化，我们能够更快地收敛到一条有效的路径。在 t=6 到 t=16 之间，数据包现在可以正确到达 A（而在没有毒化的方法中，这段时间内的数据包会丢失）。此外，由于毒化，我们避免了在那段时间内向其他人传播无效路由。更好的是，我们可以向其他人传播毒化信息，让他们知道通过我们（和 R2）到 A 的路径是无效的。

让我们正式化毒化的规则。毒化来源于两个方面之一：你的一条路由超时，或者你发现了一个本地故障（例如，你的一条链路中断）。当发生这些情况之一时，你可以将相应的表条目更新为无穷大代价，重置 TTL，并向你的邻居通告这个毒化信息。

毒化是如何传播的？当你收到来自当前下一跳的毒化通告时，接受它。你的下一跳在告诉你路由不再存在（类似于规则 2 中通告更差的路径），所以你需要更新你的表格。当你更新表格时，像其他任何表格更新一样重置 TTL。你也像其他任何表格更新一样，向你的邻居通告毒化信息，这样你的邻居也会知道这条无效的路由。

最后一个修改：既然我们的表格中包含了毒化信息，我们必须注意不要沿着毒化的路由转发数据包。如果一个表条目说 A 可以通过 R1 到达，代价是无穷大，这实际上意味着通过 R1 无法到达 A。如果我们收到一个发往 A 的数据包，我们不能将它转发给 R1。

对于每个目的地：

如果你收到关于该目的地的通告，更新表格

并重置 TTL

如果：
- 目的地不在表格中。
- 通告的代价加上到邻居的链路代价比已知的最佳代价更好。
- 通告来自当前的下一跳。包括毒化通告。
在表格更新时以及定期（按照通告间隔）向所有邻居发布通告。
如果一个表条目过期，将该条目毒化并通告它。

规则 6A：水平分割

让我们回到我们最喜欢的运行示例，以展示另一个问题。假设我们处于稳态，转发表中有到 A 的正确最短路由。通告正在定期重发，但所有通告都被拒绝，因为我们处于稳态。

R1-R2 链路中断，R2 的条目过期，因为 R1 停止发送定期通告。R2 现在的转发表是空的。接下来会发生什么？

最终，R3 会向 R2 重发其通告，包含目的地（A）、下一跳（R3），以及通过下一跳的代价（3）。

R2 的表格是空的，所以它接受这个通告，并添加目的地（A）、下一跳（R3），以及通过下一跳的代价（3 + 1 = 4）。

我们创建了一个路由环路！R2 会将数据包转发给 R3，而 R3 会将数据包转发给 R2。

这个问题起初可能很难发现，所以让我们直观地重新表述一下。假设我接受了来自 Alice 的一条路由，这意味着我会将数据包转发给 Alice。如果我之后将这条路由回传给 Alice，会发生什么？如果她接受了这条路由，她最终会将数据包转发给我，而我会将数据包回传给她。

如果网络拓扑从未改变，这个通告是无害的。我向 Alice 提供的路径是从 Alice 到我，再回到 Alice。这条新路径肯定更昂贵，因为它添加了一个不必要的环路，所以 Alice 总会拒绝这个通告。

然而，如果 Alice 失去了她的路由，这个通告就很危险了。现在，我的通告在欺骗 Alice，让她认为她可以向我发送数据包。但是，我的路径依赖于 Alice herself，所以如果她接受了我的路径，我们就会创建一个环路，她向我发送数据包，结果我却把数据包回传给她。关键问题是：Alice 认为我所通告的路径是独立的，绝不会经过 Alice。但实际上，我的路径确实经过 Alice，所以如果她接受了我的路径，她最终会把数据包转发回自己。

为了解决这个问题，我们需要避免向给我们提供路由的人回传该路由。我们绝不想让 Alice 接受一条会把数据包回传给她自己的路由。

这引出了一个解决方案，称为水平分割，即我们永远不会将一条路由回传给给我们提供该路由的人。

对于每个目的地：

如果你收到关于该目的地的通告，更新表格

并重置 TTL

如果：
- 目的地不在表格中。
- 通告的代价加上到邻居的链路代价比已知的最佳代价更好。
- 通告来自当前的下一跳。包括毒化通告。
在表格更新时以及定期（按照通告间隔）向所有邻居发布通告。
- 但不要向提供该路由的下一跳回传。
如果一个表条目过期，将该条目毒化并通告它。

规则 6B：毒性逆转（Poison Reverse）

毒性逆转是另一种避免路由环路的方法。我们可以使用水平分割（split horizon）或毒性逆转中的一种（而非同时使用）来解决之前的问题。

在水平分割中，如果某个邻居向我提供了一条路由，我不会将该路由回传给它。

相比之下，在毒性逆转中，如果某个邻居向我提供了一条路由，我会明确地向其返回毒性通告。换句话说，我会明确告诉它：“不要将数据包转发给我（因为我只会把数据包转发回你那里）。”

让我们再次看演示，不过这次用毒性逆转代替水平分割。和之前一样，先达到稳定状态，然后 R1-R2 链路断开，R2 丢失其表项。

如果我们两种修复方法都不采用，此时 R3 会向 R2 通告其路由，而 R2 会接受一条经过自身的路由。

如果我们采用水平分割，此时 R3 不会向 R2 回传其路由。

在毒性逆转方法中，R3 会明确向 R2 发送一条通告：“我是 R3，到 A 的距离是无穷大。”

R2 没有 A 的表项（它原来的表项已过期），所以会接受这条新的毒性路由。现在，R2 的路由表明确表示无法通过 R3 到达 A。在毒性逆转的帮助下，我们避免了路由环路！

在我们的网络模型中，水平分割和毒性逆转都有助于避免路由环路。更一般地说，如果确实出现路由环路，毒性逆转能更快地消除它们。

例如，假设我们由于某种原因出现了路由环路，R2 和 R3 相互转发数据包。

在水平分割方法中，不会发送毒性通告。R2 从 R3 获得路由，所以不会向 R3 发送任何相关信息。同样，R3 从 R2 获得路由，所以也不会向 R2 发送任何相关信息。环路会一直存在，直到表项过期。在这之前，数据包可能会在环路中丢失。

相比之下，如果我们使用毒性逆转方法，R3 会明确向 R2 发送毒性通告：“我是 R3，到 A 的距离是无穷大。”R2 会接受这条通告（根据规则 2，来自当前下一跳的路由），并更新其路由表，使通过 R3 的路径失效。毒性逆转通告能立即消除路由环路。

对于每个目的地：

如果你收到关于该目的地的通告，在以下情况更新路由表并重置 TTL：
- 该目的地不在路由表中。
- 通告的成本加上到邻居的链路成本，优于已知的最佳成本。
- 通告来自当前下一跳（包括毒性通告）。
当路由表更新时，以及定期（按照通告间隔），向所有邻居发送通告。
- 但不要向当前下一跳回传通告。
- …… 或者，向当前下一跳回传毒性通告。
如果某个表项过期，将该表项标记为毒性并进行通告。

注意，水平分割和毒性逆转是两种选择，你只能选择其中一种（不能同时使用）。要么不对下一跳回传任何信息，要么明确地向下一跳回传毒性通告。

规则 7：计数到无穷大（Count to Infinity）

水平分割或毒性逆转帮助我们避免了长度为 2 的环路（例如 R1 转发给 R2，R2 又转发给 R1）。但我们仍然可能遇到涉及 3 个或更多路由器的路由环路。

来看看原因，考虑这个网络。假设路由表达到稳定状态。R1 和 R2 都转发到 R3，R3 再转发到 A。

A-R3 链路断开了！现在无法到达 A。根据规则 5，R3 更新其路由表，将到 A 的成本设为无穷大，并向 R2 和 R1 发送这条毒性通告。

R2 收到毒性通告后更新其路由表（根据规则 2，接受来自下一跳的通告）。现在，R2 和 R3 都知道无法到达 A。

但发送给 R1 的毒性通告丢失了！R1 没有收到毒性通告，所以仍然认为可以通过 R3 到达 A。（毒性通告之后可能会重发，但在本演示中，所有即将发生的问题都会在毒性通告重发之前发生。）

此时，R2 和 R3 无法到达 A，但 R1 认为自己仍然可以到达 A。

最终，R1 发送通告。R1 到 A 的路径是通过 R3，所以根据水平分割，它不会向 R3 通告。但是，R1 仍然会向 R2 通告：“我是 R1，到 A 的距离是 2。”

R2 没有到达 A 的路径，所以会接受这条路由。现在，R2 错误地认为可以通过成本 3 到达 A。

R2 发送关于其新路由的通告。根据水平分割，R2 不会向 R1 回传通告，但会向 R3 通告：“我是 R2，到 A 的距离是 3。”

R3 没有到达 A 的路径，所以会接受这条路由。现在，R3 错误地认为可以通过成本 4 到达 A。

接下来，R3 向 R1 发送通告（根据水平分割，不会向 R2 发送）：“我是 R3，到 A 的距离是 4。”

R1 会接受这条通告（根据规则 2，来自当前下一跳的通告）并更新其路由表。现在，R1 认为到 A 的成本是 5。

或许你已经看出趋势了。R1 向 R2 通告（根据水平分割，不会向 R3 通告）：“我是 R1，到 A 的距离是 5。”

R2 接受这条通告（根据规则 2），认为到 A 的成本是 6。

R2 向 R3 通告成本 6，R3 现在认为到 A 的成本是 7。

R3 向 R1 通告成本 7，R1 现在认为到 A 的成本是 8。

R1、R2 和 R3 会继续在一个循环中相互发送通告，成本不断增加（根据规则 2，这些都会被接受）。此外，前往 A 的数据包会被困在这些路由器之间的转发环路中。

让我们再重申一下问题。毒性通告没有正确传播到所有主机，所以其中一个路由器的路由表中仍然有一条无效路径。然后，这条无效路径在环路中被通告，规则 2 导致成本不断增加，没有尽头。

为什么水平分割没能拯救我们？记住，水平分割只是阻止路由器向其下一跳回传通告。但在这种情况下，环路长度为 3，我们从未向下一跳回传通告。

（注意：毒性逆转也无法拯救我们。如果 R3 向 R2 通告毒性，R2 会忽略该毒性，因为 R2 的下一跳是 R1，而不是 R3。）

这被称为计数到无穷大问题，我们目前的修复方法（对过期路由进行毒化、水平分割、毒性逆转）都无法解决它。

为了解决这个问题，我们将设置一个最大成本。在 RIP（路由信息协议）中，这个值是 15。所有大于这个最大值的成本（即 16 或更高）都被视为无穷大。

有了这个修复，环路仍然会存在一段时间，但最终所有成本都会达到 16（无穷大）。让我们看看实际过程。

每次通告后，成本都在增加。最终，R1 向 R2 通告：“我是 R1，到 A 的距离是 14。”R2 接受（根据规则 2）并将成本更新为 15。

R2 向 R3 通告：“我是 R2，到 A 的距离是 15。”R3 接受（根据规则 2），但不会将成本更新为 16，而是更新为无穷大。

接下来，R3 向 R1 通告：“我是 R3，到 A 的距离是无穷大。”R1 接受（根据规则 2），现在 R1 的成本也变为无穷大。（注意：这条通告看起来就像毒性通告，尽管无穷大来源于计数到无穷大，而非检测到故障。）

最后，R1 向 R2 通告：“我是 R1，到 A 的距离是无穷大。”R2 接受（根据规则 2），现在所有路由器的成本都为无穷大。

我们再次达到了稳定状态！未来的所有通告都会是无穷大成本，不会改变路由表。最终，无穷大成本的表项都会过期。或者，如果出现另一条到 A 的路由，它会取代无穷大成本的表项。

对于每个目的地：

如果你收到关于该目的地的通告，在以下情况更新路由表并重置 TTL：
- 该目的地不在路由表中。
- 通告的成本加上到邻居的链路成本，优于已知的最佳成本。
- 通告来自当前下一跳（包括毒性通告）。
当路由表更新时，以及定期（按照通告间隔），向所有邻居发送通告。
- 但不要向当前下一跳回传通告。
- …… 或者，向当前下一跳回传毒性通告。
- 任何大于或等于 16 的成本都被通告为无穷大。
如果某个表项过期，将该表项标记为毒性并进行通告。

事件驱动更新（Eventful Updates）

路由器可能需要发送通告的情况有三种：

当路由表发生变化时发送通告。这些被称为触发更新。路由表可能在以下情况发生变化：接受新的通告、添加新链路（例如新的静态路由）、链路断开（例如路由被毒化）。
定期发送通告，每隔一个通告间隔发送一次。
当某个表项过期（并被毒性表项取代）时发送通告。

注意，触发更新是一种优化。我们不必在路由表每次变化时都发送通告，只需等待下一个通告间隔再发送变化信息即可。这种协议仍然是正确的。然而，触发更新（加上定期更新）有助于我们的协议更快地收敛到正确的路由，因为我们会在获知新信息的那一刻就进行传播。