基于分簇结构的P2P流媒体混合分发算法

陈瑞昭， 刘永广

(广东轻工职业技术学院管理工程系,广东广州 510300)

基于分簇结构的P2P流媒体混合分发算法

陈瑞昭， 刘永广

(广东轻工职业技术学院管理工程系,广东广州 510300)

提出了一种基于分簇结构的混合分发算法，算法采用分簇的方法将流媒体中的节点资源进行簇划分, 形成由簇头、簇内节点构成的分簇网络结构，簇头与簇内节点通过拉拽算法来获得数据，而簇头间采用推送分发算法. 仿真结果表明, 该算法能提高数据块复制速度，减少数据传播时延，有效降低系统的控制开销，提高了播放连续度.

对等网络； 流媒体； P2P覆盖网； 簇； 推送算法

随着网络技术的发展，以高质量、富媒体、互动性为特征的流媒体应用是互联网业务的趋势. 在致力于提高端到端的流媒体传输性能的同时，业界的研究人员引入了P2P(Peer-to-Peer)网络来解决大规模流媒体传输时服务器资源瓶颈的难题，对P2P中流媒体的分发算法进行了较多的研究[1]，研究热点集中在成员管理和树状拓扑的构造算法上. P2P流媒体直播协议划分为3类[2]：源驱动，接收端驱动和数据驱动. 源驱动协议需要为新加入的节点指派父节点，数据从源节点开始，以接力的方式向下层的节点推送. 接收端驱动协议在接收者一侧建立树状拓扑，由接收端整合和管理节点以获取流数据. 数据驱动的协议一般与网状拓扑的覆盖网结合，节点发现自己需要的数据并从邻居节点获取这些数据.

PEERCAST[3]和COOLSTREAMING[4]是P2P流媒体直播领域代表性的原型系统，PeerCast使用了树状的拓扑，可以满足低流量的流媒体应用，而在高流量的流媒体应用方面其表现不能令人满意，当并发数目在数百的数量级时，节点的异构性引发拓扑动荡现象十分严重，高层节点的离开和崩溃导致严重的回放断续. CoolStreming构造了一个网状的网络，对网络动态变化具有更好的鲁棒性，更适合于P2P流媒体直播. CoolStreaming中的节点采用了主动发送拉拽数据请求来获得数据的拉拽算法[5]，由于重复的数据块传输浪费带宽，使得本来稀缺的上传带宽资源更稀缺，节点扮演下载服务的角色，拉拽算法无法利用处于不能映射的内外节点上传带宽，随着网络规模的增大，拉拽算法引入越来越多的传输时延[6]. 文献[7]提出了节点主动发送推送数据请求来获得数据的推送算法(Push-to-Pull Algorithm,PTPA)，但在实际运行中还是存在数据复制速度不足、回放时延较大的问题. 针对以上问题，提出了一种混合式分发数据的方法，该方法通过对流媒体中的节点资源进行分簇处理，由性能较高(处理、存储、带宽等方面性能)的节点担任簇头，在簇头间采用推送算法，而簇头与簇内节点采用拉拽算法来获得数据，获得较好的性能.

1 算法描述

基于分簇结构的混合分发算法(A Hybrid Scheduling Algorithm for P2P Stream Based on Clustering，HSAC)采用P2P网络，它是一个自组织的层次式结构网络，由一个索引数据服务器负责簇头节点的管理，记录共享信息，响应信息的查询. 网络中的节点向索引数据服务器提供自己的共享信息，并负责分发共享文件的通信，也会根据需要下载自己所需要的其他节点上的信息. 簇头之间构成一个高速转发层，采取主动发送数据的推送算法，簇头负责簇的管理和簇之间信息的交互，然后分别把附近性能较差的节点聚集成簇， 簇内节点与簇头节点之间采用请求数据的拉拽算法，形成HSAC的网络拓扑结构图，如图1所示.

图1 HSAC网络拓扑结构图Fig.1 Topology of HSAC network

1.1基于分簇结构的覆盖网络构建方法

