基于CDN－P2P流媒体直播系统方案设计实现

邓 达，吕智慧

（复旦大学 计算机科学技术学院，上海200433）

0 引 言

多媒体内容在当今互联网中得到大量发展，流媒体已成为目前因特网应用的最快增长点。流媒体的特点是数据量大、传输持续时间长，并且由于其直观性较强，对延迟、抖动、丢包率、带宽等QoS（quality of service）指标要求也就非常严格，在当前的因特网上构建大规模的性价比高的流媒体系统是一个具有挑战性的工作，并具有一定的商业意义。

如何缓解网络拥塞，提高用户获取信息的速度，成为困扰企业和服务商的一大难题。目前，互联网上的内容分发传递主流技术有CDN和P2P。这两种技术各有各的优势，也有着一些不足。CDN技术成本价高，而且实现复杂，扩展能力相应较弱。P2P则由于客户节点加入离开的动态不确定性，导致在网络友好性、可靠性和管理性上有较大欠缺。

CDN和P2P技术尽管有着各自的不足，但两者基本上是可以互补的。融合这两种技术，构建一个统一的内容分发系统方案，将会对大型流媒体直播、高清电视、巨型文件下载等高带宽需求业务的进一步普及提供广阔的发展空间。通过P2P扩展CDN的容量，同时CDN可以克服P2P的动态性、引导P2P内容分发实现对ISP、主干网的友好性，形成一种更加完善的内容分发应用模式。

1 相关研究

有研究者早在2006年就提出了融合CDN和P2P的技术方案［1］。其提出在CDN基础上叠加P2P来扩展分发能力，并深入分析了CDN和P2P融合的成本，采用了不同的客户端贡献策略进行对比，最终通过模拟实验来证明融合的有效性。其思想更多的是如何在CDN边缘服务器上利用P2P技术传输流媒体文件，以更好的降低CDN中心资源服务器的压力。

2007年以来，SIGCOMM、ACM MM、INFOCOM等著名国际会议陆续出现了多篇研究P2P内容分发的论文。大多数论文重点关注如何更好的提供P2P大规模分发的能力的同时，保持较低的延迟和较高的稳定性。其中也有少部分论文研究的是P2P内容分发对网络友好性影响。文献［2］首次大规模的部署了结合P2P和CDN技术的LiveSky，对结合技术的树形结构进行了理论推导，得出扩展因子的统计理论公式，另外还测得了详细的实验数据。

2 系统架构

CDN－P2P混合架构总体来说可以分为3种结构。其一是CDN边缘服务器之间使用P2P结构。其二是CDN各边缘服务器与其服务的peer节点组成一个自治区域，各自治区域的peer节点采用P2P架构。其三是前述两种结构的综合［2］。

本文主要采用第二种结构，在CDN各边缘服务器的P2P网络结构采用mesh和tree的混合P2P结构。采用一层的tree结构，用于保证网络的可控性和节点的异构性；接下来的网络用纯mesh结构组织，如图1所示。

图1 系统拓扑结构

放大层就是一层树结构的节点，其中每一个节点称为伪CDN节点。它们必须满足上载带宽高于媒体码率，只有这样才能起到放大CDN带宽的效果。另外，它们直接向CDN边缘服务器拉数据，服务邻居除了CDN服务器之外，没有更多的；而且他们直接互不成邻居。其余的Peer组织成mesh结构，维护各自的邻居列表。注意，CDN不是它们的直接邻居，它们并不直接向CDN发起块请求（除了特殊情况，比如刚启动或者请求紧急数据块的情况）。

3 CDN－P2P混合分发方案详细设计

本文在此详细讨论了peer节点加入后，各节点和CDN服务器所运行的算法。

3.1 节点加入算法

放大层的基本想法就是对CDN的上载能力进行放大，因此，在放大层中的伪CDN节点的上传带宽必须大于码流速率，否则就起不到放大作用。不过，在放大层初始建立，如果加入节点的能力比较弱，没有任何节点的上载速率超过码流播放速率，这样很有可能导致一开始加入的节点不能得到任何数据（因为非伪CDN节点不能向CDN直接请求非紧急的数据块）。为了避免上述情况的发生，并且由于在节点加入CDN网络之后，我们仍然会运行伪CDN置换算法，因此在节点加入过程中，我们放弃检验其上载带宽是否会高于码流速率这一限制。

