崔建群，叶咏佳，高 宽，范 静，吴黎兵

（1.华中师范大学计算机学院，湖北 武汉 430079；2.武汉大学计算机学院，湖北 武汉 430072）

1 引言

近年来，随着移动通信技术以及智能手机的迅速发展，移动流媒体业务的需求与日骤增。国内一些致力于为用户提供高清、流畅的视频服务的公司，如百度、搜狐、优酷等，纷纷将其流媒体服务扩展到移动网络中。与此同时，应用层组播[1，2.作为一种减轻流媒体服务器负载压力以及优化流媒体服务的P2P技术，在移动环境下的应用近年来一直是研究的热点[3，4]。

相对于IP组播，应用层组播具有先天稳定性不足的问题，同时移动环境的高度动态性进一步剧了这一问题，造成了组播系统中节点频繁的异常离开，进而导致其子节点产生组播服务中断的问题，严重影响了组播用户的体验。对于移动环境下组播系统稳定性的研究，以及组播系统出现故障后，故障节点的孩子节点快速重定向的研究一直是该领域的难点。

2 相关工作

为了解决应用层组播的稳定性问题，一部分研究者提出通过对终端节点进行性能评估[5，6]，来计算组播树中各节点在某一段时间的离开概率，在节点离开之前，对其孩子节点的拓扑进行调整，从而降低节点离开给整个组播系统带来的风险。另外一部分研究者提出，在节点离开后，通过重定向策略来解决节点发生故障时孩子节点的快速恢复过程[7～10]，其恢复过程又可以分为主动恢复和被动恢复两个方面。

文献[7，8]是被动恢复方案的代表。当节点退出，受影响子树将启动一个父节点的重新寻找过程，直至找到合适的节点连接上去为止。被动恢复方案的缺点是组播树重建时间长，且容易造成初始查找点的拥塞。

文献[9，10]中是主动恢复方案，该方案在树的创建过程中就为每个节点计算其应急父节点，一旦有节点退出时，其直系子节点根据该信息直接向其应急父节点发出连接请求，从而进行重定向。其缺点是应急父节点是“静态”的，不会随着组播树的拓扑结构变化而变化。

通过对以上文献进行分析，本文采用重定向策略解决应用层组播稳定性问题，并采用主动恢复过程避免被动检测过程所带来的高加入时延问题[7，8]；提出备份父节点重定向算法，解决组播拓扑变化下备份父节点的“静态”问题[9，10]。最后，本文提出利用组播树的相似度来衡量重定向算法对组播拓扑变化的影响，从而判断重定向策略的好坏。

3 节点重定向

3.1 无备份父节点重定向

在有线网络环境下，我们项目组已提出反向抑制主动告警机制[11]，通过提前预警避免因缓冲区没有数据而导致的服务中止，同时通过反向抑制告警策略，减少重复和错误警报的数量，为故障定位排除干扰。最后，通过父节点重定向机制，由发生故障节点的父节点或兄弟节点来承担其数据转发任务，达到快速恢复故障的目的，如图1所示。

Figure 1 Parent node redirection mechanism图1 父节点重定向机制

此种方案可以保证覆盖网络模型在很小改变下，获得较快的父节点重定向结果。但是，由于在此种方案下，节点的家族表FT（Family Table）中只保存了父节点和子节点的信息，如图1所示，为了找到故障源节点v3，需要v6、v7向源节点s报告，并由源节点s通过消息洪泛方式，遍历到故障源节点v3的父节点v1。其优点是相较于被动恢复过程，重加入时延较小；缺点是洪泛方式容易造成消息风暴。

3.2 基于备份父节点重定向

相较于无备份父节点方式，基于备份父节点BFN（Backup Father Node）机制的节点家族表FT中，除了保存父节点和子节点的信息外，还保存BFN 信息，如表1所示。

Table 1 Family table with backup parent node表1 带有BFN 的家族表FT

当检测到将要发生故障时，故障源节点的孩子节点除了向子节点发送抑制告警消息外，通过FT表查找BFN 并发送重定向消息，当BFN 收到来自节点的消息时，分担数据的转发任务。如图1 所示，故障源节点v3发生故障时，若故障节点v6、v7的家族表中BFN 为v1，此时v6、v7除了向自身孩子节点发送抑制告警消息外，并向v1发送重定向消息，当v1收到来自v6、v7重定向消息后，分发数据给v6、v7，（若v1连接数已满，通过v1孩子节点v4分发数据），完成故障恢复过程。

通过上述分析，采用基于BFN 机制的快速重定向策略，可以缩短故障发生与恢复故障所需的时间。

其重加入算法与无备份父节点故障恢复算法类似，但由于FT 表中存在备份父节点，所以不需要发送Poll消息，具体算法如下：

（1）节点Ni检测到其父节点Fi将要发生故障时，向BFN 发送REJOIN＿REQUEST 消息。

（2）BFN 接收到来自节点Ni的REJOIN＿REQUEST 消息后，如果孩子节点数目未达到上限，则向节点Ni发送REJOIN＿RESPONSE 消息，否则将节点的REJOIN＿REQUEST 消息转发到其孩子节点中，由孩子节点完成重加入操作，同样，加入完成后，向节点Ni发送REJOIN＿RESPONSE 消息。

（3）节点Ni收到REJOIN＿RESPONSE后，更新自己的FT 表，并通知其孩子节点更新FT 表。

其伪代码如下：

3.3 备份父节点选取算法

基于BFN 机制的快速重定向策略的好坏在一定程度上是由其BFN 选择算法决定的。对于BFN 的选定，为了保证重定向后组播树的拓扑结构基本保持不变，本文的BFN 从最近的祖先节点、父节点的兄弟节点中择优选取。其具体算法如下：

（1）根据父节点的FT 表，获取节点最近的祖先节点及其FT 表；

（2）根据所获取的祖先节点的FT 表，向其祖先节点和孩子节点（除父节点外）发送Ping消息来获取时间戳；

（3）根据所获取的时间戳，取时延最小的节点作为节点的备份父节点。

备份父节点选取算法伪代码如下：

4 组播树的相似度

对于重定向算法的好坏，目前还没有一种比较好的量化方式。本文提出一种根据节点发生故障前后组播树拓扑结构的变化程度来评估重定向算法优劣的方法。其主要思想是通过将故障前后组播树的拓扑结构进行向量化，并将向量化的组播树利用余弦定理来计算两向量的夹角大小，即组播拓扑结构改变大小，从而判断重定向机制的好坏。

4.1 组播树的向量化

由于组播树中叶子节点的离开不会导致节点的重加入，即叶子节点的离开对组播树其它节点不会产生影响，所以有以下定义：

定理1 对于含有n（n ≥2）个节点的组播树，按照从根节点开始层次遍历，若节点的孩子数依次为k1，k2，…，kn，则向量（k1，k2，…，kn）称为此组播树向量，对于任意ki，满足ki≥0，且k1≠0。

证明 若k1＝0，则表明根节点无孩子节点，即组播树的节点数n＝1，与n ≥2相违背，所以k1≠0。 □

定理2 若组播树只含有根节点（组播服务器节点），则认为此组播树所对应的向量为0。

证明 组播树只含有根节点，即k1＝0，所以所对应的向量为零向量0。 □

对于任意组播树，把组播树转换成向量的过程叫做组播树的向量化，所得到的向量叫做组播树的向量。

4.2 组播树的相似度

定理3 若节点数相同的两组播树所对应的向量为A，B，定义cos〈A，B〉的值称之为两组播树的相似度，并且对于任意两节点数相同组播树有0 ＜cos〈A，B〉≤1。

证明 由余弦定理：

可知，两组播树的相似度0 ＜cos〈A，B〉≤1。 □

证明 由公式（1）可知，扩展前后cos〈A，B〉的值保持不变。 □

定理5 对于任意两组播树，其对应的向量A、B 一定满足0≤cos〈A，B〉≤1。

证明 当A、B 其一为零向量0，即组播树只含根节点时，根据公式（1）可知，cos〈A，B〉＝0，结合定理3，有0≤cos〈A，B〉≤1。 □

5 实验验证和性能评价

5.1 仿真实验环境

为了验证文中所提出的BFN 重定向的好坏，本文采用基于OMNET＋＋网络仿真环境的OVERSIM 覆盖网络仿真框架来进行模拟仿真。所使用的软件版本分别为：OMNET＋＋4.1、OVERSIM 20101103、INET 20101019。

本文中仿真的硬件环境为Intel G630C 处理器，内存为4GB。操作系统为32位Windows XP SP3。

5.2 移动环境模拟

本实验利用InetUnderlayNetwork 来模拟底层的移动环境。图2是OMNET ＋＋下运行配置好的OVERSIM 的仿真图示。实验中用两个骨干路由（Backbone Router）来模拟移动环境中两个不同的地理区域，四个终端接入路由（overlay Access Router）中，0～2 代表相同区域不同移动基站，并且终端接入路由3和0～2形成不同区域中不同基站进行对照，终端移动节点（Overlay Terminal）通过移动基站（终端接入路由）加入组播系统形成覆盖网络。

5.3 实验参数设置

实验过程中参数设置满足以下条件：

（1）采用拓扑变化很小的NICE协议故障恢复机制[12]和基于主动检测的无备份父节点机制NBF作为对比实验。

Figure 2 Simulation of mobile environment图2 移动环境的模拟仿真

（2）组播树构造过程中，节点的连接数符合[2，4]（取整）均匀分布。

（3）实验中所有的离开节点均为组播树中的中间节点，确保一定发生重定向过程。

（4）为了模拟移动环境下节点的高度动态性，组播树中所有中间节点离开的概率为20%。

（5）在所有孩子节点都完成重定向之后，才能允许新的组播节点离开。

（6）每次对比实验中，保证组播树的规模和节点离开总数目一致。

5.4 重加入时延

为了统计节点重加入时延，实验中当节点离开时记录开始时间点，并在节点完成父节点重定向后记录结束时间点。其差值记为重加入时延。

如图3所示，对三种不同策略进行实验，组播规模为36，离开的总结点数为15。横轴代表节点的重加入时延；纵轴代表在该时延下，完成重定向的节点数占所有重定向节点数的百分比。

Figure 3 Cumulative percent／rejoin delay图3 累计百分比／重加入时延

从图3可知，采用主动告警方式的重加入时延比采用被动检测的NICE协议方式要小得多，原因是被动检测机制需要靠心跳机制来检测，并且受心跳机制的间隔时间的影响。同时，采用本文提出的BFN 方式的节点加入时延比NBF 方式更低，原因是后者需要从根节点进行洪泛定位到故障节点的父节点。

为了统计重加入时延是否受组播规模的影响，进行了如图4所示的实验。组播规模分别为10、20、30、40、50、60、70、80、90、100，每次组播节点离开的总数固定为组播规模的20%。横轴代表的是组播规模；纵轴是在某一组播规模下，20%离开节点所带来的重加入时延的平均值，单位为秒。

Figure 4 Average of rejoin delay／Multicast scale图4 平均重加入时延／组播规模

从图4 可以看出。在组播规模为20、离开节点数为4 时，NICE 机制和NBF 机制所带来的节点重加入时延最高。原因是当离开节点数较少时，重加入时延较大的节点占所有重加入节点比率较大，从而使得整体的平均重加入时延较大。从横向上看，节点的重加入时延的平均值随着组播规模的增大变化波动不大。原因是一方面组播规模的增大弱化了某次或某些次高加入时延所带来的影响；另一方面是由于实验中的重定向节点都是从父节点的兄弟节点和祖先节点中选取，对于三种机制中的任何一种，重加入时延对于该机制下所有节点来说基本一致。从纵向上看，BFN 方式中节点重加入时延的平均值在三种策略中最低，而被动检测方式的NICE协议则在平均时延方面一直是最高。

5.5 相似度

为了统计每次重定向后组播树的拓扑变化，实验中在组播树构建完成后，进行一次组播树的向量化。并在每次节点离开、所有孩子节点完成重定向后再次进行组播树的向量化，进行相似度的计算。

如图5 所示，组播规模为50，离开节点数为10。横轴代表节点离开的次数；纵轴代表该次节点离开，所有孩子节点重定向完成后，与原始组播树相似度的计算值。

Figure 5 Similarity／Number of node leaving图5 相似度／节点离开次数

从图5可以看出，随着节点离开次数的增加，组播树相似度呈现下降趋势，与理论上一致。从图5中还可以看出，NICE协议相似度最高，即重加入后组播拓扑改变最小，而文中所提出的BFN 方法，相似度接近NICE 协议，但相对于NBF 方法相似度更高。

6 结束语

本文基于固定网络的应用层组播故障恢复机制，提出了一种基于设施的移动环境下故障恢复策略。该策略利用父节点备份机制，能够达到快速重定向的目的。实验结果表明，该方式相较于NICE协议在重加入时延上具有很大的优越性。同时，创新地提出了利用组播树的相似度来衡量重定向算法对组播拓扑变化的影响，从而判断重定向策略的好坏。

实验结果表明，虽然文中所提出的快速重定向策略相较于NICE协议略逊一筹，但是相较于传统的组播故障恢复方式，有很大的改善。综合对比重加入时延以及相似度的仿真实验结果，文中所提出的基于父节点备份机制在移动环境下具有良好的优越性。

[1]Cui Jian-qun，Xiong Nai-xue，Park J H，et al.A novel and efficient source-path discovery and maintenance method for application layer multicast[J].Computers and Electrical Engineering，2013，39（1）：67-75.

[2]Cui Jian-qun，Lai Min-cai，Yang Yi，et al.Application layer multicast streaming media live system based on scribe[J].International Journal of Advancements in Computing Technology，2012，4（21）：517-525.

[3]Li Pei-long，Zhang Hong-hai，Zhao Bao-hua，et al.Scalable video multicast with adaptive modulation and coding in broad-band wireless data systems[J].Journal IEEE／ACM Transactions on Networking（TON），2012，2.（1）：57-68.

[4]Hsu C-H，Hefeeda M.A framework for cross-layer optimization of video streaming in wireless networks[J].ACM Transactions on Multimedia Computing，Communications and Applications，2011，7（1）：5.

[5]Cao J J，Su J S.Delay-bounded and high stability spanning tree algorithm for application layer multicast[J].Journal of Software，2010，2.（12）：3151-3164.（in Chinese）

[6]Zeng Bin，Zhang Da-fang，Li Wen-wei，et al.Application layer multicast algorithm based on peer performance evaluation[J].Computer Engineering，2009，35（8）：13-16.（in Chinese）

[7]Peleg A，Weiser U.MMX technology extension to the Intel architecture[J].IEEE Micro，1996，16（4）：10-20.

[8]Tremblay M，O'Connor J M，Narayanan V，et al.VIS speeds new media processing[J].IEEE Micro，1996，16（4）：35-42.

[9]Liu Shi-dong，Zhang Shun-yi.Improved reconstruction scheme for application multicast tree[J].Computer Engineering and Applications，2008，44（7）：19-22.（in Chinese）

[10]Deepu T，Lizy K J，Doug B.Bottlenecks in multimedia processing with SIMD style extensions and architectural enhancements[J].IEEE Transactions on Computers，2003，52（8）：1015-1031.

[11]Cui Jian-qun，Wu Li-bing，Wu Dan，et al.A novel fault detection mechanism of topology-aware ALM[C]∥Proc of the 2nd Asia-Pacific Conference on Computation Intelligence and Industrial Applications，2009：397-400.

[12]Brogle M，BarthloméS，Braun T.Quality of service for multicasting using NICE[C]∥Proc of 2010 ACM Symposium on Applied Computing，2010：670-677.

附中文参考文献：

[5]曹继军，苏金树.应用层组播的时延受限高稳定性生成树算法[J].软件学报，2010，2.（12）：3151-3164.

[6]曾彬，张大方，黎文伟，等.基于节点性能估算的应用层组播算法[J].计算机工程，2009，35（8）：13-16.

[9]刘世栋，张顺颐.一种改进的组播树主动重建方案研究[J].计算机工程与应用，2008，44（7）：19-22.