基于树-轮结构的应用层组播模型研究

摘要：在分析了树型和环型结构特点的基础上，该文提出一种基于树-轮拓扑结构的应用层组播模型。模型采用定域过程将距离近的节点集中在一起组成一个车轮结构，并利用近似平衡二叉树产生算法将轮心节点构建成一个时延最小的二叉树，以提高数据转发的效率。仿真结果表明，该模型具有较低的端到端延迟和链路压力以及较小的路径伸展率和控制开销，适用于大规模且实时性要求较高的应用层组播环境。

关键词：应用层组播；树形结构；车轮结构；定域过程；节点性能

中图分类号：TP18文献标识码：A文章编号：1009-3044(2011)31-0000-0c

Research of Application Layer Multicast Model Based on Wheel-Tree Architecture

YAN Ying

(College of Computer, Nanjing University of Posts & Telecommunications, Nanjing 210003, China)

Abstract: To combine the advantages of tree and ring architectures and improve the transmission efficiency of the Application Layer Multicast (ALM), this paper presents one new ALM model which constructs an overlay network based on Wheel-Tree. In this model, we use a localized process to gather those nodes with short distances together and form one wheel structure, so as to build a binary tree with the minimum delay to improve data forwarding efficiency. Simulation results show that this model could be used in the large-scale and real-time environments, and have a lower end-to-end delay and link stress, as well as smaller link stretch and control overhead.

Key words: ALM; tree architecture; wheel architecture; localized process; peer performance

组播技术分为IP组播和应用层组播两种方式。IP组播是网络层组播，效率较高，但部署开销较大。ALM由端节点实现组播功能，其有效降低了部署开销，得到了广泛的应用。

通过对文献[1]分析可知，树型结构的可扩缩性好、传输时延小，但可靠性不高；而环型结构可靠性高，但扩展性较差、传输时延大。如何结合两者的优点，提高ALM数据传输效率是值得研究的问题。

1 相关工作

YOID将组成员构造成一棵共享的数据传送树，其检测与控制算法复杂性比较高，数据传送路径较长，导致组播模型的效率低下。

HMTP可提供域间组播功能，其与YOID一样，所有组成员自组织成一棵双向的共享树，导致通信效率低下。

SCRIBE构建于Pastry， 其需要为每个组维护一棵共享树，导致模型效率较低而复杂性较高。

文献[2]提出一种结构化的Tree-Ring混合组播模型，同样，其忽视了环型结构可扩展性差和传输时延大的问题。

为解决树型和环型拓扑中存在的问题，本文提出了一种基于树状轮ALM模型 (ALM Model based on Tree and Wheel: TWALM)。

2 TWALM组播模型的设计

2.1 模型结构

该模型包含三类节点：轮心、副轮心和普通节点。轮心管理该区域中所有节点的信息；副轮心在轮心节点失效时替代轮心；普通节点只需存放轮心及其前驱和后继节点的ID号。描述如下：

1) 以簇(Cluster)为基本管理单位，构造两层(Layer)结构。任一节点必属于低层，即成员层。经过选择算法产生的轮心节点形成高层，即核心层；

2) 所有节点初始加入到成员层，采用定域将距离近的节点划分到一个车轮结构的簇，称之为区域轮，每个区域轮有一个轮心 (Leader)，其由综合性能最优的节点担任；

3) 依据每个轮心性能值大小，采用时延和度数均较小的二叉树连接各轮心，构成轮心树，使性能最优节点担任树根；

4) 轮心构成m层逻辑结构，性能最优节点在L0 层，性能次优节点在L1层，依次类推。

5) 区域轮节点数目限制在[k,3k]之间，N个节点规模的网络最多有log2(N/k+1)层，路径搜索采用分布式前向询问方式完成；

该模型如图1所示，31个节点分成5个轮，各轮心构成一棵时延最小的组播二叉树。

图1TWALM模型组织结构

2.2 模型设计

2.2.1 区域轮构建

分为三个过程：

1) 定域过程：其将网络距离较小节点加入到同一轮中，以路由器跳数、节点资源量和存活时间作为主要参数。

