论文来源

  • 标题：Efficiency of BIER Multicast in Large Networks
  • 期刊：「TNSM」IEEE TRANSACTIONS ON NETWORK AND SERVICE MANAGEMENT
  • 作者：Daniel Merling, Thomas Stüber, and Michael Menth, Senior Member, IEEE
  • 机构：University of Tübingen, Germany
  • 发表时间：December, 2023
  • 论文链接：IEEE Xplore

引言：IP多播流量的高效传输问题

在现代网络中，IP多播（IPMC）技术是实现一对多通信的有效手段，广泛应用于多媒体传输、内容交付网络（content delivery networks, CDN）等场景。然而，随着网络规模的扩大和多播组数量的增加，传统的IP多播技术面临着可扩展性的挑战。核心网络节点需要为每个多播组维护状态信息，这不仅增加了节点的存储和处理负担，还可能导致在拓扑变化或节点故障时产生大量的信令开销。为了解决这些问题，IETF提出了一种新的多播传输机制——Bit Index Explicit Replication (BIER)。BIER通过使用位掩码标记多播接收者，从而简化了多播组的存储和数据转发成本，且提高了IP多播在大型网络中的可扩展性。本文将深入探讨BIER技术的基本原理，以及它如何在大型网络中高效传输IP多播流量。

BIER的基本原理

概述

BIER技术的核心思想是通过一个位索引（Bit Index）来表示多播的接收者，而不是传统的通过一组多播路由或树来实现。这种方法极大简化了多播组成员的管理和数据包的转发过程，因为它不需要在网络中建立和维护复杂的多播分发树或进行复杂的组管理协议交互。

在BIER中，多播数据包的头部包含了一个位掩码（BitString），每一位代表一个特定的接收者。当一个多播数据包被转发时，网络中的每个节点都能通过查看这个位掩码，直接决定数据包应该被转发到哪些接口或下一跳。这种方式大大减少了多播的复杂性，同时提高了转发效率。

实现过程

  1. 位掩码和接收者映射：网络中的每个可能的多播接收节点都被分配一个唯一的位索引。这个索引被用来在多播数据包的位掩码中标识该节点。当一个节点需要发送多播数据时，它根据目标接收者的位索引，构造一个位掩码，每个目标接收者对应的位设置为1。
  2. 封装多播数据包：发送节点在多播数据包的头部加上BIER头，其中包含了目标接收者的位掩码，然后将数据包发送到网络中。
  3. 数据包转发：网络中的每个节点接收到带有BIER头的多播数据包后，通过查看其位掩码。然后，节点根据自己的BIER转发表来解析位掩码，确定数据包应该被转发到哪些接口或下一跳路由。
  4. 多路径转发：在一些配置中，一个位索引可能映射到多条路径或多个下一跳路由。在这种情况下，节点可能会根据预定义的策略（如负载均衡、故障恢复）来选择具体的下一跳或同时向多个下一跳转发数据包。
  5. 剥离位掩码：当数据包到达一个目标接收者时，接收节点的位索引对应的位掩码中的位会被检查。如果匹配，数据包会被交付给上层应用；否则，数据包会被丢弃。在某些实现中，为了进一步提高效率，数据包在传输过程中的每一跳可能会根据需要更新其位掩码。
  6. 优化和扩展：为了提高效率和扩展性，BIER还支持各种优化和扩展策略，如使用段路由（Segment Routing）技术来进一步减少头部开销，或者利用SDN（Software Defined Networking）技术动态调整位掩码，以适应网络条件的变化。

BIER的扩展和子域

由于位串的长度有限，当BIER域中的出口节点数量超过位串能表示的范围时，就需要引入扩展功能。BIER通过引入子域的概念来解决这个问题。子域是出口节点的集合，每个子域都有自己的位串定义。因此，如果一个多播数据包需要被转发到不同子域中的出口节点，就会发送多个具有不同BitString的BIER数据包，并可能通过相同的链路传输。这种设计虽然在一定程度上降低了BIER分发多播流量的效率，但通过合理选择子域，BIER仍然能够有效地减少多播流量所需的传输负载。

