分层P2P点播系统中优化的带宽资源分配策略

陈 卓，冯 钢，周 江

(1. 重庆理工大学计算机科学与工程学院 重庆 巴南区 400054; 2. 电子科技大学通信抗干扰技术国家级重点实验室 成都 611731)

近年来，基于Peer-to-Peer技术(P2P)的视频流媒体应用已成为最重要和应用最广泛的互联网应用。用户节点从其他节点处获取视频流数据的同时，也利用自己的上行带宽将所缓存的视频流数据分发给邻居节点。P2P流媒体系统以其良好的可扩展性、较低的服务器带宽开销等突出优势，使目前众多典型的视频流媒体系统[1-4]均采用了P2P技术加以实现。

P2P流媒体系统可分为P2P直播系统和P2P点播系统。在P2P直播系统中，先后进入系统的节点的播放位置基本同步。而在P2P点播系统中，各节点的播放位置却存在较大的差异。另外，P2P点播系统为了提高节点自己的互助，通常需要节点分配更大的存储空间(如1 GB[1])将已观看过的内容进行缓存以服务其他节点。P2P点播系统虽然吸引了大量用户，但视频服务提供商却很难从中赢利[5]，其根本原因是服务提供商需要为大量的服务器带宽消耗买单。因此，在保证用户流畅的视频播放的同时，如何有效地降低服务器的带宽开销是P2P点播系统亟待研究并解决的问题。

另一方面，使用分层视频编码技术能将原始视频序列压缩成多个视频层，包括基本层和多个扩展层。各层向下依赖，即高层视频的正确解码必须依靠其下的各视频层的数据正确获取。近年来，学界已将分层视频编码技术应用到P2P流媒体系统中[6-8]，其目的是为了满足节点对不同视频质量的多样化需求。在这类系统中，节点能依据自身带宽资源或对不同视频质量的需求，有选择地注册在不同的视频层。注册在不同视频层的节点所需获取的视频流速率也不同，使节点感受到不同的视频质量。虽然在引入分层视频编码后，系统的弹性和自适应性得以增强，但同时也使得分层P2P流媒体系统的优化设计变得极具挑战性。特别是当邻居选择及带宽分配不合理时，很容易导致视频服务器的带宽开销严重。本文从邻居关系建立及带宽分配的角度，研究降低基于分层视频编码技术的P2P点播系统(分层P2P点播系统)中视频服务器带宽消耗的问题。分析了分层P2P点播系统中服务器开销增加的主要原因，并给出视频服务器带宽开销的数学优化模型。描述了基于节点在线时间相似性的邻居关系建立及同层/跨层邻居选择带宽分配策略。对提出的策略进行实验评估，并给出相关结论。

1 相关研究工作

得益于互联网用户对视频点播的大量应用需求，国内外学者就基于P2P技术的点播系统进行了一系列的研究工作。文献[9]建立了数学模型，对单视频流P2P点播系统中不同的带宽分配策略进行了比较。文献[10]分析了单视频流P2P点播系统中存在视频数据的供需不平衡的问题，并提出了一种基于队列技术的改进策略。另外，文献[11-13]主要考察在多视频(多频道)的场景下优化的缓存管理机制，研究了当节点缓存空间满后，如何对缓存内容进行替换，以达到降低服务器带宽开销的目的。学界目前对于采用分层视频编码的P2P点播系统的研究工作还相对较少，文献[8]研究了分层P2P点播系统中降低起始延迟和保证视频播放质量的问题，提出了一种基于zigzag的视频数据段紧迫度评价机制和调度策略。文献[14]提出了一种研究分层视频P2P点播系统的分析模型，能够预测系统在稳定状态下系统的平均吞吐量、节点平均播放质量等关键系统参数。文献[15]研究了在多个视频播放阶段中节点的视频层选择算法，并通过大量实验，评估了分层视频P2P点播系统中节点的起始延迟和视频质量。目前还没有从优化邻居选择和带宽资源分配的角度讨论降低服务器带宽开销的研究工作，而这正是本文的研究重点。

2 视频服务器的带宽消耗模型

2.1 研究问题描述

虽然在P2P点播系统中，通过节点间的互助能够有效地降低服务器的带宽开销[1]，但系统中存在的带宽资源利用不均衡的问题，导致服务器开销依然较大。特别在基于分层编码技术的P2P点播系统中，对某些视频数据的带宽资源供需不均衡极容易导致服务器带宽开销的增加。

