一种支持P2P-VoD的层次化搜索模型

1、一种支持P2P-VoD的层次化搜索模型*基金项目：本文研究得到国家973基础研究计划课题2004CB318109、国家863高技术研究发展计划课题2006AA01Z452以及国家自然科学基金60873245，60803085的资助张铁赢，刘悦，程学旗中国科学院计算技术研究所，北京，100190E-mail: zhangtiey摘 要：P2P-VoD中的跳转操作需要高效的节点搜索，如何快速查找到“合适”的节点给我们提出了挑战。“合适”包含两方面因素：1）内容匹配；2）物理性能匹配。而传统的方法大部分只涉及对前者的研究。在本文中，我们提出了一种层次化的搜索模型（简称Mediacoop），不仅可以让

2、搜索到的节点在内容上满足要求，而且在物理性能上也能满足要求。具体而言，Mediacoop首先利用播放距离来索引全部节点，再利用延迟特征优选内容上已经符合要求的节点。在NS2模拟器上的实验表明，Mediacoop在用户体验和系统开销上均优于传统的方法。关键词：P2P搜索；流媒体；层次化搜索 Supporting VCR in P2P-VoD Using Distributed LookupZHANG Tieying, Liu Yue, CHENG Xueqi Institute of Computing Technology, Chinese Academy of Sciences, Beiji

3、ng 100190E-mail: zhangtieyAbstract: A fundamental challenge in P2P-VoD system is how to provide random seeking function. To address this problem, in this paper, we propose Mediacoop, a novel structured lookup service which can find peers to provide required data with good quality. In Mediacoop, we e

4、xploit the unchanged playpoint distance between neighbors to avoid publishing large number of sharing messages. In addition, Mediacoop considers the underlying network in order to find close supplying peers. Theoretical analysis and extensive simulations show that Mediacoop outperforms traditional m

5、ethods with less overhead. 1 引言随着互联网宽带接入的普及，P2P视频点播服务（P2P-VoD）已经成为了最流行的互联网应用之一。点播的最大特点在于用户可以随意跳转，即从当前位置跳转到前面或者后面进行观看。但是，跳转到新位置后，当前邻居很可能没有所需数据，造成了邻居节点的失效。因此，我们的目标是如何快速高效的查找到“合适”的邻居节点来提供数据。“合适”的邻居节点包含两方面特征。一是内容匹配，即该节点拥有查找者所需内容，这一点也是最基本的要求。二是质量匹配，即查该节点拥有较好的物理性能，例如高带宽和低延迟。质量匹配不仅仅是查询优化的问题，它对播放质量起到了至关重要的作

6、用。Y. Huang2，H. Pucha3以及M. Hefeeda7等人均指出，邻居节点的物理性能较差是导致无法及时获得数据的重要原因。衡量物理性能最重要的两个指标是带宽和延迟10，本文中，我们使用延迟作为衡量指标，相关细节在第2节和第3节中给出。通常，针对P2P-VoD的搜索方法只涉及内容搜索。典型的方法是使用分布式哈希表（DHT），把缓冲好的内容所对应的信息发布到网络中等待查询（如文献6 7）。但是，这种方法应用在视频服务中会造成大量的网络开销。因为每个节点缓冲的内容是随着观看进度发生变化的，节点需要不断的发布对应的信息，这就造成了巨大的网络开销。尽管文献7对节点物理性能方面进行了探索，但

7、是它提出的方法并不能应用在P2P-VoD中。文献8 9提出了非DHT的结构化搜索方法以避免大量的网络开销，但是他们都没有对节点的物理性能进行研究。在本文中，针对P2P-VoD的特征，我们提出了一个基于结构化的层次搜索模型（简称Mediacoop）。该方法的一次查找能够同时满足内容匹配和质量匹配的双重要求。具体而言Mediacoop的查找过程被分为两个阶段：第一阶段，我们使用播放点距离来定位拥有所需内容的节点。对于给定影片，各节点的播放速度是相同的，这样，节点间的播放距离是不变的（除非节点进行跳转和暂停操作）。因此，我们避免了传统方法的巨额网络开销；第二阶段，我们把备选节点索引为一个树形over

