请求下降邻域叠加选取分布式P2P视频点播调度

2018-02-09李蕾，李玲

图学学报 2018年1期

李蕾，李玲

李蕾1，李玲2

(1. 山西传媒学院传媒工程系，山西晋中 030619；2. 新余学院，江西新余 338004)

为实现对等架构的低成本视频流传输和实时播放要求，提出基于请求下降叠加选取的分布式P2P视频点播调度算法。首先，基于叠加技术构建P2P视频点播的技术指标，充分考虑输入邻域节点、输出邻域节点和媒体服务器负载3组优化指标，构建叠加架构和分布式算法流程；其次，利用请求下降策略对发送节点和服务节点选取进行改进，解决可能出现的带宽低利用率和无效的视频播放问题；最后，通过BitTorrent视频点播系统对所提算法的有效性进行了验证。

请求下降；叠加选取；分布式；P2P视频；点播

伴随网络科技的发展，网络中的视频消费逐渐占据流量消费的主要地位，据思科预测，到2017年左右，视频流量消费水平将达到全球流量交换总量的90%左右。其中最重要的是视频点播服务，生成的总流量将会达到2014年时相关水平的3倍，这将给服务器和网络带来非常严重的数据处理负担。同时，近年来用户对视频质量的需求也越来越高。

P2P技术的一个很重要应用是视频点播，PPStream、UUSee、PPLive等公司都推出了这项业务，和传统的基于服务器/客户机结构的视频点播相比，P2P技术具有扩展性好，成本低的优点，但其也有一些不利的因素。如P2P网络具有动态性、不稳定性；P2P网络中节点的差异性很大，这可能会导致播放不流畅。面对高带宽、高存储、高实时要求的VOD应用，P2P网络中有限的资源可用性的问题显得非常突出[1]，这主要表现在以下方面：①播放1080P等格式还存在问题，因为部分带宽小于1 Mbps，上传带宽更小[2]再加上P2P资源分配不均，导致视频播放不流畅。②P2P需大缓存空间，只有较大上传带宽才能满足需要，且要求使用视频的用户拥有较大缓存容量，但用户能提供空间是有限的，导致P2P资源分配不合理，影响点播质量[3]。③文献[4]指出P2P系统中，视频点播容量上限受频繁点播视频影响，如果流量超出容量限制会产生带宽饥饿现象。对节点带宽进行优化配置，可有效提升P2P视频系统容量，但系统内部的视频用户在视频点播过程中具有自私性[5]，很难通过节点资源的直接调度实现节点带宽资源和视频缓存能力的提升[6]。④由于节点硬件条件(带宽、存储)的限制，能提供的资源是有限的。

本文基于叠加技术对P2P视频点播进行优化，并构建叠加架构和分布式算法流程，同时为解决可能出现的带宽低利用率和无效的视频播放问题，利用请求下降策略对发送节点和服务节点选取过程进行了改进设计。最后，通过实验对算法的有效性进行了验证。

1 P2P视频点播叠加技术

叠加技术：P2P网络的每个节点都充当路由器的角色，将收到的数据转发给其他多个节点，这其实是在应用层构建了另一个“网络层”或称为Peer Overlay。利用叠加网络的技术，可以提高网络资源利用率。

1.1 技术指标

技术目标2. 根据上传负载，按比例配置邻域节点输出。()为上传带宽，()为发送视频块集，|()|表示()基数。引入()和|()|比例

每个对等点的邻域节点输出可配置为

技术目标3. 尽量减少由服务器维护所需的传出连接数量和上传带宽。会出现两种情形：①参与的对等节点总上传带宽小于即时传输所需带宽；②对等节点相对于视频对象数量不足。

1.2 对等节点发现

Gossip协议可实现在信息中进行信息捎带，从而实现开销的降低。对对等节点集Cand(i)采用两跳方式的原因是：两跳技术在网络处理中可有效实现路由协议复杂度的降低，并实现路由协议处理过程的简化，同时可有效提升网络的可扩展性和覆盖区间，因此本文着重对两跳对等网络进行分析。以图1为例，对于个节点进行节点遍历，发现的计算开销为O(nlgn)。

1.3 算法描述

使用分布式算法求解，引入输入邻域节点定期评估，其会影响对等节点的属于()和()的输入和输出邻域节点叠加性能。结合式(1)和式(6)可得

对于属于()和()的对等节点

对等点发现算法传播具有输出邻域节点的对等信息，以满足方程约束。当且仅当所提优化问题是不可行的，便使用媒体服务器作为输入邻域节点。

分布式邻域节点选取过程如下。其中，分布式算法见伪代码1；大写字母表示逻辑开头；运算符代表一组元素的加、减法运算。

