CS168

DVMRP

朴素算法：泛洪（Flooding）

回顾组播路由的目标：我们有一个以组为目的地的数据包，路由器需要协同工作将该数据包转发到组内的所有成员。

实现这一目标最朴素的方法是泛洪。当路由器收到一个数据包时，它会将该数据包从除了入端口之外的所有端口转发出去。

泛洪为什么有效？它能确保网络上的每个主机都收到数据包，自然也包括目标组的所有成员。

泛洪的优点是什么？概念简单，不需要运行任何路由协议。

泛洪存在哪些问题？主要有两个问题，我们将逐一解决：

泛洪会沿着多条路径发送相同的数据，而实际上数据只需要沿着一条路径发送，这浪费了带宽。
泛洪会将数据包发送给非组内成员，也浪费了带宽。

此外，环路可能会导致广播风暴，即同一个数据包在环路中无限转发，不过这个问题可以通过让路由器丢弃已经见过的数据包来解决。

反向路径广播（RPB，Reverse Path Broadcasting）

现在我们先聚焦第一个问题。（注意：目前我们仍会将组播数据包发送给所有主机，包括非组内成员，这个问题稍后解决。）

泛洪确实能将数据包发送给所有主机，但它会沿着冗余链路发送数据，造成浪费。例如，如果 R1 和 R4 之间有很多路径，泛洪会让数据包的副本沿着每一条路径从 R1 传到 R4，之后 R4 会丢弃所有重复的数据包。

理想情况下，我们希望数据包在任意一对路由器之间只沿着一条路径传输。这让你想到了什么数据结构？树结构中任意两个节点之间都只有一条路径！

具体来说，我们需要构建一棵生成树，这样每个主机都能通过唯一的路径收到数据包。

我们可以从头构建生成树，但更巧妙的是可以复用我们已经完成的一些工作。我们之前在哪里见过生成树？

在为单播数据包运行距离矢量路由时，我们构建了一棵指向目的地的生成树。这使得所有数据包都能在网络图中 “向上” 流动，朝着唯一的目的地（树的根）传输。

如果我们将这个图中的所有箭头反转，就得到了一个适合组播数据包的生成树。树的根现在是发送方，数据包的副本会在网络图中 “向下” 流动，从发送方出发，通过网络到达所有目的地。

此时，考虑反转的箭头可能会有些 confusion，所以我们换用一些更清晰的术语。在路由器树中，每个路由器有且仅有一个父节点，以及零个或多个子节点。树 “顶部” 的路由器是根，树 “底部” 没有子节点的路由器称为叶节点。（这些定义和你在任何数据结构课程中接触到的一样，没有特别之处。）

在考虑单播路由时，根是目的地。所有路由器从子节点接收数据包，然后转发给父节点，“向上” 朝着目的地传输。

相比之下，在考虑组播路由时，根是源。所有路由器从父节点接收数据包，然后转发给子节点，“向下” 通过网络到达所有目的地。

总之，组播路由的转发规则是：如果从父节点收到数据包，就将其发送给所有子节点。否则，如果从其他节点（非父节点）收到数据包，则丢弃该数据包。

这条规则有助于避免数据包沿着多条路径发送。即使到你的路径有很多条，你也只会从父节点收到一次数据包（并转发给子节点）。如果从其他节点（非父节点）收到该数据包的另一个副本，你会将其丢弃。

RPM：学习父节点和子节点

我们如何实际实现这条规则呢？每个路由器需要知道自己的父节点和所有子节点。

确定父节点很简单。记住，这棵树和单播路由的距离矢量算法所构建的树完全相同。在你的单播转发表中，到根的下一跳就是你的父节点！要确定父节点，只需复用为单播路由计算的转发表条目即可。

确定子节点则需要多做一些工作。转发表只告诉你父节点（到根的下一跳），但转发表中没有关于子节点（远离根的前一跳）的信息。

由于不知道子节点是谁，你需要子节点主动告诉你。具体来说，每个路由器都会向自己的父节点发送组播路由通告，内容为：“我是你（在以 A 为根的树中）的子节点。”（记住，每个路由器都可以从单播转发表中知道自己的父节点。）

然后，每个路由器接收这些通告，并存储关于自己子节点的额外信息。这是我们专门为组播路由添加的新信息。这个新的组播转发表与我们在单播路由中使用的转发表（用于确定父节点）是分开的。

总之，组播的转发规则是这样实现的：当收到一个数据包时，使用单播转发表（其中列出了父节点）检查该数据包是否来自父节点。如果数据包来自父节点，则使用新的组播转发表（包含来自子节点的通告）将其转发给子节点。

现在我们有了两个转发表，让我们思考一下它们各自的用途。单播转发表列出了父节点。这个表用于将单播数据包转发到目的地，就像在标准的距离矢量路由中一样。这个表还用于检查组播数据包是否来自父节点。最后，这个表还用于发送组播路由通告，告诉父节点 “我是你的子节点”。

组播转发表列出了子节点。这个表是通过接收来自子节点的通告构建的。它用于将组播数据包转发给所有子节点。

最后一个重要的观察：在距离矢量单播路由中，我们为每个目的地构建了一棵生成树。因此，单播转发表中每个目的地都有一个下一跳。换句话说，对于每个目的地，在对应的树中都有一个父节点。

