基于树环结构的流媒体应用层组播模型的研究

摘要：该文首先分析应用层组播协议，结合流媒体在 Internet 上的特点，提出了流媒体树环模型。该模型基于 NICE 协议之上，综合衡量节点自身及链路因素权重，构建适用于大规模实时流媒体的树环应用层组播模型。模拟实验表明，该模型能够最大化资源利用率和最小化控制开销，可以很好地满足实时流媒体中大内容传输的需要。

关键词：树环；应用层组播；流媒体

中图分类号：TP393 文献标识码：A 文章编号：1009-3044（2013）03-0597-03

1 概述

应用层组播[1]是在终端主机之间实现组播的功能，即数据的转发、复制等都在端系统而不是路由器上实现，应用层组播解决了网络层组播难以部署的问题，但通信效率和可靠性不高，因此，如何让组播树中的节点快速、高效的收到数据包成为应用层组播研究的一个主要问题，实现这个目标的关键是构建一棵高效的应用层转发树，而领导节点的选择策略又是转发树数据传输是否高效的决定性因素之一。

本论文通过综合衡量节点自身的能力、链路带宽和延迟等因素的权重，构建具备低延迟、高容错和高效率的应用层组播树环拓扑，很大程度上提高了流媒体在网络中的应用。

2 树环模型构建

该模型基于NICE 协议[2] 之上，构建树和环相结合的网络，目的是要构建一棵高效、可靠及可扩展的流媒体应用层组播树。模型根据IP地址分配与路由的聚类特性[3]近似划分成不同的域，域内节点构建成环，根据域首节点的选取策略选出每个域的域首节点，将域首节点构建成树拓扑，进而形成树环结构的应用层组播模型。

2.1 树环的层次性拓扑

树环模型将所有成员节点分到不同的层次中，把每层的节点分成不同的域，域内节点构建成环，每个域根据下文的域首节点选取策略选取其域内领导节点。构成的树环拓扑如图 1 所示。类似于NICE 协议模型，树环模型中的主机节点满足以下属性：①任何一个主机节点属于树环结构中的一个域；②同环的节点称为兄弟节点，父节点是处于上层环节点，孩子结点处于下层环的节点；③当在网络节点数量较大的情况下，通过设定域内节点的数目，可使模型保持较少的层次。

2.2 树环的环首节点选取及环构建

环首节点的选取是构建高效的流媒体树环应用层组播模型的关键环节，目前常用的节点选择算法有：基于最小路径延迟、基于最大链路带宽和基于最近网络拓扑。实际上，节点的差异受到系统处理器、网络带宽以及线路延迟等的影响，本文考虑节点受综合因素的影响，通过衡量节点的综合权重，找到构建高效、可靠的树环模型域首节点。

2.2.1 环首节点选择

本文将节点当前的可用网络带宽、内存占用率C、系统进程表中的空闲进程率作为节点本身的基本参数，计算自身的能力，公式如下：[Weightnode] = （1-C）×[P空闲P总进程]×[B有效带宽B总带宽]，

上式表明， 内存占用率低，即可用内存大、系统使用进程数少、可用带宽高的节点将排在前列。

一个节点的转发能力系数计算公式如下：[Weightp_bandwidth] = [BL_有效带宽BL_总带宽]，公式比值越大，说明链路转发数据的能力越强。

树环模型中域首节点的选取须保证新加入的节点能够通过少量查询快速地找到它在结构中的位置。因此，域首节点选取到其他所有节点的延迟之和最小的节点。一个节点的链路的延迟权重计算公式如下：[Weightp_delay]=1/[u，v∈V][wvu（u，v）]，其中：V为域内节点的集合，u，v∈V。 Weight p _ delay 表示找到了一个节点，使得该节点到域内其他节点的链路延迟之和最小。

综合上述分析和定义，域内节点总的权重计算公式如下：

[W总权重]=α[Weightnode]+β[Weightp_bandwidth]+γ[Weightp_delay]

其中0≤α，β，γ≤1为系数，且α+β+γ=1 。根据域首节点选择策略公式对各个域内节点计算其综合权重，选取域内权重最大值的节点作为该域的域首节点。

2.2.2 树环模型中环的构建

