基于N ICE协议的应用层组播稳定性研究

随冬梅

(商丘师范学院软件学院,河南商丘 476000)

基于N ICE协议的应用层组播稳定性研究

随冬梅

(商丘师范学院软件学院,河南商丘 476000)

应用层组播树是由终端用户组成,其稳定性不能得到保证.本文面向P2P视频直播应用,基于N ICE协议,通过分析终端用户的行为和能力,提出一种新的簇首选择算法来提高组播树的稳定性,另外,在改进的N ICE协议上建立冗余虚拟链路来重构组播树,以保证组播的稳定性.

应用层组播;冗余虚拟链路;视频直播＊

0 概述

组播是一种高效的多点通信方式,IP组播效率高,但需专门的组播路由器,代价大,以至于许多ISPS不愿意提供对IP组播的支持,限制了IP组播的实际部署,因此,研究人员提出了应用层组播的概念,并成为研究热点.应用层组播利用现有的网络作为底层的基础设施为终端用户提供组播服务,终端用户在物理网络上自主组织成一个虚拟的覆盖网络,组播数据沿着组播树进行分发.这种易部署性是应用层组播较之IP组播最大的优点.但是,因为构成组播树的中间节点并不是专门的网络路由器,而是自主的终端主机,所以应用层组播树会因为单个终端主机的退出和失效而影响用户接受组播数据的连续性,尤其是在P2P视频直播应用中.在P2P视频直播中,当用户的数量巨大时,每时每刻都有很多节点的加入与离开,致使数据传输暂时中断,影响该节点的子孙用户的视频观看.因此,提高应用层组播的稳定性是提高应用层组播服务质量的必然要求.

本文面向可扩展流媒体视频直播应用,改进N ICE协议[1]的簇首选择算法和数据拓扑结构,以达到在组播树创建时就达到较高的稳定性.并在组播树上部署冗余虚拟链路来解决节点失效后的组播树的重构问题,缩短节点失效后组播树恢复时间.

1 NICE协议概述

1.1 NICE协议的层结构

如图1所示,所有的节点都要加入第0层,每层的节点被分在一个个簇(c luster)中,每个簇的规模在K～3K-1之间,其中,K为常数.每个簇都有一个簇首,簇首是这个簇的图论中心.

在N ICE协议中,组播数据分发时,如果该节点仅是最底层的一个成员,那么组播数据首先会到达该群的所有节点,然后由该群的簇首通知其它群的簇首,然后逐步扩展到所有群的所有节点.在这个组播树中,簇首的性能对整个网络的传输性能影响较大.N ICE协议没有考虑转发节点的能力差异,它的簇首仅仅是根据图论的中心论选出来的节点,这可能会造成能力弱的节点处于转发树的高层,使节点负载较高,致使系统稳定性大为降低.因此,依据面向流媒体视频直播的应用背景,通过分析P2P网络中终端节点的行为,并考虑终端节点的服务能力,对N ICE协议作了相应的改进.

1.2 组播节点的加入与失效

1.节点的加入:当一个成员要加入组播组的时候必须映射到L0层的某个簇上.首先,新节点向RP提出加入请求,RP返回高层节点的信息(逻辑和物理地址),请求者与获得的所有节点进行联系以确定距离自己最近的节点,并以此类推,顺序查询至L0层某簇.如果这个簇未满,则加入,否则簇分裂.

图1 NICE协议的层结构

2.节点失效:簇中的其他主机接收不到离开节点的刷新信息,经过一定的时间就认为该成员失效了.如果离开的主机是这个簇中的领导成员,那么就在剩下的成员中选择一个作为新的领导成员.

2 改进的NICE协议

2.1 一种新的簇首选择算法

文献[2]验证了文献[3]中得到的在P2P视频直播中用户在线时间符合对数正态分布的结论,并指出用户平均剩余在线时间会随着用户已经在线时间的增大而增大.本文对N ICE的改进主要是根据节点的能力(节点的服务带宽)和节点在线时间长短,提出一种新的簇首选择算法.根据文献[2]的分析,节点已在线的时间越长,其继续停留的平均时间越大,退出概率越小.我们定义p rob(i,t)为节点i已在线时间为t时离开组播树的概率,则t↑⇒E(p rob(i,t))↓.in tr(i)为节点i离开时所影响的所有子孙节点的个数,即节点i的失效恢复代价.显然整个组播树T的期望失效恢复代价可以表示公式:

其中in tr(i)与j＊O(k)有关.j为节点i所在最高层.k为节点i所属簇的大小.

因为E(p rob(i,t))的大小仅仅与节点i的已在线时间有关,我们不能改变其大小,所以降低失效恢复代价可行的方法是尽量减少在线时间短的节点处于组播树的高层.因此,在选择簇首时,要把能力不足和退出组播组可能性大的节点排除,在能力强和在组播组中继续停留的可能性大的节点中选择簇首.

设Cap(i)为节点i总服务能力.rem(i,j)为节点i在j层时的剩余能力.设j层某簇节点的集合为SPHj,节点个数为Cn个.

具体算法描述如下:

1)首先对SPHj中所有节点按照节点的可用带宽rem(i,j)进行降序排序,得到集合SPHj1.这样具有较大带宽服务能力的节点占据SPHj1中的靠前位置.

2)取SPHj1中前αCn个节点按照节点的已在线时间t进行降序排序,得到SPHj2.这里参数α可根据应用需求选择(α≤1).我们用αCn调节在带宽服务能力强的节点中选择稳定度大的节点的个数.

3)选取SPHj2中排名最前的节点为该簇的簇首.

