一种基于节点带宽的自适应数据调度策略在PPVoD系统中的应用研究

黄志艳

(泰山职业技术学院，山东泰安 271000)

随着互联网宽带的普及和发展，网络音频和视频已经成为网络多媒体主流应用，流媒体的诞生，更是促进了这些应用的规模化上升。流媒体是一种包含数据采集、压缩、存储和传输等多项技术的一种网络应用工具。在传统应用过程中，流媒体通常采用的系统架构是C/S模式，随着网络用户的快速增加，该模式易受到服务器带宽、并发进程等服务能力的约束，成为流媒体发展的瓶颈。为了解决该问题，在许多计算机学者的努力下，引入了P2P技术，该技术的目的是使网络中的用户分享拥有的资源，以无中介、对等的传输方式进行资源交换。

在国外，基于P2P技术的流媒体发展迅速，得到十分广泛的应用，其在世界著名的各大高校，比如斯坦福大学［1］、中弗罗里达大学［2］、马里兰大学［3］、香港大学［4］等拥有 P2P 技术研究机构，微软研究院［5］专门成立了的P2P技术研究组，经过诸多学者的努力，P2P技术研究成果显著，已经涌现了SkyPe［6］、Split-stream和PeerCast［7］等诸多经典的系统。在国内，基于P2P的流媒体技术也在高速发展着，已经诞生了PPLive［8］、AnySee［9］，PPStream、QQLive［10］等流媒体点播平台，截至 2012 年6 月，我国 P2P 市场经济产值已经高达6.83亿元，随着P2P技术的改进和发展，基于该技术的流媒体应用前景广阔。

1 PPVoD系统中数据传输模式

在采用P2P技术的流媒体系统中，数据传输模式主要有三种:推模式、拉模式以及推拉结合的模式。

1.1 推模式

推模式(Push)是指数据的拥有者按照既定路径把自身拥有的数据向外发布。推模式的实现方式主要是组播树，其要求节点之间必须存在父子关系。该模式的基本思想是主动将数据文件“推”给需要数据的节点，其实质是假设代理节点具有很大的存储功能和长时间在线，以便将服务器的功能转嫁于代理节点，其缺陷是一般与系统的动态性和已勾选互相矛盾，很难实现。

1.2 拉模式

拉模式(Pull)是通过接收节点的主动请求以获得数据，是指接收节点的驱动模式［11］。在基于P2P技术的Cool Streaming直播系统中，基于数据驱动的方式，在覆盖网中采用了拉模式获取节点所缺少的数据片段，交换BM信息是每隔一定周期进行一次，这样以便确认数据是否可以使用。该策略在系统运行过程中会产生一定的延迟，并且这些延迟将会随着节点的增多不断地扩散，因此，基于拉模式的数据传输系统会降低系统的实时性。

1.3 推拉结合模式

由于单纯的推模式和拉模式具有不可抗拒的缺点，为了弥补他们的缺点，人们将推拉(Push-Pull)传输模式的优点进行结合，产生了推拉结合模式。在使用该模式的流媒体系统中，时间被分成连续的时间片，根据每个时间片的相关情况，数据传输模式采取推模式或拉模式。当系统进入稳定播放阶段时，对上个时间片内服务节点的性能进行评估，依据评估结果向每个服务节点制定自身所需数据，之后，采用推模式进行数据传输。但是，在推拉结合的模式中，由于推拉数据的阀值不够明显，推的数据可能会被重复下载，导致数据冗余和带宽资源的浪费。

2 PPVoD系统中数据调度策略

基于P2P技术的流媒体系统建立在Gossip协议基础上，系统中的所有的合作节点能够自动有机构成一张网状拓扑结构，因此，某个应用节点可以从多个合作节点中获得所需数据，同时，该节点也必须分享其拥有的数据，因此，基于P2P技术的流媒体系统的性能和服务质量受流媒体数据调度的效率的直接影响。在P2P流媒体系统中，数据调度策略主要有三种，分别是最少优先策略、随机调度策略、最急优先策略［12］。