本算法是一个动态、分布执行的算法，节点首先将消息发送给周围的一组节点，周围节点在接收到消息后根据需要对消息进行转发. 这样，消息就可以通过节点之间接力的方式进行传递. 每个节点用一个二元组(IP，id)来标识，IP表示该节点的编号，id为节点的标识值，对簇头的集合C的所有节点标识值id为1，其余簇成员节点集合标识为0. 节点缓冲中的各个分段的可用性信息被表示为一个缓冲映射，称为缓冲映射信息(Buffer_Map，BM)，每个节点会和它的邻居节点不断交换各自的BM，收到的节点可能会转发该节点的消息. 算法通过BM信息建立和维持与相邻节点的链路，并承载一些控制信息，算法同时设置另外4个控制消息. 节点Vi用CH(Vi)宣布自己为簇头节点，用JOIN(Vj,Vi)请求加入以Vj为簇头的簇，成为其成员节点. 若Vj为簇头节点，则用ACCEPT(Vi,Vj)消息接受节点Vi的加入请求，或者用REJECT(Vi,Vj)消息拒绝节点Vi的加入请求. 网络拓扑图中的每一节点中，存在一张拓扑结构表，用来记录与节点相关的拓扑结构. 通过让每个节点定期向相邻节点发送和接收BM消息，以获取相邻节点的信息，不断更新自身的相邻节点集NList，以适应节点的动态性. 如果节点离开，它就会向邻居节点发出“离开”信息，收到信息的节点应会在其相邻节点集删去此节点. 因此，通过定期监测邻居信息，获得邻居的相关信息，也就能找到自己所需要的数据.

1.1.2 节点的退出及更换簇头节点 在簇的初始化完成以后，随着节点的频繁变动，网络的拓扑结构会发生变化，节点的退出包括簇内节点的退出与簇头节点的退出，在HSAC系统中的节点通过周期性地与邻居节点发送在线消息以保持联系.

(1)簇内节点的退出.如果簇内节点由于节点失效而被动离开时，簇头节点不会收到该节点发来的在线消息，那么几个在线周期后簇头节点将把该节点的状态视为离开，并将其从成员列表中删除，其它非簇头邻居节点更新自己的邻居表.

(2)簇头节点的退出.若节点Vi是簇头节点Vk的成员节点，当Vk脱离网络，则Vk发出JOIN(-1,Vi)消息. 因为无ID为-1的节点，节点Vk以此消息辞去簇头角色，重新执行初始化过程.

(3)更换簇头节点.由于P2P网络的动态性，簇头节点在任何时候都有可能更换. 若Vj是簇头节点而Vi是以Vk为簇头的成员节点，则Vi将比较Vj与Vk的负载情况. 若节点Vk的负载小于节点Vj的负载，则Vi还是以Vk作为自己的簇头节点，只是刷新自己的邻居表. 若节点Vk的负载大于节点Vj的负载，则Vi脱离原簇，发出JOIN(Vj,Vi)消息请求成为Vj的成员节点. 而Vk节点收到JOIN(Vj,Vi)消息后将Vi从成员表中删除.

1.2数据传送算法

数据传送是指如何在所构建的应用层覆盖网络上传输实时流媒体数据. P2P中每个节点和其邻居周期性地交换数据可用性信息，通过分析数据可用性信息有选择地从其邻居获取数据，节点Buffer_Map变化或者邻居Buffer_Map的变化都会触发数据传送，接收到完整的数据块、添加新邻居、邻居Buffer_Map更新都会导致Buffer_Map的变化.

1.2.1 推送算法 簇头之间采取簇头节点主动发送推送数据的请求，向它的伙伴节点发送自己的缓存信息，拥有数据块的簇头节点主动连接有较多子节点的伙伴节点之后就成为上传服务器，如算法1所示.

算法1推送算法

for each packet j

计算每个数据块的时间戳time-stamp[j];

for each packet j

n←时间戳最大的数据块个数;

if n=1

推送该数据块;

else

在时间戳相同的数据块中找发送次数最小的数据块p;

推送该数据块p;

end if

end for

end for

for 每个连接的簇头节点

通过轮盘赌算法，找子节点层数越多的簇头节点作为目标节点;

向选择的目标节点发起请求;

end for

if 推送该数据块的请求时间迟于该数据块的播放时间

then

拒绝接收;

else if 本节点正在从别的伙伴处接收该数据块

then

拒绝接收;

else if 本节点的缓存中已经拥有该数据块

then

拒绝接收;

else

接收该数据块;

end if

1.2.2 拉拽算法 簇头与簇内节点、簇内节点间主动发送拉拽数据请求来获得数据，这种模式与DONet(Data-driven Overlay network)[4]中的纯拉策略相同，数据提供者首选有足够带宽而且所拥有的数据块有充分处理时间的节点，如算法2所示.

