云辅助P2P-VoD系统中一种邻居选择算法

丛鑫，双锴，苏森，杨放春，孙鑫

（1.北京邮电大学 网络与交换技术国家重点实验室，北京 100876；2.辽宁工程技术大学 电子与信息工程学院，辽宁 葫芦岛 125105）

1 引言

近年来，视频点播(VoD, video-on-demand)服务已经成为网络上最流行的应用之一。传统的VoD系统使用内容分发网络(CDN, content delivery network)将视频数据发送给节点，但随着节点数目的增加，基础设施的投入是呈线性增长的。当前的VoD系统使用P2P(peer-to-peer)技术，利用节点相互交换视频数据，可以使VoD服务提供商以较小的开销服务较大数量的节点，但P2P-VoD系统中不可回避的问题是，服务器带宽开销很高但利用率很低。例如文献[1]指出，VoD服务提供商每月的开销中带宽支出占50%以上。在PPLive中[2]，一天之中超过50%的时间服务器带宽利用率都低于20%，而造成这种现象的原因是一天中各个时间段内节点请求视频的用户访问数量是不均衡的，在21:00点，视频请求数量达到最大，7:00达到最小。而随着基于内容的云平台的应用，为上述P2P-VoD架构下遇到的问题提供了一种可能的解决方案:在每天的请求高峰时段，由云平台充当视频服务器分担部分负载，利用云提供商和因特网服务提供商(ISP, Internet service providers)的价格差异，降低VoD服务提供商服务器带宽开销，提高带宽利用率。

通常情况下，VoD系统中，节点需要把下载到的视频数据存储在硬盘或内存(称为缓冲区)中来保证视频播放的平滑性。这种方法需要节点设备有一定大小的缓冲区，可以在播放点异步的节点间相互传播视频数据，但是如何在播放点异步的情况下有效地寻找到能提供所需视频数据的邻居节点是一个需要考虑的问题。文献[3]提出在大规模的P2P系统中，可以将视频数据缓存到缓冲区中而后共享给其他节点。文献[4]将具有相似到达时间的节点分成一组，在组内进行视频内容的交换。文献[5]允许节点随机加入一个或多个多播树，并且规定只能从父节点向子节点定向的传输视频数据。文献[6]设计了一种以下载进程和令牌为基础的节点数据交换过程，但未考虑到使用移动设备的用户参与系统的情况。另一个需要考虑的问题是节点缓冲区大小对视频共享的影响。节点间只能相互共享存在于缓冲区内的视频数据，当节点缓冲区足够大时，能全部存储已观看过的视频数据；反之，只能部分存储。文献[7]设计一种区分数据优先级的算法，节点下载的数据块按紧急程度分别来源于高优先数据集和保留数据集。文献[8]应用随机模型和启发式算法进行数据块的下载，但未考虑视频服务器提供数据的因素。文献[9]从文件片选择、邻居节点选择和副本管理方面评估了存在的算法在节点资源有限和充足情形下的性能，但未涉及基于缓冲区的算法。

在现实中，计算机节点有较大的缓冲区，可以存储全部观看过的视频，因此能够服务其播放点之前任何有数据请求的用户；同时也存在手机、PDA等节点，其拥有较小的缓冲区，可以存储部分观看过的视频数据，只能服务其播放点之前部分有数据请求的用户。本文的出发点在于当越来越多的小缓冲区节点加入到VoD系统时，如何设计视频数据块的下载策略才能保证节点所需数据块的高可用性(即数据块能以较高的概率下载)和提升节点的下载速率，从而降低VoD提供商的服务器带宽开销。

本文采用基于内容的云平台和P2P技术构建云辅助的 P2P-VoD架构。在此架构下设计了 NCS(neighbors and chunks selection)算法以辅助节点有效地共享视频数据。NCS算法包含节点选择子算法和块下载子算法。基于缓冲区的节点选择算法以下载点为基准使节点有效地查找到能够提供视频数据的邻居节点，基于缓冲区的块下载算法计算了 2种不同的块下载策略在此架构下所需要的最小缓冲区值，为视频块的下载方法提供理论依据。本文贡献如下。

1）详细研究小缓冲区节点对P2P-VoD系统的影响，设计基于缓冲区的节点选择算法，能够使节点以高概率选择到提供视频数据的邻居节点。

