CDN与P2P混合网络架构下一种基于系统稳定状态的流媒体调度策略＊

徐 广，唐瑞春，宋佑举

（中国海洋大学信息科学与工程学院，山东青岛266100）

CDN与P2P混合网络架构下一种基于系统稳定状态的流媒体调度策略＊

徐 广，唐瑞春，宋佑举

（中国海洋大学信息科学与工程学院，山东青岛266100）

针对大规模流媒体系统的稳定性问题，提出在CDN与P2P混合网络架构下的1种基于预防和恢复机制的流媒体调度策略SSBS（scheduling strategy based stability）。首先利用基于可靠度模型的调度算法预防系统不稳定状态，其次通过系统稳定模型检测系统不稳定状态，采用分级恢复机制使系统快速恢复到稳定状态。实验结果表明该方法能有效控制CDN与P2P混合架构下大规模流媒体系统的稳定性。

CDN；P2P；系统稳定状态；流媒体

流媒体有着重要的应用背景，但是流媒体传输需要大量的带宽和服务器资源，如何为大规模的用户提供及时、稳定可靠的服务是衡量流媒体系统服务优劣的标志，如果单纯的提高硬件来提升流媒体系统提供服务的稳定性成本太大。更为科学的网络架构和调度策略才是解决问题的关键。

为了缓解流媒体的带宽占用高、持续时间长等特点对主干网络造成的压力，CDN（Content Delivery Network）［1］与P2P（peer to peer）［2］是目前2种主流的流媒体服务技术。CDN是把流媒体服务器布置在网络的边缘，采用重定向技术把用户的请求转向离用户最近的边缘服务器，CDN技术具有高可靠性的服务及可管理性的优点，但是CDN建设成本高并且可扩展性差。P2P技术充分利用了客户端的资源，能够在不增加成本的情况下满足用户激增的要求，但是P2P节点不易管理并且由于节点能力的限制不能像服务器一样提供稳定的服务。所以出现了CDN与P2P技术的融合［3－5，14－16］的设想与研究。但是到目前为止2种技术混合的思想还不够完善，还没有引起广泛的应用。

目前常见的流媒体调度算法可以分为2类，1类是是通过为用户选择数据块的最佳提供者［6－7，10－11］达到提高服务质量从而提升系统服务性能；另1类是通过提高用户请求命中率［8－9，12－13］来提高服务质量从而提高系统服务性能。综上所述，目前的流媒体调度算法是基于预防系统服务性能下降而提出的策略。

本文提出的CDN与P2P网络架构下的基于系统稳定状态的流媒体调度策略首先使用基于可靠度的数据调度算法为用户提供可靠的服务，预防由于可靠度不高得数据块提供节点中断服务造成的用户播放抖动，同时可预防由于大量用户请求失败导致的重复请求对服务器和带宽资源造成的压力而引发的服务性能不佳的现象。其次建立系统稳定状态模型检测系统的服务性能，如果系统的服务性能下降时，采用相应的调度策略进行恢复。实验结果证明了本策略的有效性。

1 相关工作

1.1 问题提出

由分时系统处理任务的特性可知当服务器处理的任务数多时的平均处理时间比任务数少时要长。当网络通信量大时，由于分组在网络节点进行处理时需要排队等候有可能出现缓冲区溢出丢包现象，因此当通信量大时的网络时延和丢包率比通信量小时要大。基于这个理论，系统在单位时间内处理的任务数及通信量越少用户体验越好。用户请求包括新的用户请求及请求失败用户重复请求2类。因此减少用户请求的方法有2种：一是拒绝请求服务，另一种是提高服务成功率减少重复请求的用户数量。

目前主流的调度策略有2种，1种流媒体调度算法［10－11］选择出最佳服务提供者可以预防接收节点产生的播放抖动现象，同时减少了重复请求给服务器和网络带来的压力；另1种流媒体调度算法［12－13］是预测节点将要请求的内容提前缓存减少用户的时延，提高系统的服务性能。因此目前的调度策略都是基于预防机制，但当系统服务性能下降时如果继续使用这种预防机制的调度策略不能遏制系统的服务性能下降的状态，所以本文提出了1种基于预防与检测恢复机制的调度策略，首先根据可靠度模型选出最佳数据块的提供者提高成功率，预防重复请求给系统带来的压力。同时根据系统稳定模型判断系统的服务质量等级，如果系统服务质量极差时使用恢复机制恢复系统的服务质量。

1.2 环境描述

