基于核心的树（CBT）

CBT 的定义

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

然而，我们现在将尝试一种完全不同于 DVMRP 的方法。

在基于核心的树（CBT） 方法中，每个目的组都有自己的树。一个目的组的 CBT 就是一棵连接该组所有成员的树。

同时思考 CBT 树和 DVMRP 树可能会让人混淆。目前，你可以认为它们是完全不同的树，没有任何共同之处。

构建 CBT

要构建一棵基于核心的树，这棵树需要一个根，我们称之为核心。核心是网络中预先选定的某个任意路由器。

现在，我们将构建一棵以核心为根、连接所有组成员的树。

如果一个成员想要加入一个组，该成员会向核心单播一条加入消息。这个数据包会经过多个路由器到达核心。所有这些路由器也会加入这棵树，这样树就有了从核心到新成员的路径。

更正式地说，如果你是一个路由器，并且收到了针对特定组的加入消息，你就知道自己现在是这个组的树的一部分了。加入消息的入站链路是你的子链路（指向远离根的方向）。加入消息的出站链路（到根的下一跳）是你的父链路（指向根的方向）。你可以记录下自己的父节点和子节点，以记住自己在树中的位置。没有全局的 “掌控者” 记住这棵树；树上的每个路由器都负责记住自己的父节点和子节点。

如果一个成员想要离开一个组，该成员可以向其在树上的直接父节点单播一条退出消息。如果你的所有子节点都发送了退出消息，这意味着你也可以离开这棵树，因此你可以向自己的直接父节点发送一条退出消息。退出消息发送给直接父节点后，不会再进一步转发。

记住，我们为每个组构建一棵单独的树。这意味着路由器必须记住它们在所属的每棵树中的父节点和子节点。此外，加入和离开消息必须与特定的组相关联，例如 “我想要加入组 G2”。

关于核心，有一些细节需要说明，不过这并不是该协议背后的主要直觉。

• 由于核心是一个路由器，它有一个单播 IP 地址，所有设备都可以向核心发送单播数据包。

• 我们为每个组构建一棵单独的树。不同的组可以使用不同的核心。

• 我们假设所有设备都知道组到核心的映射，例如 “组 G1 使用 R2 作为核心”。这种映射可以通过类似 DNS 的方式发布（回想一下：DNS 用于分发键值对很有用）。

• 核心不是组成员。在我们的模型中，我们假设主机可以加入 / 离开组，而路由器不能。核心是路由器，因此它不会加入组播组。

关于加入和退出消息，也有一些细节需要说明，不过这也不是该协议背后的主要直觉。

• 加入和退出消息在技术上是由第一跳路由器发送的。路由器使用 IGMP 检测到其直连主机中的一台加入或离开了组，然后第一跳路由器发送加入或退出消息。

• 实际上，会针对加入消息发送 JOIN-ACK，路由器在收到 JOIN-ACK 时记录它们的父节点和子节点。同样，会针对退出消息发送 QUIT-ACK 消息。在本课程中，我们将忽略这个特性。

使用 CBT

既然我们已经为一个组构建了 CBT，那么如何使用它们向该组发送消息呢？

情况 1：如果你是组成员，这意味着你已经连接到这棵树了。因此，你只需要向树上的所有节点广播消息即可。

更具体地说，你首先将数据包转发到你在树上的父节点。然后，树上的每个路由器收到数据包后，会将数据包泛洪到其所有树链路（包括父链路和子链路）。

情况 2：如果你不是组成员，你没有连接到这棵树，所以情况 1 的策略不适用。相反，你可以将数据包单播到核心。然后，核心可以向树上的所有节点广播该消息。

更具体地说，当你向核心单播数据包时，你需要对数据包进行封装。外部头部包含到达核心的单播信息。内部头部包含组播信息。

当核心收到数据包时，它会解开外部头部，看到内部的组播数据包。然后核心能够沿着树广播这个数据包。和情况 1 一样，树上的每个路由器收到数据包后，会将数据包泛洪到其所有树链路（包括父链路和子链路）。

优势：更好的扩展性