当我们反转箭头时，最终会为每个源构建一棵生成树。组播转发表中每个源都有一个子节点列表。换句话说，组播转发表条目可以解释为：“如果收到来自源 A 的数据包，将其转发给子节点 R6、R7。”

反向路径组播（RPM，Reverse Path Multicasting）：剪枝（Pruning）

我们的反向路径广播规则确保了数据包沿着生成树传输，从源（根）开始，“向下” 通过网络到达所有目的地。使用树结构解决了第一个问题（数据包通过多条路径传输而浪费带宽）。

然而，我们还有第二个问题需要解决。到目前为止，我们的数据包仍然在广播给所有主机，包括不在组内的主机，这浪费了带宽。

为了解决这个问题，我们将对树进行剪枝，即切断没有组内成员的分支。

剪枝从子节点向父节点传播。假设你是 R5，直接连接着 3 台主机。通过 IGMP（即与这些主机通信），你得知它们都不在该组中。这意味着你没有必要成为这棵树的一部分。

你可以向父节点发送一个通告：“我是你的子节点，但我的所有后代都不在这个组中，所以不要给我发送数据包。” 父节点随后可以相应地更新其组播转发表条目，使你不再是子节点之一。注意，剪枝消息只发送给直接父节点（不会进一步转发）。

剪枝也可以在树的更高层级发生。考虑 R3，一个有 2 个子节点的路由器。假设两个子节点都发送了剪枝通告，表明它们不在这个组中。如果你的所有子节点都不在这个组中，那么你也没有必要参与这个组。因此，你也可以将自己从这棵树中移除。你可以通过向父节点发送剪枝通告来实现，这样父节点就会停止向你发送数据包。

注意：更高层级的路由器可能既有子节点路由器，也有直接连接的主机。在这种情况下，只有当所有子节点都发送了剪枝通告，并且所有直接连接的主机都不在这个组中时，路由器才能将自己从树中移除。

剪枝使我们的组播转发表变得稍微复杂一些。到目前为止，每个条目将一个源映射到一个子节点列表：“如果收到来自源 A 的数据包，将其转发给子节点 R11、R12。” 然而，子节点列表现在还取决于目的组。例如，可能 R11 和 R2 都有属于组 G1 的后代。但是，只有 R11 有属于组 G2 的后代（即 R12 已经向你发送了剪枝消息）。

为了解决这个问题，我们的组播转发表必须为每个源、每个组都有一个条目。例如：“如果收到来自源 A 到组 G1 的数据包，将其转发给子节点 R11、R12。”

另一个单独的条目是：“如果收到来自源 A 到组 G2 的数据包，将其转发给子节点 R11。”

另一种理解这种修改的方式：以前，我们为每个源有一棵生成树，展示该源如何向其他所有节点发送组播数据包。然而，现在我们会根据目的组切断树的分支。因此，我们需要为每个源、每个目的组都有一棵生成树。

最后一点：可能目前你的所有子节点都不属于某个组，但一段时间后，某个后代可能决定加入该组。为了解决这个问题，每个路由器会定期清除所有剪枝信息，这样就不再有节点被剪枝。这会使所有节点恢复到原始的 RPB 行为，即总是将数据包转发给所有子节点。

这样，如果你的某个后代已经加入了一个组，那么在计时器到期后，你不再被剪枝，会重新加入树中。另一方面，如果仍然没有后代属于该组，你可以再次向父节点发送剪枝消息，使自己从树中移除。

DVMRP 规则总结

路由规则：

对于每个源的生成树，你需要了解自己的父节点和子节点。

学习父节点：无需额外操作。单播转发表已经标识了父节点。
学习子节点：每个节点向自己的父节点发送通告。收到这些通告后，你就知道了自己的子节点是谁。

转发规则：

收到数据包时，使用给定源的单播转发表检查该数据包是否来自父节点。
如果数据包来自父节点，使用新的组播转发表将其转发给子节点。只转发给给定目的组的未被剪枝的子节点。
否则，如果数据包不是来自父节点，则直接丢弃。

剪枝规则：

对于每个（目的组，源）对：

如果收到来自子节点的剪枝消息，将该子节点从该目的组的组播转发表条目中移除。
如果没有后代（直接连接的主机或子节点）属于该组，向父节点发送剪枝消息。
定期清除所有剪枝信息（恢复为向所有子节点转发）。

DVMRP 的优缺点

这个路由协议的缺点是什么？

剪枝信息会定期清除。清除时，数据包会再次广播给所有节点，直到剪枝重新收敛（回想一下，没有剪枝时，数据包会发送给所有节点）。

转发表的扩展性较差。组播转发表需要为每个源、每个目的组都有一个条目。

这个路由协议的优点是什么？

DVMRP 是对现有路由协议（距离矢量）的简单、优雅的扩展。我们能够巧妙地复用单播转发表来帮助实现 DVMRP。例如，我们不必费力思考如何确定父节点，因为单播转发表已经为我们做好了。

由于我们复用了距离矢量协议的传输树，所生成的树也是最低成本树。换句话说，它们为我们提供了从发送方到所有组内成员的最佳路径。这就是为什么我们说 IP 组播是最优的：换句话说，就网络拓扑中的成本而言，DVMRP 实现了最佳可能的性能。

将组播和单播路由耦合的一个缺点是切换协议更困难。例如，如果我们将单播路由协议从距离矢量切换到链路状态，我们也必须重新考虑组播路由协议。

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