目前CDN与P2P融合主要有2种方式［14－16］：1）将CDN的Cache设备以P2P的方式组织，实现CDN Cache设备之间的内容交换，提升CDN的内容分发能力。2）以CDN为可靠的内容核心，以P2P为服务边缘的架构，在CDN的管理机制和基本服务能力基础上引入P2P网络。可以在不增加成本的同时有效提升CDN服务能力，轻松应对突发用户的访问，更有效地避免了P2P应用的诸多弊端。为了更有效的应对大量用户的请求，本文提到的CDN与P2P的流媒体点播系统采用的第2种方案，见图1。

图1 CDN与P2P混合网络架构结构图Fig.1 The structure over CDN and P2Pnetwork

工作环境主要由服务器、服务节点、请求节点3类节点组成。请求节点指正在请求媒体内容的节点；当请求节点请求得到媒体内容后既是请求节点也是服务节点。

调度策略工作的环境采用CDN与P2P结合的方式完成媒体内容的分发，服务器的服务方式分为3个阶段［9］：1）初始化阶段即CDN服务器提供服务阶段2）当节点数目达到某一数量时系统进入CDN－P2P混合提供服务阶段即提供服务的节点由服务器和用户节点组成3）当节点数目增加到某一数量时系统进入P2P服务阶段即提供服务的节点全部由用户节点组成。

2 基于系统稳定状态的调度算法

本文提出的CDN与P2P混合网络架构下1种基于系统稳定状态的流媒体调度策略是1种基于预防与检测恢复机制的调度策略。本文的预防机制是当系统处于CDN－P2P服务模式及P2P服务模式时通过选择服务可靠度高的节点提高系统的服务质量进而提升系统服务性能。检测机制通过建立系统稳定状态等级模型评价系统的稳定状态等级。恢复机制是当检测到系统处于不稳定状态时采取的1种促使系统尽快恢复稳定状态的策略。

2.1 基于可靠度的数据调度算法

可靠度为节点提供稳定高效服务的能力。稳定性指节点在提供服务的时间内不会中断服务，评价时综合考虑节点在线时间、节点拖动次数等指标。高效性指节点在单位时间内提供更多服务的能力，评价时考虑节点上行带宽因素。服务器对节点的RD评定值的计算方法如下。节点为其他节点提供服务时的带宽、节点在线时长、拖动次数，查找数值表转换成对应的分值：Band、Time、Jump然后计算加权和

基于RD的数据调度算法如下。

1）While（Request＿List中有请求内容）

找出所有拥有此节点请求资源的节点k；

为每个节点k计算出

t［k，j］＝deadline［j］－currenttime；

（注释：t［k，j］：限定的节点k为节点j提供服务的时间）

if （拥有资源的节点只有1个）

把节点k存入集合supplier［j］中；

把节点j请求的资源放入rare＿set集合中；

把请求队列Request＿List中出j外的所有节点i做如下操作：

t［k，i］＝deadline［i］－currenttime－partblocksize／bandwidth［k］；

else

拥有资源的节点k如果t［k，i］＞partblocksize／bandwidth［k］则把节点k存入集合supplier［j］中；

2）while（i＜请求节点的个数）

把supplier［i］集合中的节点按照Rd值进行排序，选出最优的数据块

2.2 系统稳定状态

由于服务器的处理能力和网络带宽的限制，大量节点请求服务器与少量节点请求服务时，可利用资源多少不同，系统对节点的响应速度是有差异的。为了避免大量节点请求时由于占用资源过多导致系统响应速度慢及节点响应延迟大的问题，需要对系统稳定状态做出评价，服务器的稳定状态包含了服务器的性能和网络性能。评价时综合考虑服务器中央处理器利用率、服务器出口带宽占用率、抖动率及点播时延等指标。前2项指标反映了服务器的资源占用情况，后2项反映了网络的资源占用情况，系统稳定状态等级评定值具体计算方法如下。

服务器中央处理器利用率、服务器出口带宽占用率、抖动率及点播时延率，分别计算出相应的数值，cpu、sband、jitter、delay然后计算加权和。

2.3 基于分级的恢复机制

分级恢复机制把两方面内容分级：一是把用户请求分级，另一个是把流媒体文件分级。用户请求分级是把用户的请求分为高优先级与低优先级2种，优先级高低划分的标准是最短剩余时间优先策略（shortest remaining time，SRT），SRT策略总是把请求节点期望收到数据剩余时间最短的请求定义为高优先级。流媒体文件分级是根据清晰度把同一种流媒体分为不同质量等级G1、G2、G3……Gn。分表代表媒体的质量如高清、标清、普清等。

分级恢复策略的恢复机制是如果系统的稳定等级最低并且用户请求为低优先级则拒绝服务，拒绝服务可以有效的缓解服务器的压力，减轻网络负担。否则根据稳定等级确定传输流媒体的质量等级，不同质量等级的文件的大小不同，传输时占用的网络资源不同，低稳定状态的系统传输占用网络资源小的文件可以缓解系统的压力。此恢复机制能够在提供一定服务质量的同时最大可能的减轻系统的负载使系统恢复到稳定状态，从而为用户提供更高效的服务。

