基于链路权重的SDN 组播链路恢复机制
2022-04-13崔丽丽曾学文朱小勇
崔丽丽，曾学文，朱小勇
（1.中国科学院声学研究所国家网络新媒体工程技术研究中心，北京 100190；2.中国科学院大学，北京 100049）
组播在网络层实现“尽力而为”的一对一组的传输功能，可以极大地减轻网络负载，但也存在传输效率低、安全性差、不易部署等问题[1-2]。软件定义网络（Software Defined Network，SDN）[3]为组播方式提供了解决思路。SDN 由控制器和数据转发设备（如交换机、路由器）两部分组成，通过抽象底层网络协议，以实现控制和转发的分离[4]，从而简化网络模型[5]。
有关研究表明，网络中的一条链路平均每30 分钟就会经历一次故障[6]，其概率高于节点故障，如果不能很好地解决单链路故障问题，网络数据传输将会遭遇很高的丢包率，这对数据敏感的应用来说是灾难性的，也会影响整体性能。
因此，组播链路故障快速恢复技术存在一定研究价值，针对以上问题，提出一种基于链路权重的组播树恢复策略（Multicast Tree Recovery Strategy based on Link Weight，LW-MTR）。
1 相关工作
组播链路故障恢复方法可分为主动式和被动式[7]。主动式方法在故障发生之前计算备份路径，当出现故障时，转换至备份路径，恢复数据传输[8]，时延较短，但造成了一定的资源损耗；被动式方法是在链路中断之后，重新寻找新的路径，消耗资源少，但时延较长。显然，针对备份表项的资源开销和恢复路径的时间开销需要策略进行有效权衡。针对两种策略，已有不少学者作出研究。
针对被动式恢复，文献[9]提出在检测到故障后，在主路径上标记并回溯数据包，向第一个方便的重路由节点发出故障信号，自动建立一条迂回路径。该方案的目标是在故障检测后实现零丢包，不需要控制器干预，不足之处为恢复时间较长。
针对主动式恢复，文献[10]提出一种拥塞感知的快速故障恢复方案(CAFFE)，该方案不仅可以从广泛的故障场景中快速恢复受影响的流量，而且可以避免恢复后网络中潜在的拥塞。CAFFE 通过在邻居交换机检测到故障时立即绕道而行来实现快速恢复，所有这些路径都是CAFFE 预先设置的，允许交换机自动恢复传输，而不需要等待控制器的响应。文献[11]提出基于分段路由的主动式链路故障恢复方案（SR-PLFR），将通过同一链路的受影响流视为聚合流，为之计算备份路径，并将其转化为混合整数非线性规划模型，把工作路径和备份路径划分成段，以满足硬件要求。但是，这两种恢复策略均存在消耗资源较多的问题。
也有研究提出主动恢复和被动恢复结合的机制。文献[12]提出一种保护加恢复式故障恢复机制，为所有路径设置备份路径，当出现组播链路故障后，由备份路径恢复组播链路传输，当控制器安装好新的最优路径后，再迁移至最优路径，不足之处为消耗资源过多。
2 组播树的恢复机制
2.1 问题描述
以下为一个组播链路故障的恢复实例。将每个交换机记为一个节点，以组播汇聚节点（Rendezvous Point，RP）为根节点建立组播树[13]，记故障链路中靠近根的节点为故障链路起点（StartNode，SN），记另一个端节点为故障链路终点（DestinationNode，DN）。
如图1 所示，8 个交换机和10 条链路构成组播树。其中，RP 与组播源相连，R5、R6、R7 与组播成员直连，3 条通信路径分别为RP-R1-R3-R6，RP-R2-R4-R7，RP-R2-R5。当
图1 组播链路故障恢复实例
提前备份路径对交换机中流表项有一定的挑战，需要交换机有充足的存储容量。
但是，有些链路并不需要提前备份路径，因此文中研究的重点在于平衡主动恢复所需备份表项的资源开销和被动恢复所需重新计算路径的时间开销，文中的研究按照链路权重（LinkWeight，LW），将组播链路分为两类，针对LW=1，找到最佳的备份方式；针对LW=0，即无需备份的链路，找到快速恢复链路的方法，平衡资源开销和时间开销，达到组播树的全局最优恢复。
2.2 链路权重
建立一个组播拓扑G=（N，L），其中，N表示交换机集合，L表示链路集合。对于一条链路l∈L，FDN（l）表示通过链路l的所有流的数量（FlowDataNumber，FDN）,可使用抓包工具监测数据流，获取FDN值。
定义1 在网络G中，设链路l（i，j）能提供的最大带宽为Bmax（l（i，j）），Bl（l（i，j））表示链路已消耗带宽，则l（i，j）链路带宽利用率（Link Bandwidth Utilization，LBU）如下：
其中，i、j为节点名称，可使用网络性能监测工具监测链路，通过获取链路已消耗带宽Bl（l（i，j））和链路最大带宽Bmax（l（i，j））计算LBU值。
基于FDN和LBU，为平衡主动恢复所需备份表项的资源开销和被动恢复所需重新计算路径的时间开销，将组播链路进行分类，针对每类链路使用对应的恢复策略，链路权重的评估标准如下：
其中，α+β=1，α∈[0,1]，β∈[0,1]，α和β用来调节FDN和LBU之间的权重，需要注意的是，。因此，LW的最大值为1，最小值为0。将LW二值化，[0,0.4]定义为LW=0，(0.4，1]定义为LW=1。
按照图2的示例拓扑，设α=0.5、β=0.5，16 条链路的链路权重值如表1 所示，根据LW的取值对链路分类。其中LW=1的链路需要提前备份，LW=0的链路待中断后再重建路径。
表1 链路权重值
图2 链路权重示例拓扑
2.3 故障恢复策略
2.3.1 主动恢复
对于主动恢复（Active Recovery，AR），AR（l）表示网络G=（N，L）中的主动恢复链路l集合，AR（l）={l|l∈L,LW=1}。
AR（l）是LW=1的所有链路的集合，对于LW=1的链路来说，每一条链路失效都会对大片区域产生影响，会导致组播树中的多条链路传输中断。因此，针对LW=1的链路，为了组播数据高效地传输，以较短的时延达到尽快恢复组播树的效果，需要一个备份机制对高权重链路进行备份。当检测到链路中断时，采用备份链路，将时延降到最低，重构组播树，恢复组播数据的接收，提升组播的传输效率。
采用Networkx[14]中的all_shortest_paths 函数，利用Dijkstra 算法，将AR中工作链路起点到目的组播成员所有备份路径放在AllBackupPath。然后按照备份交换机数量增序排列，如果备份交换机数量相同，则按照带宽利用率增序排列，备份路径选择策略算法如下：
如图1 所示，如果
2.3.2 被动恢复
对于被动恢复（Passive Recovery，PR），PR（l）表示网络G=（N，L）中的被动恢复链路l集合PR（l）={l|l∈L,LW=0}。
PR（l）是LW=0的所有链路的集合，即链路l具有较低权重的链路。即通过链路l的流的数量很少或这些流对时延和丢包率的需求不高，因此，不需要对这些链路提前备份以免造成资源过度消耗。
当检测到某条链路故障时，使用Networkx 中的all_shortest_paths 函数，寻找故障链路起点与目的组播成员间的备份路径，并按照最小带宽利用率优先的原则，选择重构路径，恢复组播数据的接收；
当故障链路起点与目的组播成员间的最短路径不存在，使用Networkx 中的all_shortest_paths 函数，寻找RP 与故障链路终点间的备份路径，并按照最小带宽利用率优先的原则，选择重构路径，完成组播数据的继续传输，被动恢复策略算法如下：
如图1 所示，如果
3 仿真实验
3.1 仿真环境
在控制层面和数据转发层面，分别选择控制器和交换机进行仿真实验。表2 为仿真环境参数，并选择表3 中两种网络拓扑进行实验。
表2 仿真环境参数
表3 拓扑信息描述
3.2 仿真结果
假设所有链路的故障率相同，为仿真链路故障，在Mininet 中采用“link node1 node2 down”指令使node1node2 链路中断，为获取LBU值，采用Iperf 软件监测链路，获取链路已消耗带宽Bl（l（i，j））和链路最大带宽Bmax（l（i，j））。采用Wireshark 抓包，获取FDN值。采用备份流表项占比、路径恢复时间两个指标作为评价标准，并与现有的方法进行对比，如表4所示。
图3 基于Fat-tree（K=4）的网络拓扑
表4 故障恢复策略对比
3.2.1 备份流表项占比
在主动式恢复中，需要提前备份路径，因此产生了一定程度上的资源消耗，使用BF（Backup Flow Table Entry）表示备份路径所需的总流表项数，WF（Work Flow Table Entry）表示工作路径所需的总流表项数，记备份流表项占比PBF=BF/（BF+WF）；备份PBF数值越大，代表备份流表项占总消耗资源的比重越大，一定程度上为链路带来了较重的负载。
考虑到数据的可靠性，采取多次实验取平均值。如图4 所示，改变组播成员数量，当接收者不断增加时，通过链路的数据流的数量和链路的带宽利用率都会增加，由公式可知，链路权重变大，故而需要提前备份的路径增加，备份流表项占比不断增加。因为被动恢复不需要提前备份路径，只在链路故障之后才会重新计算，所以方案DPR的备份流表项占比低于方案CAFFE和LW-MTR，比方案CAFFE 减少大约27.2%，比方案LW-MTR 减少大约10.1%。对比方案CAFFE，方案LW-MTR 备份路径流表项占比减少大约17.1%。在拓扑2上进行了相同的实验，如图5所示，相比方案LW-MTR备份流表项占比减少15.1%。
图4 拓扑1实验结果
图5 拓扑2实验结果
根据仿真数据可以说明，方案LW-MTR 备份流表项对比方案CAFFE 有所减少，可以有效减少链路中的负载，优化交换机中流表项的备份数量。
3.2.2 路径恢复时间
故障恢复时间(Failure Recovery Time)[19]包括故障检测时间（Fault Detection Time，TFD）和路径恢复时间（Path Recovery Time，TPR），如图6 所示。
图6 故障恢复时间
为缩短故障恢复时间，可从减少故障检测时间和路径恢复时间两个方面入手，文中的研究内容为减少路径恢复时间。在目的节点上，采用Wireshark抓包，以观察数据流的传输。记录检测到链路中断后的时间T1，并获取链路中断后恢复接收第一个数据包的到达时间T2，路径恢复时间即为T2-T1。
在拓扑2 中，改变组播成员数量，使故障链路的数量保持一定，并进行多次实验。实验数据如图7 所示，方案LW-MTR的路径恢复时间最短，平均比方案CAFFE 减少了4.6 ms，因为方案DPR 是被动恢复，恢复时间较长，方案LW-MTR 平均恢复时间比方案DPR 减少了6.8 ms；还可以观察到，改变组播成员数量，保持故障链路数量一定，恢复时间只是略微增加。
图7 拓扑2实验结果
4 结束语
文中提出了基于链路权重的SDN 组播链路故障恢复机制。为平衡备份表项的资源开销和恢复路径的时间开销，首先根据链路带宽利用率和数据流的数量定义链路权重，然后针对不同的链路提出了两种策略，针对链路权重LW=1的链路，采用主动恢复的方式，针对链路权重LW=0的链路，采用被动恢复的方式，并与现有方法进行了对比，采用备份流表项占比和路径恢复时间作为评价指标。仿真实验结果显示，该方案在备份流表项占比和路径恢复时间上有明显优势。