2.2 冗余虚拟链路

RVL(Redundant Virtual Link)算法[4]是一种支持应用层组播树快速重构的算法,该算法在组播树结构的基础上增加冗余的虚拟连接作为备用连接.当节点离开后,受影响节点迅速利用备用连接恢复组播数据接收.RVL算法将应用层组播树节点区分为叶节点和中转节点,备用连接增加策略有多种,有的策略是在任意节点间增加任意数目的备用连接;有的策略是中转节点可以与任意数目的备用连接相连,而叶节点只能与一条备用连接相连等.RVL算法缩短了节点离开后组播树的恢复时间.这类算法虽然增加了维护备用连接的控制开销,但是在节点离开较为频繁的组播环境中,提高应用层组播稳定性的效果比较明显.

在改进簇首选择算法后,由于簇首不再是簇拓扑结构的中心节点,它到其他所有节点的距离之和也不一定是这个簇中最小的.而在视频直播应用中,对网络延迟有严格的限制.从数据源到接收者的端到端延时应保证在流媒体传输的时延范围之内,保证组播参与者尽快地收到组播包,因此在构建组播树时应考虑减少时延.原N ICE协议使用的是基本路径树,这种数据传输树不是一棵基于约束的优化树,为了减小传输时延,本文采用最小延迟树作为数据拓扑.因为在每个簇中,簇首通过信息交换了解簇中所有节点之间的延迟信息,由簇首执行D ijk stra算法在簇中形成最小延迟树.

本文在每个簇的最小延迟树中相隔两代的节点间以概率P增加一条冗余虚拟链路,即在祖父节点和孙子之间增加一条链路.概率P的大小决定增加链路的数量.P越大,需要增加的冗余虚拟链路越多,这增大了节点的处理负担,P越小,则组播树的稳定性也会随之下降,因此,应根据情况选择一个较优的P值.

3 仿真实验

为了验证改进的协议的性能,采用N S2网络仿真工具对N ICE协议在改进前后的稳定性进行对比分析.实验中节点的网络拓扑由GT-ITM生成,N ICE协议参数K=5,节点的在线时间的概率密度分布采用参数为m=4.4n=1.6的对数正态分布.在N ICE原始组播树的基础上,使用前面的策略为组播树增添冗余虚拟链路,并设概率P=0.5.

失效恢复代价也即当中间节点退出或失效后所影响的所有子孙节点个数.在组播树中,树的失效恢复代价越小,组播树越稳定,我们用累积失效恢复代价来表示组播树的稳定性.

图2 N ICE改进前后的累计失效恢复代价的比较

图3 节点失效情况下组播树的平均恢复时间

如图2所示,当节点失效时,改进后的N ICE协议的稳定性效果非常明显.这是因为改进后N ICE在选择簇首时,使节点能力弱的和离开组播树可能性大的节点为非簇首,节点能力强的和继续留在组播树中可能性大的节点为簇首,从而降低了节点的失效恢复代价.

从图3可以看出,改进后的组播树的平均恢复时间远远小于原协议的组播树的平均恢复时间.这是因为一方面改进后的组播树降低了节点的失效率,另一方面,以概率P增加的冗余虚拟链路也大大减少了组播树的恢复时间.

4 结语

P2P系统的节点行为总是不可控制的,每时每刻都有很多节点的加入与离开,严重影响应用层组播系统的稳定性.本文针对应用层组播生成树的稳定性进行分析,基于p2p的节点特性提出了一种改进的N ICE簇首选择算法.并采用在生成树中增加冗余虚拟链路的方法以增加组播树的稳定性,缩短节点失效后组播树的恢复时间.仿真实验结果显示,与N ICE协议相比,改进后的N ICE协议具有良好的稳定效果.

[1]S.Banerjee,B.Bhattacharjee,C.Kommareddy,Scalable application layermulticast[C].In Proceedings of 2002 ACM Conference on Applications,Technologies,Architectures,and Protocols for Computer Communications(SIGCOMM’02), 2002:205-217.

[2]罗建光,赵黎,杨士强.基于用户行为分析的应用层组播树生成算法[J].计算机研究与发展,2006,43(9): 1557-1563.

[3]Veloso E,AlmeidaV,MeiraW.A Hierarchical Characterization of a Live Streaming Media Work load[C]//Proc.of ACM SIGCOMM Workshop on Internet Measurement.New York,USA:[s.n.],2002.

[3]Roca V.A Host-based Multicast(HBM)So lution for Group Communications[C]//Proc.of IEEE Int’1 Conf.on Networking.Colmar,France:[s.n.],2001.

[4]A ynan El-Sayed.Application Level Multicast Transmission Techniques Over the Internet[D].paris:University of Paris,2004.

Abstract:The application level multicast tree is composed of the end hosts which can no t ensure the stability of them ulticast tree.Based on live streaming,this paper proposes a new cluster-leader selected algorithm in NICE protoco l through analyzing of end hosts’behavior and capabilities,and adds the Redundant Virtual Link to reconstruction of the application level multicast tree,in order to imp rove the stability of NICE protoco l.

Keywords:Application Level Multicast;Redundant Virtual L ink;live streaming

Research on Stability of Application Layer Multicast Based on NICE Protocol

SUI Dong-mei
(Soft Academy,Shangqiu Teachers College,Shangqiu 476000,China)

TP393

A

1004-7077(2010)02-0056-04

2010-01-25

随冬梅(1978-),女,河南省商丘人,硕士研究生,主要研究方向为网络通信。

[责任编辑:袁 伟]