一种基于层次结构的可扩展应用层组播模型

张有为 (长江大学计算机科学学院,湖北荆州434023)

虽然应用层组播技术的应用日益广泛,但是其缺点也比较明显,主要在于可靠性不高,并且缺乏网络拥塞控制机制[1～2]。基于 “单数据流”的应用层组播协议,如 Narada[3]、HMTP[4]、NICE[5]、DONet[6]等可以解决应用层组播某一方面的问题,但是无法兼顾系统的可扩展性和健壮性。

采用多描述编码MDC(Multiple Description Coding,MDC)技术[7～8]的组播协议CoopNet[9]和SplitSream[10]通过多路并发传输的方式较好地平衡了组播系统的可扩展性和健壮性。但多树模型却无法有效解决描述的同步问题,从而无法获得较高的图像质量。此外,节点在加入系统时,多树结构的的控制开销要远大于单树结构。

为此,笔者充分考虑节点的异构性以及节点失效而对性能造成的影响,提出了一种基于层次结构的应用层组播模型-RSA。RSA采用多描述编码技术对媒体数据编码,并以此构造多树的分层结构模型,采用分布式算法实现了节点中描述资源和对资源请求的均匀分布,以提高流媒体系统的健壮性和可扩展性。

1 基于层次结构的应用层组播模型

对于组播节点而言,采用多描述编码技术不需要考虑描述的接收次序,因此特别适合于动态的网络环境。基于层次结构的应用层组播模型RSA中采用该技术对节目内容进行编码,并以此构建多树的组播模型。

RSA给出了一种基于多树的分层结构模型,这种结构很好地解决了描述之间的同步问题,实现了节点的快速加入,并提高了图像质量。此外,RSA还提出了基于资源均匀分布的最大覆盖算法MAXC-通过将节点对描述的请求均匀地分布在最多的父节点以实现模型的健壮性,同时也有利于实现图像质量快速恢复。

如图1所示,节目内容在源节点S被编码成3个描述(D1,D2,D3),节点之间的可用带宽按照式(1)映射成描述码率的倍数Weight(其中SubDescription和Avail_BW分别为单个描述的码率和节点间的可用带宽):

图1 多树模型的数据传输

例如A→D之间的带宽权值为3,表示D可以从A获取3个描述。如图1(a)所示,节点D可以从父节点集{A}、{A,B}、{A,C}或{A,B,C}中均能获得最大的描述集(D1,D2,D3)。但是,只考虑图像质量这一个方面无法保障系统的健壮性。MAXC算法将对最大描述集的请求均匀地分布在最大的父亲集中,从而保证在节点失效的情况下不至于出现图像质量的剧烈抖动。图1中的节点D选择{A,B,C}作为其父亲集,并根据加权的MAXC算法将对(D1,D2,D3)的请求均匀地分布在3个父节点上。

2 模型设计

RAS模型结构如图2所示,主要由描述资源的均匀分布算法和资源请求的最大覆盖算法、组播过程中节点的加入、数据传输的优化和对节点失效的恢复等几部分组成。

图2 RSA模型结构图

2.1 描述资源均匀分布优化算法

多树组播模型在动态环境中有较好的健壮性,但是,如果描述资源在父节点中的分布不均匀,却会造成对拥有丰富描述资源节点的过度依赖,进而在节点失效时产生图像质量的剧烈抖动。如图 1(a)所示,当节点A失效时,图像质量会下降,且无法依靠节点B、C(不包含描述D3)中已有的描述资源来进行恢复,只能重新搜索新的父节点来进行图像质量的恢复,但会产生较大的延迟。因此,笔者提出了一种描述资源均匀分布的方案,以此来提高动态网络中的图像质量。

由图1(a)可知,描述资源的分布比例为:D1＞D2＞D3。如果节点C不再请求D1而是D3,则会形成如图1(b)所示的分布比例:D1=D2=D3,均匀分布。则节点D请求父亲集{A}、{A,B}、{A,C}、{B,C}、{A,B,C}中的任一集合均能获得最大的描述集;与此同时,当节点D的父节点集{A,B,C}中任一节点的失效时,仍然可以通过调用MAXC算法来重新调整对父节点的描述请求,从在线的父节点中请求最大描述集,从而在不降低图像质量的情况下实现节点的无缝切换和快速恢复。

为实现描述资源在各层节点中的均匀分布,需要为节点中的描述设定属性参数 RefCount-“引用计数”。节点应优先请求父节点中RefCount的描述。图3(a)所示为节点C(假设C在A,B之后加入组播树)根据父亲集信息生成的请求矩阵Req_MX,其中,Res_set为父节点中的描述资源,请求集 Req_set初始化为NULL。图3(b)显示父节点中描述资源的引用情况,其中D3的RefCount在C加入前为1,C加入后向S请求D3描述,其RefCount更新为2。图3(c)显示按以下规则生成所生成的扫描矩阵Scan_MX:

1)Res(描述资源)按照RefCount升序排列;

2)若RefCount相同,则按Res在所有父节点中的资源数量的升序排列;

图3 均匀分布算法中的数据结构

3)Pat(父节点)按拥有资源数量的升序排列;

4)矩阵中(i,j)为 “1” 表示Pat拥有 Res;“0”则表示Pat没有 Res。

