国家政策对基于P2P的视频点播系统综述

《计算机学报》2010年4期，2010，33（4）本课题得到国家精品课程集成项目（JPKC-5）资助。沈时军，男，1982年生，博士研究生，主要研究方向为流媒体技术、移动计算。E-mail：[e-mail]。联系地址：北京清华大学东主楼8-303。电话：[phone]。李三立，男，1935年生，中国工程院院士，清华大学教授，博士生导师，主要研究领域为高性能集群计算、网格计算、移动计算、流媒体技术等。2012年全国高考模拟参考部分基于P2P的视频点播系统综述沈时军李三立（清华信息科学与技术国家实验室北京100084）（清华大学计算机科学与技术系北京100084）摘要近十年来，基于对等网络（Peer-to-Peer，P2P）的视频点播系统（Video-on-Demand，VoD）受到了越来越多的关注。它吸引人的原因在于，与传统的基于服务器/客户机结构的视频点播系统相比，P2P技术具有成本低、扩展性好的优点。但是，由于对等网络内在的不稳定性、异构性，这类系统在实现上面临着诸多挑战。本文对现有的该类系统的体系结构进行模块划分，并对各模块的实现策略进行讨论；特别是对VoD/P2P实现中的三个主要方面，即数据传输、数据存储、激励机制进行了综述。关键词对等网络；视频点播；传输拓扑；编码方案中图法分类号TP393P2P-basedVideo-on-DemandSystems:ASurveySHENShi-JunLISan-Li(TsinghuaNationalLaboratoryforInformationScience&Technology,Beijing100084)(DepartmentofComputerScienceandTechnology,TsinghuaUniversity,Beijing100084)AbstractOverthepastdecade,Peer-to-Peer(P2P)basedVideo-on-Demand(VoD)systemshavere-ceivedatremendousamountofresearchfocus.Theyareimmenselyattractivebecauseoftheircheapde-ploymentandhighscalabilitycomparedtotraditionalClient/Server(C/S)basedVoDsystems.However,duetotheinstabilityandheterogeneityofP2Pnetworks,therearemanychallengesindesigning,implementing,anddeployingsuchsystems.Forinstance,thelackofresources(e.g.,sourcenodes,bandwidth,storage,etc.)usuallybecomesabarrierthatpreventspracticalsystemsfromnormaloperation.Basedontheobservation,thispaperoutlinesthecomponentsofexistingVoD/P2Parchitecturesandsurveysapproachestotheirdesign,focusingonhowtomakefulluseoflimitedresourcesinP2PbasedVoDsystems.Specifically,theauthors《计算机学报》2010年4期，2010，33（4）本课题得到国家精品课程集成项目（JPKC-5）资助。沈时军，男，1982年生，博士研究生，主要研究方向为流媒体技术、移动计算。E-mail：[e-mail]。联系地址：北京清华大学东主楼8-303。电话：[phone]。李三立，男，1935年生，中国工程院院士，清华大学教授，博士生导师，主要研究领域为高性能集群计算、网格计算、移动计算、流媒体技术等。presentasurveyinthreeaspects:(1)datatransmission,referringtohowtomakefulluseofnodes’bandwidth;(2)datastorage,referringtohowtomakefulluseofnodes’storage;and(3)incentivemechanismsthatstim-ulatenodestocontributemoreresources.KeywordsPeer-to-Peer;Video-on-Demand;transmissiontopology;encodingscheme《计算机学报》2010年4期，2010，33（4）第3页共16页1引言上世纪九十年代，在万维网取得了巨大成功之后，人们进一步希望可以在网上随意观看自己喜爱的视频节目，即视频点播。最初的VoD系统是基于C/S结构的，为了增加系统支持的用户量，并降低用户的等待时间，人们提出了batching[1-2]、patching[3]等一系列算法。但点播不同于传统的Web应用，其高带宽消耗、时延敏感的特性很快使C/S结构暴露出可扩展性差的问题。于是，一个自然而然的想法是将多个服务器分散部署到网络中，当用户点播节目时，可以从距离自己最近的服务器取得数据。这就是CDN（ContentDistributionNetworks）的思想，它一定程度上提高了点播系统的可扩展性，但同时引入了新的问题：由于需要很多服务器，整个系统的部署与维护将非常昂贵。对于这个问题，人们很快有了解决办法：他们发现用户终端的性能不断提高，甚至可以达到服务器的标准。由此，基于对等网络的视频点播系统（下文称为VoD/P2P）出现了。视频点播并不是采用P2P技术的最初应用，事实上在它之前，基于P2P的文件共享系统已经非常流行。第一个现代意义上的P2P文件共享系统开始于1999年，一个年仅18岁的美国人开发了Napster，并在它上面共享音乐文件。Napster迅速流行，在2001年达到了150万最高在线用户。虽然Napster最终因为版权问题而停止运行，但它引发了P2P使用的高潮。在它之后很多类似的系统，如Gnutella、KaZaA、eDonkey、Bittorrent等，今天仍被广泛使用。在文件共享系统之后，P2P的另一个重要应用是视频直播。大约从2004年底到2005年，基于P2P的网络视频渐渐流行起来，如Coolstreaming、GridMedia、PPLive、PPStream等。这些系统通过转播体育娱乐节目，吸引了大量用户。到了2007年，P2P直播已经取得了相当成功，几乎没有人怀疑它的广阔前景。也就在这时，很多公司，包括PPStream、PPLive、UUSee、VeohTV、Joost，推出了另一个更具挑战性的业务——P2P点播。文件共享、视频直播、视频点播有一个共同的特点：耗带宽。为了提高系统的可扩展性并降低成本，P2P技术成为它们的首选。但是，采用P2P技术又有一些不利的因素。例如，P2P网络是动态的、不稳定的（churning），节点的上线、下线是任意的。如果正在提供服务的节点突然下线了，将会对接收服务的节点造成影响。而且，P2P网络中节点的差异性很大，如上传带宽，有一些校园网用户可以达到100Mbps，但某些ADSL用户可能只有几百Kbps，甚至达不到一个视频的平均码率。这些因素对文件共享系统来说，可能只是影响文件的下载时间；但对时延敏感的视频直播、点播应用，却可能造成播放不流畅，甚至无法播放的严重后果。视频的直播与点播，虽然相似，但又有很多不同之处。直播更像电视，用户只能选择看或不看，并没有太多的交互性；点播则更像DVD，用户可以选择何时播放，并且在观看过程中可以进行暂停、恢复、拖动播放等VCR操作。因此，同一频道不同用户的播放进度，在直播中是相近的，而在点播中却可能相差很大。播放进度差异的直接影响是，用户间数据共享的机会更少。因此在实现上，点播比直播更具挑战性。表1给出了基于P2P的视频直播表1基于P2P的视频直播与视频点播的比较视频直播视频点播请求并发性请求并发性高请求异步、分散端到端延迟希望尽可能小没有要求频道数量一般较少，用户集中于少量频道一般很多，用户分散在不同频道VCR要求实时节目，交互性少一般支持暂停、恢复、拖动播放等操作数据共享难度用户间播放进度差异小，共享容易用户间播放进度差异大，共享困难《计算机学报》2010年4期，2010，33（4）第4页共16页图1传输中的拓扑结构。图中箭头表示数据流向。（a）单树结构（单源）；（b）多树结构（多源），实线与虚线代表两棵不同的组播树；（c）网状结构（多源）。与视频点播的一个比较。面对高带宽、高存储、高实时要求的VoD应用，P2P网络中有限的资源可用性的问题显得非常突出。这表现在两个方面：（1）由于节点硬件条件（带宽、存储）的限制，能提供的资源是有限的；（2）由于缺乏一个有效的激励机制，节点愿提供的资源是有限的。目前，虽然已有很多大型的VoD/P2P系统，如PPLive、PPStream、迅雷等，但它们在很大程度上依赖于服务器或CDN，因而普遍存在“成本过高、盈利困难”的问题。本文致力于研究如何在VoD应用中发挥P2P技术的优势，对VoD/P2P系统在三个方面作综述，也就是：（1）数据传输：讨论如何充分地利用节点的有限带宽；（2）数据存储：讨论如何充分地利用节点的有限存储；（3）激励机制：讨论如何刺激节点贡献资源。本文接下来将如下安排：第2节讨论VoD/P2P的数据传输，包括传输过程中的拓扑结构以及编码技术；第3节讨论VoD/P2P的数据存储，包括存储过程中的资源查找结构、编码方案以及替换策略；第4节讨论VoD/P2P的激励机制，介绍三种常见的策略；最后，第5节总结全文。2传输问题VoD/P2P的传输希望解决如下的问题：如何从一个或多个源节点向多个目标节点分发数据，使之在动态的、异构的网络中：（1）保证视频的传输率，即目标节点的有效输入带宽不能小于视频的码率；（2）减少用户等待时间，即用户从发出点播请求到视频播放的时间间隔尽可能短；（3）降低带宽浪费，即点播不能消耗很多不必要的带宽而影响其它应用。近年来，对传输问题的研究主要集中在拓扑结构与编码技术两方面。2.1传输中的拓扑结构在早期的基于C/S结构的点播系统中，人们曾希望采用IP组播技术来降低系统的带宽消耗。但遗憾的是，在实际环境中，IP组播并不能很好地被支持。不过借助于P2P，IP组播可以有一个替代策略，即应用层组播（ApplicationLayerMulticast，ALM）。它的基本思想是，在应用层，P2P网络的每个节点都充当路由器的角色，将收到的数据转发给其它多个节点。这其实是在应用层构建了另一个“网络层”，或称为PeerOverlay。本文接下来所说的传输中的拓扑结构，也就是PeerOverlay的拓扑结构。在PeerOverlay中，若每个节点最多只有一个上游节点提供数据，称这样的拓扑为单源结构。而与此对应的，若每个节点可以有多个上游节点提供数据，称这个拓扑为多源结构。对单源、多源结构的一个更严格的定义是：P2P网络中，针对某一个频道，将其中的节点抽象为有向图的点，将一个节点向另一个节点提供数据的链路抽象为有向图的边，则形成一个有向图G；如果G中每个点的入度不大于1，称G是单源结构，反之，称G为多源结构。图1给出了不同拓扑的PeerOverlay的例子。在VoD/P2P的早期研究中，大多数的传输拓扑是单源结构的，如树状[4-9]、链状[10]、环状[11]。在P2Cast[9]中，同一频道中到达时间相近的peer组成一个session。在每个session中，server连同这些peer构成一棵应用层的组播树。那些到达时间稍晚的peer，也可以