2）在云辅助P2P-VoD架构下，计算2种不同的块下载策略——最少优先和贪婪策略所需要的最小缓冲区的值，并以此为基础为不同缓冲区大小的节点选择合适的块下载方案以达到系统中视频数据块的高可用性提供理论依据。

3）建立云辅助P2P-VoD模拟器来评估NCS算法性能。实验表明，提出的算法能够降低服务器负载和请求的拒绝率，提升节点的下载速率。同时也研究了不同移动设备在系统中占据的比例不同时，服务器负载的变化情况。结果表明，随着小缓冲区节点的增加，服务器负载的增加程度较低。

2 云辅助P2P-VoD系统架构

如图1所示，云辅助P2P-VoD系统中主要由4个组成部分，分别是节点、视频提供商存储服务器和tracker服务器、云存储服务器和云分发服务器，各部分功能如下。

图1 云辅助P2P-VoD系统架构

节点:使用各种设备在系统中观看视频的用户。它们从视频提供商存储服务器，云分发服务器或其他节点处下载视频数据；同时也将缓冲区中的视频数据共享给其他节点。

视频提供商存储服务器:负责存储视频源和分发视频数据。当一天之中节点的请求处于空闲时段时，由其独立地提供服务。当服务器负载很重时，提前发送高流行度视频数据到云存储服务器中[10]。

视频提供商tracker服务器:负责记录节点到达的时间并依据下载点对节点进行排序；返回节点的邻居列表。

云存储服务器:归属于云提供商，例如Amazon。它负责接收来自视频提供商存储服务器发送的视频数据并将其转发到云分发服务器上。

云分发服务器:例如CloudFront[11]，使用整个云网络服务器，自动将视频内容发送到离请求节点最近的位于网络边缘的服务器上，如图1所示，节点c向云服务器请求数据时，云分发服务器先将数据调度到位于云网络边缘距离节点c较近的服务器a上，由服务器a应答。

在上述架构基础上，本文考虑如何通过节点间的有效合作来降低 VoD服务提供商的服务器带宽开销，同时直接降低云分发服务器的开销。

3 NCS算法

3.1 节点缓冲区模型

对于云辅助P2P-VoD系统中的节点，考虑3个特征:节点的播放点是异步的；节点必须提前下载当前播放点的数据；不同节点的缓冲区大小是不同的。为了描述基于缓冲区的邻居选择算法，首先引入一些定义来建模节点视频的缓冲区，如图2所示。

播放点Pi:节点i当前的播放点，是正在播放视频块的序号。

下载点bi:在播放点Pi之后的第一个未下载的块的序号。

平滑级ui:在播放点Pi之后还能持续播放的块的数量，等于bi−Pi。标识的是节点播放平滑性。

平滑播放阈值 δ:平滑播放所必须的块。平滑播放窗口值为[Pi, Pi+δ]。

缓冲区大小si:节点i 的存储视频数据的存储区大小。

图2中，为了保证播放的平滑性，节点a正在下载的块(bi+1)是急需的，而节点b正在下载的块在δ之后，对于节点b来说，当前下载的块是不急需的。节点b的贡献程度应该大于节点a，一方面是因为其从系统中获取了更多的视频数据(节点 b的播放点大于节点a)，需要更多的回报系统，另一方面此时上传视频数据到其他节点不会影响节点b的播放平滑性。

图2 节点缓冲区定义

3.2 基于缓冲区的节点选择算法

文献[6]证明了随机节点选择算法效率是很低的，同时也提出了基于缓冲区的节点数据交换过程，但其未考虑系统中存在小缓冲区节点时的情况。本文提出一种基于下载点的节点选择算法，即有相似下载点的节点为邻居进行视频数据共享，这些节点形成Overlay网络。相似的下载点保证请求的视频数据能够以较大的概率存在于被请求的节点缓冲区中。

