一种改进的应用层组播树构建和维护算法

刘浩杰 金鑫

(武汉理工大学 信息工程学院，湖北武汉 430072)

0 引言

当前，为了缓解由于不断增加的通信需求所带来的网络瓶颈问题，组播技术越来越受研究者的关注。而其中应用层的组播主要基于端到端的思想［1］，它保持网络原有的简单、不可靠、单播的转发模式，由端系统实现组播转发功能，让网络的核心部分用于数据通信而不实现特殊应用。因此，能够有效地降低核心网络的复杂性，便于升级维护，同时提高网络的通用性和灵活性，在增加新应用时不必改变核心网络。基于应用层组播技术设计的视频会议系统、多媒体网络教学系统以及媒体流的分发系统等，有着十分广泛的应用，因此对应用层组播技术进行研究，具有重要的现实意义。

1 相关工作

目前，已经有众多的研究者对应用层组播技术进行了研究，先后提出了一系列组播方法。如，文献［2］在单播系统的基础上，开发了一种基于组播的直播系统，系统测试表明，新的系统能够提供较好、较稳定的流媒体服务;文献［3］在综合考虑了节点的性能和位置重要性的基础上，提出了一种改进的组播算法PPE，仿真结果表明，PPE能有效地降低延迟和控制开销，在大规模节点环境中能有效改善组播树的性能。文献［4］基于前向式重构技术，采用自底向上的方法将本地选择策略和全局选择策略进行有机结合。仿真结果表明，该算法相对于传统的方法在计算开销和转发质量等方面都有一定的进步。另外，还有文献［5］针对矿区网络的视频传输问题，开发了一种基于实时流媒体服务的多源应用层组播系统，该系统能够大大降低网络的丢包率;文献［6］设计和实现了一种异构的多媒体会议系统集成框架。但是，该文仅仅只是谈到如何利用组播技术来设计集成框架，而对于整个系统的其他关键模块并没有阐述。总的来说，已有的组播方法有其可取之处，但是都无法自适应地应对不同网络应用场景下的转发需求，转发时延、系统的吞吐量等方面都还有待改善，鉴于此，本文从组播树的建立和动态维护两方面出发，提出了一种改进的组播算法，并通过仿真验证了本文方法的有效性。

2 组播树的建立

建立过程如下，首先，转发节点之间形成一个稳定的覆盖网，然后根据会议主题动态的创建组播树，用于传输会议的数据。图1给出了组播树建立的全过程。其中，New Node表示要加入群组的新成员节点，Server是服务器，实心的节点和粗线条表示当前组播树。

图1 组播树建立过程

算法的基本过程如下

Step1，New Node访问服务器Server(图中用1表示)，Server返回群组成员地址信息(图中用2表示)与连接信息。在选择Server时，New node主要考虑负载均衡和网络延时的情况，选择最近的Server作为父节点，下面给出节点与Server的距离定义:任意一个New Node n与任意一个标号为k的Server的距离为

其中，LB*(k)为标号为k的服务器的负载均衡归一化值:

其中，Degree(k)表示服务器与节点相连的最大分支数，即标号为k的服务器的度;Constraints(k)表示当前服务器的资源占用情况。RTT(k)为n节点与标号为k的服务器的链路延时归一化值

其中，RTTn(k)表示n节点与标号为k的服务器的链路延时;max{RTTn}和min{RTTn}分别表示n节点到组播树服务器延时的最大值和最小值;w1和w2表示权重，满足0≤w1，w2≤1，且w1+w2=1。

Step2，New Node进行其每一个链接的可用带宽和连接性能(图中用3表示)的测量。在测量带宽时，本文借助MPEG视频数据流随时间做周期性变化特性实现对可用带宽A的测量;

Step3，New-Node综合考虑了度数、延时和带宽等因素，利用启发式规则，通过比较从各个候选父节点中选择综合性能最佳的节点进行连接。限于篇幅，本文仅给出基于度数约束的组播树构造算法部分伪码，如下所示，其中，dmax(i)表示节点i的最大度约束，dnow(i)表示节点 i的当前连接数，node(i)表示节点 i，ddegree(i)表示节点i的度约束。

算法1:基于度数约束的ALMT构造算法

在算法1中，本文设计的度数计算方法如下:假设，某一节点当前的可用网络带宽为N Kbps，CPU占用率为C，可用内存大小为M MB，进程数为P个。本文设计新节点选择其父节点的过程按照下式的综合评价值排队

(4)式能够确保那些CPU占用率低、可用内存大、系统进程数少的节点将总是拥有最高的优先级成为父节点。

3 组播树的动态维护

3.1 节点的故障检测

由于节点的退出，会导致组播树在分发数据过程中出现故障。因此故障检测是十分重要的，下面主要针对节点异常退出情况进行了故障检测。

为了检测节点的异常退出情况，组播树中的节点定期的向组内发送Heartbeat消息来宣告自身的存在，同时监听其邻节点的消息并更新其邻节点列表的状态。本文提出的故障检测算法的主要步骤如下

Step1.在DS中创建检测算法的后台线程;

Step 2.每隔100秒，DS向所有终端发送一带特定标识的数据包Datas;

Step 3.终端收到Datas后做出回应，向DS发送应答数据包Datar;

Step 4.DS接收到Datar后，记录终端的IP，并保存在数组ArrayIP中;

Step 5.如果某IP不在当前ArrayIP中，调用覆盖网重构算法，对该节点的退出进行组播网重构;

Step 6.向所有在线的终端泛洪新的组播网信息。

3.2 组播树的重构

对于任意节点Cj，本文先给出如下的定义描述和参数说明