回想一下，DVMRP 的扩展性较差，因为路由器必须为每个源、每个目的组维护一棵单独的树。每棵树都显示了从一个源到一个目的组的所有成员的最短路径。

在 CBT 方法中，一个目的组的 CBT 只是一棵连接该组所有成员的树。

注意，CBT 对所有源都是相同的。与 DVMRP（每个源、每个目的组对应一棵数）不同，我们现在每个目的组只需要一棵数。

比较 DVMRP 树和 CBT 树以了解协议的扩展性很有用，但除此之外，每种协议中构建的树具有完全不同的语义。如果你感到困惑，或许将这些树视为完全独立的概念会更容易。

回想一下，DVMRP 的另一个扩展性问题是，修剪状态会定期清除，当这种情况发生时，数据包会广播到网络中的所有设备（包括非组成员）。CBT 也解决了这个问题，因为在 CBT 的运行过程中，数据包无需广播到所有设备。树本身告诉我们组成员的位置，因此确保非组成员永远不会收到数据包。

效率分析

回想一下，DVMRP 构建了从发送方到所有组成员的最低成本树。通过沿着这些树转发数据包，我们确保数据包会沿着到所有组成员的最低成本路径转发。

相比之下，CBT 树根本不涉及发送方，因此不再有最优性保证。从发送方到所有组成员的路径不一定是最低成本路径。

CBT 以牺牲效率换取了更好的扩展性。CBT 的扩展性更好，因为需要构建的树更少（即路由器存储的状态更少），但作为交换，数据包可能会沿着非最优路径转发。

CBT 的效率在很大程度上取决于选择哪个路由器作为核心。例如，考虑下面的拓扑结构以及核心的各种选择。

无论选择哪个核心，至少有一对路由器通过非最优路径连接。我们不再有从一个源到所有组成员的最短路径树的保证。

例如，如果 A 计划向组发送大量数据包，R2 可能是一个不错的核心选择，因为它恰好沿着最短路径将 A 连接到 B 和 C。然而，如果 B 想要向组发送数据包，数据包将沿着非最优路径到达 C。

找到最优核心是不可行的，特别是因为成员可以随时加入或离开组。在实践中，运营商通常手动选择核心。

CBT 的其他优缺点

CBT 在根节点处创建了一个单点故障。为了引入容错能力，我们需要树有多个核心。这是可以实现的，尽管会带来更多复杂性。我们不会进一步讨论多核心树，但如果你感兴趣，可以查看下面链接的论文。

回想一下，DVMRP 是作为距离向量的扩展构建的，这导致组播协议（DVMRP）和单播协议（距离向量）紧密耦合。更改一个协议也需要更新另一个协议。相比之下，CBT 与单播路由协议解耦。CBT 确实使用单播转发表（例如，将加入消息转发到根），但这些转发表是如何生成的并不重要（距离向量、链路状态、硬编码等）。因此，CBT 不依赖于任何特定的单播协议，并且可以与任何单播协议一起工作。

关于 CBT 的进一步阅读：https://people.eecs.berkeley.edu/~sylvia/cs268-2019/papers/cbt.pdf

DVMRP 和 CBT 哪个更好？正如我们所看到的，这两种协议各有取舍。

如果你有一个源向一个大型组发送数据，那么 DVMRP 可能是更好的解决方案，因为它将确保所有这些数据沿着网络中的最优路径传输。大量数据（发送给大量组成员）的传输中，使用最优路径会节省大量带宽。此外，如果组很大（例如，几乎包括网络上的所有设备），那么 DVMRP 偶尔的泛洪可能不是大问题。

相比之下，如果你的组很小，且成员分散在大型网络中，那么 CBT 可能是更好的解决方案。CBT 将避免向非成员泛洪数据包，这会浪费大量带宽（因为大多数设备都不是该组成员）。

在实践中，DVMRP 和 CBT 现在都在使用。DVMRP 有时被称为 PIM-DM（协议无关组播 - 密集模式），这反映了 DVMRP 适用于大型组的特点。CBT 有时被称为 PIM-SM（协议无关组播 - 稀疏模式），这反映了 CBT 适用于较小组的特点。

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