节点以Req_MX和Scan_MX为参数调用MAXC算法生成最大资源的覆盖以及对应的请求,如图3(a)所示。

2.2 节点加入

为了避免节点失效造成过大的图像质量抖动,系统中节点的最大入度和出度设定为K(K为节目编码的描述个数)。当节点加入组播树时,从服务器获取K个度小于K且Weight≥1的节点信息作为父亲集。节点根据父亲集信息生成请求矩阵Req_MX和Scan_MX作为MAXC算法的参数,其伪代码如下:

节点根据由MAXC算法生成的请求集向父节点请求资源请求描述,如图1(b)所示,节点D的请求集为(A(D1),B(D2),C(D3))。

2.3 数据传输优化

节点在加入组播后,需不断调整父亲集、更新请求集以提高系统的性能。其更新的基本思想为:①当节点加入组播树后,通过继续搜索新的父节点来请求加入时所缺描述资源,以获得最佳视频质量;②继续为节点搜索最大请求集,若对某个父节点的描述请求数量大于1,则将其分裂为多个单一的描述请求,即将对K个描述的请求均匀地分配到K个父节点上。

2.4 节点失效时的视频质量恢复

当发生节点失效时,系统按照以下步骤对视频质量进行修复:

1)将离线的父节点从Req_MX删除。

2)调用MAXC算法,对在线父节点中的资源请求重新分配。

3)根据数据传输过程中的优化方法为节点生成新的请求集。

由于实现了描述资源和描述请求的均匀分布,在2)中,实现视频质量的无缝切换是大概率事件;通过3)中的优化策略,节点能实现请求集的快速更新,能避免了图像质量的剧烈抖动。

3 仿真试验

采用流行的网络仿真器NS2对RSA模型进行仿真,对平均数据接收率 (Mean Receiving Rate,MRR)、平均恢复时间 (Mean Recovery Time,MRT)、平均链路强度 (Mean Link Stress,M LS)进行评估。

试验中,将RSA和CoopNet进行对比。使用通用的网络拓扑生成器GT-ITM生成 transit-stub类型的物理网络拓扑,并且将码率为300Kbps的媒体数据编码成4个描述,服务器的度设定为64,节点度为4,节点之间的可用带宽分布为200～400Kbps。

在试验的前500s内拓扑节点数量按指数递增,从16增加到512,在系统稳定后的600～1100s内,每隔100s随机安排16个节点离开,用来模拟在节点失效时数据接收率的变化。

图4表明,随着节点的增加,CoopNet的MRR出现了的比较明显的下降,但是RSA的MRR却没有显著的变化,并且比CoopNet高出约20%。

图5显示,在节点失效时RSA中图像质量的抖动约为15%,而CoopNet达到了30%;另一方面,图4显示RSA在节点失效时,其MRT为20s,而CoopNet则为40s。

由于资源的均匀分布降低了链路的强度,图6显示,在0～500s内,RSA的MLS要比CoopNet的低20%。

图4 节点加入时的平均数据接收率

4 结 语

笔者所提出RSA模型采用MAXC算法提高了节点的视频接收质量,实现了节点失效时视频质量的快速恢复。试验证明,RSA具有很好的健壮性和可扩展性。

图5 节点失效时的平均数据接收率

图6 节点加入时的平均链路强度

[1]罗万明,林闯,阎保平.TCP/IP拥塞控制研究[J].计算机学报,2001,24(1):1～18.

[2]黄伟红,孙正兴,张福炎.Internet视频流中的自适应拥塞控制技术研究 [J].计算机学报,2001,24(8):797～801.

[3]Chu Yanghua,Sanjay Rao,Zhang Hui.A Case For EndSystem Multicast[A].Selected Areas in Communications[C].Santa Clara,CA:IEEE June,2000.1456～1471.

[4]Zhang B,Jamin S,Zhang L.Host multicast:A frame work fo r delivering multicast to end users[A].T wenty-First Annual Joint Conference of the IEEE Computer and Communications Societies[C].California,US:IEEE June,2002.1366～1375.

[5]Suman Banerjee,Bobby Bhatacharjee,Christopher Kommareddy.Scalable Application Layer Multicast[A].Consumer Communications and Networking Conference[C].Karlsruhe,Germany.IEEE:Jan,2002.43～51.

[6]Zhang X,Liu J,Li B,et al.CoolStreaming/DoNet:A data-Driven Overlay network for peer-to-peer live Media Streaming[A].24th Annual Joint Conference of the IEEE Computer and Communications Societies[C].Miami,FL:IEEE.March,2005.2102～2111.

[7]肖友能,薛向阳,曾玮.视频转码技术回顾 [J].通信学报,2002,23(8):72～80.

[8]李彬,黄峰,孙立峰,杨士强.一种鲁棒灵活的非平衡多描述视频编码和传输方案 [J].计算机学报,2008,31(7):1155～1164.

[9]Padmanabhan V,Wang H,Chou P,et al.Distributing streaming media content using cooperative networking[J].IEEE Transactions on Multimedia,2002,8(2):233～242.

[10]Castro M,D ruschel P,Kermarrec A M,et al.Split Stream:High-bandwidth content distribution in a cooperative environment[J].IEEE Transactions on Knowledge and Data Engineering,2003,20(9):1273～1281.