刘艳萍，杨喜敏*，冯伟，唐菀

(1 中南民族大学 计算机科学学院，武汉 430074；2 海能达通信股份有限公司，深圳 518000)

随着Internet的飞速发展，特别是5G时代的到来，视频直播、IPTV、实时监控等网络业务与应用与日俱增[1-2].一发多收的组播显然比一对一的单播更符合这些网络业务的性能需求[3-4]，但由于资源容量的有限性和组播协议复杂[5]等诸多原因，传统的组播技术已难以适应这些业务的大规模应用[6].软件定义网络(Software-Defined Networking, SDN)与生俱来的全局视角和可编程等特性[7-8]，可以赋予组播管理更高的效率和灵活性[9-10]，但实时维护数据平面转发设备中的组播报文转发规则，既会增加控制器的负担，也会影响组播报文的传输性能[11].

位索引显式复制(Bit Index Explicit Replication, BIER)[12]是一种新的协议无关组播技术.中间节点完全基于组播报文携带的二进制位串跨域转发组播报文[13]，既不需要维护每条组播数据流的状态，也不受接收者动态变化的影响，极大简化了组播信息管理和维护的时空复杂度，能提升组播报文的转发效率，且易于实现大规模组播结合 SDN的全局视角等固有优势，BIER还可有效应对组播网络动态变化的问题[14].

BIER的组播报文转发规则用一个二进制位串来表示,其中的每一位对应一个交换机/转发设备.要支持BIER，交换机就需要配备位索引转发表(Bit Index Forwarding Table, BIFT)，并依据其存储的转发规则来转发组播报文.因此，为网络中的所有交换机构建BIFT是BIER应用时的关键之处.尤其是当网络拓扑发生变化或动态规划网络资源而需调整组播报文的传输路径时，BIFT重构效率不仅会直接影响组播报文的传输性能，甚至会导致网络传输的中断.

文中将对组播路由树依据接收者的构成模式进行分类，并设计基于子树分类和归并的BIFT构造器(BIFT Constructor based on Classifying and Combining, C3-BIFT)，通过一次组播路由树的回溯遍历，快速构建所有交换机的BIFT，以尽量减小对接收者加入延迟和组播报文传输性能的影响.

1 相关工作及问题描述

BIER自2014年被提出后就备受关注. IETF于2017年发布的RFC 8279和2019年4月发布的BIER体系架构RFC 8556中，详细描述了服务供应商的骨干网络如何承载组播流量的方法、协议和过程.既有研究结果表明，BIER不仅能够使SDN网络组播的管理和配置更加简单和高效[12]，组播报文的快速重路由也相当简捷[13].HF-BIER(Hierarchical Forwarding Bit Index Explicit Replication)模型[15]是通过分层BIER网络的方法来解决链路中的数据冗余问题.PAPN 等提出的IPFRR(IP Fast Reroute)则是以位串替代反向路径信号的机制，来解决由于链路或者交换机故障导致的网络流量中断问题[16].不过，这些研究较少涉及BIER位串和交换机BIFT的更新和重构方法，是否能在网络拓扑变更、组播组成员变化以及动态规划网络资源时依然保证组播性能尚未可知.

在一个由8个交换机(s1 ～ s8)组成的网络，如图1所示，当有源连接于s1、接收者连接于s5的组播组W时，一是要基于组播路由树为网络中的交换机构建BIFT；二是交换机s1要以位串“00010000”将组播报文封装成BIER报文后才能依据其BIFT中的规则转发到相应的端口；三是后续交换机在转发报文时，需要修改BIER头中的位串以保证报文传输的方向.因此，当组播组固定且传输路径不变时，BIFT的构建重点在于是否正确，而不是构建效率.

当有名为h的主机(假设连接于s3)要加入组播组W时，s3将h的加入请求以packet_in消息发送给控制器；组播管理器通常是一个SDN北向应用或控制器中的模块，既需要重构交换机BIFT，也需要通知s1使用新的位串“00010100”来标记组播报文.这些工作在SDN网络中，都是通过控制器下发的流表/组表项来完成.也就是说，相对于传统组播主机加入延迟，BIER用于SDN网络组播时，加入延迟不仅包括各种报文的封装与传输时延，还包括请求处理、组播路由树构造、BIFT重建和入口位串生成等的处理时间.除BIFT重建和入口位串生成的时间开销外，其它时延也是SDN网络组播加入延迟固有的构成部分.因此，要保证组播报文的传输性能和请求者的加入延迟没有明显变化，就必须快速重建相关交换机的BIFT和入口交换机的BIER头.

图1 BIER通信过程Fig.1 BIER communication process

2 解决方案

2.1组播子树分类及其BIFT

交换机的BIFT存储组播报文的分发规则，初始BIER头实际标注的是接收者直连的交换机，再加上组播树的生成算法已相当成熟，通过组播树构建交换机的BIFT显然是一种优选的解决方案.组播树通常有源树和共享树两种.源树是以组播源为树根、以接收者为叶子的转发树；共享树则是以汇集交换机为根、以接收者为叶子的转发树.鉴于共享树中组播源与汇集交换机的报文传输并不影响BIFT的构建过程，下面基于源树来描述交换机BIFT的构建方案.