8、lay（覆盖网），该过程是以AS域间延迟及IP前缀为基础进行索引，其结果是能够找到与查询者延迟最小的节点子集，以完成节点质量匹配。我们在理论上证明了以不低于传统DHT的查找效率O(logN)，Mediacoop能够同时完成上述两阶段查找。我们在NS2模拟器上做了大量对比实验，结果表明Mediacoop在启动时间、跳转延迟、播放连贯度和网络开销上的优势十分明显。2 相关工作P2P-VoD网络一般分为树形结构和网状结构两类。树形结构被较早提出，但是由于树形结构并不适用于动态性很强的P2P网络，目前主要的研究方向集中在网状结构。我们先简单介绍树形结构的已有方法。P2Cast4是一个典型的单播树系统，

9、它使用补丁技术进行数据流分发。然而，在这种分发模型中，一个播放节点只有唯一的父亲节点提供数据，这对于异构网络来说是远远不够的。另外，在动态性很强的P2P环境下维护树形结构是很困难的。作为改进，P2VoD5把分发树组织为层次结构。当节点离开的时候会自动由上层节点替代，新加入系统的节点被分配到最低层。但是，P2VoD并没有提出适合点播的动态交互操作，例如跳转等。作为网络结构上的极大改进，网状结构是目前主要的研究方向。PROP6作为网状结构的代表，以DHT作为基础提供P2P-VoD服务。在PROP中，只要节点获取到一个数据块，它便把该数据块的信息发布到网络中。当节点需要数据的时候，它先去查询DHT获

10、得拥有所请求内容的节点，再向这些节点请求数据。这种方法带来一个严重的问题，在观看过程中，节点收到的内容随播放进度发生变化，这样，节点就要不断地发布新收到的内容信息。这种频繁的更新消息带来了巨大的网络开销。不仅如此，当缓冲区中陈旧数据被丢弃的时候，也要发布相应的删除信息。PROMISE7在节点的物理性能上进行了探索，基于网络带宽提出了一种节点选择方法。在播放过程中，它利用实际传输的媒体数据探测邻居节点可以提供的可用带宽，从而进行节点的优化筛选。但是，这种方法是在节点间建立网络连接后进行数据传输的时候进行的，也就是说此时的资源节点（或称为邻居节点）已经存在，目的是进行节点“选择”而不是“查找”。O

11、BN8减少了上述DHT方法带来的网络开销，它利用节点间缓冲区的重叠关系构建非DHT的结构化overlay。但是，节点物理性能的研究依然没有在OBN中得以实现。RINDY9使用类似的方法构建了一个多环的查找网络。查询者缩小环形范围直至找到候选节点集合，再使用Gossip协议定位拥有所需内容节点。但是，Gossip协议会带来较大的网络开销并且这种方法依然没有考虑节点物理性能上的优劣。时间0该swarm的的播放点为10号数据块.播放距离播放距离24911141031516P1P2P3P28P19节点数据块图 1b 播放点覆盖网Fig. 1b Playpoint overlayP5P6播放时间P0P1

12、4P151289101216561114741315P4P7P8P9P24P19P133P28P1P2P3P14图1a 播放点相同的节点归为同一个swarm Fig. 1a Peers playing the same point are in the same swarm. 3 Mediacoop的详细设计Mediacoop的两大中心任务是：1）如何提供高效的内容查询；2）如何找到网络延迟较低的节点。相应地，Mediacoop的搜索过程分为两个阶段，这两个阶段对应着两个不同的覆盖网。3.1 播放点覆盖网（Playpoint Overlay）本节介绍第一阶段查询的基本思想。第一阶段的目标是内容

13、匹配查询，我们把一部电影分为M个数据块，每一个数据块对应一个播放点。拥有相同播放点的节点被归为同一个swarm（如图1a所示）。对于给定影片，不同节点播放该影片的速度是一样的。因此，正常播放情况下，播放点间的距离是不发生变化的（除非节点进行VCR操作（停止、跳转或暂停）。在第一阶段，我们的想法是利用播放点距离把全部的swarm索引在一个环上（如图1b所示）。这样，任何一个swarm只要建立好索引信息（即路由表），即使在播放过程中，不用再更新索引也可以获知其他swarm当前的状态。请求者可以方便的查找到拥有目标播放点的swarm，整个查找过程类似于著名的Chord网络11，不同之处在于我们使用了