通过上述分析，我们可以看出BIER技术在大型网络中传输IP多播流量时具有显著的优势，尤其是在减少核心网络状态管理和信令开销方面。然而，合理的子域划分对于确保BIER技术的高效性至关重要。

BIER与传统IPMC的对比

传统的IPMC通过在网络中的每个节点上维护特定的多播组状态来实现数据包的分发，这种方法在小规模网络中表现良好。然而，随着多播组数量的增加，核心节点需要维护庞大的转发信息库（FIB），导致了三个方面的可扩展性问题：一是核心节点需要维护可能非常庞大的FIB；二是当订阅者变化时，受影响的IPMC组需要更新，这会引起严重的信令开销；三是当链路或节点故障，或者拓扑变化时，许多多播组的流量可能会受到影响，从而导致许多路由器经历大量的信令负载。

BIER通过使用BitString标记每个多播接收者，从而避免了维护多播组的存储和信令传输开销，实现了状态无关的传输。然而，当网络规模扩大后，多播接收者的数量会超出有限长度的BitString的表示范围，因此BIER引入了子域的概念，将接收者划分到较小的子域中，然后分别为每个子域发送BIER多播数据包。此时，BIER显然违背了多播一次发送多点接收的初衷，降低了多播的效率。

综上所述，BIER相较于传统IP多播在大型网络中的可扩展性方面具有明显优势，但其效率在流量负载减少方面却不如IPMC。

BIER的挑战：大型网络中的BIER子域分配问题

在大型网络中，BIER的子域分配问题变得尤为重要。由于BIER在传输过程中，不同的BIER子域划分方式，可能会产生不同数量的多播数据包副本同时在网络中传输。因此，怎样合理划分子域，以便在发送多个数据包副本的情况下仍保持较低的BIER流量，是BIER在大型网络中的重要应用挑战。 本文的工作提出并比较了多种算法来选择BIER网络的子域，包括随机子域聚类、最优子域聚类算法（特定拓扑结构下）、整数线性规划子域聚类算法和启发式算法。本文的结果表明，适当的子域选择对于降低大型BIER网络中的流量负载至关重要。

随机子域聚类

随机BIER子域聚类算法是最简单的方法，它将一组BIER的出口节点（BFER）随机分配到子域中，每个子域的大小限制为b个BFERs。本文在评估中使用这种算法作为基线进行比较。

最优子域聚类算法（特定拓扑结构下）

对于选定的规则拓扑，如线状、环状和完美二叉树，我们描述了最优子域聚类。例如，在线状拓扑中，从一端开始，将接下来的b个相邻节点分配到一个子域中。在环状拓扑中，选择一个任意位置并选择一个方向，然后将接下来的b个相邻节点分配到一个子域中。对于完美二叉树，假定树的高度为$h$，则一共有$2^h-1$个节点。假设BitString的大小为$2^k$，本文将所有根深度为$h-k+1$的子树作为初始子域，其他未分配的节点被分配到最近的可能的子域。

整数线性规划子域聚类算法（最优）

本文设计了一个总体流量负载最小化的最优子域聚类问题的整数线性规划模型。决策变量：$x^S_v$ 表示节点$v$ 是否属于$S$ 子域，$y^S_{v,e}$ 表示与节点$v$ 相连的链路$e$ 是否为子域$S$ 的转发路径。

启发式子域聚类算法

本文提出了一个包含两个阶段的启发式聚类算法。第一阶段选择初始子域，第二阶段根据目标函数改进这些子域。该算法首先随机选择s个节点作为不同子域的中心节点，然后将最近的未分配节点分配给这些中心节点，直到达到b个BFERs。重复第一阶段以生成多个聚类，并选择最佳聚类进行第二阶段的改进。

