本文译自 Distance-Vector Protocols
，依照 CC BY-SA 4.0
许可发布
。 中文翻译，保留原文结构与图表引用。
算法概述
在本节中，我们将设计一种距离向量协议（distance-vector protocol），它是三类路由算法之一（另外两类是链路状态和路径向量）。
距离向量协议在互联网和 ARPANET（互联网的前身）中有着悠久的历史。典型的距离向量协议是路由信息协议（Routing Information Protocol，RIP），而我们将设计的 D-V 协议与 RIP 有许多相似之处。
为了直观理解本节将研究的路由协议，请考虑以下网络。
一开始，每台路由器的转发表（forwarding table）都是空的。我们的目标是填充每台路由器的转发表，使数据包可以从任何地方路由到目的地 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 的消息。
如果有多个目的地呢？我们可以重复运行同一个算法，每个目的地运行一次。于是，转发表将包含多个表项，每个目的地对应一个表项。
为简单起见，本讲义将只关注一个目的地，但我们设计的协议可以扩展到多个目的地。
{: .blue}
回顾一下目前为止的协议。
对每个目的地：
如果听说有一条通往该目的地的路径，就更新表。
然后告诉你的所有邻居。
通告与消息的方向
在这个协议中，很容易混淆通告和消息的发送方向。
关于如何到达 A 的通告从 A 开始向外传播。例如，B 向 D 发出通告：“我是 B，发往 A 的消息可以通过我发送。”
相比之下，实际发往 A 的消息是朝 A 向内发送的。例如，一条消息可能从 D 出发，在前往 A 的途中被发送给 B。
通告的方向恰好与消息本身的方向相反。注意不要把通告与实际消息混淆！
规则 1：Bellman-Ford 更新
如果有多条路径可以到达 A 呢？
在这种情况下，R3 和 R4 都会通告自己可以到达 A。R5 应选择把数据包转发给 R3 还是 R4？
回想一下，我们的目标是找到贯穿网络的最低开销路由。为了让路由器从多条被通告的路径中选出开销最低的一条，我们还需要在通告中包含开销。
R3 的通告现在是：“我是 R3，我能以开销 3 到达 A。”
R4 的通告现在是：“我是 R4，我能以开销 2 到达 A。”
现在，R5 注意到 R4 提供的路径更短，于是决定通过 R4 转发数据包。
我们将用转发表记住到目的地的当前已知最优开销（以及相应的下一跳）。转发表的每个表项现在告诉我们：目的地、该目的地的下一跳，以及经由该下一跳到达目的地的开销。
注意：严格来说，转发表存储键值对，把每个目的地映射到一个包含下一跳和距离的二元组。为简单起见，我们将表画成 3 列。
R5 不一定会同时听到两条路径，因此需要更精确地说明听到新路径时会发生什么。听到一条路径时有三种可能：
如果表中没有到该目的地的路径，就接受这条路径。如果我没有办法到达 A，就应接受任何被提供的路径。
如果新路径（我们听到的）比当前已知最优路径（转发表中的）更好，就应接受新路径，并用它替换表中的旧路径。
如果新路径比当前已知最优路径更差，就应忽略新路径，继续使用表中的路径。
{: .blue}
回顾一下目前为止的协议。
对每个目的地：
如果听说有一条通往该目的地的路径，则在以下情况下更新表：
目的地不在表中。
通告的开销优于当前已知最优开销。
然后告诉你的所有邻居。
如何知道新路径更好还是更差？必须小心，因为并非所有链路的开销都相同。当有人通告一条路径时，经由该路径的开销实际上是两个数之和：从你到邻居的链路开销，加上从邻居到目的地的开销（由邻居通告）。
举个具体例子，假设我们听到：“我是 R1，A 距我为 5。”这条新路径的开销实际上是 1（我们到 R1 的链路开销）加 5（通告中 R1 到 A 的开销），即 6。
稍后，我们可能听到：“我是 R2，A 距我为 3。”只看通告中的开销是不对的。在这种情况下，新路径的开销实际上是 10（我们到 R2 的链路开销）加 3（通告中 R2 到 A 的开销），即 13。这个开销并不优于当前已知最优开销 6，因此不更新表。数据包仍被转发给 R1。
{: .blue}
回顾一下目前为止的协议。
对每个目的地：
如果听说有一条通往该目的地的路径，则在以下情况下更新表：
目的地不在表中。
通告的开销加上到邻居的链路开销，优于当前已知最优开销。
然后告诉你的所有邻居。
对于听到的每个通告，我们都要比较两个数。一个是表中的当前已知最优开销。另一个是到邻居的链路开销与邻居通告的从邻居到目的地的开销之和。如果后者更小，我们就采用新路径并放弃旧路径。
规则 1：分布式 Bellman-Ford 算法
这个操作看起来熟悉吗？事实证明，这恰好就是 Dijkstra 最短路径算法中的松弛（relaxation）操作！
Bellman-Ford 是另一种以松弛为关键操作的最短路径算法。Bellman-Ford 甚至比 Dijkstra 更简单：反复遍历所有边，对每条边执行松弛，直到得到所有最短路径。
你可能曾在数据结构课程（如加州大学伯克利分校的 CS 61B）中实现过 Dijkstra 或 Bellman-Ford。遗憾的是，你写的代码对我们的路由协议并没有太大用处。请记住，路由协议必须是分布式的，因为路由器没有网络的全局视图（不存在中央主脑）。此外，路由器异步运行。没有人强制规定路由器执行松弛操作的顺序，或发送通告的顺序。
相反，我们一直在设计的路由协议是 Bellman-Ford 算法的分布式异步版本。该协议是分布式的，因为我们没有让一台计算机运行整个算法。每台路由器都在看不到完整图的情况下计算答案中属于自己的部分（填充自己的转发表）。该协议是异步的，因为所有路由器可以同时运行算法，无须控制操作顺序。
注意：虽然为简单起见我们只展示一个目的地，但别忘了，我们的路由协议将能够找到通往所有目的地的最短路径，就像集中式（单机）Dijkstra 或 Bellman-Ford 算法一样。
Bellman-Ford 演示
术语说明：当我们向邻居发送“我是 R1，我能以开销 5 到达 A”这样的消息时，这通常称为 通告（announcing） 或 宣告（advertising） 一条路由。注意，通告包含三个值：目的地、你的身份（以便邻居转发给你），以及从你到目的地的总开销。
再把目前的算法复述一遍：
收到另一台路由器的通告时，把目的地到另一台路由器的开销（该开销在通告中）与另一台路由器到你的链路开销相加。如果这个和小于表中到目的地的当前已知最优距离，就把该目的地的转发表项替换为新的下一跳（通告中另一台路由器的身份）和新的距离（刚刚算出的和）。
如果收到另一台路由器的通告，而目的地不在转发表中呢？你没有到该目的地的当前已知最优距离，因为还不知道如何到达它。此时，可以向转发表添加一个新表项，其中包含新目的地，以及通告给出的下一跳和开销。
当转发表发生变化时，意味着你发现了一条通往目的地的新路径。为了把新路径传播给网络其余部分，需要向相邻路由器通告这条新路径（目的地、你的身份和经由你的开销）。
记住这个算法，让我们演练一个例子。在这个网络中，因为边没有标注，所以假设所有边的开销都是 1。我们要用通往唯一目的地 A 的路由填充转发表。
首先，通过静态路由，我们在 R1 的转发表中硬编码一个表项。要到达目的地 A，下一跳就是 A 本身，这条路径的开销为 1。
R1 的转发表发生了变化，因此 R1 会创建一条包含 3 个值的新通告：目的地（A）、路由器的身份（R1），以及经由该路由器到目的地的开销（1）。该通告被发送给 R1 的所有相邻路由器，也就是只有 R2。
R2 收到通告，并在转发表中查找与目的地 A 对应的表项。转发表为空，因此不存在这样的表项。所以，R2 将添加一个包含 3 个值的新表项：目的地（A）、下一跳（通告中的 R1），以及经由 R1 到目的地的开销（2，即通告中的开销与到 R1 的链路开销之和）。
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 的转发表为空，因此会安装一个包含 3 个值的新表项：目的地（A）、下一跳（通告中的 R2），以及经由 R2 到目的地的开销（3，即通告中的开销与 R3-R2 链路开销之和）。
根据目前的规则，如果更新了转发表，就需要向所有邻居发送通告。尽管我们看得出接下来的通告不会改变任何东西，但 R3 并没有我们所拥有的网络全局视图，因此 R3 会向其所有邻居（即 R2）发送通告。通告包含：目的地（A）、下一跳（R3）和经由该下一跳的开销（3）。
R2 收到该通告。转发表告诉 R2 有一条开销为 2 的路径可到达 A。通告提供的路径开销为 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 的开销改变了。
{: .blue}
回顾一下目前为止的协议。
对每个目的地：
如果听到关于该目的地的通告，则在以下情况下更新表：
目的地不在表中。
通告的开销加上到邻居的链路开销，优于当前已知最优开销。
通告来自当前下一跳。
然后告诉你的所有邻居。
为支持不断变化的拓扑，路由器会无限期运行路由协议。
假设协议无限期运行，但拓扑没有变化。最初，一些松弛会成功，转发表会发生变化。最终，当我们找到贯穿网络的所有最低开销路由时，算法将收敛（converge）。此时，即使继续对边执行松弛，转发表也不会改变。每次松弛都会被拒绝，因为通往目标的当前已知最优路径都已是最短路径，我们永远找不到更好的路径来替换当前最短路径。网络收敛时的状态称为稳态（steady state）。
之后，假设我们改变拓扑（例如某台路由器发生故障）。随着协议继续运行，因为底层图已经改变，一些松弛可能再次成功。一段时间后，交付树会再次收敛到新的最低开销路由，并停止变化，直到下次拓扑改变。
打个比方，想象一池水。在稳态下，没有扰动时，水面完全静止。如果向水中扔一块石头，环境会在适应刚刚发生的变化时产生一些涟漪，但过一段时间，水面会再次完全静止。
规则 3：重新发送
回想上一节的另一项路由挑战：数据包可能被丢弃。
例如，让我们倒回先前例子的最开始。R2 和 R3 的转发表为空，R1 则已用硬编码的到 A 路由完成更新。如果 R1 发出通告，但数据包被丢弃了呢？R2 永远听不到通告，协议便会失败。
你可以尝试设计更复杂的机制来保证可靠性（例如强制接收方发送确认），但我们采用一种简单方法：如果有通告要发，就每隔几秒重新发送一次。事实证明，这种简单方法与我们后续的一些设计选择配合良好，无须更复杂的机制。
严格来说，协议会定义一个通告间隔（advertisement interval）。实践中常用 30 秒。如果间隔为 X 秒，则每条通告都必须每隔 X 秒重新发送一次。
只要等待足够久并把数据包重发足够多次，只要链路有时能工作，它最终就会成功发送通告。如果链路丢弃每一个数据包，通告便不可能发送出去（而且成功率为 0% 的链路或许本来就不应出现在图中）。最终，经过足够多次重发，该协议仍会收敛。
{: .blue}
回顾一下目前为止的协议。
对每个目的地：
如果听到关于该目的地的通告，则在以下情况下更新表：
目的地不在表中。
通告的开销加上到邻居的链路开销，优于当前已知最优开销。
通告来自当前下一跳。
在表更新时以及定期（通告间隔）向所有邻居通告。
注意，按间隔重新发送可以与先前的规则配合使用；先前规则要求每当转发表改变时发送通告。变化后立即发送的通告称为触发更新（triggered updates）。
即使只按间隔发送通告，协议仍会收敛。表发生变化，我们等待间隔结束，然后发出通告。不过，在间隔更新之外加入触发更新是一种可以帮助协议更快收敛的优化。一旦知道更新，不妨立即通告，无须等待间隔。
采用这条新规则后，一旦网络收敛，每台路由器仍会定期重新发送通告，但没有通告会被接受，因为网络处于稳态，每台路由器都已经拥有最低开销路由。
在先前例子中，网络收敛后，R3 可能决定重新发送通告，其中目的地为 A、下一跳为 R3、经由 R3 的开销为 3。但 R2 会忽略该通告，因为它的转发表已有开销更低、为 2 的路由（通告路径的开销是 3 + 1 = 4）。
规则 4：过期
回想先前的路由挑战：网络拓扑可能变化。尤其是链路和路由器可能发生故障。如果网络中的路由器发生故障，我们的路由可能变得无效。发生故障的路由器不会告诉我们这个问题（因为它已经故障），因此我们会困在这条无效路由上。
为解决这个问题，我们给每条路由（即每个表项）一个有限的生存时间（time to live，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 时为 9；t=3 时为 8；t=4 时为 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，因此我们将从表中删除该表项。
{: .blue}
回顾一下目前为止的协议。
对每个目的地：
如果听到关于该目的地的通告，则在以下情况下更新表并重置 TTL：
目的地不在表中。
通告的开销加上到邻居的链路开销，优于当前已知最优开销。
通告来自当前下一跳。
在表更新时以及定期（通告间隔）向所有邻居通告。
如果表项过期，则将其删除。
注意不要混淆路由器必须维护的各种计时器。
通告间隔告诉路由器何时向邻居通告路由。通常整个表共用一个计时器，因此每当通告间隔计时器到期，路由器就通告表中的所有路由。在上例中，通告间隔计时器为 5 秒，因为 R2 在 t=0 和 t=5 时发送了通告。
相比之下，TTL 告诉路由器何时删除表项。每个表项都有独立的 TTL，为该特定表项倒计时。在上例中，初始 TTL 为 11 秒（接受通告时重置为 11），并针对每个表项倒计时。
至此，我们已经有了一个基本可用的路由协议！下面添加一些优化，使其更快收敛。
规则 5：毒化过期路由
等待路由过期很慢。为了理解原因，让我们重看先前的演示。
在这个例子中，我们是 R3。假设到 t=5 时，我们已经学到一条经 R2 到 A 的路由，并且该路由还剩 11 秒 TTL。
t=6 时，A 到 R2 的链路中断了！表项现在已经失效，因为如果把数据包转发给 R2，它们实际上无法到达 A。然而我们还不知道该表项已经失效，必须再等 10 秒让这条路由过期。
同样在 t=6，我们收到一条新通告：“我是 R1，A 距我为 1。”查看表后发现已有一种到达 A 的方式，因此拒绝该通告。（注意：这对本演示并不重要，但这里假设不接受等开销路径。）
要是我们知道现有路由已经失效，就能立即接受这条新通告。但事实上，我们注定还要使用这条失效路径 10 秒。
时间流逝。到 t=11（五秒后），失效路由仍有 5 秒 TTL。
t=11 时，我们收到另一条通告：“我是 R1，A 距我为 1。”R1 正在重发先前的通告。我们再次查看表，仍有 A 的表项，因此再次拒绝该通告。
同样，要是有办法知道现有路由已经失效……我们就能接受这条新通告。然而按当前做法，我们注定还要在剩余 5 秒内继续使用失效路径。
时间流逝。到 t=16（五秒后），失效路由的 TTL 终于达到 0，我们可以从表中删除该表项。
同样在 t=16，R1 再次重发通告：“我是 R1，A 距我为 1。”终于，我们的表中没有到 A 的路由了（失效路由刚被删除），所以可以接受该通告。
刚才发生了什么？t=6 时故障发生，表中的表项变得无效。然而，由于失效路由还剩 10 秒 TTL，我们注定还要使用它 10 秒。在此期间，任何发往 A 的数据包都会丢失，因为我们会沿失效路径转发数据包。此外，我们还可能向他人通告这条失效路由，导致他们也丢失数据包。最后，如我们所见，我们可能以为失效路径仍有效而拒绝新路径。
这里的关键问题是：发生故障时，没有人报告故障，因此我们被迫依赖超时来删除失效路径。这很慢。有没有办法更早检测到故障？
解决方案是毒化（poison）：发生故障时，如果可能，就明确通告某条路径已经失效。
用自然语言表示，R2 发送的新毒化通告是：“我是 R2，我已经无法到达 A。”在协议中，我们通过通告一条开销为无穷大的路径来编码该消息：“我是 R2，A 距我为无穷大。”这条无穷开销路径代表一条失效路径。
毒化路径像其他路径一样传播。如果我们把数据包转发给 R2，并收到 R2 的毒化消息，就更新转发表并把开销替换为无穷大（按照规则 2）。还可以向邻居通告这个无穷开销的毒化信息，让他们也得知该路径已失效。这使无效路径的信息能在网络中传播，可能比等待路径超时快得多。
让我们重看先前的演示，但这次在路由到期时进行毒化。和之前一样，假设到 t=5 时，我们已学到一条经 R2 到 A 的路由，并且还剩 11 秒 TTL。
t=6 时，A 到 R2 的链路中断！表项现在已失效，但我们此刻还不知道。
经过修改后，R2 不再什么都不说，而是向我们发送毒化通告：“我是 R2，A 距我为无穷大。”按照规则 2（接受来自下一跳的通告），我们注意到 R2 是下一跳，于是接受通告并更新表。
现在，表项编码了 A 经由 R2 实际上不可达这一事实。与其他表项一样，该表项也有 TTL。我们也可以像通告其他表项那样，向邻居通告这条无穷开销路径。这会告诉邻居，我们也无法再到达 A。
同样在 t=6，表更新后，我们收到一条新通告：“我是 R1，A 距我为 1。”使用该路由的距离为 2（链路为 1，通告为 1），优于表中的无穷大。我们接受通告并更新表。现在，发往 A 的数据包经 R1 而不是 R2 路由。
在先前演示中，t=6 时我们被迫等待失效路由过期 10 秒。多亏毒化通告，我们得以在 t=6 立即使该失效路由无效并接受新路径。
借助毒化，我们更快地收敛到有效路径。t=6 到 t=16 之间，数据包现在能够正确到达 A（而在无毒化方法中，这段时间的数据包会丢失）。此外，得益于毒化，我们避免在这段时间向他人传播失效路由。更好的是，我们可以向他人传播毒化信息，告知他们经由我们（以及 R2）到 A 的路径已经失效。
下面形式化说明毒化规则。毒化来自两个来源之一：你的一条路由超时，或者你注意到本地故障（例如某条链路中断）。发生其中任一情况时，可以把相应表项的开销更新为无穷大、重置 TTL，并向邻居通告该毒化信息。
毒化如何传播？收到当前下一跳的毒化通告时，接受它。下一跳是在告诉你路由已不存在（类似于规则 2 中通告更差路径），所以需要更新表。更新表时，像其他表更新一样重置 TTL。还要像其他表更新一样向邻居通告毒化信息，让邻居也知道这条失效路由。
最后一项修改：既然表中现在包含毒化信息，就必须小心，不要沿毒化路由转发数据包。如果表项显示经 R1 到 A 的开销为无穷大，实际上意味着经 R1 无法到达 A。收到目的地为 A 的数据包时，不能把它转发给 R1。
{: .blue}
回顾一下目前为止的协议。
对每个目的地：
如果听到关于该目的地的通告，则在以下情况下更新表并重置 TTL：
目的地不在表中。
通告的开销加上到邻居的链路开销，优于当前已知最优开销。
通告来自当前下一跳。包括毒化通告。
在表更新时以及定期（通告间隔）向所有邻居通告。
如果表项过期，将该表项变为毒化表项并通告它。
规则 6A：水平分割
让我们再次回到最常用的贯穿示例，以说明另一个问题。假设网络处于稳态，转发表中有到 A 的正确最短路由。通告被定期重发，但因为处于稳态，所有通告都被拒绝。
R1-R2 链路中断，而由于 R1 停止发送定期通告，R2 的表项过期。R2 现在的转发表为空。接下来会怎样？
最终，R3 向 R2 重发通告，其中目的地为（A）、下一跳为（R3）、经下一跳的开销为（3）。
R2 的表为空，因此接受通告并添加目的地（A）、下一跳（R3）和经下一跳的开销（3 + 1 = 4）。
我们制造了一个路由环路（routing loop）！R2 会把数据包转发给 R3，而 R3 会把数据包转发给 R2。
这个问题起初可能很难察觉，因此让我们直观地重新表述。假设我接受了 Alice 的一条路由，这意味着我会把数据包转发给 Alice。如果随后又把这条路由提供给 Alice，会发生什么？如果她接受该路由，她会把数据包转发给我，而我又会把数据包转回给她。
如果网络拓扑从不变化，这条通告没有危害。我提供给 Alice 的路径从 Alice 出发，到我这里，再回到 Alice。由于添加了不必要的环路，这条新路径肯定更昂贵，因此 Alice 总会拒绝该通告。
然而，如果 Alice 丢失了她的路由，这条通告就很危险。此时我的通告会让 Alice 误以为她可以把数据包发给我。但是我的路径依赖 Alice 本人，所以如果她接受该路径，就会形成一个环路：她把数据包发给我，而我马上又把它发回给她。关键问题是：Alice 以为我通告的路径是独立的，绝不会经过 Alice；但实际上我的路径确实经过 Alice，因此如果她接受我的路径，最终会把数据包转发回自己。
为解决这个问题，需要避免向 Alice 提供已经涉及她本人的路由。我们绝不希望 Alice 接受一条会把数据包发回自己的路由。
这引出一种称为水平分割（split horizon）的解决方案：绝不把一条路由通告回提供该路由的人。
{: .blue}
回顾一下目前为止的协议。
对每个目的地：
如果听到关于该目的地的通告，则在以下情况下更新表并重置 TTL：
目的地不在表中。
通告的开销加上到邻居的链路开销，优于当前已知最优开销。
通告来自当前下一跳。包括毒化通告。
在表更新时以及定期（通告间隔）向所有邻居通告。
但不要通告回下一跳。
如果表项过期，将该表项变为毒化表项并通告它。
规则 6B：毒性逆转
毒性逆转（poison reverse）是另一种避免路由环路的方法。可以用水平分割或毒性逆转解决先前的问题（但不能同时使用两者）。
在水平分割中，如果有人给我一条路由，我就不把这条路由通告回去。
相比之下，在毒性逆转中，如果有人给我一条路由，我会明确向其通告毒化信息。换言之，我明确告诉对方：“不要把数据包转发给我”（因为我只会把它们转发回给你）。
让我们再次查看演示，但这次使用毒性逆转而不是水平分割。和之前一样，网络先达到稳态，然后 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 的路径失效。毒性逆转通告立即消除了路由环路。
{: .blue}
回顾一下目前为止的协议。
对每个目的地：
如果听到关于该目的地的通告，则在以下情况下更新表并重置 TTL：
目的地不在表中。
通告的开销加上到邻居的链路开销，优于当前已知最优开销。
通告来自当前下一跳。包括毒化通告。
在表更新时以及定期（通告间隔）向所有邻居通告。
但不要通告回下一跳。
……或者，向下一跳通告毒化信息。
如果表项过期，将该表项变为毒化表项并通告它。
注意，水平分割和毒性逆转是两种选择，只能选其中一种（不能同时使用）。你要么不向下一跳发送任何信息，要么明确向下一跳通告毒化信息。
规则 7：计数到无穷
水平分割或毒性逆转帮助我们避免了长度为 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），并认为能以开销 6 到达 A。
R2 向 R3 通告开销 6，R3 现在认为能以开销 7 到达 A。
R3 向 R1 通告开销 7，R1 现在认为能以开销 8 到达 A。
R1、R2 和 R3 会继续循环地互相发送通告，开销不断增大（按照规则 2，这些通告都会被接受）。此外，发往 A 的数据包会陷在这些路由器之间的转发环路中。
让我们再次表述这个问题。毒化信息没有正确传播到所有主机，因此其中一台路由器的表中仍有一条失效路径。随后，这条失效路径在环路中被通告，而规则 2 使开销不断增大，看不到尽头。
为什么水平分割没有拯救我们？请记住，水平分割只阻止路由器向其下一跳发回通告。但在本例中，环路长度为 3，而且我们从未向下一跳发回通告。
（注意：毒性逆转也救不了我们。如果 R3 向 R2 通告毒化信息，R2 会忽略它，因为 R2 的下一跳是 R1，而不是 R3。）
这称为计数到无穷（count-to-infinity）问题，而我们目前的所有修复（毒化过期路由、水平分割、毒性逆转）都无法解决它。
为解决这个问题，我们将强制设定最大开销。在 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 的路由，它会替换无穷开销表项。
{: .blue}
回顾一下目前为止的协议。
对每个目的地：
如果听到关于该目的地的通告，则在以下情况下更新表并重置 TTL：
目的地不在表中。
通告的开销加上到邻居的链路开销，优于当前已知最优开销。
通告来自当前下一跳。包括毒化通告。
在表更新时以及定期（通告间隔）向所有邻居通告。
但不要通告回下一跳。
……或者，向下一跳通告毒化信息。
任何大于或等于 16 的开销都被通告为无穷大。
如果表项过期，将该表项变为毒化表项并通告它。
事件更新
路由器可能在三种情况下发送通告：
在表发生变化时发送通告。这些称为触发更新。当我们接受新通告、添加新链路（例如新的静态路由），或者链路中断（例如路由被毒化）时，表可能发生变化。
定期发送通告，每个通告间隔发送一次。
当表项过期（并被毒化信息取代）时发送通告。
注意，触发更新是一种优化。我们可以不在每次表变化时通告，而是等待下一个通告间隔再通告变化；协议仍然正确。不过，在定期更新之外使用触发更新，可以帮助协议更快地收敛到正确路由，因为我们在学到新信息的瞬间就会传播它。
howIdobetter