路由协议和架构/距离向量算法

距离向量 (DV) 算法基于在路由器邻域内分发有关整个网络的信息。

每个路由器定期生成一个 DV，它是一组目标-成本对

• 目标: 生成路由器已知的目标 (在实际 IP 网络中，它们是带子网掩码的网络地址)；
• 成本: 从生成路由器到目标路径的成本。

接收路由器从每个 DV 中了解

• 可达目标: 它们将添加到本地已知的目标中；
• 方向: 这些目标可以通过生成路由器访问；
• 成本: 生成路由器报告的成本加上接收路由器和生成路由器之间链路的成本。

每个节点存储来自其邻居的所有 DV，并通过为每个目标选择最佳成本，以构建其路由表和 DV

生成节点 A 的路由表和新 DV 的过程。

基本算法

• 主流程
  1. DV 被宣布给相邻路由器；
  2. 它等待超时；
  3. 它返回到步骤 1；
• 收到新的 DV 时
  1. DV 被保存到内存中；
  2. DV 与存储的 DV 合并；
• 当链路发生故障 (在物理层检测到) 时
  1. 来自该链路的所有 DV 都被删除；
  2. 剩余的 DV 被合并；
• 当在超时时间内未收到 DV 时
  1. 丢失的 DV 被删除；
  2. 剩余的 DV 被合并。

备注

• 可靠性: 超时避免使用链路启动信号，这些信号可能并不总是可用 (例如，如果故障发生在集线器之外)；
• 效率: 当链路发生故障时，路由器会在不与相邻节点交换任何 DV 的情况下获得其新的路由表；
• 收敛速度: 当路由器更改其 DV 时，它不会宣布它，直到主进程的下一个超时 (没有触发更新)。

触发更新

路由器可以在更新其路由表后立即发送其更新的 DV，而不必等待默认超时，以提高收敛时间。它可以宣布整个 DV，或者，就像在实际实现中更常见的那样，只宣布更改的路由。

触发更新不会重置主进程的超时，以避免路由器同时开始生成 DV (同步)。

无穷计数

无穷计数示例。

当到达不再可达的目标的成本逐渐增加到无穷大时，就会触发无穷计数。

示例

在侧边图中，A 和 B 之间链路的故障会触发无穷计数

1. B 在物理层检测到故障并删除来自 A 的 DV，但 C 无法在物理层检测到故障；
2. C 向 B 宣布，它可以通过成本为 2 的路径到达 A，这实际上是穿过 B 的旧路径；
3. B 更新来自 C 的 DV，表明 A 现在可以通过穿过 C 的替代路径到达，成本为 3；
4. B 反过来将其 DV 发送给 C，C 更新它并将成本增加到 4，依此类推。

效果

B 认为它可以通过 C 访问 A，而 C 认为它可以通过 B 访问 A → 发送到 A 的数据包开始在 B 和 C 之间弹跳 (弹跳效应)，使 B 和 C 之间的链路饱和，直到其 TTL 降至 0。

原因

与黑洞和路由循环不同，无穷计数是 DV 算法的特定问题，因为 DV 中包含的信息没有考虑网络拓扑。

可能的解决方案

• 无穷阈值: 无穷计数的上限；
• 附加算法: 它们可以防止无穷计数，但会使协议更繁重，并倾向于降低其可靠性，因为它们无法预见所有可能的故障
  • 路由中毒: 不好的消息胜过没有消息；
  • 分隔视野: 如果 C 通过 B 访问目标 A，B 没有必要尝试通过 C 访问 A；
  • 路径保持: 让谣言平静下来，等待真相。

无穷阈值

可以定义一个阈值: 当成本达到阈值时，目标将被认为不再可达。

例如，RIP 的阈值等于 16: 级联中超过 15 个路由器不能连接。

具有复杂指标 (例如 IGRP) 的协议需要非常高的阈值才能考虑差异化的成本: 例如，基于带宽的指标可能会导致广泛的成本值范围。

如果弹跳效应发生在低成本链路上，则需要相当长的时间才能将成本增加到阈值 → 同时可以使用两个指标

• 一个用于路径成本的指标 (例如，基于链路带宽)；
• 一个用于无穷计数的指标 (例如，基于跳数)。

当用于无穷计数的指标返回 '无穷大' 时，无论路径成本如何，目标都将被认为不可达。

路由中毒

检测到故障的路由器将不再可达的目标的成本传播为无穷大 → 其他路由器会听到故障并反过来传播 '中毒' 信息。

分隔视野

每个路由器都区分发送给其邻居的 DV: 在每个 DV 中，它会省略那些可以通过穿过它正在发送 DV 的邻居的路径访问的目标 → 它不会触发 '虚假' 路径出现在不再可达的目标方向，因为在 DV 中发送了过时的信息。

特点

• 它避免了两个节点之间的无穷计数 (除非是特定的循环)；
• 它提高了 DV 算法的收敛时间；
• 路由器必须为每个链路计算不同的 DV。

带有中毒反向的分隔视野

在实际实现中，DV 可能被分成多个数据包 → 如果 DV 中的某些条目被省略，接收节点不知道这些条目是被分隔视野机制有意省略，还是包含它们的包丢失了。

在带有中毒反向的分隔视野中，目标不会被省略，而是被传输，但被 '中毒'，成本为无穷大，因此接收节点可以确定它已收到构成 DV 的所有数据包 → 这会延长收敛时间。

路径保持