算法2拉拽算法

if 潜在数据提供者个数=1

该节点为数据提供者;

else

把有足够带宽而且所拥有的数据块有充分处理时间的节点作为数据提供者;

end if

if 拉拽该数据块的请求时间迟于该数据块的播放时间then

拒绝接收;

else if 本节点正在从别的伙伴处接收该数据块

then

拒绝接收;

else if 本节点的缓存中已经拥有该数据块

then

拒绝接收;

else

接收该数据块;

end if

Do更新缓冲映射信息Buffer Map

2 实验仿真与分析

为了验证HSAC的性能，使用了GT-ITM网络拓扑生成器[8]及NS-2 网络仿真器对HSAC进行测试. 仿真参数为：视频长度为120 min(电影的标准长度)，视频流码流为390 Kbps， 数据块划分时间间隔为1 s，缓冲时间为60 s，节点的邻居节点数量限制为5个，参与网络的节点个数1 000，接入平均上传带宽为500 Kbps，其中20%的节点上传带宽为1 000 Kbps，40%的节点上传带宽为500 Kbps，40%的节点上传带宽为250 Kbps，上传带宽约为流码率的1.3倍.

仿真主要测试了数据块复制速度、播放缓冲延迟、控制开销等3个指标，并与DONet算法和文献[7]中的PTPA算法进行比较, 其中，DONet算法采用数据驱动方式,流媒体数据的传输是基于接收节点的主动请求的拉拽算法,也就是纯拉策略，而PTPA算法则采用每个节点都主动尽力将自己拥有的数据传输给它的邻居节点的推送策略.

2.1数据块复制速度

数据块复制速度是数据块从产生至分发到节点的时间关系，影响P2P直播系统源端到接收端的回放延时. 如图2所示，由于HSAC算法采用分簇的覆盖网络构建方法及数据传输推拉结合策略，把处理、存储、带宽等方面性能较佳节点作为簇头节点，更能发掘快速传输数据的潜力，覆盖所有节点的时间为14 s，采用推送策略的PTPA算法覆盖所有节点的时间为20 s,而DONet的纯拉策略由于需要多次交互才能找到合适的下载节点，不能有效地发掘节点的上传带宽，覆盖所有节点的时间需要60 s. HSAC中的节点根据自己的BM信息和邻居的BM信息来调度数据块的复制传输，簇头节点在收到数据块时进行数据调度，节省了数据调度的延迟，并且可以最大限度利用节点的上传带宽. PTPA算法虽然能主动传输数据，但由于没有充分发挥性能较佳的节点性能，使得数据传输速度略迟于HSAC，而DONet算法在BM信息更新时才能触发新一轮的数据调度，BM信息广播的频率会影响数据块复制的速度，不能有效利用节点的上传带宽. 在相同BM信息广播频率的情况下，DONet算法表现不如HSAC及PTPA算法.

图2 不同算法下数据块的复制速度

2.2播放缓冲延迟

播放缓冲延迟是节点从加入网络至回放开始的延迟时间. 仿真中节点缓冲时间为60 s，缓冲比97%时节点开始回放流媒体数据，如图3所示，HSAC均优于PTPA算法及DONet算法. 在节点数量较少时(节点数目少于300)，新加入的节点需要更多的时间来缓冲数据，随着网络规模的增大，缓冲时间减少，HSAC比PTPA算法需要的缓冲时间大约少10 s，比DONet算法需要的缓冲时间大约少40 s. 而在节点数量较大的情况下(节点数目大于400)，节点缓冲的时间并不会随着网络规模的增大而减少. 这是因为每个节点的伙伴个数是有限的，拥有剩余带宽的节点并不都能发现新加入的节点. 缓冲时间与节点的上传带宽相关，在节点的平均上传带宽仅为码率的1.3 倍时，HSAC的缓冲时间大概为40 s，PTPA算法的缓冲时间为50 s，而DONet算法需要多出大概20 s的缓冲时间.

图3 不同算法下的回放缓冲延迟Fig.3 Buffer-to-play delay of different algorithms

2.3控制开销