本文的评估结果表明，启发式算法的结果与最优算法相比非常接近。整数线性规划算法的运行时间随着网络规模（尤其是子域数量）的增加而增加，对于某些拓扑，具有128个节点或具有4个子域的网络，整数线性规划算法难以在3天内得出计算结果。因此，整数线性规划算法仅适用于小型网络拓扑。对于网络规模多达2048个节点的网络来说，启发式算法的质量几乎是最优的。对于更大的网络，启发式算法的质量有所下降，但仍然比随机子域要好得多。因此，启发式算法可能适用于实际应用中的子域优化。

实验验证：网络拓扑、规模和多播组大小的影响

在研究网络中多播传输的效率时，网络拓扑、网络大小以及多播组的大小是影响多播效率的关键因素。为了深入理解这些因素如何影响多播传输，本文设计了一系列实验来分析它们对多播效率的具体影响。

1. 网络拓扑的影响： 网络拓扑是指网络中节点的布局和它们之间连接的模式。不同的网络拓扑，如全连接拓扑、线性拓扑、环形拓扑和二叉树拓扑，会导致数据包在网络中的传播路径不同，从而影响多播传输的效率。例如，在全连接拓扑中，每个节点都直接与其他所有节点相连，这可能导致多播传输没有显著的流量节省；而在线性拓扑或环形拓扑中，多播传输可以显著减少重复数据包的数量，因为多个接收者可能会共享相同的传输路径。

2. 网络规模的影响： 网络规模即网络中节点的总数。在大型网络中，多播传输相较于单播传输可能会节省更多的流量，因为单播需要发送多个副本到不同的目的地，而多播可以通过构建分发树来避免这种重复。然而，当网络规模增大到一定程度时，传统的IP多播（IPMC）可能会遇到可扩展性问题，因为核心节点需要维护与多播组相关的状态信息。这时，BIER能够通过将接收者划分为不同的子域来扩展多播传输的规模。

3. 多播组大小的影响： 多播组的大小指的是接收特定多播数据的节点数量。多播组的大小直接影响到多播传输的效率。在小型多播组中，多播与单播之间的流量节省可能不明显，因为多播传输的优势在于同时向多个接收者发送相同的数据。随着多播组大小的增加，多播传输的流量节省潜力也会增加。

流量规模分析

本文比较了传统IPMC和BIER在不同网络拓扑、网络规模和多播组大小下的流量规模。实验结果显示，两种多播机制在节省网络流量方面都有潜力，但它们的表现受到网络拓扑和多播组大小的影响。

1. 网络拓扑： 在线性和环形拓扑中，IPMC和BIER都能显著减少与单播相比的总体网络流量。这是因为这些拓扑结构中存在许多共享路径，多播可以有效利用这一点来减少重复的数据包传输。然而，在全连接拓扑和具有较高节点度的随机拓扑中，多播的流量节省潜力较低，因为这些拓扑结构提供了更多的直接连接，从而减少了多播的优势。

2. 网络规模： 随着网络规模的增加，IPMC的流量节省潜力增加，而BIER的流量节省潜力则受到子域数量的影响。在大型网络中，BIER可能需要发送多个冗余包以覆盖所有子域，这可能会降低其相对于IPMC的流量节省效率。尽管如此，BIER在大多数网络拓扑中仍然能够有效减少多播流量。

3. 多播组大小： 多播组大小的增加会提高IPMC和BIER的流量节省潜力。在小型多播组中，两者相比单播的流量节省并不显著。但随着多播组大小的增加，节省的流量也随之增加。这一结果表明，多播传输在大型多播组中更为有效。

BitString大小分析

BIER协议头部的BitString大小对多播传输的效率有直接影响。一个较小的BitString会减少每个数据包的额外开销，但可能需要更多的多播数据包副本来覆盖大型网络中的所有子域。相反，一个较大的BitString可以减少多播数据包副本的数量，但会增加每个数据包的大小。因此，寻找最优的BIER头部大小是实现高效多播传输的关键。