3.1.1 放大层的初始建立

起初，CDN节点设置放大层节点个数为N，这一数据是根据CDN的带宽和码流速率而确定的。每当节点加入，且当前CDN的伪CDN节点数＜N，那么就将新加入的节点设为伪CDN节点，与CDN直接成为邻居，并且给他分配其余相应的邻居。由于伪CDN节点直接向CDN节点请求数据，因此其作为邻居的作用更多的是向其邻居节点传送数据，没有必要与同为放大层的任何伪CDN节点成为邻居。

3.1.2 伪CDN节点更换算法

随着节点的陆续加入，更多更强的节点会进入CDN的网络。原先在放大层中的伪CDN节点会变得不是网络中最强的节点，因此，更换算法势在必行。更换算法的执行是以时间驱动的，即各个伪CDN节点每隔一段时间会运行一次，用来寻找更强的节点。这里的强并不仅仅是指上载带宽的强，而是多方面的综合，可以包括网络情况，节点本身性能情况，节点的地理位置，节点存在网络中的时间等众多因素。

本系统中，我们考虑两点：节点的上载带宽和稳定性。假设某节目时长为L，当前时间为t，节点在网络中已经经过时间为s，那么稳定性计算公式SI为［3］

假设节点上载带宽为U b／s，码流速率为R b／s，那么计算其强弱的指标P为

式中：K——调整带宽和稳定性之间强弱的参数。可以看出，这一公式是为了使得节点的上载带宽和在网络中存在的时间融合成一个强度的值，用来表示节点的强弱。

具体的节点更换算法是：对于每一个伪CDN节点a，其遍历自己的邻居，如果发现邻居里面最强的节点b比自己更强，那么就让b替换自己伪CDN节点的地位，主动与CDN断开连接，而b则与CDN成为邻居。注意到，如果b不仅与伪CDN节点a是邻居，而是与另一些伪CDN节点也为邻居，那么将b置换为伪CDN节点的同时，会破坏放大层所满足的基本条件：伪CDN节点之间不能是邻居！因此，在对换之后，我们必须再次遍历b，将其与可能的伪CDN邻居关系解除。

3.1.3 伪CDN状态监控

此算法也是以时间间隔运行的。其目的是向CDN节点上传特定的数据包，以上报自己当前的状态。包括已用上传带宽，剩余上传带宽等。这样CDN节点就会对其下的伪CDN节点的状态有相应的估计，对于将来节点加入时，给与其缓冲的节点可以更好的计算。当然，为了保证所有的伪CDN节点之间互不成为邻居，我们在这里也让节点自己查找自己所有的邻居，如果有邻居是伪CDN节点，那么就断开邻居关系。

3.1.4 伪CDN节点的离开

伪CDN节点的离开，就是从其已有的邻居里面，选择最强的邻居替换自己，即，再次执行更换算法。这样，即使一个强节点离开了，也会用相应的比较强的节点来替换自己，就不会对网络产生非常大的影响了。这种方法也很好的保证了网络的稳定性。

3.2 节点加入缓冲算法

当某个节点加入直播网络，CDN节点根据自己，放大层伪CDN节点和当前加入节点的状况估算出节点的最快可能播放时间，然后进行缓冲。

具体地讲，如果当前节点加入后，直接从当前时刻开始进行缓冲，假设进过t之后缓冲完成，那么播放至少要等t之后才开始，也就是说，当前加入节点至少已经有了t秒的时延。如果可以从加入时刻开始，直接缓冲t后的数据，就可以大幅减少延迟的发生。在此，问题的难点在于，精确地估算出缓冲完成所需要的时间非常难。但，如果结合CDN的稳定性，实际上可以对缓冲时间有粗略估计。

根据当前CDN和伪CDN的带宽情况，选择适当的节点，以速率v，直接推送给加入节点buffer长度为α的数据。这样，至少需要t＝α·len（buffer）／v的时间才可以缓冲完。在此同时，我们通过P2P方式，让当前节点向其邻居节点拉数据来填充其后1－α的buffer（如果是伪CDN节点的缓冲，直接向CDN所要数据块）。