定义1：基于网络拓扑图G(V,E)生成的组播源为h的源树,是以h的直接后继为根的子树的集合Th={Tv|v∈V-{h},(h,v)∈E}. 其中，V是非空的节点集，E是非空的节点间的边集.

推论1：源树Th中的接收者集合为：R={v|v∈V-{h},不存在x∈V,(v,x)∈E}；交换机集合为：S=V-{h}-R.

(1)

BIER本身只定义了中间节点的报文转发规则，因此，为保证报文传输过程的完整性，即为交换机构造BIFT的同时也构造交换机向接收者的报文转发规则，所提出的解决方案基于树根的直接后继节点集的构成模式，依据式(1)将树中的节点划分为A、B和C三类，如图2所示.

图2 子树类型Fig.2 Types of subtrees

事实上，A类子树的根都是组播报文的接收者；B类子树仅需将组播报文转发给它连接于它的A类子树；C类子树稍复杂，既需本地转发组播报文，还需维护BIER头中的位串，以保证报文的传输方向.

定义2：BIER的组播报文转发规则是一个由位串、邻节点和报文出端口构成的三元组.

定义3：一个BIFT是由BIER组播报文转发规则构成的集合.

Bbift(v)={(2N(v),-,locale)}∪{(0,i,vi)|Ti∈Tv,f(i)=A} ，

(2)

(3)

2.2 组播子树归并

组播子树归并是将组播子树归并为以其根节点表示的一个单一节点，且根节点的类型不变.A类子树无需归并，或可认为归并结果与原节点相同；B类和C类子树归并后为一个类型不变的单一节点，子树归并及BIFT生成过程如图3所示.

m:Tv=∑Ti∈Tv,f(i)=BN(i)+∑Tj∈Tv,f(j)=Cm(j)+N(j).

(4)

定义4：组播子树归并后的位串为其所有子树的位串的和.计算过程见式(4).

图3 子树归并及BIFT生成Fig.3 Subtree merging and BIFT generation

子树归并后，B类子树仅需向其父节点注册其自身的信息，而C类归并后，则需向其父节点归集其自身及其子树的位串.

子树归并的过程是各节点的BIFT逐步向上归并直至组播树的树根的过程.

2.3 算法描述

基于前面对解决方案的描述，C3-BIFT采用深度优先递归遍历名为T的路由树，生成每个节点的BIER串及每个交换机的BIFT，并对子树进行合并，再以向上回溯的方法处理下一个子树，直到到达树T的根节点.下面给出C3-BIFT的伪代码描述.

算法:BIFT生成算法 C3-BIFT输入:组播树T, 根节点s1输出:BIFT表bift_table1.Ts ← SubTree(s1)2.while Depth(Ts) != 2 do3. ∃ si ∈ s.Child4. C3-BIFT (T,si, bift_table)5.end while6.tree_type← SubTreeType(Ts)7.if tree_type == 'A' then8. bift_table←treeInfo(s,'00000000',port) 9.else if tree_type == 'B' then 10. bift_table ← subTreeInfo(s, Ts) 11. bift_table← treeInfo(s, cString, 'local') 12. CombineSubtree(Ts, bift_table)13.else if tree_type == 'C' then 14. bift_table← subTreeInfo(s, Ts)15. bift_table← treeInfo(s, cString, 'local')16. CombineSubtree(Ts, bift_table)17.end if18.return bift_table

C3-BIFT算法从树T的根节点s1开始，进行深度优先递归遍历每一个节点的孩子节点，直到到达只有一个节点的子树Ts，这个子树为A类子树或者B类子树.随后对子树Ts进行相关处理，如果子树是A类子树，则s的位串为“00000000”；如果是B类子树或C类子树，首先生成s的BIFT，存入map_tree中，再合并子树Ts为子树根节点s，s的位串为s的BIFT中所有位串逻辑或后的值；然后返回本次的bift_table，结束本次递归，进入上层递归，继续以上操作，直到子树Ts的根节点为树T的根节点，返回最终的bift_table，算法结束.

由于C3-BIFT采用深度优先递归遍历组播树的所有节点，其时间复杂度为O(n=|T|)；空间复杂度则相关于树的最大深度d，为O(d)，当树趋于平衡时，d逼近Log(n).

3 实验与性能评估

3.1 仿真环境及性能指标

实验在Ubuntu 16.04系统上使用Mininet 2.2.1网络模拟器进行，选用OpenDayLight 0.6.4 Carbon作为SDN控制器，使用VLC 2.2.1和Wireshark 2.6.1分别完成数据包发送和分析.

仿真实验的网络拓扑如图4所示，网络中有8个交换机、8个接收者、1个组播源，组播源h0用来发送数据，交换机s1为BIER组播入口交换机.