随机调度策略是三种策略中较为简单的，该算法在众多的服务节点中随机选择一个拥有所需数据片段的节点作为服务节点，向其发送数据请求，获得所需数据。该算法具有复杂度较低，便于维护节点之间的负载均衡的特点，但是，该算法由于过于简单，其忽略了系统间存在的异构性、节点的带宽、服务质量等特性，因此，其效率低下。

最少优先策略是一种使用较为广泛的调度策略，它是以数据片段冗余度优先的策略。最少优先策略的基本思想是记录拥有该节点缺少数据片段的节点数量，节点数目用冗余度表示，冗余度比较小的节点在请求数据时优先被选择，冗余度较大的节点实施在请求数据时，可以实行任务分配，优先选择节点带宽较高的服务节点相应节点请求，因此，该节点能够动态的实现良好的负载均衡，提高了带宽利用率。但是，由于即将播放的数据不能及时获得系统刚刚发布的冗余度较小的数据，忽略了直播系统的实时性需求，不适于对延迟要求较高的系统。

最急优先策略又被称为贪婪策略，基于该策略的系统中，缺少数据片段的节点优先选择距离其最近的服务节点下载数据，这样就可以充分的播放节点的实时性需求，优先选择紧迫性较高的数据片段，提高了播放的连续性，有效弥补了最少优先策略的缺点。但是该策略忽视了整个系统，只考虑了单个节点，虽然看似对每个节点都有利，实际上降低了数据块的共享几率，不能有效调动每个伙伴节点的数据传输能力，从而造成系统整体性能的下降。

3 基于节点带宽的自适应数据调度策略

3.1 数据缓冲区

在P2P系统中，数据调度是一个NP-Hard问题，因此，寻找一个次优的调度方案，成为人们研究的热点。本文在保证服务质量的条件下，采用自适应多级反馈队列，推拉结合，高效利用节点带宽，缓解媒体服务器的负载，基于功能划分，数据缓冲区分为Extra Buffer、Pushing Buffer和Pulling Buffer三个部分，如图1所示。

图1 数据缓冲区结构Fig.1 Data buffer structure

已播缓冲区(Extra Buffer):该缓冲区存放播放点之前的数据，其基本的功能是杜绝产生无效的数据请求，以便能够为合作节点提供高效的服务，该缓冲区的大小主要取决于数据传输时延和节点间数据调度的周期。

拉缓冲区(Pulling Buffer):该缓冲区存放弹性时间较短的数据。为了保证视频播放的流畅度，该部分所缺少的数据片段具有较高的优先级，系统采用拉模式从合作节点处获得。该缓冲区的大小主要取决于拉模式造成的数据时延。

推缓冲区(Pushing Buffer):该缓冲区存放缓冲时间较长的数据。其既可以采用拉模式获得数据片段，也可以采用推模式获得数据片段，其大小主要取决于该缓冲区需要满足的服务能力，同时还取决于直播中节点和数据源的播放点之间的差值。

推拉两缓冲区的大小与系统性能密切相关，影响节点的带宽利用率、传输延迟和播放流畅度，因此，本文基于P2P自身的动态性特征进行适应性调整，能够获得较好的系统性能。

3.2 服务节点集、邻居节点集和备用节点集

备用节点集、邻居节点集和服务节点集在基于P2P技术的流媒体系统中需要覆盖网进行维护的三个节点集合。(1)备用节点集是指选择部分节点放在一起，其可能转化为邻居节点;(2)邻居节点集是指在系统运行过程中，与本节点播放统一频道的其他正在播放的节点的集合，邻居节点在运行过程中可能转化为合作节点;(3)服务节点集指为缺少数据片段的节点提供视频服务的节点的集合。

图2 节点集角色转换流程Fig.2 Node set role conversion process