2.4 基于系统稳定状态的调度算法

输入：

Request＿L：用户请求信息队列

stability：系统稳定状态值，值越小系统越稳定，初始值为0

priority：用户请求优先级

high＿p：高优先级请求

low＿p：低优先级请求

S1、S2：2个0～1之间的常量值且S1＞S2，当稳定值大于S1时系统处于不稳定状态，当系统在2个值之间时系统处于次稳定状态，当系统稳定值小于S2时系统处于稳定状态

refuse：是否拒绝用户请求，值为yes时表示响应请求，为no时表示拒绝请求

inform：返回给用户的信息：能为用户提供可靠服务的节点信息

算法：

While（Request＿L不为空）

｛Step1：获取系统稳定状态值：

refuse＝yes

stability＝getStability（）；

Step2：根据稳定值确定是否为用户提供服务及传输文件等级

if（stability＞S1）

if（priority＝＝high＿p）

file＿level＝G1

end if

if（priority＝＝low＿p）

refuse＝no

end if

end if

if（stability＞S2并且stability＜S1）

file＿level＝G2

end if

if（stability＜S2）

file＿level＝G3

end if

Step3：根据用户请求信息选择合适的服务节点

if（refuse＝yes）

执行基于RD的数据调度过程并且把选择出的最优节点信息写入inform

end if

if（refuse＝no）

inform赋值为空

end if

Step4：把inform及file＿level传送给请求用户｝

3 实验结果与分析

3.1 实验数据设置

本文利用相对比较法确定公式中的权重，按照三级比例标度两两比较评分，其分值设为xij，则三级比例标度的含义如下：

评分值构成矩阵X＝（xij）n×n。因素i的权重系数为：

3.2 实验结果

把本算法SSBS和不是基于系统稳定性调度算法NONBSSA及P2P环境下的SVCP2PSA算法的节点连接成功率、抖动率和吞吐量等指标进行比较。

图2 不同请求率下的连接成功率Fig.2 The Link utilization under different request rate

图2可以看出当在80之前时SSBS和NONBSSA的连接成功率率相差不大，而SVCP2PSA比NONBSSA的成功率低因为P2P开始工作时节点少，当在第2、3阶段时，NONBSSA和SVCP2PSA的连接成功率比SSBS的低，因为基于稳定性调度算法在分配时根据系统的资源占用率即系统稳定状态进行调度，当资源占用率稍高时调度算法改变了传输策略并且筛选任务降低系统资源利用率，所以SSBS比其余2种算法的连接成功率高。

图3 不同请求率下的抖动率Fig.3 Jitter rate under different request rate

在图3中，SVCP2PSA的抖动率明显比其余2个算法的抖动率高，因为此算法是纯P2P环境没有服务器的参与，节点的服务能力不能和专门服务器比较所以抖动率自然就高。系统工作的第1阶段2种算法的抖动率没有明显的区别，当系统进入第2阶段时，普通调度算法的抖动率稍微比基于稳定性调度算法的抖动率高，因为用户数量的增多增加了服务器的负载，检测预防机制及时调整降低了服务器的负载减少了服务器处于高负载状态的时间，所以基于稳定性算法的抖动率小。当系统进入第3阶段时，普通调度算法的抖动率和基于稳定性调度算法的抖动率有明显的差别，因为第3阶段是P2P工作阶段，P2P的无序网络流量使得网络状况变得负载沉重，所以普通调度算法的抖动率大，而基于稳定调度算法已经改变了传输策略，适当的降低了网络的负载所以抖动率小。

图4 不同请求率下的系统吞吐量Fig.4 system throughput underdifferent request rate

图4看出3种算法的系统吞吐量都随着节点请求率的增加而增加，但是前2个阶段NONBSSA算法和SSBS算法的系统吞吐量始终比SVCP2PSA的系统吞吐量大，因为有服务器参与服务，服务器的服务质量比节点提供服务的稳定性好。第2阶段SSBS算法比NONBSSA算法和SVCP2PSA算法的系统吞吐量大而NONBSSA算法和SVCP2PSA算法的系统吞吐量差不多，因为在第3阶段3种方法都是P2P方式提供服务，但是SSBS算法采用了恢复机制的调度方案，提高了系统的稳定性从而增加了系统的吞吐量。

4 结语

基于CDN与P2P的网络流媒体分发方式可以增强流媒体业务的扩展性，相比传统的P2P技术又能够提供一定程度的服务质量保证。基于这种网络架构，本文提出了1种基于系统稳定状态的流媒体调度算法，建立了系统稳定状态等级的评价模型，把流媒体文件分为不同质量等级，根据不同的系统稳定状态等级选择不同的传输策略；建立了基于用户行为（在线时间、拖动次数）的节点可靠度评价模型，算法选择当前符合条件的可靠度最高的节点作为服务节点。最后对这种方案进行仿真，仿真证明本方案能够在保证一定程度服务质量的的同时提高系统的稳定性。