14、播放点距离而不是哈希值。因此，播放点距离的不变性使得节点不需要更新索引信息也能获知其他swarm的状态。这个特性使Mediacoop大大减少了网络开销。3.2 前缀树覆盖网（Prefix-Tree Overlay）第一阶段查询的结果我们称之为种子节点，该种子节点满足内容匹配要求，在第二阶段中，我们的目标是从种子节点出发，找到网络延迟最小的节点子集。实际上，第二阶段查询就是在种子节点所属的swarm中进行的，因为根据第一阶段的查找过程，最后定位的swarm就是种子节点所在的节点集合。因此，如何把swarm内部的节点索引起来是第二阶段的首要任务。因为查询目标是延迟最小，而延迟和AS域的IP前缀又有

15、密切关系10，我们的基本想法是用IP前缀把同一个swarm中的节点索引起来，如图4b所示的索引树。根据全局延迟表得知延迟最小的IP前缀并作为查询目标，再根据图4b所示的索引树便可找到属于目标IP前缀的节点。那么节点间延迟又是如何来获知的呢？首先，我们从边际网关协议公共信息提供处获取BGP路由表及其更新信息，例如从RouteViews （）和RIPERIS（表1 CCDT of CoolFish (时间: 2009.09.02, 15:00)Tab. 1 CCDT of CoolFish (time: 15:00, 2/9/2009)域*延迟域15

16、9.226.40.*202.127.200.*210.72.15.*159.226.40.*031（）（）202.127.200.*31（）058（）210.72.15.（）58（）0接下来，所有的域被组织成二叉树的结构，以前缀码的方式对叶子节点进行编码，每个叶子节点代表一个域。这样，叶子节点的个数K和全部域的个数是相等的。每个叶子节点以其物理地址作为标识（即IP前缀），在表现形式上是其对应的前缀码。叶子节点间的距离由他们前缀码的异或运算得出。在形式上的表示如下： （1）3.4 双层路由表的构建上述两个覆盖网分别对应的是播放点路由表和IP前缀路由表。路由表播放点路由表IP前缀路由表图3 节点的

17、双层路由表Fig.3 Hierarchical figure table(a)(b)IP前缀距离路由节点2021P1(IP:Port), P2(IP:Port)播放点距离路由节点2021P1(IP:Port), P2(IP:Port)播放点路由表：播放点路由表存储了其他swarm播放点的信息。以节点p的播放点路由表为例，该表有logM （M 是数据块的数量）行，第i行（0 i < logM）保存着个节点的播放点信息，该个节点与p播放距离为。播放距离（p1p2）的定义如下：顺时针沿播放点覆盖网（即图1b所示的环）p1到p2的跳数。在形式上表示为： Mod M （2）M是数据块的个数, 是节

18、点pi的播放点。图3a给出了播放点路由表的结构。IP前缀路由表：以节点p为例，其IP前缀路由表存储了和自己所在同一swarm中的其他节点信息。IP前缀路由表有logK (K 是叶子节点的数量) 行。第j行（0 j < logK）保存着个节点的IP前缀信息，该节点与p的前缀码距离为。该距离的计算方法如公式（1）所示。图3b给出了IP前缀路由表的结构示意图。3.4 查找过程Swarm is indexed by peer IP prefixes0011210.77.*00001111202.112. *P13P16P17P14P15这个域的IP前缀为 159.102. *Destinatio

19、nP5P6P7P4播放时间P0P1312389101216561114741315P1P2P3P8P9P19P15P14P24P28节点数据块图4b 第二阶段查找Fig. 4b The second stage lookup图4a 第一阶段查找Fig. 4a The first stage lookup内容匹配查询：即在播放点覆盖网中进行的第一阶段查询。该查询过程为递归方式，描述如下：查询发起者P发出内容匹配查询消息，当节点A收到该消息，它首先根据公式（2）计算自己与目标数据块的距离D，然后该节点从自己的播放点路由表中选出与D最近的节点B并把该查询消息转发给B。该查询结束的条件为：1）发现节点

20、C的距离等于D，此时节点C作为种子节点被返回；或2）已没有更近的节点可以转发，此时当前节点作为种子节点被返回，如图4a所示。质量匹配查询：即从第一阶段获得的种子节点出发，在IP前缀覆盖网中进行的第二阶段查询。查询目标是发起者P的CCTD中延迟最小的域，然后发起者P 向种子节点发送查询消息。种子节点从自己的IP前缀路由表中找到距离目标最近的节点，并向其转发查询消息。转发节点递归的进行上述操作直到没有更近的节点进行转发（注意这里和上述结束条件不同，我们的目的是获得更多的节点）。在查询过程中，任意符合要求（IP地址和目标IP前缀一致）的节点都将被返回。如果最后仍没有返回任何节点，那么发起者P会要求种