伪代码1：分布式邻域节点选取 1. 情形1：|in(i)|=N2. best_cand=index(maxf(j): jÎcand(i))3. worst_in=index(minf(j): jÎin(i))4. if serverÎ|in(i)| then5. if then6. in(i)=in(i)-server+best_cand7. else if f(best_cand)>f(worst_in) then8. in(i)=in(i)-worst_in+best_cand9. end if10. else11. if f(best_cand)>f(worst_in)&≥m then12. in(i)=in(i)-worst_in+best_cand13. else if then14. in(i)=in(i)-worst_in+server15. end if16. end if 17. 情形2：|in(i)|

对于代码中的情形1，对等点具有输入邻居节点，并搜索是否有一些候选对等体可能比其已经拥有的更好。存在两种情形：

(1) 对于属于媒体服务器()[第4~9行]，如果从()中删除服务器，并添加_，对等点的聚合传入数据流大于[第5行]，则执行交换过程[第6行]。如果对等点的总计传入数据流小于[第7行]，然后移除_，并添加_，max(())减小，那么，就可以在不排除服务器的情况下进行交换(第8行)。

(2) 对于不属于媒体服务器() [第10~16行]，如果通过移除_并添加_[第11行]，max(())减小，同时如果对等点的总计传入数据流大于等于，则执行交换过程[第12行]。如果通过交换过程max(())数值不降低，但是融合的传入数据流低于播放速率[第13行]，则可对媒体服务器()执行交换过程，在最差的媒体服务器之间，可确保不间断的视频接收。

2 分布式块传输调度

2.1 请求下降策略

基于服务质量的顺序选择算法对队列中的请求传输块进行顺序排列，如图2所示。

输出队列

请求期限请求到达估计 0.15请求A0.11 0.40请求B0.18 0.20请求C0.25 0.30请求D0.32

图2中，如果发送节点的负载均衡，则表明该列表性能好。然而，如果发送节点服务请求多于其可承受负载，则该列表性能恶化。为避免这种情况，采取请求下降策略，判断发送者请求是否能及时交付，如果不能则服务请求数量下降，如图3所示。

输出队列

请求期限请求到达估计 0.15请求A0.18 0.20请求B0.25 0.30请求C0.32 0.35请求D0.39

2.2 发送节点和服务节点选取

发送节点选取：考虑发送节点，其中，()=2 Mbps，()=3；发送节点，其中，()=0.4 Mbps，()=0。当()=0表示无请求挂起，则保持空闲，不利于节点流量均衡。为减轻其影响，需对目标式(12)进行改进

3 实验与分析

3.1 参数对比实验

利用OPNET进行P2P视频点播系统建模，所采用的视频测试集包含4个视频，每个时长12 min，如图4所示。并选取Improving QoS、iPASS和Kangaroo算法做对比。平均对等上传带宽为avg=2000 Kbps，视频播放速率等于平均对等上传带宽，即=avg=2000 Kbps。实验方案包括500个对等节点，并包含3个阶段：①对等节点以统一速率进入系统；②无对等节点到达和离开；③对等节点以统一离开率离开系统[9-10]。图5(a)~(c)给出了在4种不同的情况下的视频点播行为，节点以恒定比例离开：1，2，5，10节点/秒。

在图5中，算法模拟需运行至仅剩50个对等点留在系统中。根据图4可知，即使对于非常高的对等节点离开率，例如10节点/秒，其剩余节点的空闲率仍然小于7%(平均为4%)，服务率小于20%(平均为10%)。在对等节点离开期间，服务器对系统的贡献并没有显著增加。其有助于减少带宽，这是因为系统中有较少对等节点。

图4 模拟器操作界面

图5 对等节点离开率对算法影响

图6是6种参数对等节点到达率对算法影响图。其中，空闲率(%)和服务率(%)是在500个节点以1，5，10个节点/秒速度进入系统；标准偏差的正态分布为3，5，20，40。

根据图6可知，空闲率(%)的增加和高比例带宽(高达40%)是由服务器提供的。这种现象是不可避免的，因为任何优化算法都需要一些适应时间。当所有的对等节点加入到系统中后，似乎达到稳定的状态，可观测到空闲率(%)和服务率(%)处于稳定状态。两个对等节点相距越近，其能够提供输出节点所需内容的概率越低，因此需要由服务器进行提供，从而增加服务器负担。

3.2 算法性能对比

表1对比了选取的几种算法在节点自适应动态行为、服务器支持、资源平衡性、对等节点异质性开发等性能上的表现。

根据表1可知，本文算法相对于其他3种算法，具有更高的自适应动态行为，且具有服务支持性能、资源平衡性以及对等节点异质开发能力。体现了本方法的有效性。

为实现算法横向对比验证，选取Improving QoS、iPASS和Kangaroo 3种基于P2P的视频点播算法进行性能对比。实验参数：平均的视频持续时间为=1/=90 min，视频数据流的到达间隔为=1/=20 min。对比指标选择视频流量效率和上述上行链路效率，见表2。