［1］ Pallis G，Vakali A.Insight and perspectives for content delivery networks［J］.Communications of ACM，2006，49（1）：101－106.

［2］ Lan X，Zheng N，Xue J，et al.A peer－to－peer architecture for efficient live scalable media streaming on internet［C］.New York：Proceedings of the 15th International Conference on Multimedia，2007：783－786.

［3］ Liu Xuening，Yin Hao，Lin Chuang，et al.A Novel and highquality measurement study of commercial CDN－P2Plive streaming［J］.Communications and Mobile Computing，2009，6（1）：325－329.

［4］ Yin Hao，Lin Chuang，Zhang Qian，et al.TrustStream：A Secure and scalable architecture for large－scale internet media streaming［J］.Circuits and Systems for Video Technology，2008，18（12）：1692－1702.

［5］ Xu D，SSKulkarni，C Rosenberg，et al.Analysis of a CDN P2P hybrid architecture for cost－effective streaming media distribution［J］.Multimedia Systems，2006，11（4）：383－399.

［6］ Zhang X，Liu J，Li B，et al.Coolstreaming／DONet：A data－driven overlay network for peer－to－peer live media streaming［C］.USA：Proceedings of IEEE INFOCOM，Miami，2005：2012－2111.

［7］ Vikash Agarwal，Reza Rejaie.Adaptive multi－source streaming in heterogeneous peer－to－peer networks［C］.San Jose：Proceeding of Multimedia Computing and NetWorking，2005：151－160.

［8］ 杨戈，樊秀梅.基于CDN的流媒体动态调度算法［J］.通信学报，2009（2）：42－46.

［9］ 郑常熠，佘宇东，王新，等.CDN与P2P混合网络架构下基于用户行为的VoD分发策略［C］.∥2007年通信理论与技术新发展，北京：电子工业出版社，2007：2027－2032.

［10］ 吴艾，刘心松，李凡，等.提供可靠服务的P2P流媒体点播系统［J］.电子与信息学报，2009，31（10）：2294－2298.

［11］ 唐瑞春，刘斌，徐仕儒.分层P2P系统中基于簇缓存的节点选择策略［J］.中国海洋大学学报：自然科学版，2010，40（1）：104－108.

［12］ Tang Rui－chun，Wei Qing－lei，Liu Bin.A proxy－caching prefix assignment algorithm based on P2Pcooperation in the media streaming system［C］.Wuhan：2009International Conference on Multimedia Information Networking and Security，2009：658－662.

［13］ 唐瑞春，魏青磊，刘斌.一种基于P2P协作的代理缓存流媒体调度算法［J］.电子与信息学报，2009，31（11）：2757－2761.

［14］ Shi Kang，Hao Yin.LiveSky：Enhancing CDN with P2P［J］.ACM Transactions on Multimedia Computing，Communications，and Applications，2010，6（3）：1－19.

［15］ Yin Hao，Liu Xuening，Zhan Tongyu，et al.A hybrid CDN－P2P system for video－on－demand［C］.Hainan：Proceedings of the 2010Second International Conference on Future Networks，2010：309－313.

［16］ Yin Hao，Liu Xuening，Zhan Tongyu，et al.Design and deployment of a hybrid CDN－P2Psystem for live video streaming：experiences with LiveSky［C］.Beijing：International Multimedia Conference，2009：25－34.

A Stability Based Streaming Media Scheme over CDN and P2P Hybrid Network

XU Guang，TANG Rui－Chun，SONG You－Ju
（College of Information Science and Engeering，Ocean University of China，Qingdao 266100，China）

This paper presents a streaming media schedule scheme based on preventing and detecting recovery mechanism over CDN and P2Phybrid network，in order to solve the stability problem of the largescale streaming media VOD system.First and foremost，It use data scheduling algorithm of reliability model to prevent systems instability，then it uses the system stability model to detect the system stability and take advantage of the hierarchical recovery mechanism to enable the system quickly recover to stable state.The simulation result shows that this mechanism can effectively control system stability of largescale media system in CDN and P2Pmixing network architechture.

CDN；P2P；system stability；streaming media

TP393

A

1672－5174（2012）1－2－163－06

数字家庭服务媒体设备集成技术研究项目（2011BAH16B03）资助

2011－01－17；

2011－06－20

徐 广（1986－），男，硕士生，研究方向：网络流媒体。E－mail：tangruichun＠ouc.edu.cn

责任编辑 陈呈超