分层P2P点播系统中带宽资源供需不均衡问题主要由两个因素所致：1) 某个节点p拥有足够的上行带宽资源，但却没有缓存其他邻居节点所需要的数据，使p的带宽资源无法有效的利用，而其他邻居节点所需的视频数据只能通过视频服务器获取。特别是当考虑用户连续点播多个视频时[13]，用户需要在存储空间满时决策如何对缓存数据进行替换。2)某个节点p缓存了节点q所需的数据，但由于p的带宽资源已经分配给其他邻居节点，导致q无法获得服务。本文重点考察多个用户点播同一个分层视频节目，假设用户的缓存空间足够存放一个完整的分层视频。主要从上述第二个因素加以考察，研究新的邻居关系建立及带宽资源分配策略，以降低视频服务器的开销。

2.2 分层P2P VoD视频分发模型

假设整个视频内容分为K个等长的视频区域(section)，而一个视频区域是由多个分别属于不同视频层的数据段(segment)构成。若该视频节目分解为J个视频层，则每个视频区域则包括了J个数据段。如图1所示，视频内容分解为S1,S2,…,SK个视频区域。对于其中的任意一个Si，包括了Si,1,Si,2,…,Si,J一共J个数据段，其中，1≤i≤K。

图1 分层视频内容的组织结构

假设点播节点的存储空间足够缓存整个视频内容。只要一个节点p缓存了部分视频内容，就可以利用自己的上行带宽将缓存内容提供给请求节点。若节点p注册在视频层Lj(1≤j≤J)，且正观看到视频区域Si。根据分层视频编码的解码依赖性原理，若节点p要保证流畅的视频播放，则需要同时获得视频层L1～Lj的数据段Si,1,Si,2,…,Si,j。进一步，由于第Lj层的各数据段都具有相同的视频流解码速率rj，则节点p需要获得的视频流速率为另外，只要某个节点q缓存了节点p所需的视频内容，则节点q成为节点p潜在的服务节点，特别说明不论p，q是否处于相同的视频层。

2.3 服务器的带宽资源开销优化模型

假设系统中有N个节点正在点播同一个视频节目。由于这些节点进入系统的时间随机，使各节点当前正在观看的视频区域存在差异，也即表明这N个节点当前可以是正观看S1～SK不同位置的内容。定义当前N个节点对某一个数据段Si,j总的带宽资源需求为Di,j，可表示如下：

约束条件1)表示节点p对于视频数据段Si,j分配的带宽资源不能为负。约束条件2)表示对节点p所能分配的上行带宽资源的限制，也即如果节点没有缓存数据段Si,j，则不能向请求Si,j的节点分配带宽资源。约束条件3)表示节点所能够分配的带宽资源受到其自身最大上行带宽资源限制。约束条件4)表示分层视频编码所具有的解码依赖关系，也即当节点 p 需要视频内容Si,j时，视频数据段Si,1,Si,2,…,Si,j-1也需同时获取才能实现视频解码。

但上述优化问题是一个非线性优化问题，不易求解。因此把上述非线性优化问题转化为一个等价的线性优化问题。实际上，系统中缓存了数据段Si,j的节点分配给Si,j的带宽资源总和不应该多于系统中节点对Si,j的带宽总需求。若在满足了对数据段Si,j的带宽资源供需平衡的前提下，缓存Si,j的节点可将多余的带宽资源分配给其他数据段，而如果没有缓存其他数据段，则保留多余的带宽资源。因此，上述非线性优化问题可转化为线性优化问题：

3 基于在线时间相似性的邻居选择及带宽资源分配策略

3.1 基于节点在线时间的相似性建立邻居关系

在分层P2P点播系统中，节点所缓存的视频数据的多寡和节点在线观看视频的时间密切相关。也即观看某个视频时间越久的在线节点其磁盘空间中缓存的视频数据也越多。这也意味着一个在线时间长度为tp的节点p，只能从在线时间长于tp的在线节点处获取所需的视频数据。若P2P点播系统中的管理节点(Tracker)能够增加记录系统中节点的在线时间长度以及所节点所注册的视频层Lj(1≤j≤J)，则能有效地帮助新进入系统的节点建立合理的邻居关系。