由表2可知，本文模型在上行链路效率和视频流量效率两项指标均显著优于其他3种对比算法的相关指标，说明本文模型在处理故障时具有优势。

(a) 到达率对空闲率影响

((1) 均匀分布，到达率10节点/秒；(2) 普通分布，到达偏差5 s；(3) 均匀分布，到达率5节点/秒；(4) 普通分布，到达偏差20 s；(5) 普通分布，到达偏差30 s；(6) 均匀分布，到达率1节点/秒)

(b) 到达率对服务率影响

((1) 普通分布，到达偏差5 s；(2) 普通分布，到达偏差20 s； (3) 均匀分布，到达率10节点/秒；(4) 均匀分布，到达率5节点/秒；(5) 普通分布，到达偏差30 s；(6) 均匀分布，到达率1节点/秒)

表1 视频点播系统对比

表2 模型指标对比(%)

4 结束语

本文提出的一种基于请求下降叠加选取的分布式P2P视频点播调度算法，充分考虑输入邻域节点、输出邻域节点和媒体服务器负载3组优化指标，构建分布式算法流程，并利用请求下降策略解决可能出现的带宽低利用率和无效的视频播放问题，实验结果验证了所提方法的有效性。

[1] 沈时军, 李三立. 基于P2P的视频点播系统综述[J]. 计算机学报, 2010, 33(4): 613-624.

[2] XU K, LIU X, MA Z, et al. Exploring the policy selection of the P2P VoD system: a simulation-based research [J]. Peer-to-Peer Networking and Applications, 2015, 8(3): 459-473.

[3] 聂华, 张敏, 郭敬荣,等. 基于内容流行度差异性的CDN-P2P融合分发网络缓存替换机制研究[J]. 通信学报, 2015, 36(z1): 9-15.

[4] 何明, 张玉洁, 孟祥武. 面向用户需求的非结构化P2P资源定位泛洪策略[J]. 软件学报, 2015, 26(3): 640-662.

[5] CONG X, SHUANG K, SU S, et al. An efficient server bandwidth costs decreased mechanism towards mobile devices in cloud-assisted P2P-VoD system [J]. Peer-to- Peer Networking and Applications, 2014, 7(2): 175-187.

[6] GRAMATIKOV S, JAUREGUIZAR F. Modelling and analysis of non-cooperative peer-assisted VoD streaming in managed networks [J]. Multimedia Tools and Applications, 2016, 75(8): 4321-4348.

[7] 翟海滨, 张鸿, 刘欣然, 等. 最小化出口流量花费的接入级P2P缓存容量设计方法[J]. 电子学报, 2015, (5): 879-887.

[8] CHEN H Y, SUN Z G, YI F. Buffer Bank storage: an economic, scalable and universally usable in-network storage model for streaming data applications [J]. Science China Information Sciences, 2016, 59(1): 1-15.

[9] CHANG C L, CHEN W M, HUNG C H. Reliable consideration of P2P-based VoD system with interleaved video frame distribution [J]. IEEE Systems Journal, 2014, 8(1): 304-312.

[10] DUQUE J P U, GOMEZ N G. Throughput analysis of P2P video streaming on single-hop wireless networks [J]. IEEE Latin America Transactions, 2015, 13(11): 3684-3689.

Distributed P2P Video on Demand Scheduling Based on Request Drop Neighborhood Overlay

LI Lei1, LI Ling2

(1. Department of Communication Engineering, Communication University of Shanxi, Jinzhong Shanxi 030619, China; 2. Xinyu University, Xinyu Jiangxi 338004, China)

In order to achieve peer-to-peer architectures for low cost video stream transmission and real-time playback requirements, this paper proposes a distributed P2P video on demand scheduling algorithm based on request drop neighborhood overlay. Firstly, this paper constructs technical index of P2P VOD (video on demand) based on the superposition technique, considers the three parameters optimization index of the input neighborhood nodes, the output neighborhood nodes and the media server load, and then constructs the overlay structure and distributed algorithm flow. Secondly, this paper uses the request descent strategy to improve the selection of the sending nodes and service nodes, which can solve the problem of broadband low utilization ratio and invalid video playback. Finally, experimental results based on the BitTorrent VOD system verify the effectiveness of the proposed algorithm.

request drop; overlay selection; distributed; P2P video; on demand

TN 943

10.11996/JG.j.2095-302X.2018010030

2095-302X(2018)01-0030-06

2017-04-16；

2017-06-03

江西省教育厅科技项目(GJJ151205)

李蕾(1982-)，女，山西长治人，讲师，硕士。主要研究方向为图像处理及广播电视技术。E-mail：sherry0790@163.com