姓 名： 刘永鹏 专 业： 计算机应用 指导老师：王宗敏 教授 李润知 讲师 P2P VoD资源路由查找算法研究 姓 名： 刘永鹏 专 业： 计算机应用 指导老师：王宗敏 教授 李润知 讲师

报告提纲 课题研究背景及研究现状 1 2 本文的主要工作 3 下一步主要工作

课题研究背景 从2004年开始，基于P2P的网络视频服务逐渐流行，出现了大量的商用直播系统，如Cool streaming、GridMedia、PPLive、PPStream等。 2008年左右，P2P技术在流媒体直播中取得巨大的成功，工业界和学术界将注意力转向另一种更具挑战的视频业务，P2P视频点播服务（P2P VoD）。 2000 左右P2P技术开始兴起，首先在文件共享系统方面的到了应用。 2004年左右出现p2p直播体育、娱乐节目的直播汇总取得了巨大的成功，吸引了大量用户 后来出现p2p点播

视频点播应用现状 思科的统计数据显示2012年90％互联网流量来自视频。 2012年，VoD视频点播次数会达到每月70亿次以上。

视频应用网站

P2P技术在视频应用中的优势 视频应用服务的特点 P2P 技术的优势 耗带宽 高存储 高实时性 分散带宽 节省费用 提高扩展性

P2P VoD应用面临的挑战 点播的最大特点在于用户可以随意跳转，即从当前位置跳转到前面或者后面进行观看。 面临的挑战很多，研究有很多方面，我只说明下与本文研究相关的一个问题， 这也是本文要主要解决的问题：用户跳转后

国内外研究现状 采用分布式哈希表DHT（文献[1, 2, 3]），网络开销大。 Wang Dan等人提出了一种动态跳跃表( DSL )的结构，将观看同一视频片段的节点映射成表中的节点。通过DSL链表确定资源。 Cheng Ben等人提出了一种环形的结构，其中每个节点维持一个同心环，并根据该结构提出快速定位资源的方案。 InstantLeap将视频流沿着时间轴划分成若干个片段，将观看相同片段的节点看成一个组，通过该结构实现数据发现。 Zhang Qian等将有相似兴趣点的节点聚簇，利用节点之间的兴趣相似性，缩短资源查找的时延。 研究总结： 根据前人的研究发现，他们都是在查找模型上做了大量的设计和创新，将P2P VoD松散的网络组织成某种结构，在此基础上实现查找。所以本文沿用这一思想，经过反复的论证后提出了一种可行的双层覆盖网结构的查找模型。 根据前人的研究发现，他们都是在查找模型上做了大量的设计和创新，所提的查找策略也是基于模型的基础上实现的。所以本文沿用这一思想，经过反复的论证后提出了一种可行的双层覆盖网结构的查找模型。 我们按照节点到达系统的时间，把到达时间在同一时间段T内的所有节点聚合成一个覆盖网。

主要工作 本文设计了一个双层结构的查找模型。 根据模型，提出了基于索引路由表的资源查找算法。 论述了算法的理论分析和动态调整策略。

第一部分 双层覆盖网结构的查找模型

P2P VoD 排队服务模型 我们按照节点到达系统的时间，把到达时间在同一时间段T内的所有节点聚合成一个覆盖网

双层结构查找模型描述（一） 节点加入到 VoD 系统是由一个启动引导服务器引导实现的。 启动引导服务器是系统的全局计时器标准，每隔一个时间单位T生成一个播放簇。 节点加入系统时，首先向启动引导服务器发送加入请求。启动引导服务器根据节点到达时间划分P2P VoD网络，即分配一个簇关键字，和有相同关键字的簇邻居节点。 把同一时间段T内到达的所有节点称作一个播放簇。 P2P VoD系统中观看同一部影片的所有节点，按照其到达系统的时间被划分成了多个簇。

假设一部影片的时长为Tm，系统按照T的时间间隔划分到达系统的节点，则系统中会有Tm/T个覆盖网络。 节点加入到P2P VoD 系统是由一个启动引导服务器(Bootstrapping Tracking Server)引导实现的。 引导服务器是系统的全局计时器标准，并每隔一个时间单位T生成一个播放簇关键字。 节点加入系统首先向启动引导服务器申请加入请求，并分配部分有相同关键字的簇首节点和簇邻居节点。

播放位置近似的覆盖网结构优点 提高数据分发的效率 最大化节点之间的服务时间 同一个播放簇内节点之间的播放位置，在整个影片播放过程中始终保持接近。 节点缓存的数据在短时间内会以极大的概率被其邻居节点使用。 最大化节点之间的服务时间 例如：P1，P3间的同步在线时间远大于P1与P18节点间的同步时间，因此P1选择P3作为视频源比选择P18有更长的服务时间保证。 P3 可以持续不断的为P1提供流数据。

内部结构松散，更加适用于节点的动态性 基于邻居列表，播放簇内部是松散的网状结构，当发现某个邻居失效时，可从列表中另选节点。 相比树型转发结构，维护的开销大大降低，而且可靠性仍能保证。 比要维护一个转发树型结构，结构的维护的开销大大降低，而且可靠性仍能保证。

双层结构查找模型（二） 上层设计分布式的簇首索引覆盖网