我们假定估算缓冲时间为t。显然，t之后，buffer的前α已经完成了，后1－α是经过P2P方法来获取的，所以并不能保证。但是，后1－α部分并不一定需要完全填满。引入另一个系数β，如果后1－α的buffer有β已经填满，那么就直接开始播放。否则会再等待一段时间进行缓冲，然后再播放。具体流程图如图2所示。

3.3 块调度算法

图2 节点加入缓冲算法

块调度算法就是对于某一个节点，向其邻居节点或者CDN节点提出哪些数据块的申请，并且以什么样的结构进行交换的算法。块的结构是用BufferMap的思路，把缓冲区分成多块，最基本的请求单位就是块，并且请求的结构是一个队列，越靠前的请求块，其优先级越高。在带宽有限的情况下，队列后部的请求块可能会延时或者会被放弃传送。本系统中，块调度算法分为两个阶段，第一个阶段是缓冲阶段，使用随机调度算法结合之前提到的缓冲算法，第二阶段是缓冲完成后的块调度算法。

第一部分缓冲时的块调度算法直接采用随机算法，即，对于给定的邻居列表，从有本节点所需要的块的邻居中随机选取一个，发起块请求。采用随机算法的原因是节点刚刚加入网络，对网络中其它节点信息获知量很少，而且，这一过程仅仅在节点刚进入网络进行缓冲中使用，因此不适合，也不必要复杂的算法。

第二部分的块调度算法，采用邻居评分和划分块优先级的方法来调度［4］。

对于缓冲区，我们划分为4个部分，分别占有1／8，1／8，1／2，1／4，叫做紧急区1，紧急区2，普通区和稀缺块区。各个区域的块的优先级从高到低依次为紧急区1，紧急区2，稀缺块区和普通区。其中只有当紧急区1的数据块还未填满的时候，节点可以向CDN直接索要紧急数据块。对于其余部分的块，只能向邻居发起请求。

对于节点评分机制，是用来评估各个邻居对于本节点的传输性能，以此区别各个邻居的贡献能力。最终向各个邻居请求的块的队列会基于各个邻居的评分的基础之上，分数越高的邻居，向其请求的数据块就会越多，而且越有可能是紧急区2的数据块。

3.4 CDN服务器的加入控制算法

3.4.1 节点加入条件

即使是CDN－P2P混合分发系统，为了保证直播系统的质量等要求，我们也不能任意的加入无数的节点。弱节点超过一定的限度，整个网络资源就会相当贫乏。可以想象，如果加入的节点的上载带宽小于码流带宽，那么加入越多的节点，整个网络的带宽资源就会越多的消耗，直到无法再提供最低限度的服务。因此，我们必须设置准入条件，以确保直播系统的稳定和质量保证。

在本系统中，我们可以得到的保证的上载带宽有CDN节点和放大层中的各个位CDN节点。因此，我们基于这些参数给出节点加入的限制条件。

先考虑CDN上载带宽U，CDN的带宽分为3部分，一部分用于给各个伪CDN提供最原始的视频数据U1，另一部分提供各个节点的紧急请求数据包U2，还有一部分是提供新加入节点的缓冲U3。而伪CDN节点，带宽V，基本就是给各个邻居提供的上载带宽V1，或者提供一些加入节点的缓冲数据V2。假设码流速率为R，那么准入条件为U＋∑V≥U1＋U2×α＋∑V1＋（U3＋∑V2）×β＋R式中：α、β——一定的参数，一般比1稍大，用来估计紧急请求和缓冲带宽在节点加后的上界。如果当前CDN网络满足上述条件，那么允许新节点加入，否则，可以将需要加入的节点引渡到其它CDN边缘服务器。

3.4.2 节点加入算法

随机算法，每当有节点加入，则直接对其运行节点加入算法：首先判断是否满足准入条件，是否可为伪CDN节点，分配给其缓冲的节点，给其分配邻居，等等。如果在某一时间，有非常多的节点迅速的加入网络，形成flash crowd的情况，那么，CDN包括伪CDN节点很有可能会面临巨大的压力，以至于它们无法给每个加入的节点进行缓冲和数据交换，这样就会对整个网络有很大的影响。

为了适当的减少上述问题的危害性，我们在系统中做了适当的改进。我们并不是每次对加入的节点都进行逐一处理，我们加入一个节点加入队列。也就是说，当节点需要加入网络时，我们先将其进入加入队列中，然后每隔特定的时间t（实验中为0.1s）或者队列满了的时候，让CDN对整个队列进行处理。

