网络编码与家族体系下的可靠多播方案

周艳玲，张思成

(合肥学院 计算机科学与技术系，安徽 合肥 230001)

1 引言

在多播中应用网络编码技术，除了有提升网络吞吐量的显著优势，还有实现多播网络的流量均衡、提高带宽利用率、提升网络的可靠性、降低最优吞吐量问题的计算复杂度[1]等优点.网络编码理论使得在单源多播的网络环境下，数据的传输可以达到最大流最小割定理所决定的网络流量理论上的最大值[2].在有向无环网络中研究最早也较为成熟的网络编码是线性网络编码，在线性网络编码中网络节点对传输的信息进行线性操作.在多播网络中，只要在足够大的有限域Fq中通过合适的线性网络编码，总能使多播传输达到其理论的最大容量.允许多播中的网络节点进行网络编码，网络编码能够显著改善网络的性能，使得多播传输达到其理论传输容量.

本文在研究其它多播容错算法和网络编码的基础上，提出一个新的可靠多播方案，即，网络编码与家族体系下的可靠多播方案(Reliable Multicast Scheme Based on the Family System and Network Coding, RM-FSNC).通过引入家族等级关系和隧道技术对多播故障进行有效的恢复，引入网络编码提高网络的容量和安全性.在一定程度上节省了网络资源，降低了网络开销，有效地提高了多播可靠性.

2 相关工作

随着网络的发展和网络新应用的出现，多播通信势在必行.多播的可靠性是广大用户关心的头等重要的问题.处理多播网络通信的故障恢复也成为一个研究的热点问题.近几年来在多播故障恢复方面的研究却很少.