云辅助P2P-VoD系统存在tracker服务器，在tracker服务器中存储记录节点的列表，可以记录节点的到达、离开时间及当前下载点的位置，为了避免形成Overlay网络时发生不匹配问题，tracker服务器依据已有的方法[12～14]将地理位置较近的节点放到同一张节点列表中。当新节点p加入系统时，它首先连接 tracker服务器并向其发送视频数据请求。tracker服务器返回包含下载点与p相似的一组节点的列表。p从列表中选择一组节点作为邻居节点，并与它们建立连接获得视频数据。需要注意的是:由于每个节点存在最大的连接数目，可能会拒绝p的连接请求，因此p需要发送其当前下载点和贡献等级到它的邻居节点。贡献等级定义为节点的上传能力，即它能给每个邻居节点上传数据的速率，较大的贡献等级会使邻居节点获得较大的下载速率。应答节点收集请求节点的贡献等级，并将其排序，选择较大的贡献等级的节点来服务。由于刚加入的节点没有贡献等级而不能获得视频数据，为此，每个节点需预留一个连接随机选择节点进行服务。本文假设节点能够如实地传播它们贡献等级到邻居节点上，这个假设能够被已经广泛研究的声誉激励系统所保证，或者部署到已经存在的暗网(darknets)中。

上述过程的关键是如何维护相似下载点的节点列表。tracker服务器通过节点的到达时间和下载点排序在线节点。当新节点加入时，追踪器记录其到达时间，并将其放置到列表的末尾。在本文中，邻居列表的范围为[,γεN εN-](,γ ε是取值从0～1的参数，N是在线节点的数目，能够被追踪到服务器统计）。需要注意的是不同节点有不同的下载能力，系统中节点可能会比其早到达的邻居节点有更快的下载速率，因此它有更大的下载点，此时它的下载速率会下降，这是因为邻居节点缓冲区内缺少当前需要的视频数据，因此节点需要选择有更大的下载点的节点作为邻居。为了适应这种情况，tracker服务器需要知道节点当前的下载点，并且返回节点新的邻居列表。节点需要定期和tracker服务器取得联系并且将其最新的下载点上传到 tracker服务器上，tracker服务器根据节点的新下载点更新节点列表。

3.3 最少优先和贪婪的块下载算法

与P2P文件系统相比，P2P-VoD系统为保证播放的平滑性，每个数据块必须在指定的时间内被下载到节点缓冲区中，因此，以何种策略下载以保证视频数据块的高可用性是需要解决的问题。有2个策略可以被考虑——最少优先和贪婪策略。最小优先是先下载离播放点最远的数据块，这种策略在获得紧急块时花费的代价比较大[8]；贪婪策略是下载距离播放点最近的数据块，这种方法不能保证稀少块的可用性。借鉴文献[8]的思想和文献[15]的模型，建立云辅助P2P-VoD系统下的块下载算法模型。假设节点缓冲区中缺失的块集合为A。块下载方案为u，表示节点以何种策略选择 A中的数据块。在系统达到稳态时，缓冲区中块i已经被下载的概率为pu(i)，则块i+1被下载的概率为

从式(1)中可以看出，第i+1块被下载是通过第i块下载后右移一块实现的，因此其概率是在本次时间段开始时第i块已经被下载的概率，加上在本次时间段结束时第i块被以P2P方式下载的概率或从服务器处获得数据的概率。pu(i)(1–pu(i))是节点没有第i块但其邻居节点有的概率，表明可以从邻居处下载；(1–pu(i))(1–pu(i))是节点没有第 i块同时在邻居节点处也没有找到的概率，表明只能从服务器处下载这个块。需要注意的是，在每个时间段，服务器由于其连接数的限制不能全部应答所有的节点请求，因此参数Ps表示的是服务器能够服务本次请求的概率。式(2)表示的是缓冲区第一个块能够被服务器或者邻居节点下载的概率值，|m|是节点的入度集元素个数，R是服务器等待队列的节点数目。su(i)是节点p从邻居节点k处请求第i块时，p没有块i，但k有块i的概率，su(i)计算可表示为（）

利用文献[15]给出的su(i)的定义如下。

1) 最少优先(标记为r)

2) 贪婪策略(标记为g)

其中，b是节点的平均缓冲区大小。

寻求的目标是辅助节点根据自己的缓冲区大小来选择合适的块下载方案以达到尽快获得需要的视频数据的目的。通过式(1)和式(2)，建立差分方程如下:

节点在ui＜ δ时向服务器请求数据，由于有云分发服务器的存在，因此可以假设同一时间段内所有节点的请求都能够得到满足，因此 Ps=1。同理，1/R的值也为 1。通过对上述数学模型的分析和计算，可以得出2个块下载策略所需要的最小缓冲区大小值。

结论1 最少优先方案需要的最小缓冲区为:i=（1-pr（i））-1+ c。