21、子节点随机的返回在同一swarm中的节点即可，因为这些节点虽然没有最低的延迟，但是在内容上都是满足要求的，如图4b所示。4 理论分析及实验结果4.1 理论分析在本节中，我们分析Mediacoop的查找效率。因为该方法涉及到两阶段查找，我们可以建立如下分析模型： 是总的查找跳数，和分别是第一阶段和第二阶段的查找跳数，M是数据块的数量，K 是域（即叶子节点）的数量。我们首先分析第一阶段的查找效率。Mediacoop是一个结构化的搜索方法，其搜索过程类似传统的DTH方法，例如Chord。但是，我们使用的是播放点而非节点标识来建立索引。因此，我们方法的效率不是传统DHT方法的O(logN)，而是和播放

22、点覆盖网对应的环上的播放点数量紧密相关的（即数据块数量M）：这里，N 是网络中全部节点的数量。总的来说，对于流行的P2P系统，节点的数量是十分庞大的，而一部影片的数据块的数量却是相当有限的。举例来说，根据我们实际经验，对于时长为2小时的电影，720个数据块就足矣了。也就是说，M << N，因此我们有：在第二阶段，搜索过程实际上是在二叉树上的折半查找。因此，第二阶段的查找效率和折半查找的时间复杂度一致：这里，K 是域的数量。第二阶段的搜索过程在一个较小的范围中进行的，即第一阶段的目标swarm。而平均来看，全部节点是均匀分布在每个数据块中的，即每个swarm的节点个数 n = N/M

23、。这样，K 小于或等于n，K取最大值n的条件是每个域正好只有一个节点。因此，Mediacoop总的搜索效率为：即：也就是说，我们在不低于传统DHT一次查询的效率下，可以进行两阶段查询，既满足了内容上的要求，也在物理性能上得以提升。4.2 评价指标及实验参数P2P-VoD的评价指标分为两个方面：一是用户体验，二是系统扩展性。前者主要指启动时间、跳转延迟和播放连贯率；后者是服务器压力和网络开销。在本文中，我们对以上几点均进行验证。除此之外，我们还对搜索跳数进行了实验对比。我们把Mediacoop分为两个版本进行验证，第一个是单纯的内容搜索，不具备延迟探测，即第二阶段没有搜索，取而代之的是使用Gos

24、sip协议定位节点（该版本简称Mediacoop(no-DA)）；第二个版本是两阶段都有（简称 为Mediacoop(DA)）。为了和目前较为流行的方法进行对比，我们实现了具有代表性的基于DHT的P2P-VoD系统PROP 6。限于本文讨论的内容，我们没有实现PROP中的中心服务器功能。同时，我们实现了传统的“缓存转发”系统P2VoD5进行对比 P2VoD没有跳转功能，在实现中我们对其加入了此项功能。我们的对比试验是在NS2模拟器上进行的。电影时长设置为3600秒，码率为500Kbps，一个数据块对应的播放时长为10s。我们使用拓扑结构生成器GT-ITM 13生成了典型的transit-stu

25、b网络，其包含了860个路由器，并随机选择100个stub节点作为域的分隔节点 GT-ITM本身不能够区分transit节点和stub节点，我们在GT-TIM源码基础上开发了工具进行分离。每个stub节点之间的延迟为10ms60ms。同时生成8,000个节点以均匀分布的方式依附于每个域上。整个实验分为12组进行，对应的节点数量从100到8000不等。节点的加入以指数递减的方式进行18： 是初始加入速率，为扩散参数。相应地，我们设置节点平均加入时间间隔为5秒，平均在线时间为1800秒。下载带宽为1Mbps上行带宽可以支持2个并行流。启动和跳转时的缓冲数据量为能够播放5秒钟的数据。模拟试验程序运行

26、在我们的超级计算机Dawning 4000A上，总共运行时间为4天。图6 控制信息开销随节点数的变化Fig. 6. Control overhead 图10 跳转延迟变化情况Fig. 10 Seek latency图7 服务器压力随节点数的变化Fig. 7 Sever stress图5 平均跳数随节点数的变化Fig. 5 Average number of hops图8 启动时间变化情况Fig. 8 Startup time图9 播放连贯度变化情况Fig. 9 Playback continuity 4.3 实验结果1 平均跳数：在本项指标中，因为我们验证的是搜索到目标所进行的跳数，是针对结构