(1)

其中d为量化的网络半径值，i为轮心编号，Hi为节点到P的跳数，Srci为节点资源量，S为资源总量，Timei为节点存活时间，T为系统存活总时间，0 ≤ α，β≤ 1。

新节点由公式2计算其到所有轮心节点的量化距离值di：

(2)

依次将d1，d2，…. dN与d进行比较，若仅dk满足dk

2) 初始轮过程：包含两个子过程：一是将普通节点构建成一个轮；二是将普通节点与轮心节点相连，形成车轮状结构。

3) 在此基础上，采用VRing[3]中提出的算法来构建一个冗余链路，用于增强在区域轮中数据传输可靠性，降低时延。

2.2.2 轮心节点选举

根据各节点的资源占有量、时延、带宽和生存时间计算其性能值，使性能值较高的节点在核心层中。

参照文献[4]的优先级算法，设F(t)为t时间内节点移动次数；S为节点包含资源总量；P为包含资源占总资源S的百分比；M(i，j)表示节点是区域i的第j个成员；N(i)为轮i中成员数目；T(r*T0)表示第r个抽样时刻，T0为抽样间隔，其中，r=1, 2, 3，4 …,t /T0；Capability (F(t),S,ρ,t)为节点性能值。

将源节点资源进行分割，则源节点资源总量S为：

S=s[1]+s[2]+… s[k]+ … +s[n]，1≤ k ≤n

其中n为分片总数，设Da->b(s[k])为节点a传给节点b的数据信息为s[k]，则在第r个采样时刻T(r*T0)，节点M(i，j)接收与发送的数分别如式(3)、(4)所示：

(3)

其中，1 ≤ a，b，c ≤ n;

(4)

其中，1≤m,n,p,k ≤ N(i,j);

则抽样时刻T(r*T0) 节点M(i，j)转发效率如式(5)所示：

(5)

在t 时间内，通过(3)式可近似得到节点M(i,j) 接收与发送的数据分别如式(6)、(7)所示。

(6) (7)

由(6)、(7)式可得出通过节点M(i,j)的数据流量总和D(M(i,j))及其包含资源占总资源的百分比P，如式(9)所示。

D(M(i，j))=Drecev(M(i，j))+Dsend(M(i，j))(8)

P=D(M(i，j))/S (9)

则在t时间内平均转发效率为:

(10)

C_per(P)和C_eff(ρ)分别表示随P和ρ的变化时，节点性能的变化趋势，其由式 (11)、(12)计算：

(11)(12)

(13)

式中压扩参数A取值87.6；x、y分别表示归一化压缩器输入与输出。

系统抖动性由节点加入退出系统的频率决定。设C_fre(F(t))表示节点的性能值随F(t)的变化。采用类似Fibonacci数列的分布，其如下所示。

(14)

节点性能值计算如式(15)所示。

Capability(F(t),S,ρ,t)=α*C _ fre(F(t))+

β*C_per(P)+η*C_eff(ρ)(15)

式中的α,β,η (0≤α，β, η≤1)根据网络环境和实际要求优选。

区域轮中各节点的性能值进行排序比较，拥有最大值的即为轮心节点。

2.2.3 轮心树构建

在各区域轮选举出轮心后，以发送源为树根，在轮心间构建一棵时延较小的组播二叉树。副轮心间备份路径也参照该算法来构建。轮心树的构建近似于最小延迟生成树算法[5]。

2.3 成员管理与维护

TWALM采用HELLO消息来跟踪成员加入、退出或失效。

1) 新成员加入：当有新节点向RP节点发送加入请求时，RP发起定域过程，返回给新节点所有满足条件组的标识Gi，节点向具有最小网络半径d组发送JOIN消息，完成加入过程。

2) 成员退出：当组播组G中的一个成员u要离开，它向邻居节点发送QUIT消息，离得最近的邻居将其占用的区域合并。如果u是一个轮心，则其在退出前选举产生新的轮心，然后通告其它节点以及RP节点。

轮内节点间通过发送 HELLO信息通告彼此存在，如果在一定时间内收不到某节点 u的HELLO信息，则将该失效节点等同退出处理。