证明 从式(4)、式(6)和式(7)得到，最少优先的差分方程为:d pr（i）di= pr（i）（1-pr（i ））2+ (1 -pr(i))3ps，解此差分方程得到di = d pr( i)/(pr(i)-1)2，从而得到

结论2 贪婪策略需要的最小缓冲区大小为:i=（1-pg（b））-1ln （pg（i-1）+c 。

证明 从式(5)得出

sg（i）=1- 1 R-pg（b）+pg（i+1）≥ 1-pg（b ）这是由于pg(i)是增函数且pg(0)=1/R，替换su(i)为1−pu(b)。从式(6)和式(7)可得，贪婪策略的差分方程为

解这个方程得到

文献[15]观察到缓冲区的靠前位置的数据使用最少优先策略可以获得较高的pu(i)，即能保证块的高可用性。如图3所示，以pu(i)= 0.94为例，当 119×5＜bi–pi＜252×5(每块的大小为 5 KB)时，2种块下载策略中，选择最少优先会使块i+1更容易被下载到。

图3 最少优先和贪婪策略最小缓冲区大小

4 模拟实验和性能分析

4.1 实验模拟初始化

本文实验环境如下，Myeclipse 8.5平台，双核CPU和 4GB内存的服务器。模拟实验是建立在PeerSim引擎基础之上，这是为了保证尽可能地接近真实世界的情况。实验的参数设置如表1所示。

节点到达符合参数为1/4的泊松分布。每个节点最大有15个邻居节点。节点每2min发送最新的下载点到 tracker服务器，实验运行的结果数据每2min统计一次。

表1 模拟实验参数设置

4.2 模拟实验结果

1) 运行时服务器带宽开销

如图4所示，开始时在系统中没有节点，因此由服务器应答请求。随着时间的增长，一些节点加入到系统中，此时新加入节点能从早加入的节点处获得数据，使服务器的带宽开销降低。在第5个时刻，一批新节点由于节点最大连接数的限制，部分节点没有足够的邻居节点，服务器参与数据上传而造成服务器负载的加重。可以看出随着节点的加入服务器带宽开销逐步降低最后达到稳定。通过计算，相比于BPB[6]服务器带宽开销降低大约6.16%。图5显示在不同参数0.2ε=和0.4ε=时的服务器带宽开销情况。随着服务器返回的邻居列表中节点数目的增加，大缓冲区节点被选中作为邻居节点的概率加大，此时节点在没有服务器参与的情况下也可以获得足够的下载速率来保持视频平滑播放。需要注意的是:当ε增大时，返回的邻居列表也会增大，会导致额外的服务器带宽开销。设置γ的原因是:如果节点a和节点b下载点相近，下载点靠后的节点a达到最大连接数的概率较低，同时块下载方案使 a可能拥有节点b所需要的视频数据，可以根据不同的在线节点数目来选择γ，这里取γ=0.1。当参数ε从0.2～0.4时，服务器带宽开销降低了4.93%。

图4 与BPB比较的服务器带宽开销

图5 不同参数ε下的服务器带宽开销

2) 节点请求的拒绝率

为了研究节点请求拒绝情况，模拟实验监视了每个节点如何发送下载请求和应答来自其他节点请求的行为，并且记录了请求被拒绝的数目。图 6显示NCS算法的拒绝次数下降了27.74%，导致这种现象的原因是:NCS使相似下载点的节点所需要的视频数据即使在邻居节点的缓冲区较小时也有较大的概率存在于邻居节点的缓冲区中。图7显示，由于邻居列表中的候选节点数目的增大，拒绝数明显降低。

3) 节点的平均下载速率

节点下载速率是一个关键的评价指标。为了保证播放的平滑性，下载速率应该大于视频播放速率 r。如果小于视频播放率，缺少的速率就会从服务器处下载，这会增加服务器的带宽开销。图8显示NCS算法相比于BPB提升了5.23%的节点下载速率，这是由于NCS算法能够从低连接数的节点处获得视频数据，同时，在降低了请求拒绝率的情况下，节点能够较快地获得视频数据。图 9显示，在不同的参数ε下，平均下载速率提升了大约2.47%。

图6 节点请求拒绝数

图7 不同参数ε下节点请求拒绝数

图8 节点的平均下载速率

图9 不同参数ε下的节点评价下载速率

图10 在不同小缓冲区，节点数目对服务器的带宽开销