若在视频层Lj一共有kj个在线节点正在点播视频节目。不失一般性，管理节点依据这kj个节点的在线时间长度将节点进行排序，记为：p1, p2,…, p|kj|，这意味着kj个节点的在线时间满足t1≥t2≥…≥t|kj|。对于处于同视频层的任意两个在线节点pj为pk，若tj≥tk，则称pj为pk的前驱节点。而一个在时间点tk进入系统的节点pk首先经由管理节点获得在线时间和自己相似的m个前驱节点pk-1,pk-2,…, pk-m的信息。这m个前驱节点采用3.2节描述的同层带宽资源分配策略，为节点pk分配其所需的L1～Lj层视频流。另外，由于视频解码依赖性的因素，使处于视频层Lj+1,Lj+2,…, LJ的节点在满足同层节点的带宽资源分配后，若仍有剩余上行带宽资源，则能够成为节点pk的潜在服务节点。管理节点能够为节点pk提供部分与其在线时间相似的处于其他视频层的节点信息。这也意味着当节点pk在无法从同视频层的前驱节点获得足够视频流时，还可以向其他视频层中缓存了所需视频数据的节点请求带宽资源，进一步降低分层P2P点播系统中视频服务器的带宽资源开销。

3.2 同层/跨层带宽资源分配策略

在3.1节提出的基于节点在线观看视频时间相似性的基础上，本节提出一种分层P2P点播系统中的带宽资源分配策略。该策略包括同视频层带宽资源分配策略和跨视频层带宽资源分配策略。

1) 同视频层带宽资源分配策略。通过3.1节邻居关系的建立，使得处于视频层Lj的节点pk同时拥有处于同视频层和其他视频层的多个邻居节点。由于处于同视频层的节点的带宽资源往往近似，且更容易使节点pk获取到所需的视频层L1～Lj的视频数据。因此节点pk优先向与自己在线时间相似的同层邻居节点(部分前驱节点)请求带宽资源。节点pk先从在线时间距离tk最近的邻居节点pk-1请求带宽资源，如果pk-1的可用上行带宽资源无法满足，则再依次向其他邻居节点pk-2,pk-3,…, pk-m请求带宽资源，pk,…, pk-m的在线时间满足tk≤…≤ tk-m+1≤tk-m。

对于处于视频Lj的节点pk而言，要获取到自己所需的视频播放质量，则需要同时获得L1~Lj各层足够的视频流，即r1,r2,…, rj。如果节点pk在某个视频层Li(1≤i≤j)不能通过同视频层上的邻居节点(部分前驱节点)获得足够的视频流，则pk需要通过向能提供Li层视频流数据的异层节点q请求。本文称这类跨层的服务节点为“帮助者”。节点pk在Lj层的“帮助者”q应具有两个条件：

1) q和pk不在同一视频层，但q必须缓存了pk所需的视频层Lj的数据。由于视频解码的依赖关系，能成为节点p在视频层Lj(1≤j≤J)的“帮助者”q所处的视频层Lv应满足j

2) 节点q在完成对其所在的视频层Lv中节点的带宽资源分配后，剩余带宽auq≠0。

同层/跨层带宽资源分配策略的伪码描述如下：

对于系统中的一个节点q，若该节点在线观看视频节目的时间为tq，且如果节点q同时收到来自n个邻居节点的跨视频层的带宽资源请求。这时，节点q则成为这n个邻居节点的跨层视频服务节点。节点q按照在线观看视频的时长将这n个邻居节点排列为p1, p2,…, pn，也即t1> t2,…, > tn。节点q将按照这n个节点的排列顺序分配自己的剩余带宽资源。该策略的主要目的是对于一个在线观看视频时间越长的节点，其缓存的视频内容越多，能够为更多的节点提供带宽资源服务，因此应该优先予以服务。“帮者”的可用带宽资源分配策略的伪码如下所示。

4 数值结果与讨论

