路由状态
不良的路由策略
到目前为止，我们将路由问题定义为：当路由器收到一个数据包时，路由器如何知道将数据包转发到哪里，以确保它最终能到达目的地？
一旦我们找到一种解决这个问题的算法（一种路由协议），我们就可以应用该算法生成一个结果，我们称之为路由状态。你可以将路由状态看作是每个路由器用于转发收到的数据包的一组规则。路由状态是什么样子的？我们如何判断一个给定的路由状态是有效的还是良好的？
首先，我们可以考虑一些生成路由状态的不良策略。一种可能的路由策略是：路由器将数据包转发给随机选择的邻居。直觉上，我们已经可以看出，用这种策略生成的路由状态可能是无效的。如果使用这种策略，我们无法确保数据包能到达最终目的地。
另一种可能的不良策略是：路由器将数据包的副本转发给它的每一个邻居。直觉上，这种策略在某种意义上可能是有效的，因为数据包的副本最终会扩散到整个网络，很可能到达目的地。然而，这种策略效率低下，因为它浪费了大量带宽，将数据包转发到了不需要用于将数据包发送到目的地的路由器。
我们可以直观地看出这两种策略是不好的，但为了分析更智能的路由协议，我们需要正式定义路由状态的样子。然后，我们需要正式定义什么使路由状态有效，什么使路由状态良好。
转发表
在我们的网络模型中，每个路由器都有一些 outgoing 链路，连接到相邻的路由器和主机。换句话说，在底层图中，每个路由器节点有一些邻居，通过边与路由器相连。
当路由器收到一个数据包时，根据数据包元数据中的最终目的地，路由器需要决定应该将数据包转发到哪个相邻的路由器或主机。数据包将要转发到的下一个中间路由器称为下一跳。
例如，考虑这个网络。如果 R2 收到一个最终目的地是 B 的数据包，相应的下一跳自然是 R3。可能的下一跳选择是 R1、R3 和 R4（与 R2 相邻的三个路由器），而 R3 是能将数据包发送到更接近 B 的下一跳。
如果 R2 收到一个最终目的地是 A 的数据包，那么相应的下一跳自然是 R1。
对于每个可能的最终目的地，我们可以写下将数据包转发到更接近该目的地的相应下一跳。结果称为转发表。
注意，在目的地到下一跳的映射中，一个下一跳可以被多次使用。例如，在 R2 的转发表中，发往 B 的数据包和发往 C 的数据包都将被转发到 R3。
通过写下每个中间路由器的转发表，我们现在就有了网络的完整路由状态。换句话说，给定一个具有某个最终目的地的数据包，我们确切地知道每个路由器将如何转发该数据包。
在物理世界中，路由器通常不会将目的地映射到下一跳，而是将目的地映射到物理端口，每个物理端口对应一条链路。在图模型中，我们现在是将每个目的地映射到一条边，而不是将每个目的地映射到一个相邻节点。在物理世界中，你可以认为路由器有几根 outgoing 线路，每根线路都连接到另一个路由器。路由器在转发表中写下的不是相邻路由器，而是数据包应该沿着哪根线路发送。
这是一个细微的区别，它反映了路由器并不真正关心相邻路由器的身份。路由器需要做的唯一决定是将数据包沿着某一根线路发送，不管这根线路连接的是谁。在这些笔记中，为了简单起见，我们将转发表绘制为将目的地映射到下一跳（而不是物理端口）。
基于目的地的转发
使用转发表的一个结果是，对于一个给定的数据包，转发数据包的决定只取决于数据包的目的地域段。换句话说，如果一个路由器收到许多不同的数据包，且所有数据包都具有相同的目的地，那么它们都将被路由到相同的下一跳（假设转发表保持不变）。由于每个目的地只映射到一个下一跳，因此具有相同目的地的两个数据包不可能被转发到不同的路由器。这种方法称为基于目的地的转发或基于目的地的路由。
基于目的地的路由是最常见的路由方法，也是现代互联网中使用的方法。理论上，可能存在其他使用额外元数据来做出转发决定的方法，但这些方法通常只在有限的应用中使用（例如，在特定的本地网络内部）。
在后面的单元中，当我们考虑数据中心拓扑时，我们可能会考虑基于目的地的转发方法，其中特定目的地可能有多个下一跳。在本单元中，我们假设每个目的地只映射到一个下一跳。
路由与转发
既然我们已经介绍了转发表的概念，我们需要区分创建转发表的过程和使用转发表的过程。
路由是路由器之间相互通信以确定如何填充其转发表的过程。
转发是接收数据包、在表中查找其相应的下一跳并将数据包发送到相应邻居的过程。
转发与路由不同。在转发数据包时，路由器使用现有的转发表，而不知道该表是如何生成的。
转发是一个本地过程。当路由器转发数据包时，路由器不需要知道完整的网络拓扑。路由器也不关心数据包被转发到下一跳之后的去向。路由器只需要知道到达的数据包及其自己的转发表。
相比之下，路由是一个全局过程。为了填写转发表，我们需要了解有关网络全局拓扑的一些信息。
例如，在填写 R2 的转发表时，我们必须以某种方式知道目的地 B 与 R3 相关联，即使主机 B 并不直接连接到 R2。在路由过程中，每个路由器也需要知道非本地目的地。
路由状态的有效性是全局的
回想一下，路由状态由每个路由器的转发表组成，这些转发表共同告诉我们数据包将如何通过网络传输。给定一个路由状态，我们如何判断它是正确的还是错误的？
首先，我们需要正式定义路由状态有效性，以确定一个路由状态是否有效（尽管这个术语在加州大学伯克利分校的 CS 168 课程之外可能不被广泛使用）。有效性的主要要求是：路由状态需要产生确保数据包实际到达目的地的转发决策。
请注意，有效性必须在全局范围内评估，而不是在本地范围内。查看本地路由状态，例如单个路由器的转发表，无法告诉我们路由状态是否有效。例如，在路由器 R2 的本地转发表中，我们可能会看到目的地 A 的下一跳是路由器 R3，但我们无法确定这是否有效。将数据包转发到 R3 会帮助数据包到达目的地 A 吗？仅从转发表中无法判断。
相反，我们需要考虑全局路由状态，它由所有路由器中的所有转发表的集合组成。
路由状态有效性的定义
现在，我们可以定义一个正式的条件，用于检查给定路由状态下数据包是否能到达目的地。
一个全局路由状态是有效的，当且仅当对于任何目的地，数据包不会陷入死胡同或环路。
死胡同是指数据包到达路由器，但路由器不知道如何将数据包转发到其目的地，因此数据包没有被转发。如果路由器的转发表中没有包含数据包目的地的条目，就可能会出现这种情况。
请注意，死胡同条件仅适用于中间路由器，而不适用于终端主机。当数据包到达目的地终端主机时，终端主机无需进一步转发数据包，因此我们不会在死胡同条件中考虑终端主机。
环路是指数据包在相同的节点之间循环发送。请注意，因为我们使用的是基于目的地的转发，下一跳只取决于目的地，所以一旦数据包进入环路，它将永远被困在环路中。当数据包第一次、第十次或第五百次到达路由器时，它将以完全相同的方式被转发（因为最终目的地是相同的）。由于这适用于环路上的每个路由器，数据包将永远被困在环路中。
这个条件（没有死胡同，没有环路）对于路由的有效性来说既是必要的也是充分的。让我们检查这个逻辑蕴含的两个方向。
没有死胡同和没有环路是有效性的必要条件。换句话说，一个状态是有效的，仅当它没有死胡同和没有环路。
证明：如果存在死胡同，数据包将无法到达目的地。数据包将到达死胡同且不被转发。
如果存在环路，数据包将无法到达目的地。数据包将永远被困在环路中（如前所述，由于基于目的地的转发）。此外，请注意，最终目的地不可能是环路的一部分，因为目的地不会转发数据包。因此，被困在环路中的数据包将无法到达目的地。
现在，让我们检查另一个方向。如果没有环路且没有死胡同，那么该状态是有效的。
证明：假设路由状态没有环路和死胡同。数据包不会到达同一个节点两次（因为没有环路）。此外，数据包在到达目的地之前不会停止（因为没有死胡同）。因此，数据包必须继续在网络中传输，到达不同的节点。由于要访问的唯一节点数量是有限的，因此数据包最终必须到达目的地。因此，路由状态必须是有效的。
定向交付树
现在我们有了路由状态有效性的正式定义，我们可以问：给定一个全局路由状态，如何检查它是否有效？
为了简化问题，让我们先只考虑一个目的地终端主机，忽略所有其他终端主机。在每个路由器中，我们可以查找这个目的地，得到相应的下一跳，这告诉我们每个路由器将如何转发发往这个目的地的数据包。
我们可以将每个路由器（针对这个单一目的地）的下一跳表示为一个箭头，这向我们展示了这个数据包到达单一目的地可能采取的所有路径。
在生成的图中，每个节点将只有一个 outgoing 箭头。这反映了我们的假设，即在每个路由器的转发表中，一个目的地只对应一个下一跳。
请注意，在生成的图中，一旦两条路径相遇，它们就永远不会分开。换句话说，即使有多个 incoming 箭头（路径）指向一个节点，由于只有一个 outgoing 箭头，这些路径现在将汇聚成一条单一的路径。这反映了我们的基于目的地的转发方法，因为每个路由器只使用最终目的地来决定如何转发数据包。路由器并不关心数据包最初是如何到达该路由器的。
我们绘制的箭头形成了一组数据包可以到达单一目的地的路径。这组路径称为定向交付树。
在图论中，有效交付树中的箭头必须形成一个有向生成树，以目的地为根。回想一下，生成树是图中触及每个节点并形成树的一组边。我们希望交付树是一棵树，因为不应该有 cycles（数据包不能在环路中传输）。我们希望交付树是生成树（触及每个节点），因为我们希望能从任何地方到达目的地。交付树是有向的，因为边有箭头，告诉我们转发数据包的方向。
有效交付树中的所有边都应该指向目的地。换句话说，从任何节点开始，沿着箭头前进都应该能到达目的地。
验证路由状态的有效性
和之前一样，让我们只考虑一个目的地终端主机，忽略所有其他终端主机。
示例：尽管这里有多个终端主机，但让我们只考虑终端主机 A。
使用每个路由器的转发表，我们将箭头绘制到网络中，形成这个单一目的地的定向交付树。正式地说，对于每个路由器（图中的节点），我们将从该节点绘制一个 outgoing 箭头。
示例：使用转发表（未显示），我们可以为每个路由器绘制一个 outgoing 箭头。
为简单起见，此时我们可以删除所有没有箭头的链路。这些没有箭头的链路永远不会被用于向单一目的地发送数据包，因为它们不在交付树上。
示例：我们可以删除所有没有箭头的链路。
如果剩余的图是一个有效的定向交付树（生成树，所有箭头都指向目的地），那么我们可以说这个路由状态对于这个单一目的地是有效的。
在上面的示例中，剩余的图确实是一个汇聚于 A 的有效生成树，所以我们可以说这个路由状态对于 A 是有效的。
以下是一些无效路由状态的示例：
这个状态是无效的。直觉上，存在一个死胡同路由器。发往 A 的数据包可能会被发送到这个路由器，而这个路由器会丢弃数据包而不转发。正式地说，剩余的图不是生成树，因为边没有全部连接（有两个断开的组件，这在树中是不允许的）。
这个状态也是无效的。直觉上，存在一个数据包可能陷入的环路。正式地说，剩余的图不是生成树，因为边是断开的，并且存在一个 cycle。
我们可以对每个不同的终端主机重复这个过程（每次隔离一个不同的终端主机）。如果路由状态对于所有目的地都是有效的，那么我们可以说这个路由状态是有效的，并且总能将数据包传递到它们的正确目的地。
最小成本路由
现在我们已经定义了什么使路由状态有效（路由没有环路和死胡同），我们还可以定义什么使路由状态良好。一个网络可能有多个有效的路由状态，我们需要一些指标来帮助确定一个路由是否比另一个更好。
最小成本路由是衡量路由是否良好的一种常见方法。在最小成本路由中，我们为每个链路分配一个数值成本，并寻找使成本最小的路由。换句话说，我们希望路由能使数据包沿着到达目的地的最低成本路径传输。
我们可以考虑为链路分配许多不同的成本。成本可以取决于构建链路的价格、传播延迟、链路的物理距离、不可靠性、带宽等因素。例如，我们可以基于链路的质量（带宽和传播延迟）分配成本，这样最低成本路径会优先选择质量更高的链路。
通过允许运营商任意设置链路成本，我们让运营商能够根据他们的特定需求优化网络。我们分配的成本取决于运营商的网络目标。如果我们有一个 400 Gbps 链路，传播延迟为 20 ms，还有一个 10 Gbps 链路，传播延迟为 5 ms，哪一个成本更低？这取决于我们是在优化带宽、传播延迟、两者的某种组合，还是其他完全不同的东西。
如果我们为每个链路分配成本 1，那么最小成本路径就是经过最少链路的路径。我们有时称之为最小化跳数。在这些笔记中，如果图的边没有标注成本，你可以假设所有边的成本都是 1。
网络运营商可以决定如何为每个链路分配成本。运营商可以手动分配成本。或者，运营商可以让网络自动配置成本，尽管这可能不适用于一些无法自动测量的指标（例如，网络不知道构建链路的财务成本）。
在设计路由协议时，我们可以抽象掉成本是如何分配的。从路由协议的角度来看，其他人（例如网络运营商）已经基于他们认为重要的东西分配了成本。该算法将成本作为输入，并计算最小成本路径，而不管成本实际上代表什么。
请注意，成本对于每个路由器来说是本地的。路由器知道自己 outgoing 链路的成本，但无法自动知道所有链路的成本。这与我们之前提到的约束一致，即路由器没有整个网络拓扑的全局视图。
为简单起见，路由协议对成本的定义做了一些假设。
我们假设成本始终是正整数。这与许多常见的现实生活指标一致，例如链路长度或链路的货币成本。如果我们试图最小化数据包传输的总物理距离，负链路成本是没有意义的。沿着一条链路传输不可能减少总距离。这个假设将有助于简化我们后面的协议，因为我们不必担心像负权重环路这样的边缘情况（在这种情况下，最小成本解决方案是永远绕着环路传输）。
我们假设成本是对称的。从 A 到 B 的成本与从 B 到 A 的成本相同。这反映了我们将要绘制的图表，其中一条边用一个单一的对称成本标注。理论上，可能存在非对称链路成本，但在实践中不会这样做，并且会导致更复杂的路由协议。
有了这些假设，我们对良好路由（最小成本）的定义与我们对有效路由的定义是一致的。特别是，最小成本路由不会有任何环路，因为成本是正的（遍历环路只会增加成本）。
静态路由
生成路由的一种可能方法是让网络运营商手动填充转发表。这被称为静态路由。
静态路由本身并不实用（例如，不可扩展，容易出现人为错误），但即使实现了路由协议，一些路由仍然需要由运营商手动创建。你可以将这些手动路由视为 “trivial” 或 “基本情况” 路由，路由协议在此基础上生成更复杂的路由。
如果我们直接连接到我们想要路由数据包的另一台机器，我们可以手动配置一条路由来将数据包转发到那台机器。这些路由称为直接路由或连接路由。例如，你的家用路由器通过一条链路连接到你的个人电脑，所以你的家用路由器可以在转发表中添加一个对应于你的电脑的条目。这个条目是通过告诉路由器有关该连接而添加的，不是通过运行任何路由协议添加的。
也可以使用静态路由在转发表中为目的地硬编码条目，即使我们没有直接连接到该目的地。如果有一条永远不会改变的路由，并且我们希望该路由始终留在我们的转发表中，而不管路由协议在做什么，这会很有用。
（注：文档部分内容可能由 AI 生成）