控制开销(overhead)是衡量算法效率的一个重要指标，在流媒体分发系统，大量的开销用于数据块的传输和交换，它是指节点的控制流量和视频流量的比率，通信开销的大小是系统可扩展性的重要表现，取每个节点上控制开销的平均值. 在实验开始阶段，各个节点加入有一个大约为 1 min的初始化时间，自加入开始每个节点在线时长都至少为120 min，默认的流率为500 kbps. 图4给出了不同节点数下，HSAC和PTPA算法及DONet算法在邻居节点数n=3和n=5的控制开销，可以看出3种算法的控制开销不随着网络规模的增大而增大，这说明它们都具有很好的可扩展性，HSAC由于利用簇头节点的性能，数据传输算法又减少了节点之间BM和请求的交换，其控制开销明显低于DONet算法，而PTPA算法跟HSAC一样，由于减少了交换的开销，控制开销仅次于HSAC.

图4 不同算法下的控制开销

3 结论

提出的HSAC采用分簇的方法将流媒体中的节点资源进行簇划分，簇头与簇内节点通过拉拽算法来获得数据，充分发挥了高能力节点的性能优势，而簇头间采用推送分发算法，能减少数据传播时延，提高了流媒体的传输质量，适合大规模的流媒体服务的应用. 但HSAC也面临着过分依赖超级簇头节点等问题，是HSAC今后研究改进的重点.

[1] DESHPANDE H,BAWA M, GARCIA-MONINA H.Streaming live media over a peer-to-peer network[C]∥Technical Report CS-2001-31, Stanford, CA, USA: CS Dept, Stanford University, 2001.

[2] SILVERSTON T, FOURMAUX O. Source vs data-driven approach for Live P2P streaming networking[C]∥International Conference on Systems and International Conference on Mobile Communications and Learning Technologies. Mauritius: IEEE, 2006:99.

[3] BAWA M, DESHPANDE H, GARCIA-MONINA H. Transience of peers amp; streaming media[J]. ACM SIGCOMM Comput Commun Rev, 2003,33(1):107-112.

[4] ZHANG X, LIU J, LI B, et al. Coolstreaming/donet: A data-driven overlay network for peer-to-peer live media streaming[C]∥24th Annual Joint Conference of the IEEE Computer and Communications Societies. Miami, FL, USA: IEEE, 2005:2102-2111.

[5] LI B, XIE S, KEUNG G Y, et al. An empirical study of the coolstreaming system[J]. IEEE Journal on Selected Areas in Communications, 2007, 12(25):1627-1639.

[6] 郑凯．一种P2P VOD系统的缓存部署及调度机制[J]．华南师范大学学报:自然科学版，2009(2):34-37．

ZHENG Kai. A mechanism of cache deploymenting and scheduling of P2P VOD system[J]. Journal of South China Normal University: Natural Science Edition, 2009(2):34-37．

[7] 周卫,叶梧.推送模式的P2P流媒体分发算法[J]. 科学技术与工程,2008,8(4):946-952.

ZHOU Wei,YE Wu.Push Based Scheduling for P2P Streaming[J].Science Technology and Engineering, 2008,8(4):946-952.

[8] CALVERT K，DOAR M,ZEGURA E.Modeling internet topology [J]．IEEE Communications Magazine,1997(6):160-163．

Keywords： peer-to-peer;stream media; P2P overlay network; clustering; push algorithm

【责任编辑 庄晓琼】

AHYBRIDSCHEDULINGALGORITHMFORP2PSTREAMBASEDONCLUSTERING

CHEN Ruizhao, LIU Yongguang)

(Department of Management, Guangdong Industry Technical College, Guangzhou 510300, China)

A hybrid scheduling algorithm based on clustering is presented. In the algorithm, node resources are divided into cluster head and cluster nodes by clustering method and form a clustering network structure. For the network, data is obtained by push algorithm between cluster heads and heads, while pull algorithm between cluster heads and inter-cluster nodes. Simulations show that the algorithm can increase the speed of data block duplication, reduce the data propagation delay and the control overhead of streaming system efficiently, and improve the degree of continuous playback.

2009-09-14

广东省计算机网络重点实验室开放基金资助项目(cn200407)；广东轻工职业技术学院自然科学基金资助项目(KX010405)

陈瑞昭(1970—)，男，广东潮州人，广东轻工职业技术学院讲师，主要研究方向：信息网络理论与技术，Email:chen_rz@163.com.

1000-5463(2010)01-0037-05

TP393

A