传统的多播中，数据流以树结构进行分发，一条链路出现故障将影响它的下游多个多播组成员的通信.一些研究提出利用单播恢复方案来实现多播通信下的故障恢复，如文献[3-4]分别提出了链路保护、路径保护及改进的链路保护方案.在链路保护方案中，多播树上的每一条链路都建立了保护路径.在路径保护方案中，每个目的节点，都必须从源节点开始建立一条保护路径.改进的链路方案与链路方案不同的是故障的通知点不同，在链路保护方案中，故障的通知点为链路的端节点，而改进的链路保护方案中，故障的通知点是链路端节点的父节点或兄弟节点.双树(“Dual-Tree”)[5]是Aiguo Fei等提出的一种容错多播方案，它除了基本的多播树外，还构造了第二棵与第一棵节点无关多播树作为备份结构.在基本多播树出现故障的情况下，通过注入通信流到第二棵树上来快速的重新连接受影响的多播节点.Vignesh[6]、M. Yazid[7]等人提出的一种容错多播方案-双森林("Dual-Forest”)多播容错方案，它是对双树方案的改进.类似于双树容错多播方案，双森林方案使用简化的拓扑结构来建立备份路径的.除了基本的多播树外，也是像双树方案一样，构造了一棵与基本多播树节点无关的多播树作为备份结构.在基本多播树出现故障的情况下，通过发现故障的节点执行双森林算法1以及收到重组消息的节点执行相应的双森林算法2来快速的重新连接受影响的多播节点，以确保多播树的正常通信.Craig, A.Nandy[8]等人提出基于软件层面上的流量工程下的故障恢复方案，此方案在网络硬件出现故障时，其故障恢复的效率并不理想.

链路保护、路径保护及改进的路径保护可以有效地实现单链路的故障恢复，但需要浪费不必要的带宽资源.双树算法和双森林虽然克服了前三种不能很好的处理单节点故障的缺陷，但算法的执行比较复杂，冗余路径的存在造成了资源的严重浪费，并且实现起来比较麻烦，不利于实际的应用.

3 RM-FSNC方案描述

3.1 家族体系的引入

图1 家族体系的多播树和成员关系表图 图2 具有家族体系的多播通信图

图1有12个表达式的关系.根据图1中的表达式关系，可以将图1的多播树转化为图2基于家族等级关系下的隧道容错多播树.在图2中，当节点2或链路1-2出现故障时，受到影响的多播组成员有(g1，g2，g3，g4)，数量大于多播树节点的度2，此时多播组成员g2会通过隧道g2g6与成员节点g6进行通信，并且主动向其他的成员节点发出请求建立内部多播树并继续进行信息传输.当故障恢复时，多播成员g2受到了来自节点1的信息，此时就自动关闭隧道，恢复到正常的多播树进行信息传递.当链路2-4出现故障时，收到影响的多播组成员有(g1，g2)，数量等于多播树的度2，此时多播成员g1会通过隧道g1g3与成员节点g3进行通信，并且将通过隧道g1g2与成员g2进行通信.当故障恢复时，多播组成员g1收到来自节点4的信息，此时就自动关闭隧道，恢复到正常的多播树进行信息的传递.

3.2 网络编码的引入

RM-FSNC方案将网络编码理论应用于多播通信中，在网络编码多播中，源节点对数据包的处理功能由传统的分块、存储、转发三个基本功能，变成分块、编码、存储、转发.保证了网络中的数据包在传输的过程中，不会因为哪个数据包的丢失而引起数据包无法正常接收.源节点发送的数据包始终是数据分块的编码后的数据包，因此网络传输过程中的安全性和可靠性也显著提高.目的节点所接受到的数据是由两部分组成，一部分为线性网络编码后的信息流，另一部分为线性编码系数向量.在目的节点所接受的信息流，不需要关心信息流的次序问题，只需要关心是否收到与目的节点入度数相同的信息流数量，然后将信息流分离，按照接收的次序，将线性编码系数向量组成线性系数矩阵，将线性编码后的信息流组成一个目的信息流向量，经过运算得到原信息流的向量组合，最终形成原始数据.这个方法较传统方法的优点是，算法简单，不需要复杂的局部编码矩阵和全局编码矩阵的运算.减少了中间编码节点的开销，节省了时间，方便了计算.另外，在源节点就对信息流进行了信息分割和信息编码，使得信息在传输过程中安全系数更高，并且节点和相邻链路，链路与相邻节点之间的信息传递的计算时间降低，传输速度提高，不需要太多的缓冲存储.具有编码能力的网络节点采用最简单的线性网络编码.在编解码的过程中需要的时间最短，编码算法简单.图3为在多播通信树中具有编码能力的节点信息流图与不具有编码节点的信息流图.图4为在网络编码和家族体制支持下的多播通信树图.

图3 编码节点和非编码节点信息转发图 图4 具有网络编码和家族体系下的多播树

3.3 RM-FSNC中故障恢复方案

在多播通信的过程中，源节点将信息划分成几个数据块，一般情况下，数据块的划分的数量是根据节点的度来定的，在图4中，节点1的度为2，所以源节点将信息划分成两个数据块，然后进行简单的线性编码和组合后形成新的编码信息X1和X2，两个信息在不同的分支上传输.中间节点2、3、4、5、6、7在多播通信过程中不需要编码功能，直接转发数据包到下行链路上.数据包X12是一个按照先后顺序的一个包，先转发X1再转发X2，同理，X21也是一个按照时间先后顺序的一个数据包，先转发X2再转发X1.在正常情况下，目的节点都能够收到X1和X2数据包，然后通过线性编码的逆运算就可以恢复原数据包.当多播组成员节点在指定的时间内没有收到多播源的信息，这时系统就知道多播树中的某节点或某链路发生了故障，在极短的时间内启动已经建立好的备份隧道，并自由的建立受影响的多播组成员的内部多播树，此时多播通信正常进行.当故障恢复后，关闭备份隧道，受影响的多播组成员由内部多播树状态转换成正常的多播树状态，进行多播信息的正常传输.如果故障一直没有恢复，多播信息就一直通过备份隧道和内部多播树进行受影响的多播组成员的信息传输.其算法流程图如图5所示.

3.4 RM-FSNC方案的特点

(1)多播指的是一点对多点的多播形式，在多播组中，首先，根据多播源和多播组成员建立一棵最短路径树.然后，根据分支节点的分支情况来划分多播组成员，并建立成员的最高级的家族关系.本文以二叉树为例，根节点为分支节点，这是划分成两个大的家族，再分别以每一大家族的根节点为分支节点，分别划分各自的家族关系，直到组成员直接的分支节点将组成员划分成组成员数量的最低级的家族关系.对于每一个等级的家族关系，找出家族之间的最短路径，然后通过隧道来建立两个同等级家族之间的路径关系.

(2)线性网络编码在多播网络中的应用，保证在通信开始源节点就对原信息进行了分块和编码，提高了网络通信过程中的安全性.编码和译码算法非常的简单，因此，时间的消耗较以往也没有增加.从而提高了多播网络的可靠性.

(3)当多播树出现故障时，不管是节点故障还是链路故障，首先，分析受到影响的成员节点是属于哪一等级的家族，然后，根据该家族的等级来寻找同一等级家族的隧道作为备份路径，通过隧道来进行信息的正常传输.直到故障解除后，再次恢复到正常工作路径上进行传输.

(4)当受影响的多播组成员数量多于多播树的节点度的平均值时，就在受影响的成员内部以隧道节点为源节点建立最短多播路径树.

(5)基于家族等级关系的隧道容错多播树方案，不仅可以解决节点故障，而且可以解决链路故障，并且解决这两种故障的方法都是一样的，都是通过建立同等级家族间最短路径隧道来进行故障的容错.当故障恢复后，隧道端的主动节点自动关闭隧道，并切换到正常的多播树继续进行多播信息的传递.

(6)在该方案中，故障的检测是由多播组成员主动发起的，故障恢复后链路的切换也是由多播组成员主动发起的，因此，该算法将主动权和控制权集中在端节点，简化了中间节点的功能，这样有利于系统的维护，并且对于多播而言，动态性是多播的主要特性，多播组成员的动态变化对算法影响不大.

图5 RM-FSNC方案下多播故障恢复算法流程图 图6 算法1和算法2时间复杂度比较图

4 RM-FSNC方案的性能分析

RM-FSNC方案是继双树容错方案和双森林容错方案之后提出的一个新的多播容错方案.双树容错方案所建立的备份树为所有成员节点之间的简单的连接，并且在建立备份树的过程中没有考虑备份树的额外开销问题.双森林容错方案是用森林代替了备份树，其容错是通过备份森林来实现的，备份森林是两部分多播组成员之间的连接，然后再通过一条最短路径将两部分成员进行连接，在建立备份森林的过程中仅仅考虑到建立两部分成员之间连接的路径开销问题，但没有考虑到两部分成员的额外开销问题.RM-FSNC方案采取了双树和双森林多播容错方案的优点，在建立备份树的过程中，需要分析受影响的成员的家族等级，从而选择相应的隧道进行通信恢复，同时，内部最优多播树可以降低系统的额外开销.双树容错方案只能进行链路故障的恢复，双森林容错方案能进行链路故障和节点故障，但出现故障时，要先判断故障类型，然后采用相应的多播故障容错算法进行故障恢复.RM-FSNC方案不仅能进行链路故障恢复而且能进行节点故障恢复，在出现故障时，不需要判断故障的类型，直接采用RM-FSNC故障恢复算法进行故障恢复.

RM-FSNC故障恢复方案属于主动式的故障恢复类型，在故障发生的时候，直接调用备份隧道进行故障恢复，降低了网络延迟，节省了大量的时间.

图6为本文中的方案与传统故障恢复发难复杂度的比较图，算法1线为本文中的RM-FSNC方案中所体现的时间复杂度，算法2线为传统的故障恢复算法所体现的时间复杂度.通过图6可以看出，本文的方案随着网络节点的增多，其复杂度呈现缓慢增长的趋势，而传统的多项式复杂度网络编码算法其复杂度随着网络节点的增加呈现快速增长的趋势.实验证明，随着网络节点数的增加，该方案的优势更加突出.

5 结论

RM-FSNC方案是继双树容错方案和双森林容错方案之后提出的一个新的多播容错方案.RM-FSNC方案采取了双树和双森林多播容错方案的优点，在建立备份树的过程中，首先分析受影响多播组成员的家族关系等级，然后选取相应的隧道来进行多播通信恢复，对于受影响的多播组成员根据数量来建立内部最优多播树进行备份树的多播通信，在多播容错恢复的过程中，始终考虑系统的额外开销问题，尽量将系统的额外开销减少的最小.该方案不仅能进行链路故障恢复而且能进行节点故障恢复，在出现故障时，不需要判断故障的类型.该方案属于主动式的故障恢复类型，在故障发生的时候，直接调用备份隧道进行故障恢复，降低了网络延迟.对于动态性多播通信，RM-FSNC方案有利于多播规模的扩展，与以往的故障恢复算法进行比较，可以发现新的多播容错方案在节省时间和网络带宽上都有了进一步的提高.

[参考文献]

[1]陶少国,黄佳庆,等.一种改进的最小代价网络编码算法[J].华中科技大学学报,2012,36(5):1-4.

[2]刘宴涛，夏桂阳,等.一种基于子树分解的组播线性网络编码算法[J].计算机工程,2015,41(11)：153-159.

[3]C. Wu, W. Lee, Y.Hou, W.Chu. A new preplanned self-healing scheme for multicast ATM network[C].Bei Jing:IEEE ICCT'96,1996.

[4]C. Wu, W. Lee, Y. Hou. Back-up VP preplanning strategies for survivable multicast ATM networks[C].Canada: IEEE International Conference on Communications,1997.

[5]A.Fei, J.Cui, M.Gerla, D.Gavendish. A "Dual-Tree" Scheme for Fault-Tolerant Multicast[C].Helsinki: IEEE ICC,2001.

[6]Vignesh R R,C-H LUNC,A. PANDEY. A subtree-based approach to failure detection and protection for multicast in SDN[J].Frontiers of Information Technology & Electronic Engineering，2016,17(7):682-700.

[7]M. Yazid SAIDI, B.Cousin, M. Molnar. An Efficient Multicast Protection Scheme based on Dual-Forest[J].Irisa Internal Research Report,2006,28(3):34-40.

[8]Craig,A. Nandy,B.Lambadaris, et al. Load balancing for multicast traffic in SDN using real-time link cost modification[C].London :IEEE International Conference on Communications,2015.