4) 不同小缓冲区节点数目对服务器带宽开销影响

最后测试的是，当拥有小缓冲区的节点数目不同时，服务器带宽开销情况。图 10显示当网络中小缓冲区节点数目占总节点数的10%、20%、30%、40%时服务器带宽开销变化情况。随着小缓冲区节点数目的增加，服务器带宽开销仅有少量的增加。以网络中小缓冲区节点占总节点数的10%为基准，当这个数值是 20%时，服务器带宽开销增加了4.78%、30%时增加了5.02%、40%时增加了5.14%。这表明随着小缓冲区节点数目的增加，服务器带宽开销增加程度小于 6%，这是由于节点能够从其他节点处获得足够的下载速率来保证平滑播放从而减少了对服务器的请求。

5 结束语

本文首先引入了云辅助的P2P-VoD系统架构，并详细阐述了不同缓冲区大小的节点在播放点异步时如何相互获取视频数据的节点选择算法，通过减少对VoD服务提供商服务器的请求从而降低其带宽开销。其次，分析了2种不同的块下载策略，为节点选择哪些块进行优先下载提供了依据，从而保证需要下载的块都是高可用的。最后，模拟实验从服务器带宽开销、请求拒绝率和下载速率方面进行了分析和比较，实验证明NCS算法可以取得比较好的效果。

下一步工作是设计一个基于税收机制的分布式算法来激励高能力节点尽可能多地贡献自己资源，辅助低能力节点获得充足的下载速率从而实现平滑播放，最终达到降低VoD供应商服务器带宽开销的目的。

[1]YEUNG M K H, YU-KWONG K.On game theoretic peer selection for resilient peer-to-peer media streaming[J].Transactionss on Parallel and Distributed Systems, 2009, 20:1512-1525.

[2]PPLive[EB/OL].http://www.pptv.com/.

[3]YAN H, TOM Z J F, DAH-MING C, et al.Challenges, design and analysis of a large-scale P2P-VoD system[A].ACM SIGCOMM[C].2008.375-388.

[4]SHARMA A, BESTAVRORS A, MATTA I.dPAM:a distributed perfecting protocol for scalable asynchronous multicast in P2P systems[A].IEEE International Conference on Network Protocols (ICNP)[C].2005.1139-1150.

[5]LUPU E, SLOMAN M, DULAY N, et al.PONDER:performance aware P2P video on demand service[A].GLOBECOM[C].2007.225-230.

[6]CHAO L, ZHENGHUA F, YONG L.iPASS:incentivized peer-assisted system for asynchronous streaming[A].INFOCOM[C].2009.2741-2745.

[7]VLAVIANOS A, ILIOFOTOU M, FALOUTSOS M.Bitos:enhancing bittorrent for supporting streaming applications[A].IEEE Global Internet Symposium[C].2006.1-6.

[8]YIPENG Z, DAHMING C, LUI J C S.A simple model for analyzing P2P streaming protocols[A].IEEE International Conference on Network Protocols (ICNP)[C].2007.226-235.

[9]ZHEN M, KE X, YIFENG Z.Exploring the policy selection of P2P VoD system-a simulation based research[A].International Workshop on Quality of Service (IWQoS)[C].2012.1-4.

[10]HAITAO L, LILI Z, JIANGCHUAN L, et al.Cost-effective partial migration of VoD services to content clouds[A].IEEE International Conference on Cloud Computing[C].2011.203-210.

[11]Amazon[EB/OL].http://aws.amazon.com/cloudfront/.

[12]XIAO L, YUNHAO L, LIONEL M N.Improving unstructured peer-to-peer systems by adaptive connection establishment[J].IEEE Transactions on Computers, 2005, 54(9):1091-1103.

[13]YUNHAO L, XIAO L, ABDOL-HOSSEIN E, et al.Approaching optimal peer-to-peer overlays[A].13th Annual Meeting of IEEE MASCOTS[C].2005.407-414.

[14]YUNHAO L, XIAO L, XIAO L, et al.Location awareness in unstructured peer-to-peer systems[J].IEEE Transactions on Parallel and Distributed Systems, 2005, 16(2):163-174.

[15]LUI B Q Z J, DAH-MING C.Exploring the optimal chunk selection policy for data-driven P2P streaming systems[A].IEEE 9th International Conference on Peer-to-Peer Computing[C].2009.271-280.