图4 实验网络拓扑Fig.4 Experimental network topology

主要采用组播加入延迟、流表项数和BIFT构建时间三项指标，通过与传统的SDN组播进行对比来评估C3-BIFT算法对网络性能的影响.这里的流表项数指的是每次组播网络组成员发生变化，需要更新的交换机流表项数，此指标能够有效地反映组播延迟与流表项更新数的关系.

3.2 结果与分析

仿真实验在下面4个场景进行，测量采用C3-BIFT算法后网络中组播接收者的加入延迟，并与基于SDN的传统组播进行对比，取10次测试平均值作为接收者初始加入延迟.

(1)初始加入：单个接收者加入初始组播组，即组播组第1个接收者加入.

(2)空组加入：每次从所有主机中随机选择一个接收者加入空组播组，即仅当组播组中没有任何其他接收者时，才允许该接收者加入组播组，但不要求组播组为初始状态.每轮测试8个接收者.

(3)连续加入：每次从所有主机中随机选择一个接收者加入组播组，直至所有接收者都加入组播组.与空组加入不同的是，接收者加入组播时并不要求组播组为空，且加入后不会离开组播组.

(4) 随机加入：接收者随机加入或离开组播组.与其它实验不同，接收者既可以加入，也可以离开组播组，且任何接收者加入组播组时也不要求组播组必须是空的.每次测试采集50次接收者的加入延迟，最后计算每个接收者的多次加入延迟的平均值为其加入延迟.

组播加入延迟如图5所示， BIER组播接收者的加入延迟基本小于传统SDN组播中的加入延迟，传统的SDN组播接收者加入延迟的波动也更加明显.这是由于在每次接收者加入或退出组播时，支持BIER的控制器只需向发送者直连的交换机下发1条组表项，向接收者直连的交换机下发1条流表项，即可完成组播报文的传递.而在传统的SDN组播中，控制器需要向组播路径上的所有交换机下发流表项，下发流表项的数目完全取决于组播路径中的交换机数量.在本实验的4个场景中，当交换机直连的主机已经有了接收者的情况下，传统SDN组播只需要下发/更新一条流表项就可以完成新接收者的组播处理.例如，在图4的拓扑中，如果h3已经在组播内，这时h8再加入组播组的话，传统的SDN组播只需要更新一条流表项就可以完成新的组播报文的传递.仿真实验的网络中，交换机数量有限且层数较少，在连续加入的场景中，传统的SDN组播网络平均只需要更新1.875条流表，但是传统组播每次主机加入都要进行寻路，而BIER组播只需要进行简单的位串计算就可以，寻路的过程远比BIER的位串计算时间要高，从而传统组播接收者的加入延迟基本比BIER组播网络接收者的加入延迟高.还可以看到，由于接收者加入BIER组播时，控制器仅需控制入口和出口交换机，所以，无论接收者是密集还是稀疏，接收者的加入延迟都不会像传统的SDN组播网络那样存在较大的波动，而是会处于一个相对稳定的态势.

图5 组播加入延迟Fig.5 Multicast join delays in different scenarios

C3-BIER算法为所有交换机构建BIFT时间与树的深度、宽度与节点数的关系如图6所示，从其中可以看出BIFT构建时间与树的深度与节点数基本成正相关；当树的宽度小于30时，BIFT的构建时间随着宽度的增加缓慢上升，而当树的宽度大于30时，BIFT构建时间随着宽度的增加上升比较明显.

图6 交换机BIFT构建时间与树的深度、宽度、节点数的关系Fig.6 The relationship between the BIFT construction time and thetree depth and width, and the number of nodes on the tree

总体而言，多播加入延迟的高低主要与下发流表项或组表项的数量有关.传统的SDN组播网络接收者加入延迟与交换机的数量有着密切的关系，而在采用BIER的组播中，接收者加入组播时涉及的交换机最多只有2个，使得加入延迟更加稳定.此外，实验也验证了所设计的BIFT构建算法的有效性，且接收者加入组播组时的请求处理时间没有明显增加.

4 总结与展望

BIER采用位串匹配的方式进行组播报文的转发，能够有效的适应动态的组播网络.所提出的解决方案能够在组播网络发生变化时，通过快速重构各个SDN交换机的BIFT，强化BIER组播对网络动态变化的适应能力.设计的基于子树合并和分类的BIFT构建算法C3-BIFT中，采用所提出的依据组播报文接收者的组播路由子树分类模式，通过一次组播路由树的回溯遍历，为全网交换机构建BIFT.仿真实验表明，接收者加入BIER组播时涉及的交换机将不超过2个，使接收者的加入延迟比较稳定，不会呈现出类似于传统的SDN网络的波动.所提出的C3-BIFT算法的时间开销几乎不增加流表的更新时间，也不会导致接收者的加入延迟发生明显的变化.下一步工作将继续优化C3-BIER算法，以能够在组播网络拓扑发生变化的情况下，实现全网交换机的BIFT快速重构.