2.4 数据传输

在传输实时流媒体数据时，将数据分块，然后通过实时传输模型以连续流方式顺序从源向目的地发送，目的地缓存一定数据后即可播放多媒体内容。在传输非实时数据时，先将数据块传给轮心，再由轮心负责向本轮内其它节点以泛洪方式传送。

3 性能仿真与分析

采用以下参数对模型性能进行评价：

1) 平均端到端延迟(Average End-to- End Delay)：指从源端到组播树中每个组成员节点的端到端延迟之和与整个组播组成员数量之比。lT(ui)为源端到第i个区域轮的节点u的延迟时间，N为整个组播树中成员数量。

(16)

2) 平均链路压力(Average Link Stress):指在某一条链路上同时要转发的相同的数据包的数目。Sl是每条链路l的压力, L是物理拓扑中的链路的数目。

ALS=∑l∈LSl/ |L| (17)

3) 平均路径伸展度(Average Path Stretch)：指数据所传输的路径长度与直接由单播方式所传输路径长度的比值。Sr是节点r的伸展度，R是组播树中成员的数目。

APS=∑r∈RSr/|R|(18)

4) 控制开销(Control Overhead)：包括组播树维护以及节点间的通信负载。n为节点数目，Ji为节点i加入负载，Di为节点i离开负载，Hi为节点i定时握手负载。

(19)

在Ubuntu8.04下搭建NS2平台进行仿真实验，通过GT-ITM生成Transit-Stub网络拓扑，包括2个Transit域、4个Stub域与200个路由器。设Transit域间和域内延迟分别为120和80ms，Stub域间和域内延迟分别为30 和10ms。实验对NICE、CAN和TWALM模型进行比较。

由图2可知，TWALM模型比其它两个模型有更小的AED，这是因为TWALM两层结构中分别采用不同的路由方法，轮心的选取遵循到其它成员距离总和最小的原则，降低了在轮内数据传输延迟。

由图3可知，NICE的ALS性能最差， NICE链路压力较大最大，CAN模型采用泛洪路由机制，使链路压力可以在所有的路径上比较均匀地分布，而TWALM通过位于簇边缘成员拥有较少的邻居，具有最低的ALS。

图2 三种模型AED比较

图3 三种模型ALS比较

由图4可知，TWALM在成员层的区域轮内采用泛洪路由方式来传输数据，在核心层采用最小生成树组播算法进行组播路由，其扩展性更好。

图4 三种模型APS比较

由图5可知，NICE控制开销最大；而在CAN和TWALM模型中，组成员只需与它的邻居节点交换状态信息，并且后者通过划分簇的方法，来减少了处于不同簇的成员间维护开销，达到CO最优化目的。

图5 三种模型CO比较

4 结论

本文结合树型结构和环型结构的优点，提出了一种基于树和轮结构的ALM模型。该模型减轻了对核心层节点的压力，减小了传输时延，提高了传输效率与可靠性。仿真结果表明，该模型具有较低的端到端延迟和链路压力以及较小的路径伸展度和控制开销，能够满足日益增长的多媒体应用。

参考文献：

[1] 孙勃, 陈越, 韩冰.基于树与环应用层组播覆盖网的研究与比较[J].计算机工程与设计,2008,29(10):2457-2463.

[2] 陈永刚,贾春福,吕述望,等.Tree-Ring:一种结构化的应用层组播模型[J].计算机工程,2008,34(11):23-25.

[3] Sobeih A,Yurcik W,Hou Jennifer.VRing: A Case for Building Application-layer Multicast Rings[C].Proceeding of MASCOTS'04.2004:437-446.

[4] 许建真,许密画,张福炎.基于优先级的高效应用层组播层次结构管理模型[J].小型微型计算机系统,2008,29(9):1669-1673.

[5] 曹佳,鲁士文.应用层多播的最小延迟生成树算法[J].软件学报,2005,16(10):1766-1773.

收稿日期：2011-08-17

作者简介：严英（1976-），女，江苏海门人，硕士，讲师，主要研究方向为基于通信网络的计算机应用技术。