基于P2P技术的流媒体系统在运行过程中根据数据片段的需要可以动态调整邻居节点、服务节点和备用节点之间转换，如图2所示，转换过程分为四个步骤:(1)系统初始时，一个节点P加入系统后，此时该节点无法获得备用节点的缓冲区状态，因此可以通过覆盖网中包含的节点信息，收集到近邻节点并将其存放到备用节点列表中;(2)节点P可以向备用节点请求其拥有的缓冲区状态，并且节点P和备用节点之间存在同时播放同一频道，缓冲区重合的现象，那么，节点P可以将该类备用节点转换为邻居节点并将其降入邻居节点集中;(3)节点P会与邻居节点按照设定周期交换各自的缓冲区状态，以便高效的进行数据调度;(4)当节点P的邻居节点由于服务能力过载，无法为节点P提供服务时，其将会被重新纳入备用节点集中。

3.3 多层反馈队列

在本文提出的数据调度策略中，引入了多层反馈队列机制，该机制可以根据数据片段弹性时间的大小，设置反馈队列的层次级别，进而估测合作节点服务能力，高效率的进行数据调度。根据合作节点反馈的数据片段的信息，动态更新反馈队列，本文的多层反馈队列如图3所示。

图3 多层反馈队列Fig.3 Multi-layer feedback queue

推队列(Pushing Queue):该队列存放的数据片段是推缓冲区中所缺少的数据片段，如果这些数据片段存放于其合作节点的缓冲区中，此时可以采用稀有片段优先的选择策略和拉模式获取队列中缺少的数据片段;如果这些数据片段在合作节点缓冲区中不存在，则采用随机策略和推模式获取该队列中缺少的数据片段。

拉队列(Pulling Queue):该队列存放拉缓冲区中缺少的数据片段，采用序号优先的数据片段选择策略以拉模式从合作节点中获得数据片段;

已发请求队列(Sent Queue):该队列存放使用拉模式请求的、但未到达的数据片段。

3.4 数据调度策略分析

基于前面内容所述，本文提出了基于节点带宽的自适应数据调度策略，经过分析，该策略具有以下三个优势:

(1)保证对等节点流媒体点播的流畅度。播放点增长到数据片段的序号的时间间隔为数据片度的弹性时间，本文提出的策略可以在每个数据片段的弹性时间内，将所需数据片段放入缓冲区内，弹性时间较低的数据片段采用拉模式，直接从视频源服务器获取或者优先从有较强服务能力的合作节点处获取。

(2)提高带宽利用率。本文提出的策略能够准确的评估合作节点服务能力，根据合作节点的处理能力、服务带宽等服务能力指标自适应调整视频获取节点，避免数据片段丢弃率上升，提高了节点带宽利用率。

(3)拉模式和推模式优势相连，降低系统延迟。在数据传输过程中，拉模式根据接收节点的需求，主动进行数据请求，调度到的数据具有很高的精确度，但产生了附加的延迟;推模式的结果很难预计，但是其延迟较低，因此，将二者的优势相互结合，在保证播放流畅度前提下，尽量降低系统传输延迟。基于节点带宽的自适应数据调度策略流程如表1所示:

表1 基于节点带宽的自适应数据调度策略流程Table 1 Based on the node bandwidth adaptive data scheduling strategy process

为了简化实验，本文将推队列和拉队列中需要调度的数据片段按照传输模式分为两种类型:

(1)在所有合作节点都不存在的数据片段，本文数据调度策略可以采用推模式获取;

(2)部分已知的合作节点拥有某数据片段，本文数据调度策略使用拉模式获取;

拉队列中的数据片段采用序号优先的策略，推队列中的数据调度策略采用最少优先策略，同时规定，拉队列中的数据片段的优先级高于推队列中的数据片段的优先级。

4 实验及其分析

4.1 实验环境及评比方法