如果到目标的路径成本增加，它很可能触发无穷计数 → 该条目将被 '冻结' 一段特定时间，等待网络其余部分找到可能的替代路径，然后，如果没有人继续宣布该目标，它将被视为不可达，并且其条目将被删除。

DUAL

扩散更新算法 (DUAL) 是一种旨在通过保证即使在瞬态情况下也不存在路由循环来提高 DV 算法可扩展性的附加算法。

• 正状态变化: 如果任何邻居节点宣布一条具有更低成本的替代路径，则会立即接受，因为它肯定不会导致路由循环；
• 负状态变化: 如果
  • 当前的下一跳宣布当前路由的成本增加（忽略其他邻居节点的更差宣布），
  • 或者路由器在物理层检测到当前路由所属链路的故障，

  那么 DUAL 算法必须被激活。

  1. 选择可行后继者: 只有当它保证通过它的替代路径不会导致路由循环时，才会选择另一个邻居；
  2. 扩散过程: 如果找不到可行后继者，节点将进入一种“恐慌模式”，并向其邻居求助，等待有人报告通往该目的地的可行路径。

选择可行后继者

如果当前路由由于负状态变化而不再可用，则只有在可以证明新路径不会创建循环的情况下才会选择替代路径，也就是说，只有在确定新的下一跳不使用该节点本身到达目的地的情况下才选择替代路径。

邻居节点 $K$ 是路由器 $R$ 的可行后继者当且仅当它到目的地 $D$ 的距离小于路由器 $R$ 在状态变化之前所拥有的距离。

$d\left(K,D\right)<d\left(R,D\right)$

这保证了邻居 $K$ 可以使用不经过路由器 $R$ 的路径到达目的地 $D$: 如果路径 $K\rightarrow D$ 经过 $R$，它的成本不能低于子路径 $R\rightarrow D$ 的成本。

如果存在多个可行后继者，则选择提供通往目的地 $D$ 的最低成本路径的邻居 $X$

$\min {\{L\left(R,X\right)+d\left(X,D\right)\}}$

其中

• $L\left(R,X\right)$ 是路由器 $R$ 与其邻居 $X$ 之间的链路的成本；
• $d\left(X,D\right)$ 是邻居节点 $X$ 到目标节点 $D$ 的距离。

选择的可行继任节点不一定是通往目标节点的最佳路径所经过的邻居节点。如果机制没有选择最佳的邻居节点，后者将继续广播实际上是最优的路径，且不改变其成本→路由器会识别到新的、更好的路径，但该路径没有被选择，并会采用新的路径（状态发生积极变化）。

扩散过程

如果路由器 $R$ 无法为目标节点找到任何可行的继任节点

1. 它会在路由表中临时冻结与目标节点相关的条目→数据包会继续走旧路径，该路径绝对没有环路，并且可能不再能到达目标节点；
2. 它会进入活动状态
   1. 它会向其所有邻居（除了旧路径的下一跳节点）发送查询消息，询问它们是否能找到比旧路径更好的路径，并且该路径绝对没有环路；
   2. 它会等待从每个邻居接收回复消息；
   3. 它会选择最佳路径并退出活动状态。

每个收到路由器 $R$ 查询消息的邻居路由器 $X$ 会发送包含其 DV（与通过该邻居的路径相关）的回复消息

• 如果路由器 $R$ 不是其通往目标节点的下一跳节点，因此其通往目标节点的路径成本没有改变，那么路由器 $X$ 会报告路由器 $R$ 可以使用该路径；
• 如果路由器 $R$ 是其通往目标节点的下一跳节点，那么路由器 $X$ 应该依次开始寻找新的路径，可以通过选择可行的继任节点或也进入活动状态。

优点和缺点

优点

• 非常容易实现，基于 DV 算法的协议易于配置；
• 它需要的处理资源有限→路由器使用廉价的硬件；
• 适用于小型且稳定的网络，且网络中负状态变化频率不高；
• DUAL 算法保证网络无环路：即使在瞬态状态下，也不会出现路由环路（虽然黑洞仍然会被容忍）。

缺点

• 该算法的最坏情况时间复杂度为指数级，其正常时间复杂度介于 $O\left(n^{2}\right)$ 和 $O\left(n^{3}\right)$ 之间；
• 收敛速度可能相当慢，与网络中最慢的链路和最慢的路由器成正比；
• 很难理解和预测其在大而复杂的网络中的行为：没有节点拥有网络的拓扑图→很难检测到潜在的路由环路；
• 由于拓扑结构的特定变化，它可能会引发路由环路；
• 用于改进其行为的附加技术会使协议更加复杂，而且它们也不能完全解决拓扑知识缺失的问题；
• '无穷大'阈值限制了该算法只能用于小型网络（例如，具有少量跳数的网络）。

路径向量算法

路径向量（PV）算法添加了关于宣布的路由的信息：它也会宣布路径，即路径上的 经过的节点列表。

生成节点 A 路由表和新 PV 的过程。

交叉节点列表可以避免路由循环的出现：接收节点可以通过观察其标识符是否出现在列表中来检测到宣布的路由是否经过它，从而将其丢弃而不是传播它 → 两次经过同一个节点的路径无法形成。

路径向量是距离向量和链路状态之间的中间算法：它添加了关于宣布路径的严格必要信息，而无需像链路状态那样需要了解整个网络拓扑结构的复杂性。

应用

PV 算法在 BGP 协议的域间路由中使用： B5. 边界网关协议#路径向量算法.