处理的方式是将他们组织成小型树状结构［5］，根据他们的上传带宽进行从大到小排列。然后从队列的两头进行配对。从队列头中取出上传带宽最大的节点a，算出其速率是码流的K倍，接着相应的从队列的尾部取出K个节点，让a和这K个节点组成一棵树，a给其下的K个节点进行缓冲，而CDN则分配给a进行缓冲。这样，CDN网络相当于只用了一道缓冲码流，就直接服务了K＋1个节点。继续这样的操作，直到队列为空为止。

4 实验设计及结果分析

根据本实验的参数设置，如果不用P2P，而使用纯CDN结构，实验节点是不能全部得到服务的。因此，我们仅将基于中心结构的P2P随机算法系统与本论文的系统进行对比试验。

Zhang Meng的p2pstrmsim是一个基于消息的C＋＋实现的P2P模拟程序，其中模拟了节点的地理信息，加入方式，各个节点的传输带宽等基本信息，也监控了包括节点启动时延，播放时延，播放质量等关键指标。本实验采用p2pstrmsim程序为基础，并且在处理节点消息队列中，加入我们特定的算法进行模拟。

算法3.1.2、3.1.3以及3.3都是基于时间的算法，每隔一个固定的时间执行。其余算法是基于事件的，例如节点加入，节点离开或触发相应的算法执行。实验的基本参数如下：

Peer节点分为3种不同的节点：上传带宽：512kb／s，384kb／s，128kb／s，下载带宽为1000kb／s，512kb／s，384 kb／s比例为0.1，0.5和0.4。每个peer默认最多有15个邻居。仿真时间为600s，码流大小为300kb／s，缓冲区长度为20s。每隔一秒交换一次buffermap。

4.1 验证加入缓冲算法效果

本实验重点对比两种算法在缓冲时间上的区别，体现出修改后的算法的优越性。实验使用2个CDN服务器，带宽为40M，放大层节点个数为90个。500个节点模拟。节点采用节匀速加入退出策略，在前80%的时间匀速加入，后50%的时间有20%的节点匀速离开。可以计算，放大比例为

图3是缓冲时间的累积分布图（cdf图）。纵坐标是节点的比例，横坐标是缓冲的时间。原先的随机算法，在缓冲时，由于直接采用固定20s的时间进行缓冲，因此，所有的启动延迟都是20s。而从此图可以看出，改进算法的节点缓冲平均时间为16s左右。可见，改进算法确实有一定的效果。

图3 启动延迟对比

图4，显示了两种算法的质量参数（质量度用已经播放的数据块除以应该播放的数据块来表示）。对比两种曲线可以看出，两种算法的质量参数几乎相等，不过在放大层建立的初期，质量都有部分下降。并且改进算法的下降比随机算法提前，从这点也可以看出，改进算法减少缓冲时间的效果是在保证播放质量的前提下实现的。

图4 质量对比图1

关于在放大层建立的初期会导致质量的下降，这是由于我们的算法导致的。设想，我们节点的缓冲算法除了CDN会推给节点一部分数据，另一部分是需要节点向Peer之间互传获取的。而一开始，节点十分少，互传几乎得不到数据，因此会致使节点再次等待缓冲。一旦缓冲结束，由于节点稀少，启动的节点只能向CDN请求紧急数据包，这会大大加重CDN的负载，因此导致质量下降。

4.2 验证flash crowd情况下的效果

此实验重点对比两种算法在flash crowd情况下的区别，体现出修改后的算法的优越性。本实验使用3个CDN服务器，带宽为50M，放大层节点个数为90个。1000个节点模拟。节点一开始速加入100个节点。在0.4＊MAX＿SIM＿DURATION（大约240s）时刻，在0.05＊MAX＿SIM＿DURATION（大约30s）的持续时间内将所有的剩余节点加入。最后匀速有20%节点退出。

图5是在线节点数与时间的关系图。节点在240s到280s之间，从103个节点直接增加至1000个节点，从而测试在flash crowd情况下，系统的具体反映情况。

图5 在线节点数目

图6，显示了两种算法的质量参数。在放大层的建立之初，改进算法和随机算法的质量差不多。在加入节点出现flash crowd时，改进算法比之随机算法有更好的质量度。