域内的所有节点构建成环结构，环的构造采用简单的贪婪算法。贪婪的局部构建环算[4]法描述如下：

① 出域内综合权重最大一个节点x作为域首节点，标记为已访问的；

② 在未标记访问节点中选出权重最大的节点y作为备用域首节点；，标记已访问；

③ 再从y开始按域内权重的顺序依次连接未标记访问的节点，直到覆盖所有域内节点；

④ 当访问到域内权重最小值时，将其与备用域首节点相连，即完成了环的构建。

2.3 树环模型中树的构建

给定域首节点构成的网络G=（V，E）和成员节点集，找到覆盖所有组成员的最优树，使树的所有链路的权值和最小为最优。启发式构建树的算法[5]描述为：

① 构成包含所有域首节点组成的虚拟网，对每对成员利用Floyd 算法求最小权重，把虚链路加入虚拟网中，并为路径指派权值，该虚拟网是全连通网；

② 用prim算法生成最小生成树；

③ 恢复原始路径，得出近似方案。

3 树环拓扑的维护管理

3.1 节点加入

组播模型中存在一个集中汇聚节点（RP），RP维护会话中所有成员的活动信息，当一个新节点加入组播组时必须映射到Layer0的某个域上，首先新节点向RP发出加入请求，加入时满足加入父节点度的约束条件及请求节点的时延阀值，加入过程从最顶层的节点开始，顺序探测每个层次的域直到找到最近的域为止。

3.2 节点的退出

点的退出分正常退出和异常退出。节点正常退出时，发送退出消息给所有的相邻节点，相邻节点收到退出消息后调用相应的拓扑修复机制；节点的意外退出可能由失效节点或链路失效引起的。本文将树环模型中异常失效分为链路失效、域首节点的失效和域内节点的失效。

4 实验仿真

4.1 度量参数

1）节点出度。节点出度表示该节点需要向多少个节点转发数据，如果节点的出度较低，并且出度比较均衡，边可以充分利用节点的带宽资源，又能避免节点过载。

2）路径伸展度。路径伸展度指从源节点到某个目的节点之间沿应用层组播路径的延时与沿网络层单播最短路径的延时之比，它表征了应用层组播路由在延时方面的额外付出。

4.2 实验数据分析

使用GT-ITM生成 transit-stub类型的物理网络拓扑，为了验证 Tree_Ring 模型的效果，将树环与 Nice（K=5）进行了对比。本论文仅给出 Tree_Ring 模型与 NICE 的节点出度对比（图3）、路径伸展度对比（图4）、节点失效时数据传输率对比图（图5）。

结论分析：树环模型中节点的出度70%以上为1，节点的平衡能力较好；树环模型中的路径伸展度80%都控制在3以内，传输延迟维持在较低的水平；不同的节点失效率时，树环的数据传输均比 NICE 较高，大大提高了容错能力。

5 结束语

本文针对如何构建一棵基于流媒体传输的应用层组播转发树问题，重点研究了转发树中域首节点的选取策略，在研究基于最小路径延迟、基于最大链路带宽、基于最近网络拓扑三种最优父母节点选择策略的基础上 ，打破了传统仅按图论中心论选择领导节点的习惯。尽管带宽、延迟是流媒体传输最关键的因素， 同时要兼顾节点的计算能力，在相同基本度数的条件下， 那些综合性能更好的节点将被选择，这样构建的树环组播树不仅具有较高的容错能力，同时大大提高了数据转发效率。

参考文献：

[1] 李珺晟，余镇危，潘耘.应用层组播综述[J].计算机应用研究，2004（11）：1417.

[2] S.Banerjee，B.Bhatta charjee，C.Kommareddy. Scalable application layer multicast. Technical report， UMIACS TR-2002-53 and CS-TR 4373， Department of Computer Science， University of Maryland， College Park， MD 20742，USA， May 2002.

[3] 杨贯中，郭超，陆绍飞，等.分层分域的应用层组播拓扑构建方法[J].计算机工程与设计，2008.

[4] 孙勃，陈越，韩冰.基于树与环应用层组播覆盖网的研究与比较[J].计算机工程与设计，2008（5）.

[5] 陈永刚，贾春福，吕述望，等. Tree-Ring：一种结构化的应用层组播模型[J].计算机工程，2008（6）.