27、化搜索方法的，因此并不涉及P2VoD。图5 给出了12组实验对应的平均跳数的实验数据。从结果可以看到，PROP体现了典型的基于DHT方法的“logN”法则，而Mediacoop两个版本的表现均强于PROP。虽然我们看到Mediacoop(no-DA)跳数少于Mediacoop(DA)，那是因为前者没有第二阶段的搜索过程。2 网络开销：网络开销主要是指控制信息的数量，因为P2VoD是树形结构，并非网状，因此在本项指标中也不考虑P2VoD。如图6所示， PROP在三者的比较中表现最差，因为它要不断的发布和删除内容信息，导致了大量的控制消息。Mediacoop(no-DA)的网络开销虽然强于PROP

28、但是要比Mediacoop(DA)大的多，因为它在第二阶段使用了Gossip协议，也带来了大量的控制信息。相比之下，Mediacoop(DA)能够减少4070%的网络开销。3 服务器压力：在实验中，有一个具备1000Mbps上能力的内容服务器。如果一个节点没有及时收到其请求的数据，它就立即向内容服务器请求数据。从图7 可以看到，对于Mediacoop(no-DA)，它的压力要大于Mediacoop(DA)，因为Mediacoop(no-DA)没有第二阶段搜索，得到的节点延迟较大，造成了请求数据不能及时到达。对于PROP随着数据缓冲区的不断更新，被抛弃的数据没有来得及更新，对这些数据的请求自然不

29、能得到满足，造成了更大的服务器压力。而在P2VoD中，服务器压力是最大的并且是线性增长的。这是因为它是树形的组织结构，而上层节点的离开会造成它所有孩子节点缺失数据。4 播放连贯率： 图9显示了网络规模为4000个节点时，播放连贯率随时间的变化。Mediacoop的表现要远远好于RROP和P2VoD，其原因和服务器压力一节中的相同。除此之外，PROP这种基于DHT的方法必须要等到整个数据块都接收完成后才能发布信息，这样势必造成数据共享效率的低下。5 启动和跳转时间。这两个指标涉及到两部分的性能表现，一是查找速度，二是请求数据的速度。实际上，前者就是第一项评测指标搜索的平均跳数；而后者决定于搜索到

30、的节点的质量。Mediacoop(DA) 能够找到最近的节点，从而保证了请求的数据能够快速到达。图8和图10给出了实验结果。可以看到，对于5秒的数据缓冲区，Mediacoop(DA)平均只需要3.5 秒的启动时间和2秒的跳转时间。5 结论及下一步研究节点搜索对于P2P-VoD系统是十分重要的，而最理想的搜索结果是既能满足内容匹配，又可以实现节点质量匹配。本文中提出的层次化搜索模型Mediacoop已经初步达到了上述目标。它使用了层次化的双结构模型，在内容查找阶段可以避免传统方法中大量的网络开销，同时又可以查找到具有最低网络延迟的节点集合。在理论分析上，我们证明了在小于O(logN)的情况下，就

31、可以完成两个阶段的搜索过程。由实验结果可以看到，Mediacoop在用户体验以及系统扩展性上均好于其他方法。下一步，我们将在真实的CoolFish系统中进行更深入的实验分析。参 考 文 献1 .2 Yan Huang, Tom Z. J. Fu, Dah-Ming Chiu, John C. S. Lui, Cheng Huang, “Challenges, Design and Analysis of a Large-scale P2P-VoD system”, Proc. ACM SIGCOMM 08, August 2008.3 H. Puc

32、ha, D. G. Andersen, and M. Kaminsky, “Exploiting Similarity for Multi-Source Downloads Using File Handprints”, Proc. NSDI07, 2007.4 Yang Guo, Kyoungwon Suh, Jim Kurose, and Don Towsley, “P2Cast: Peer-to-peer Patching Scheme for VoD Service,” Proc. International WWW Conference, 2003.5 T. Do, K. A. Hua, and M. Tantaoui, “P2VoD: providing fault tolerant video-on-demand streaming in peer-to-peer environment”, Proc. ICC04, Jun. 2004.6 Lei Guo, Songqing Chen, Shansi Ren, Xin Chen, and Song Jiang. "PROP: A Scalable and Reliable P2P Assisted Proxy Streaming System", Proc. ICDCS'04, Ma