除了初始的放大层建立初期质量的下降外，质量曲线显示，共有两处下降。第一处在240s过后一点。这里的下降是因为此时正好处于flash crowd的情况，大量节点加入网络导致整体质量的下降。注意，改进算法质量的下降要比原始算法小，并且有些许提前。考虑我们的缓冲算法，比完全没有缓冲会有较好的启动延时，因此对于flash crowd的反应也会相应较早

图6 质量对比图2

第二处的质量下降大约出现在430s多。此时显示整个网络已经趋于稳定。在大量节点进入播放阶段，会对网络造成一定的影响，播放的质量会有所下降，此处并没有过多节点的加入和离开，质量仍然不断下降到达最低谷。通过实验分析，在240s时，大量节点急促加入的过程中，整个系统会因为所需要的缓冲流量过多而无法支持所有节点的充分缓冲，某些节点在等待缓冲时，并没有真正的缓冲完成而被迫播放。这些节点往往会在播放了一段时间后，因为缓冲区不满而停下继续缓冲，产生不稳定性，最终导致了质量度的下降。这就是在430s后质量到达最低谷的原因。不过，即使如此，改进算法在flash crowd情况下，也比随机算法有更好的质量保证。

5 结束语

本文将CDN与P2P技术相结合，应用于流媒体视频直播系统。采用二层树形结构与mesh结构相混合的P2P架构，详细介绍了伪CDN节点的选取规则以及维护方式。本文针对直播的特殊性，利用估测缓冲完成时间来提高启动播放时延，并且针对瞬时拥塞，给出了小树结构的节点加入缓冲算法，减小P2P的动态性带来的影响，使整个系统更加稳定。最后通过仿真模拟实验，将系统改进算法与不使用本文所提算法进行对比，验证算法的有效性。

［1］Xu Dongyan，Sunil Suresh Kulkarni，Catherine Rosenberg，et al.Analysis of a CDN－P2Phybrid architecture for cost－effective streaming media distribution［J］.Computer Science Multimedia Systems，2006，11（4）：383－399.DOI：10.1007／s00530－006－0015－3.

［2］Hao Yin.Design and deployment of a hybrid CDN－P2Psystem for live video streaming：experiences with LiveSky［C］／／Beijing，China：Proc of the 17th ACM International Conference on Multimedia，2009：19－24.

［3］Wang Feng，Liu Jiangchuan，Xiong Yongqiang.Stable peers：Existence，importance，and application in peer－to－peer live video streaming［C］／／Phoenix，AZ：Proc of INFOCOM，2008：1364－1372.

［4］HUANG Yi.The dynamic communication architecture design of live streaming system based on CDN－P2P［D］.Shanghai：Fudan University，2011（in Chinese）.［黄翼.面向流媒体直播的CDN和P2P动态交互传输架构的设计［D］.上海：复旦大学，2011.］

［5］HUANG Sijia.The design of a live streaming system based on CDN and tree based P2Phybrid architecture［D］.Shanghai：Fudan University，2011（in Chinese）.［黄思嘉.基于CDN和P2P树网混合的流媒体直播系统设计［D］.上海：复旦大学，2011.］

［6］LU Zhihui，WU Jie，Fu Weiming.Towards a novel web services standard－supported CDN－P2Ploosely－coupled hybrid and management model［C］／／FL：IEEE International Conference on Services Computing，2010：297－304.

［7］Cho S，Cho J，Shin S－J.Playback latency reduction for internet live video services in CDN－P2Phybrid architecture［C］／／Cape Town，South Africa：IEEE International Conference on Communications，2011：1－5.

［8］Jiang Hai，Li Jun，Li Zhongcheng，et al.Efficient large－scale content distribution with combination of CDN and P2Pnetworks［J］.International Journal of Hybrid Information Technology，2009，2（2）：13－22.

［9］Mansy A.Analysis of adaptive streaming for hybrid CDN／P2P live video systems［C］／／19th IEEE International of Network Protocols，2011：276－285.

［10］Thinh Nguyen Kim，Seil Jeon，Younghan Kim.A CDN－P2P hybrid architecture with content／location awareness for live streaming service networks［C］／／IEEE 15th International Symposium on Consumer Electronics，2011：438－441.