CS168

链路状态协议

链路状态协议简介

回想一下，根据底层算法的不同，路由协议分为不同的类别。在上一节中，我们了解了距离矢量类协议。在本节中，我们将讨论另一大类协议 ——链路状态协议。

还记得，协议也可以分为为外部网关协议（在网络之间运行）和内部网关协议（在网络内部运行）。与距离矢量协议一样，链路状态协议通常是内部网关协议。

IS-IS（中间系统到中间系统）和 OSPF（开放式最短路径优先）是链路状态协议的两个主要例子。两者如今都被广泛部署。

链路状态概述

距离矢量协议执行的是分布式、协作式计算。每个节点根据邻居计算的结果，计算自己的那部分解决方案。所有节点的计算共同构成完整的解决方案。每个节点在计算中只需要来自邻居的本地信息（节点不知道完整的网络拓扑图）。

相比之下，链路状态协议执行的是本地计算。每个节点独立地、从头开始计算完整的解决方案，不使用来自邻居的任何计算结果。然而，要做到这一点，每个节点需要来自网络各个部分的全局信息。

用一句话概括链路状态协议：每个路由器都了解完整的网络拓扑图，然后在该图上运行最短路径算法来填充转发表。

我们需要实现两个主要步骤。首先，路由器需要以某种方式了解完整的网络拓扑图，包括每条链路的状态（通或断）、每条链路的成本以及每个目的地的位置。

然后，路由器需要在该拓扑图上运行某种算法，以了解如何将数据包转发到每个目的地。

我们先考虑第二步（最短路径），然后再考虑第一步（了解拓扑图）。

路径计算

一旦路由器拥有了网络的全局视图，就可以使用某种最短路径算法轻松计算网络中的路径。

具体来说，路由器应该计算到每个目的地的最短路径。然后，对于每个目的地，路由器记录最短路径上的下一跳，就像在距离矢量协议中一样。转发过程中不需要路径的其余部分。

这一步可以使用许多单源最短路径算法。例如，贝尔曼 - 福特算法（串行版本，没有任何距离矢量的修改）和迪杰斯特拉算法都能有效地计算从单个源到所有目的地的最短路径。我们也可以考虑其他替代方案，如广度优先搜索，或可以并行运行的算法。

我们需要注意的一点是路由器之间的不一致性。

请记住，每个路由器都独立计算最短路径，并据此决定下一跳。每个路由器只控制自己的下一跳，无法影响下一跳路由器的行为。

例如，假设 R3 计算出到 A 的最短路径，决定将数据包转发到 R2。然后，R2 计算出到 A 的最短路径，决定将数据包转发到 R3。两个路由器都计算出了有效的最短路径，但它们的决定导致了路由环路。

为避免这个问题，我们必须确保所有路由器产生的转发决策彼此兼容。所有路由器产生兼容决策需要满足哪些条件呢？

所有路由器必须就网络拓扑达成一致。假设一条链路发生故障，但只有一个路由器知道。那么不同的路由器将在完全不同的拓扑图上计算路径，可能会产生不一致的结果。
所有路由器都通过路径找到成本最低的路径。如果某个路由器由于某种原因偏好成本更高的路径，我们会得到不一致的结果。
所有成本都是正数。负成本可能会产生负权重循环。
所有路由器使用相同的平局决胜规则。如果我们假设最短路径是唯一的，那么前两个条件就足以确保每个路由器选择相同的路径。这个条件进一步确保，如果有多个路径并列最短，所有路由器都会选择同一条。

有了这四个条件，即使路由器使用不同的最短路径算法，它们仍然会计算出相同的路径，并产生兼容的决策。但在实践中，为简单起见，路由器通常都使用相同的算法。

了解拓扑图

路由器如何了解完整的网络拓扑图呢？首先，我们需要了解我们的邻居是谁（包括路由器和目的地）。然后，我们需要将该信息分发到整个网络。此外，路由器还需要将接收到的所有信息整合为一个拓扑图。

为了发现邻居，每个路由器都会向其所有邻居发送 Hello 消息。

例如，在这个网络中，R2 向其两个邻居发送消息：“你好，我是 R2。” 现在，R1 知道它与 R2 相连，R3 也知道它与 R2 相连。同样，R1 向 R2 发送 Hello 消息，所以 R2 现在知道了 R1。同样，R3 向 R2 发送 Hello 消息，所以 R2 也知道了 R3。

结果，每个路由器都知道了自己的直接邻居。请注意，R1 不知道 R3，因为 R1 和 R3 不是邻居。

我们还想知道链路是否中断。为了支持这一点，我们会定期重新发送 Hello 消息。如果某个邻居停止发送 Hello 消息（例如，错过了一定数量的 Hello 消息），我们就假设该邻居已消失。

既然我们知道了自己的邻居，就应该向所有路由器宣布这一事实。为了进行全局宣布，我们将公告发送给所有邻居。此外，如果我们收到一条公告，我们也应该将其发送给所有邻居。这确保了每条消息都能在整个网络中传播。这被称为在网络中泛洪信息。如果任何信息发生变化（例如，某个邻居消失），我们也应该泛洪该信息。