本文采用Matlab实现了一个动态仿真平台模拟分层P2P点播系统。实验中的节点规模为5 000，视频长度为60 m in，且整个视频内容切分为100个等长的视频区域(Section)，即每一个视频区域的播放时间为36 s。源视频分解为3个视频层L1, L2和L3。且r1=300 kb/s，r2=200 kb/s，r3=100 kb/s，这也表示节点注册到视频层L1, L2和L3分别需要至少R1=300 kb/s, R2=500 kb/s和R3=600 kb/s的下行带宽资源。定义节点的下行带宽分布于区间[R1, R2], [R2, R3]和[R3, 1.5R3]的比例为1:1:1。在同一带宽区间内，节点的下行带宽服从均匀分布。类似于文献[1, 8]，节点组织成一个“网状”结构的重叠网络。每个节点的邻居个数设置为8～10个[1]。为了充分评估算法的性能，本文比较了在普通视频、冷门视频和热门视频3种视频点播场景下各种策略的性能，分别以参数为λ0=30，10，60的泊松流表示节点进入普通视频，冷门视频和热门视频的速率。根据文献[1]对实际系统PPLive的测量，节点观看视频片段的时间(在线时间)服从近似的指数分布，因此分别设置参数μ=50，20，80的指数分布模拟节点观看普通视频，冷门视频和热门视频的时间长度分布。另外需要说明的是，为求解式(6)的优化问题，需在不同的统计点动态记录系统当前的以及节点的带宽资源总需求和总供应。而当系统中的在线节点规模较大时需求解大规模的线性优化，如在仿真系统的100个统计周期以后，每统计一次理论最优解，需解一个3´105～6´105个变量的大规模线性优化。

本文分200个统计周期分别统计了视频服务器的实时带宽资源开销，也即每隔36 s统计一次。图2、图3和图4分别显示了普通视频、冷门视频和热门视频场景下的服务器带宽资源开销。文献[8]中所采用的随机邻居建立及带宽分配策略称为随机策略。通过解式(6)的线性优化得到的理论最优值称为最优化数值结果。

图2显示了对于普通视频场景，在各个统计周期内，本文提出的策略都非常接近于解优化问题后得到的服务器带宽消耗的理论最小值，这相对于随机请求策略降低视频服务器的带宽消耗非常明显。

另外，可以看到在第100个统计周期(等于整个视频文件的时长)以前，视频服务器的带宽资源消耗逐步上升的过程；但到了100个统计周期以后，视频服务器的带宽开销呈现出平稳的特性。其中，理论最小的服务器带宽资源开销平均值为86.3 Mb/s，采用本文提出的策略所需平均服务器带宽资源为92.8 Mb/s，而采用随机策略时，服务器所需的平均带宽资源开销则为126.4 Mb/s。在前100个统计周期内系统中，节点数量稳步增加，从而使服务器的带宽消耗也稳步增加。进一步分析发现其主要原因是这段时间只有节点异常退出系统的情况，而使节点进入系统的速率是大于节点离开系统的速率，导致了节点数量稳步增加。而在100个统计周期后，系统中节点的退出包括异常退出和观看完整个视频退出两种情况，使节点进入系统的速率基本等于节点退出系统的速率，进而使整个系统中的节点总数趋于动态稳定。因此导致服务器的带宽资源消耗也趋于稳定。

图3显示了在普通视频点播场景中节点的上行带宽利用率，可以看到在第12个统计周期以后，采用本文的策略使节点的上行带宽利用率均在90%以上，并最终在95%上下浮动。相比之下，采用随机策略的上行带宽利用率在83%上下浮动。由于节点按照从相距自己进入频道时间最接近的同层/异层的在线节点中选取邻居节点，有效地避免了部分请求节点所需带宽资源无法得到服务，而部分节点的上行带宽资源却没有充分利用的问题。该图也进一步表明了本文的策略能够有效地提高节点之间的互助，从而实现降低服务器带宽资源开销的问题。

图2 普通视频点播场景中服务器的带宽资源消耗对比

图3 普通视频点播场景中节点的平均带宽利用率

图4 冷门视频中服务器的带宽资源消耗对比

图4反映出对于冷门视频，服务器的带宽消耗的起伏较严重。其主要原因是因为进入冷门视频频道的节点速率较低，使停留在冷门视频中并观看视频的节点数量较少，进一步使节点之间的带宽提供互助行为较弱。同时，由于进入系统的节点的上行带宽资源存在一定的随机性，节点间带宽互助也存在很大的随机波动，使服务器消耗的带宽在不同统计周期的存在较大的差异。

5 结 束 语