在本文的实验中，作者发现最优的BitString大小取决于网络拓扑和多播组的大小。在小型多播组和具有较短路径的拓扑结构（如二叉树、低节点度的网格）中，较小的BitString是最优的。而在大型多播组和线性或环形拓扑中，较大的BitString可以减少冗余包的数量，从而降低总体流量。 总的来说，实验结果表明，合理选择BitString大小对于提高多播传输的效率至关重要。在实际应用中，如果多播组的大小未知，选择一个中等大小的BitString可能是一个折中的选择。

单链路故障对BIER效率的影响

当发生单链路故障时，IP网络需要重新路由受影响的数据包，然后流量会绕过故障链路进行转移。因此，单个链路负载和总体流量负载可能会增加。 对于单链路故障后将网络分割为多个无法相互连通的子网的故障情况不在本文的考虑范围之内，因为此时多个子网无法互相连通，不存在可供恢复的策略。对于单链路故障后仍能保持连接的网络，由于IPMC不存在分域机制，在重路由后多播数据包将按照新的最短路径树转发，因此IPMC的流量负载不会增加。

但对于BIER来说，当流量重新路由后，每一个分域的路由跳数将会发生变化，从而增加网络整体的链路负载。以较为极端的环形拓扑为例，单链路故障后，两个节点之间的路由跳数将由较短变为环形的最长路径，这会导致路径拉伸并使总体流量负载增加。作者实验的环形网络中，总体流量负载将增加15%-17.3%。在非极端的mesh网络中，作者测试的总体流量负载的增长幅度为0.2%，因为在mesh网络中，单链路故障可能并不能显著增加端到端的路由长度。

因此，为了保持网络的鲁棒性，需要在设计BIER子域时考虑到链路故障的可能性，并确保有足够的备份容量来处理这些情况。从上述测试也可以看出，在非环状的网络拓扑下，BIER并不会导致过多的链路容量备份需求。

总结：BIER在大型网络中的应用前景和挑战

BIER作为一种新型的IP组播传输机制，通过其独特的位索引技术，提高了IP组播的可扩展性，特别是在大型网络中。BIER通过使用子域来扩展其在大型网络中的应用，使得核心节点无需了解每个组播组的详细信息，从而简化了网络的管理和维护。

BIER在大型网络的应用前景

BIER在大型网络中的应用前景是乐观的，因为它能够有效地减少组播组状态信息在核心节点上的存储需求，同时减少了因组播组成员变动而引起的信令开销。此外，BIER还能够避免在网络中产生重载链路，这对于流量密集型的应用场景尤为重要。

面临的挑战

尽管BIER在大型网络中有着明显的优势，但它也面临一些挑战。其中最主要的挑战是如何高效地管理子域，以及如何在链路故障时保持网络的鲁棒性。多播数据包副本的产生可能会增加网络的总体流量，尤其是在子域数量较多的情况下。此外，确定最优的BIER头部大小以平衡头部开销和冗余数据包数量也是一个挑战。

未来的研究方向

  1. 改进BIER的子域聚类算法
    • 当前的BIER子域优化算法虽然能够在一定程度上减少冗余数据包的数量，但仍有改进的空间。未来的研究可以探索更高效的算法，以进一步减少因子域划分不当而产生的额外流量。
  2. 考虑BIER-TE的扩展问题
    • BIER-TE（BIER Traffic Engineering）是BIER的一个扩展，它允许对数据包的分发树进行工程优化。未来的研究可以考虑如何将BIER-TE扩展到更大的网络规模，以及如何在链路故障时快速有效地重新路由流量。
  3. 研究BIER在不同网络拓扑中的表现
    • 不同的网络拓扑可能会对BIER的效率产生不同的影响。未来的研究可以探索BIER在各种网络拓扑中的表现，以及如何根据网络拓扑的特点来优化BIER的子域划分。

思考

  • BIER能通过划分子域将一个多播数据包拆分为多个多播数据包，从而提高其在大型网络中的扩展性。那传统的IPMC为什么不能通过这个思路来提升扩展性呢？