计算机网络中的汇聚树

定义

计算机网络中给定节点的汇聚树是由该节点与网络中所有其他节点通过最优路径（更准确地说是最短路径）连接而成的树。或者，换句话说，汇聚树是以给定节点作为目标节点，所有其他节点作为源节点形成的最小成本树。路径或成本的常用度量是跳数。

解释

汇聚树遵循最优性原理。根据该原理，在用于数据传输的路由器网络中，如果路由器“J”位于从路由器“I”到路由器“K”的最优路径上，则从路由器“J”到路由器“K”的最优路径也位于同一条路径上。

作为最优性原理的直接结果，可以看出，从所有源节点到目标节点的一组最优路由形成了以目标节点为根节点的树。

汇聚树可能不是唯一的。可以存在多个具有相同路径长度的汇聚树。路由算法的目标是找到网络中所有节点的汇聚树。由于在数据传输过程中，链路和节点可能会发生故障和恢复，因此备用汇聚树和路径也提供给节点。

作为一棵树，汇聚树不包含任何环路或循环。因此，每个数据包都可以在有限的跳数内传递。此外，数据包不会在子网上无限循环。

示例

下图左侧显示了一个网络，右侧显示了以节点 A 作为根节点的汇聚树。

更新于: 2021年2月3日

5K+ 浏览量

启动你的 职业生涯

通过完成课程获得认证

开始学习
广告