本文从邻居选择及带宽分配策略的角度，对降低分层P2P点播系统中服务器的带宽开销问题进行了系统研究，首先从视频数据的带宽供需的角度，建立了最小服务器带宽开销的理论优化模型；并提出了一种基于在线观看视频时间相似性的邻居选择及同视频层及跨视频层的及带宽分配策略。通过仿真实验表明，本文的策略在各种视频点播场景中都比已有的策略消耗更小的服务器带宽。该研究成果有助于改善现有系统的设计。

[1] HUANG Yan, FU Zhen-jia, CHIU Dah-ming. Challenges,design and analysis of a large scale P2P-VoD system[C]//Proceedings of the ACM SIGCOMM. Seattle, USA:ACM, 2008: 375-388.

[2] LIU Zi-mu, WU Chuan, LI Bao-chun, et al. UUSee:large-scale operational on-demand stream ing w ith random network coding[C]//Proceedings of the IEEE INFOCOM.San Diego, USA: IEEE, 2010: 1-9.

[3] XIE Su-su, LI Bo, KEUNG G Y, et al. The coolstreaming:Design, theory and practice[J]. IEEE Transactions on Multimedia, Special Issue on Content Storage and Delivery in Peer-to-Peer Network, 2007, 9(8): 1661-167.

[4] GILL P, ARLITT M, LI Zong-peng, et al. YouTube traffic characterization: a view from the edge[C]//Proceedings of the 7th ACM SIGCOMM Conference on Internet Measurement. San Diego, USA: ACM, 2007:15-28.

[5] HUANG Cheng, LI Jin, KEITH R. Can Internet video-on-demand be profitable[C]//Proceedings of ACM SIGCOMM. Kyoto: ACM, 2007:133-144.

[6] XIAO Xin, SHI Yuan-chun, GAO Yuan, et al. LayerP2P: a new data scheduling approach for layered stream ing in heterogeneous networks[C]//Proceedings of IEEE INFOCOM. Rio de Janeiro: IEEE, 2009: 603-611.

[7] M IESHOKRAIE S, HEFEED A M. Live peer-to-peer stream ing w ith scalable video coding and network coding[C]//ACM Multimedia Systems. Scottsdale, USA:ACM, 2010: 123-132.

[8] DING Yan, LIU Jiang-chuan, WANG Dan, et al.Peer-to-peer video-on-demand with scalable video coding[J].Elsevier Computer Communications, Special Issue on Multimedia Networking and Security in Convergent Networks, 2009, 33(14): 1589-1597.

[9] PARVEZ N, W ILLIAMSON C, MAHANTI A, et al.Analysis of bittorrent-like protocols for on-demand stored media streaming[C]//Proceedings of ACM SIGMETRICS.Annapolis: ACM, 2008: 301-312.

[10] YANG Yan, CHOW A, GOLUBCHIK L, et al. Improving QoS in BitTorrent-like VoD systems[C]//Proceedings of IEEE INFOCOM. San Diego: IEEE, 2010: 1-9.

[11] ZHOU Yi-peng, FU Zhen-jia, CHIU D M. Divisionof-labor between server and P2P for streaming VoD[C]//Proceedings of IEEE IWQoS. Coimbra: IEEE,2012: 1-9.

[12] ZHOU Y P, FU T Z J, CHIU D M. A unifying model and analysis of P2P VoD replication and scheduling[C]//Proceedings of IEEE INFOCOM. Shanghai: IEEE, 2012:1530-1538.

[13] ZHOU Yi-peng, FU Zhen-jia, CHIU D M. Server-assisted adaptive video replication for P2P VoD[J]. Elsevier Journal of Signal Processing: Image Communication, Advances in 2D/3D Video Stream ing Over P2P Networks, 2012, 27(4):484-495.

[14] MOKHTARIAN K, HEFEEDA M. Analysis of peer-assisted video-on-demand systems w ith scalable video streams[C]//Proceedings of ACM Multimedia Systems.Scottsdale, USA: ACM, 2010:133-143.

[15] ABBOUD O, ZINNER T, PUSSEP K, et al. On the impact of quality adaptation in svc-based P2P video-on-demand systems[C]//Proceedings of ACM Multimedia Systems.San Jose: ACM, 2011: 223-232.

编 辑 黄 莘