从每个播放簇中选出一个簇首节点 每个播放簇分配一个关键字Key 为保证每个播放簇的簇首节点的稳定，随机的选择簇内其他节点作为候选簇首节点。 播放簇自产生起，关键字保持唯一不变。 相邻两个播放簇间的关键字相差一个单位，例如若到达时刻为0T – 1T、1T – 2T之间的连个播放簇的关键字分别为Key1、Key2，则Key2 – Key1 = 1。

簇首节点维护邻居簇首列表，指向关键字最接近自身的前一个播放簇与后一个播放簇，即上层覆盖网形成以关键字大小排列的双向链表。

创新点 二层簇首索引覆盖网的创新点： 播放同一部影片的所有节点，播放速率恒定，节点在没跳转或者暂停操作的条件下，各播放簇间的播放位置相对距离保持恒定，因此能保证二次索引结构的稳定性，即保证查找的正确性。 引入簇关键字，将查找时间点转换成查找播放簇，增大查找成功的效率。 减低节点资源发布产生的网络开销。

第二部分 查找路由表

查找路由表 查找路由表结构 查找路由表分为左邻居和右邻居两项。 每项又有索引关键字、目标关键字和邻居簇首节点信息三部分组成。 查找路由表按照簇关键字记录节点信息，其中的第i项记录关键字为Key±2(i-1) （i=1、2、3⋯，0≤ 2 (𝑖−1) <N）的播放簇簇首节点的地址及其他信息。

查找路由表格式举例 簇首节点P11的查找路由表

查找路由表 查找路由表的初始化。 查找路由表规则的维护更新。 由于簇首节点动态改变，需要及时更新路由表。

第三部分 查找过程及算法

跨簇查找查找过程 P2 查找 是先计算K = 7， 发送请求给P1，P1 计算出目标簇关键字k = key1 + k，查找路由表，找到就离目标最近的播放簇P11。然后P11 判断自己簇关键字和目标关键字是否相同，由于不同，重复相同的查找路由表操作，发送给P15，P15查找路由表发送给P17，P17选择一批簇内邻居给P2，P2修改簇关键字，进入到对应的播放簇，P2 从新邻居类表中选择部分节点为其提供数据。

参数设置 播放时间点t，目标播放时间点 𝑡 𝑑 ，当前播放簇的起始时间点 𝑡 𝑠 ，其中t ∈ 𝑡 𝑠 ， 𝑡 𝑠 +T 。∆𝑡 为两个播放点间的时间差。 ∆𝑘为两播放簇簇关键字之差， 𝑘 𝑑 目标播放簇的簇关键词。 关键参数计算 ∆𝑡= 𝑡 𝑑 - 𝑡 𝑠 ，∆𝑘= ∆𝑡 𝑇 ， 𝑘 𝑑 = 𝑘 𝑛 +∆𝑘。

簇内查找过程 播放簇 P1 P5 P4 P10 P2 P11 P9 P3 P6 P13 P12 P7 P8 P3有查找请求，P3计算出K=0， P13 P12 P7 P8

路由表查找算法:

下一步工作 对相关算法的设计评价指标和做对比实验 将通过模拟实验，与InstantLeap， RINDY， DSL方法作对比。 理论分析与评价算法性能。

参考文献 [1] N. Vratonjic, P. Gupta, N. Knezevic, et al. Enabling DVD-like Features in P2P Video-on-Demand Systems[C]. In Proc. of the SIGCOMM Peer-to-Peer Streaming and IP-TV Workshop, August 2007. [2] W. Yiu, X. Jin, and S.H. Chan. VMesh: Distributed Segment Storage for Peer-to-Peer Interactive Video Streaming[C]. IEEE Journal on Selected Areas in Communications, Special Issue on Advances in Peer-to-Peer Streaming Systems, 25(9):1717 – 1731, December 2007. [3] Z. Yin and H. Jin. DHT Based Collaborative Multimedia Streaming and Caching Service[C]. In Proc. of the IEEE International Region 10 Conference, November 2005. [4] D. Wang and J. Liu. A Dynamic Skip List-Based Overlay for On-Demand Media Streaming with VCR Interactions[J]. IEEE Transactions on Parallel and Distributed Systems, 19(4):503-514, April 2008. [5] Cheng Bin, Jin Hai, and Liao Xiao-fei. Supporting VCR functions in p2p VoD services using ring-assisted overlays[C]. Proceedings of IEEE ICC, 2007, 1698-1703. [6] Qiu Xuan-jia, Wu Chuan, Lin Xiao-la, et al. Instantleap: Fast neighbor discovery in p2p VoD streaming[C]. Proceedings of NOSSDAV, 2009, 19-24. [7] H. Guo, J. Liu, Z. Wang. Frequency-Aware Indexing for Peer-to-Peer On-Demand Video Streaming[C]. Proceedings of IEEE ICC, 2010, 1-5. [8] Cheng Bin, Jin Hai, and Liao Xiao-fei. Supporting VCR functions in p2p VoD services using ring-assisted overlays[C]. Proceedings of IEEE ICC, 2007, 1698-1703. [9] Di Wu, Y. Liu and K. Ross. Queuing Network Models for Multi-Channel P2P Live[C]. In Proc. of IEEE INFOCOM, 2009, 73 – 81.

谢谢各位老师和同学 欢迎各位老师和同学指导与指正 谢谢各位老师和同学 欢迎各位老师和同学指导与指正 谢谢各位老师和同学抽时间 听我做报告 欢迎各位老师和同学 指导 指正 指导与指正