本文采用实验环境是PeerSim模拟器。在该模拟器中，本文对P2P流媒体系统进行仿真，网络节点的动态特性实现方法是按照18%的比例增减覆盖网中合作节点数量，实验过程中保持覆盖网的拥有最多1200个合作节点即可，同时，本文将覆盖网划分为16个AS，流媒体直播的流速率1Mbps，其最小位速率256Kbps。

本文评比算法优劣的标准采用源端时延。因为节点数目对源端时延的具有重要的影响。源端时延是指用户执行点播操作，数据从源端传输到客户端，视频正常播放之时的客户需要等待的时间。由于数据片段的时延和丢失取决于数据调度算法，因此数据调度算法大大的影响流媒体的服务质量考核的一个重要指标——时延，节点的源端时延是考核数据调度算法的重要指标。

4.2 实验结果分析

为了比较自适应数据调度算法的效果，实验过程中，本文选择两个经典的数据调度算法Coolstreaming、Tree。其研究结果如图4所示。

图4 节点数目对源端时延造成的影响Fig.4 The number of nodes on the impact of source end delay

由图4可知，随着节点数目的增多，Coolstreaming和Tree算法导致系统时延大大增加，严重的阻碍了流媒体的扩展性。由于播放初始时，客户端需要从源服务器获得数据，初始启动时，数据调度时延几乎是相等的，但是，随着动态调整覆盖网中的节点数量，节点逐渐增加，因此，节点可以从其他邻居节点获得所缺少的数据片段，此时，自适应算法就可以使用多层反馈队列动态调整数据调度，充分的考虑节点服务性能，降低流媒体系统的源端时延，直至趋于平缓，实验结果表明，基于节点带宽自适应数据调度算法能够降低系统的源端时延，优于Coolstreaming和Tree算法。

5 未来工作总结

本文详细的分析了现有数据调度策略，提出了基于节点带宽的自适应数据调度策略，实验表明该策略有效的降低了数据传输时延。该策略研究过程过中，发现未来工作的重点是寻找维护多层反馈队列和备用节点集的方法，以便更好的降低系统消耗。

［1］ Deshpande H，Hrishikesh and Bawa，Garcia Molina H.streaming live media over a P2P network［R］.In Work at CS – Stanford 2002

［2］ Tran D，Hua K，D.T.Zigzag.an efficient P2P scheme for media streaming［J］.Proc.of IEEE INFOCOM'03，2003，4-6

［3］ Suman Banerjee，Bobby Bhattacharjee，Christopher Kommareddy，etal.Scalable application layer multicast［J］，Proc.Of SIGCOMM'02，2002:205-220.

［4］ Lee，J.Y.B.，Leung，R.W.T.Study of a Server-less Architecture for VoD Applications［J］.Proc IEEE ICME，2002，8:233-236

［5］ N.Venkata Padmanabhan，Helen J.Wang，Philip A.Chou，etal.distributing streaming media content using cooperative networking［J］.Proc.Of ACM/IEEE NOSSDAV.2002，5:12-14

［6］ Deshpande H，Hrishikesh and Bawa，Garcia Molina H.Streaming Live Media over Peers［R］.Stanford University，2001

［7］ Salman A.Baset，Henning Schulzrinne.An analysis of the Skype P2P internet telephony protocol［J］.In Proc.of IEEE INFOCOM 2006，4

［8］ PPLive［DB］.2005，http://www.pplive.com

［9］ Xiaofei Liao，Hai Jin，Yunhao Liu，etal.Scalable Live Streaming Service Based Inter-Overlay Optimization［J］.IEEE Transactions on Parallel and Distribute Systems，2007，18(12):1663-1674

［10］ QQlive［DB］.2009，http://live.qq.com

［11］ Bo Liu，Yansheng Lu，Yi Cui，etal.A measurement study on AS-aware P2P streaming strategies［C］.Proc.of 3rd ICCN.China.2008:564568.

［12］ X.Hei，Y.Liu，and K.W.Ross.IPTV over P2P streaming networks:the mesh-pull approach［J］.IEEE Communications Magazine，2008:8692.