定义1节点的总度Dt(Cj)Cj节点能转发给别的终端数量;

定义2节点的已用度Du(Cj)Cj节点已经连接的终端用户数;

定义3节点的剩余度Dr(Cj)Cj节点还能连接的终端用户数;

下面将介绍组播树的重构过程

如图2所示，节点 bi有n个孩，有m-1个兄弟节点。在节点bi失效以前，要为bi的孩子节点找到一个备用父节点。过程如下

首先，在bi的孩子节点没有找到备用父节点前，设bi为unhelpful。找到之后，设 bi为 helpful。

然后，计算bi所有的孩子节点的剩余度和，如果大于n-1;则在bi和它的所有孩子节点之间形成一棵生成树;如小于n-1，则在 bi和它的 Dr(c0)+… +Dr(cn-1)个孩子节点之间重构组播树，剩余孩子节点将向bi的helpful兄弟节点发出申请。如还有子节点没找到备用父节点，则继续向祖先节点申请。

每个节点维护一个兄弟节点和祖先节点的信息列表。在节点离开后，选择一个该节点的孩子来继承该节点的地位。本文在杨氏方法［8］的基础上，选择RTT值最小的节点来继承。限于篇幅，具体的节点继承过程不再详述。

图2 基于度数约束的生成树

依据上述分析，组播树重构算法的主要步骤如下

Step1，叶子节点状态设为helpful，其他的所有节点状态设为unhelpful;

Step2，如果有节点的状态为unhelpful，将启动节点内部修复计划;

Step3，如果所有孩子节点找到了备用父节点，则将自己的状态改为helpful。否则，向父节点的兄弟中为helpful的节点发出请求;

Step4，在所有孩子节点都找备用父节点后，如果节点请求离开，则所有孩子节点从备用父节接收数据;如果失效离开，通过Heartbeat检测失效后，孩子节点都将从备用父节点开始接收数据。

Step5，在某个节点离开或者检测到失效后，该节点的父节点设置为unhelpful，所有的孩子节点将重新按Step1开始寻找新的备用父节点。

4 实验结果与分析

本文采用NS2进行模拟实验。将本文提出的算法和随机组播树算法进行了对比。首先，我们从吞吐量方面出发比较了本文算法和随机组播树算法生成的组播树的性能:分别用这两种算法构建组播节点数为40的组播树，然后从根节点发送10 Mb数据，记录下每个节点的吞吐量情况，如图3所示。

我们一共做了120组测试，依据这些实验数据，给出了如表1所示的统计结果。

算法名称平均吞吐量相对随机算法的提高随机组播树算法402.570%本文的算法583.6845%从图3和表1可知，本文算法在提高吞吐量方面明显优于传统算法。这是因为本文的方法综合考虑了节点的度数、延迟以及带宽等因素，利用启发式规则，通过比较从各个候选父节点中选择综合性能最佳的节点进行连接。而随机组播树算法由于没有考虑度数的限制，且对于带宽的估计不够准确，无法避开那些服务能力较差的节点，因此，影响了组播树的物理连接质量。

图3 吞吐量比较

表1 平均吞吐量比较

最后，本文对组播树维护算法进行了性能测试，并将其与响应式方法和Tetsuya方法和杨式方法［8，9］进行了比较。实验场景为:终端主机数量从50到250，链路传输数据时间从20ms到120ms，主机度从2到12。从图4和图5可以看出，响应式方法修复时间较长，本文算法与Tetsuya方法和杨式方法的修复时间基本一致，但是本文方法的平均转发延时是所有方法中最低的。仔细分析其原因可知，这主要是因为本文的方法在对组播树进行维护时，对非正常情况下节点的失效进行了故障监测，能够及时做出反应，由于本文的方法通过对节点状态进行helpful和 unhelpful的区分，有利于为孩子节点快速地找到替代的父亲节点，避免了数据的丢失，降低了数据的转发延迟。

5 结束语

本文提出了一种改进的组播树构建和维护算法。仿真实验表明，本文的方法能够显著地提高数据转发的效率，避免数据的丢失，降低延迟。我们的下一步工作主要包括:(1)进一步分析节点的度与数据转发延迟和丢包的关系，提出更优的组播书构建算法;(2)研究基于启发式方法来对节点失效情况进行提前预测，从而为数据转发的路径进行更优的选择，提高转发数据包的成功率。

［1］李伟，沈长宁.应用层组播协议研究［J］.计算机工程与应用，2004，24(4):156-159.

［2］程鹏，吴秋峰，戴琼海.基于应用层组播的流媒体直播系统［J］.计算机工程，2007，33(21):210-212.

［3］曾彬，张大方，黎文伟，吕磊.基于节点性能估算的应用层组播算法［J］.计算机工程，2009，35(8):13-16.

［4］邓正伟，李锋.自底向上的应用层组播树重构算法［J］.计算机工程，2011，37(2):105-107.

［5］程德强，钱建生.基于实时流媒体服务的多源应用层组播系统［J］.计算机工程，2008，34(10):224-225.

［6］李律松，李静.多媒体会议系统集成框架的研究和实现［J］.计算机工程，2006，32(21):206-208.

［7］潘耘，余镇危，王行刚等。Overlay组播路由的负载平衡问题［J］.电子与信息学报，2007，29(3):739-742.

［8］M.Yang，Z.Fei.A Proactive Approach to Reconstructing Overlay Multicast Trees［C］//in proceedings of INFOCOM，2004:2743-2753.

［9］Tetsuya Kusumoto，Yohei Kunichika and Jiro Katto.Proactive Route Maintenance and Overhead Reduction for Application Layer Multicast［C］//Proceedings of P2PMMS'05，Singapore，2005:278-287.