我们还需要确保消息不会丢失。否则，其他路由器可能会错过更新，从而在错误的拓扑图上计算路径。为解决这个问题，我们使用与距离矢量协议中相同的技巧，定期重新发送消息。只要链路正常工作，经过足够多次尝试后，我们的消息应该能被发送出去。

避免无限泛洪

我们必须小心如何在网络中泛洪公告。

R2 了解到一些信息，并向其邻居 R3 宣布。当 R3 收到该信息时，它向其邻居 R2 宣布。当 R2 收到该信息时，它又向其邻居 R3 宣布。这两个路由器陷入了相互发送公告的循环，浪费带宽，尽管没有新信息。

请注意，这与为了可靠性而定期重新发送消息不同。为了可靠性，我们可能每 5 秒重新发送一次消息。而在这个无限循环中，路由器接收并重新发送重复的公告的速率是最大的（例如，每秒数百万次）。

如果我们的网络包含环路，问题会更严重：

时间步 1：R1 向 R2 和 R3 广播。

时间步 2：R2 向 R1 和 R3 广播。R3 向 R1 和 R2 广播。

时间步 3：R1、R1、R2 和 R3 分别向（R2、R3）、（R2、R3）、（R1、R3）和（R1、R2）广播。请注意，R1 在时间步 2 收到了两条消息，所以它进行了两次广播。

时间步 4：R1、R1、R2、R2、R2、R3、R3、R3 分别向（R2、R3）、（R2、R3）、（R1、R3）、（R1、R3）、（R1、R3）、（R1、R2）、（R1、R2）、（R1、R2）广播。

时间步 5：R1 进行 6 次广播，R2 进行 5 次广播，R3 进行 5 次广播。

所有新信息在时间步 1 就已被了解。但是，所有路由器都在不断重新发送相同的信息，重复的公告呈指数级增长，最终会淹没网络。

为解决这个问题，我们需要确保路由器不会重复发送相同的信息。

当我们第一次看到一条消息时，将该消息发送给所有邻居，并记录我们已经看到过该消息。（我们无论如何都需要记录这条消息，因为我们要使用该信息来构建网络拓扑图。）然后，如果我们再次看到相同的消息，就不会再发送第二次。

为了唯一标识一条消息，我们可以引入时间戳（或其他每个消息独有的计数器）。

现在，回到前面的例子：

时间步 1：R1 向 R2 和 R3 广播。

时间步 2：R2 向 R1 和 R3 广播。R3 向 R1 和 R2 广播。

时间步 3：此时，R1、R2 和 R3 都已经看到过该消息，所以它们不会再发送。不会再发送更多的重复消息。

请注意，通过这种修改，仍然可能会发送重复消息，但我们避免了重复消息的无限发送。

收敛

在每个路由器都了解完整的网络拓扑并相应地计算出转发表后，链路状态协议会收敛到有效的最低成本路由状态。收敛依赖于每个节点使用相同的拓扑图。收敛后，只要网络拓扑不发生变化，路由状态就保持有效。

一旦网络拓扑发生变化，网络可能需要一些时间才能再次收敛。我们必须等待变化被检测到（例如，链路故障）。然后，我们必须等待新信息在网络中传播，以及路由器重新计算转发表条目。在网络收敛过程中，我们可能处于无效的路由状态，因为一些路由器使用旧拓扑图，而另一些使用更新后的拓扑图。路由状态可能会出现死端、环路或非最低成本路径。

例如，假设 R3-A 链路发生故障。R3 知道这一点，但其他路由器不知道。R3 会将数据包转发到 R1。然而，R1 仍然会将数据包转发到 R3。

链路状态协议的许多复杂性在于细节。为了确保更快的收敛并尽可能避免无效路由，我们可以在协议中进行一些小的优化和调整。

链路状态与距离矢量的比较

与距离矢量协议相比，链路状态协议有哪些优缺点呢？

在距离矢量协议中，当我们收到一条公告时，我们不一定知道所接受的路径的所有细节。我们必须相信邻居在公告中声称的内容。相比之下，在链路状态协议中，我们知道拓扑图的完整结构，因此更了解数据包所走的路径。

根据实现的不同，距离矢量协议的收敛速度可能更慢。如果网络发生变化，我们必须等待邻居重新计算并重新公告路径后，才能更新我们的转发表。然后，我们所有的邻居又必须等待我们，依此类推。相比之下，在链路状态协议中，所有路由器都能快速泛洪新信息，并同时重新计算。

链路状态协议适用于小型本地网络，但在全球互联网中扩展性不佳。特别是，链路状态协议要求每个路由器都了解整个网络。在全球互联网中，运营商可能不想向竞争对手透露其网络拓扑（例如，其路由器的位置、链路的带宽）。

在实践中，大多数网络都会结合部署距离矢量协议和链路状态协议。

（注：文档部分内容可能由 AI 生成）