（计算机软件与理论专业论文）p2p点播流媒体服务质量研究.pdf

西北大学博士学位论文 摘要 音频、视频内容分发代表了h l t e m e t 中一类重要的应用，但目前还没有满意 的解决方案。传统的c s 模式中服务器很容易成为系统瓶颈，口组播由于难以 实现可靠组播和拥塞控制等限制短期内难以在i n t e m e t 上得到广泛实施，而内 容分发网络( c o n t e n td e l i v e 巧n e t 、o r k s ，c d n ) 因费用昂贵而难以推广。研究和 应用实践表明，p 2 p ( p e * t o - p e e r ，对等网) 流媒体技术能够利用普通节点的资 源为其它节点提供服务，在不改变现有网络配置的前提下具有良好的性价比，因 而是一种具有广泛应用前景的流媒体分发方法。但由于p 2 p 流媒体系统中p e e r 节点服务能力的异构性、节点的动态性以及流媒体本身的特殊性，如带宽资源占 用高、服务持续时间长、对播放的时限和顺序有严格要求等，使得p 2 p 流媒体 分发技术面临诸多挑战。针对大规模流媒体分发服务需求，提供具有高扩展性和 q o s ( q u a l i t yo f s e i c e ，服务质量) 保障的p 2 p 点播流媒体分发服务，已经成为当 前流媒体分发技术研究中的一个重要课题。 本文围绕上述背景对p 2 p 点播流媒体分发技术进行了深入研究，并提出了 有效的解决办法。 首先针对q o s 敏感的覆盖网络构建问题，提出了一种两阶段节点选择算法 t s p s ( t w o s t a g ep e e rs e l e c t i o na l g o r i t h m ) 和一个基于多解析环结构的r n l s ( 硒n g - b a s e dn e 俩o r kl o c a t i o ns e i c e ) 节点定位方案。其中t s p s 算法在选择 提供节点时同时考虑了保证数据可用性和流媒体q o s ，即根据播放位置查找候选 提供节点后，再根据节点的网络临近性、可用带宽和丢包率等q o s 度量参数筛 选出合适的提供节点。r n l s 节点定位方案采用了半径指数增加的多解析环结构 来快速定位节点，有效支持v c r ( d e 0c a s s e t t er e c o r d e r ) 操作。节点间的信 息交换采用了基于闲谈的方式。 由于节点的服务能力有限，在实际应用中往往需要多个节点才能为单个节点 提供流媒体数据服务。设计一个多源流机制的基本挑战是节点的可用带宽未知， 而且可能在一个会话期间发生很大的变化。考虑到节点的异构性，本文研究了如 何在多个提供节点之间最优地进行带宽分配，其目标是使在播放期限之前收到的 数据块的优先级最高。为此分别提出了基于纯拉的调度算法m s s ( m u l t i s u p p l i e r 西北大学博十学位论文 s c h e d u l i n g ) 和基于推拉结合的调度算法p p m s s ( p u s h p u l lm u l t i s u p p l i e rs c h e d u l i n g ) 。 视频文件通常都很大且对传输有紧迫的q o s 要求，很多对等节点可能无法 存储整个视频文件以应对网络抖动并为其它节点提供服务。本文形式化了p 2 p 视频点播系统中服务质量敏感的复制问题，其目标是在满足所有节点数据获取最 后期限的同时使请求块的成功率最大。为此提出了一个新的缓存机制，包括一个 前摄算法和一个缓存替换算法。特别地，定义了数据块的紧迫等级d e 和贡献度 d c ，并将这两个指标用在提出的前摄算法和缓存替换算法中以确定应该请求或 替换哪些块。 p 2 p 流媒体系统的丘e er i d i n g 现象会带来系统性能的严重下降。本文针对p 2 p 流媒体网络中的仔e er i d i n g 问题提出了一个基于响应度的激励机制g b i m ( r e s p o n s i v i t y b a s e dh l c e n t i v em e c h a l l i s m ) ，其目标是根据节点的贡献提供差别 服务，同时最大化系统效用。g b 蹦使用一个两阶段排序法对请求节点进行排序， 并依据顺序优先分配带宽。 通过对仿真试验结果的比对分析，表明上述算法和机制性能良好。本文的研 究工作为推动p 2 p 点播流媒体的发展与应用提供了良好的理论和实践参考。 关键词：p 2 p 点播流媒体；服务质量；节点选择；调度策略；缓存机制；激 励机制 i i 西北大学博士学位论文 图表目录 图1 1 传统的c s 结构( 单播) 3 图1 2 基于组播的内容分发4 图1 3 基于代理的分发架构5 图l 一4 使用c d n 提供流媒体服务5 图1 5 典型的p 2 p 流媒体系统6 图1 6 点播流媒体分发中的异构性和异步性8 图1 7 链式结构9 图1 8 树状结构1 0 图1 9s p l i t s t r e 锄的多树结构11 图l 一1 0 网状结构1 1 图2 1 集中式覆盖网络2 0 图2 2 分布式覆盖网络。2 1 图2 3 混合式覆盖网络2 1 图2 4 典型的p 2 p 点播流媒体系统2 3 图3 1 拓扑不匹配问题的一个例子3 1 图3 2 节点发现和节点选择机制的相互关系3 5 图3 3 环状结构3 6 图3 4 新节点获得初始邻居列表3 7 图3 5 和邻居列表中的邻居建立连接3 8 图3 6 播放位置调整3 9 图3 7 仿真中使用的部分拓扑4 2 图3 8 不同覆盖网构建方法下的服务器流数4 3 图3 9 不同覆盖网构建方法下的启动延迟4 3 图3 1 0 不同覆盖网构建方法下的吞吐量4 4 图3 1 1 不同覆盖网构建方法下的消息总数4 4 图4 一l 典型的多节点协同调度策略4 7 v 西北大学博士学位论文 图4 2 纯拉方式下的一跳延迟5 7 图4 3 纯拉、纯推和推拉结合方式的比较一5 9 图4 4 不同调度算法下的服务器压力6 0 图4 5 不同调度算法下的启动延迟6 1 图4 6 不同调度算法下的回放连续度6 1 图5 1 优化存储问题的贪婪算法6 8 图5 2 不同方案的缓存快照7 0 图5 3 视频文件区域划分7 2 图5 4 不同缓存机制下的服务器负载7 8 图5 5 不同缓存机制下的回放完整性7 9 图5 6 不同缓存机制下的跳转延迟7 9 图6 1 节点的两种角色8 8 图6 2 不同模式下的系统效用9 2 图6 3 不同模式下的节点平均吞吐量9 3 表1 1 不同流服务策略的特点6 表3 1t s p s 算法中的符号定义3 3 表3 2 闲谈消息的结构一4 0 表4 1 调度算法建模中用到的定义一51 表6 1p 2 p 流媒体系统的主要激励机制比较8 5 表6 2 观察计数器8 8 v i 西北大学学位论文知识产权声明书 本人完全了解西北大学关于收集、保存、使用学位论文的规定。 学校有权保留并向国家有关部门或机构送交论文的复印件和电子版。 本人允许论文被查阅和借阅。本人授权西北大学可以将本学位论文的 全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫 描等复制手段保存和汇编本学位论文。同时授权中国科学技术信息研 究所等机构将本学位论文收录到中国学位论文全文数据库或其它 相关数据库。 保密论文待解密后适用本声明。 学位论文作者签名： 曼植指导教师签名： g 年莎月如日 加铲伽日 西北大学学位论文独创性声明 本人声明：所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究 成果。据我所知，除了文中特别加以标注和致谢的地方外，本论文不包含其他人已经 发表或撰写过的研究成果，也不包含为获得西北大学或其它教育机构的学位或证书而 使用过的材料与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确 的说明并表示谢意。 学位论文作者签名：夕星碰 湖8 年6 月如日 西北大学博士学位论文 1 1 引言 第一章绪论 随着n e n l e t 的日趋普及和信息传输技术的快速发展，h l t e m e t 上传输的内容 已逐渐由单纯的文字传输转变为包含文本、音频、视频的多媒体数据传输。这样 的改变不仅使h l t e m e t 使用者能获得更为丰富多样的信息，同时也代表着多媒体 网络时代的来临。 传统的分布式多媒体系统主要使用客户端服务器( c s ) 模式，所有的用户 都从服务器处获取资源。由于流媒体服务具有高带宽、长持续时间等特点，在这 种模式下，一方面随着客户数目的快速增加，服务器的资源如带宽很快就被消耗 完，成为系统瓶颈；另一方面长距离数量众多的网络连接也可能导致网络的拥塞。 和其它传统的网络服务相比，基于c s 模式的流媒体系统无法提供较好的q o s ( q u a l i t yo fs e n ，i c e ，服务质量) ，无法满足大范围实时流媒体应用的性能要求， 尤其表现在可扩展性、适应性、容错和鲁棒性等方面。为了解决这些问题，研究 者们提出了相应的解决办法：如p 组播技术和c d n ( c o n t e md e l i v e 巧n e 铆o r k s ， 内容分发网络) 。p 组播需要在网络上大范围部署支持组播的路由器，而且p 组 播本身存在种种限制，如很难实现可靠性组播和拥塞控制等，使p 组播技术并 没有得到广泛的应用。而内容分发网络则需要在网络边缘部署大量c d n 服务器。 这种方案成本较高，并且也只是部分地解决了可扩展性问题，因为c d n 服务器 很有可能成为新的系统瓶颈。 近年来兴起的对等网络( p e * t o p e e r ，p 2 p ) 技术无论在学术界还是业界都得 到了极大的关注。在对等网络中，各个节点进行对等计算，每个对等实体既是服 务的提供者，又是服务的享用者，充分挖掘了h l t e m e t 上的空闲资源，在利用率、 扩展性、容错能力等方面具有潜在的巨大优势，并在文件共享、分布式计算、协 同工作、h l t e m e t 存储等方面己经成功应用。但是，不同于一般的文件共享，流 媒体本身有其独特性质，如数据存储量大、带宽占用高、持续服务时间长、q o s 要求高等。虽然近几年学界和业界对p 2 p 流媒体系统进行了大量研究，但针对 西北大学博士学位论文 具有大规模用户数的高并发流媒体分发服务需求，当前己有的分发技术和方案在 系统可扩展性、可靠性和经济性方面均存在尚未解决的难题。 因此，在面对大规模流媒体分发服务需求时，如何提供扩展性高和有q o s 保障的流媒体分发服务，并降低系统的部署成本，已经成为当前流媒体分发技术 研究中的一个重要课题。 在p 2 p 流媒体内容分发研究过程中，提供服务的p e e r 节点服务能力的异构 性、节点的动态性以及流媒体本身的特殊性，如带宽资源占用高、服务持续时间 长、对数据的播放有较为严格的时限和顺序要求等使p 2 p 流媒体分发技术面临 更多的挑战。 首先，典型的宽带接入技术诸如a d s l 和线缆调制解调器有限的上行传输 能力只允许以限定的速率传输所需视频的一部分，因此当分发带宽需求大的内容 时并非所有的参与节点都能成为贡献源；选择哪些节点作为一个节点的提供节点 直接决定该节点获取所需数据的可能性；第二，流媒体不仅要求以到达速率回放 视频帧，而且一旦回放就要丢弃视频帧。由于用户的缓存内容在不断地变化，因 此节点的缓存管理方案应该能够捕获视频帧可用性的动态本质。第三，视频帧需 要被顺序和周期性地传输以确保平滑回放。但由于节点行为的不确定性，例如节 点在视频服务中突然加入或退出，可能导致视频帧到达延迟，因此需要一个视频 分发方案，能使分发源丢失的影响最小化。第四，系统中的自私节点可能使设计 良好的系统性能降低。为了支持上述功能，需要一个有效的和鲁棒的p 2 p 流媒 体网络架构。 1 2 研究背景 1 2 1 典型的流服务策略 典型的流媒体系统将视频节目存储于一台或多台服务器，接受用户请求，并 通过网络将节目内容传递给各用户。流媒体业务可在不同的网络平台上提供，如 驻地网、a t m 网、c a t v 网或者因特网等。与w w w ，f t p ，e m a i l 等一般数据 业务相比，流媒体业务需要为每一个用户提供一段较长时间的稳定视频流。该视 频流占用的网络带宽高，且要求网络的抖动较小，因此对承载网络提出了很高的 要求，如开始延迟、播放质量、v c r 交互操作、可扩展性等1 。 西北大学博士学位论文 传统的流媒体c s 单播模式是采用一个连接到i n t e m e t 的带宽高、服务能力强 的服务器。这种方法简单且易于管理，但可扩展性和可靠性的问题是显而易见的。 可靠性的问题来自只有一个实体服务所有用户，单点失效的问题是致命的；可扩 展性的问题是增加更多的用户时需要给服务器增加与之相称的大量资源。这种中 心化的方法还有两个关键但不是很明显的缺陷：高花费和主干网络的负载。图1 1 描绘了一个简单的视频点播系统架构。一个连接到h t 锄e t 的视频服务器作为视 频源。当一个客户想看一个电影时，它和服务器相连接，服务器给该客户传送请 求的视频。在这种情况下，即使服务器有1 g b p s 的带宽，它也只能以3 0 0 i 厂b p s 的 流速率支持近3 0 0 0 个客户。 图1 一l 传统的c s 结构( 单播) 研究表明，由于人类行为的固有特征，绝大多数的用户请求都集中在少数的 热门影片，而且由于用户数量巨大，同一时间点播相同视频节目的可能性就高， 因此可以利用基于口组播技术的策略来设计流媒体系统，以节省网络带宽，提高 系统容量。采用p 组播技术的流媒体系统一般使用静态或动态服务器调度方案， 大致分为以下几类：周期广播( p 舐o db r o a d c a s t i n g ) 方式卜1 、批处理( b a t c h i n g ) 方案 ( 3 1 、补丁( p a t c h i n g ) 方案【4 1 、p i g g y b a c k 方案5 1 和流合并方案6 1 等。 在口组播中，组播树建立在路由器上，路由器作为组播数据的分发节点，因 此具有很高的效率和可扩展性。然而，口组播改变了传统互联网基于单播的设计 原则，而且与其相关的一些问题比如组播成员管理、组播拥塞控制、组播计费机 制等至今并未得到很好的解决。因此，p 组播一直没有在互联网上得到大规模的 3 西北大学博士学位论文 部匿衣t霉蒂蓁譬垦匣 磐窿参蠹磊塑垂萎墓錾霎霾萋蓁辇鋈氮黼雾翳懿篓妻；囊丽葺羹酣菖葚奏 薹瑶垣嘲缵幽。霎苓珊害舍f i 姜螽鍪勤割为稚谤壤孺噌气涕蓁篓；堇编雾一匪 娶些霎薹薹雾戥雕塑型酗掣莩翥甏羹鞋j 葡矧囊心杉彭俩蓁蓁藿篓。冀押蠢翥 誉昆劈i 喜；霎；薹鸶咝丑蠹e 剃裂雨# 蒸曜霎纠弊旦直播系统已经先于p 2 p 点播实现大规模的应用。 已有的研究根据p e e r 节点逻辑拓扑组织将p 2 p 流媒体系统分为两大类：基于 树型和基于网状的系统。基于树型的系统又分为基于单棵树和基于多棵树的系 统。下面讨论基于单树、多树和网状的p 2 p 点播的内容分发模型及其代表性系统。 ( 1 )单棵树分发 c h a i n i n g 【1 7 】是最早把p 2 p 思想引入视频点播的服务模型，所有请求同一部影 片的节点按照到达的顺序串联成一条链状结构，这实际上是树状结构的极端情 况。在节点链中，前面的节点在缓冲区保存一部分已经看过的视频片断，为后面 的节点提供服务。后到的请求是否可以得到前一个节点的服务，取决于两者到达 西北大学博士学位论文 图1 3 基于代理的分发架构 内容分发网络是代理服务思想的发展【1 1 1 3 1 。c d n 依赖于一组物理上分布的 代理或网关。如图1 4 所示，媒体流缓存在复杂的代理服务器上，这些服务器是 事先部署的。这些代理服务器连接到一个覆盖网络上，当用户请求一个视频流时， 由最近的代理服务器而非视频源处理该请求。这种方案可以提供大范围的流服 务，但其部署和维护费用对于小的内容提供者来说太昂贵了。 图1 4 使用c d n 提供流媒体服务 c s 构架存在服务器瓶颈效应，p 组播难以实现，c d n 方式代价昂贵，使得 更多人开始研究p 2 p 在流媒体中的应用。在p 2 p 网络中，每个p e e r 节点首先要从其 它节点获得服务，其次还要为网络中的其它节点提供服务，一般还要具有一定的 路由和查询功能。p 2 p 最大的优势在于不必改变传统的网络结构，在现有i n t e m e t 层次模型上，只需改动应用层的分发和路由策略，就可以相对c s 模式大幅度提 西北大学博士学位论文 高扩展性，且易于实现，代价是整个网络的负载增加。这些增加的负载大部分是 平时闲置的节点上行带宽。此外，p 2 p 流媒体还存在播放质量无法保证、v c r 交 互操作实现困难等问题。图1 5 显示了一个典型的p 2 p 流媒体系统。 p i 图1 5 典型的p 2 p 流媒体系统 表1 1 列出了4 种流服务策略的特点。 表1 1 不同流服务策略的特点 对性能的影响可扩主要挑战 启动延迟播放质量v c r 操作 展性 c s 模式 低保证 支持 小服务器负载( 可扩 展性) 邛组播 高 保证实现困难 大 要求所有路由器支 持 代理模式 低 保证实现困难小部署和维护代价昂 ( 含c d n ) 直 贝 p 2 p 模式和方案有关不保证实现困难大节点的动态性和异 构性 1 2 2p 2 p 流媒体的分类 流媒体应用根据内容源的不同可以分为两大类：1 ) 实时流节目直播；2 ) 预 保存节目点播。实时流直播是指实时信号( 电视、卫星信号等) 通过网络实时传 送到用户端的业务；预先保存节目点播是指用户根据自己的兴趣点播预先保存的 6 西北大学博士学位论文 节目源，这种节目并不会随着时间的变化而改变。在p 2 p 流媒体系统中，这两种 应用分别简称为p 2 p 直播和p 2 p 点播。 p 2 p 直播和p 2 p 点播在实现策略上存在着区别，这是由这两种业务的不同而 造成的： 1 ) 点播的资源数目：p 2 p 点播有较多数量的影片供点播，p 2 p 直播的频道数较少， 用户有可能长时间观看。 2 ) 内容源：p 2 p 点播已知要播放的全部内容，可以安排调度播放的内容，而p 2 p 直播内容一般未知。 3 ) 用户观看要求：p 2 p 直播随到随看，各个用户间的观看内容基本保持一定程 度的同步；而p 2 p 点播用户可以从一部影片的任何部分开始观看，这减少了 数据块共享的机会，加剧了节点提供能力的异构性。 4 ) 对端到端延迟的敏感程度：p 2 p 点播只要满足播放要求，并不要求实效性， p 2 p 直播对与内容源的时间同步要求较高，如观看现场直播节目。这个区别 暗示着点播系统的拓扑可以不受距离视频源的跳数限制。 5 ) 交互操作：p 2 p 直播一般只提供播放和停止操作，而p 2 p 点播存在各种交互式 操作，例如跳转等，这一方面导致了拓扑的频繁改变，另一方面在q o s 没有 保障的情况下，用户有可能停止一段时间等缓冲结束后再继续观看，这增加 了用户离开的可能性，因此系统的动态性比直播系统更大。 其中影响两种系统设计策略的最本质的差别是节点需求的异构性和对v c r 的支持。图1 6 给出了点播流媒体分发中的异构性和异步性。 7 西北大学博士学位论文 图1 6 点播流媒体分发中的异构性和异步性 本文关注p 2 p 点播流媒体系统。 1 3 相关研究现状 1 3 1p 2 p 点播流媒体系统研究现状 最早的p 2 p 与流媒体技术的结合产生了p 2 p 直播系统，分发模式从传统的树 型分发，如z i g z a g ，发展到现在基于g o s s i p ( 闲谈) 的纯网状分发，如 c 0 0 1 s t r e a m i n g 1 5 1 和a n y s e e 1 们。直播系统已经先于p 2 p 点播实现大规模的应用。 已有的研究根据p e e r 节点逻辑拓扑组织将p 2 p 流媒体系统分为两大类：基于 树型和基于网状的系统。基于树型的系统又分为基于单棵树和基于多棵树的系 统。下面讨论基于单树、多树和网状的p 2 p 点播的内容分发模型及其代表性系统。 ( 1 ) 单棵树分发 c h a i n i n g 【1 7 】是最早把p 2 p 思想引入视频点播的服务模型，所有请求同一部影 片的节点按照到达的顺序串联成一条链状结构，这实际上是树状结构的极端情 况。在节点链中，前面的节点在缓冲区保存一部分已经看过的视频片断，为后面 的节点提供服务。后到的请求是否可以得到前一个节点的服务，取决于两者到达 时间的间隔，如果这个时间长于前面节点的缓冲区大小，就无法形成一条连续的 链，还需要直接到服务器获取资源。在链式节点的策略中，节点的加入过程如图 1 7 所示，设缓冲区窗口为5 s ，新加入节点e 要先到服务器进行资源定位，由于它 与链尾节点的到达时间相差在缓冲区窗口内，可以直接接到链尾，否则，服务器 西北大学博士学位论文 要产生另一条视频流。 图1 7 链式结构 为了能够形成一条较长的链，可以有几种改进措施，例如，g 1 0 v e 【1 8 】采用 p a t c h i n g 【1 9 】+ c h a i m n g 的策略，链上节点可能丢失的影片开头部分可以从服务器获 得；a c v o d 【2 0 】利用空闲节点，将原本属于不同链的节点或者不能连接到链的节 点最终加入到同一条链，并增强链的稳定性。 在所有节点策略相同的情况下，链的层次越深，这就意味着节点的中途离开 造成的影响越大。而且，现在的i n t 锄e t 不能保证对一对一大流量稳定的视频传 输的支持。因此，链式结构只能够支持局域网内的小规模应用。 典型的采用树型结构的p 2 p 点播流媒体系统中系统有d i r e c t s 仃e 锄犯1 1 ， p 2 c a s t 【2 2 】等。为了减小上层节点失效或离开对下层节点的影响，可以通过减少层 次来实现。在带宽和计算能力允许的情况下，增加每个节点所带的子节点，而且 尽量保证上层节点的稳定性。 以p 2 c a s t 为例，它是在d i r e c t s t r e 锄的基础上改进的，节点按照到达的时间 加入一棵应用层组播树，如图1 8 所示。新节点加入组播树时，选取与自己到达 时间较为接近的节点作为提供节点，这个节点有可能已经把最开始的一部分内容 抛弃，即它们到达时间的间隔已经超过缓冲区的大小，如果采用d i r e c t s t r e 锄策 略，该节点就无法成为新节点的提供节点。但在p 2 c a s t 策略中，如果这个时间间 隔没有大于一个所谓p a t c h i n g 窗口的大小，新节点仍然可以从提供节点获取视频 流，同时还需要从其它拥有开头部分节目的节点处获得该部分内容，即需要寻找 9 ) ) ) ) 西北大学博士学位论文 一个p a t c h i n g 流的提供节点。这样能使更多的节点加入到组播树中，减少了服务 器新开组播树的数量，并且能够均衡负载。 图1 8 树状结构 单棵树分发存在着许多问题，例如：1 ) 所有的叶子节点都没有承担转发负 载，这就会使非叶子节点的负担过重，有可能成为网络中的新瓶颈；2 ) 对网络 性能的要求很高，不适合于大规模的应用；3 ) 在节点中途退出的情况下很难实 现无缝播放；4 ) 实现v c r 操作有困难等。 ( 2 ) 多树分发 本着公平性的目的，即每个节点应该传输和它接收同样多的流量，产生了多 路径树协议。其思想是构建n 棵不同的分发树，将媒体内容分为n 部分，每部 分在不同的树中传播。重点是把每个节点放置在不同树的不同层。挑战是如何将 一个节点作为一棵树的内部节点同时又是所有其它树的叶子节点。 s p l i t s t r e 锄【2 3 1 是基于多棵树的、可用于分发大文件和流媒体的协作架构。它 构建在s c m e f 2 4 】协议上，s c 曲e 是一个建立在以p a s t 一2 5 】为查询基础结构上的发布 一订阅系统。利用p a s t r y 的特点，s p l i t s 仃e 锄中每个节点只转发一棵分发树的数 据，而接收其它分发树的数据，将转发数据的任务均匀分布到所有节点中，使系 统的容错性进一步提高。但是在s p l i t s t r e 锄中，空闲的节点可能需要为其它节点 转发自己不感兴趣的视频流。类似的策略有c o o p n e t 3 0 1 等。图1 9 给出了 s p l i t s t r e 锄的多树结构。 l o 西北大学博士学位论文 议，其命名也因此而来。数据分发采用接收者驱动模式，即接收者主动搜索感兴 趣的内容，向拥有这些内容的节点请求下载。这种方式类似于传统的p 2 p 文件下 载方式。 基于g n u s t r e 锄的策略，p r o m i s e 提出了新的应用层组播策略，称之为 c o l l e c t c a s t 。p r o m i s e 的底层网络可以是任何已有的p 2 p 网络，作者选择了p a s t r y 作为其底层的结构。u d p 传送数据包，t c p 传送信令。在选择最优的提供节点时 采用了拓扑感知技术，把网络的状况作为选择的依据。通过底层网络得到候选资 源节点的集合。集合中的每个节点有两个属性：带宽速率和有效性。在这个集合 中找到速率期望值最高而且能够满足需要的集合，确定活动集合。在播放过程中， 还需要不断监测网络节点的状况，包括丢包率和传送速率，淘汰掉不适合的节点， 更新活动集。这种方法的缺点也是很明显的，需要了解很多底层参数，算法复杂 度高。 目前有大量的研究工作集中在网状结构的构建和优化上。 ( 4 ) 小结 在当前的i n t 锄e t 环境下网状拓扑能够更好地适应节点的异构性，而且能很 好地应对节点的动态加入和退出。但数据通路的质量由于数据交换的不确定性而 不可预期。结构化的方法可以在数据通路的质量方面获得较好的性能但不能很好 地适应节点的动态变化。目前还没有更好的方案，每种解决方法都有各自的优缺 点。一种方案是否合适取决于系统的目标和应用的环境以及其实现策略。 1 3 2p 2 p 流媒体的q o s 研究现状 q o s 即服务质量，是一个综合指标，用于衡量使用一个服务的满意程度。业 界对其有着不同的定义，在互联网标准中该概念也在不断演化。i e t fr f c 2 2 1 6 【2 8 】 将q o s 定义为“分组业务传输的特性，具体表现为可达到的带宽、分组延迟和分 组丢失速率”。1 1 1 t e m e t 网络业务的q o s 精确定义尚未形成，还有许多可解释和细 化的环节【2 9 1 。m t f 集成业务框架认为分组延迟是最主要的q o s 参数描述，而匝t f 差异服务体系则进行了扩展，从而包括了可用性和丢失估计。当前公认的q o s 的 关键指标主要包括：可用性、吞吐量、时延、时延变化( 包括抖动和漂移) 和丢失。 随着1 1 1 t e m e t 和各种业务的迅猛发展，尤其是视频、话音等多媒体业务的迅 猛增长，p 网络由以前单一的数据网变成了多业务的综合数字网，传统的p 网 1 2 两北大学博士学位论文 和带宽的比值，选择比值最小的节点作为提供节点。 ( 2 ) 编码技术 由于1 1 1 t e m e t 不能提供点对点传输稳定视频流的q o s 保证，因此需要减小调度 分发数据的颗粒度，使达到一种全局与部分的优化。要把源内容分成多个小段的 数据，需要使用视频的编解码技术。 分层编码( 1 a y e r e dc o d i n g ，l c ) 【3 l 】和多重描述编码( m u l t i p l ed e s c r i p t i o nc o d i n g ， m d c ) 【3 2 】是两种最基本的在不可靠信道多路径传输的编码方式，基本思想都是把 数据编码到多个字码流上，在播放时根据需要或网络状况的限制，只需要接收到 全部或部分字码流就可以播放。l c 把视频流编码成一个基本层和若干个增强层。 基本层包含最基本的服务质量，可以单独编码，增强层的内容用于提高服务质量。 m d c 的不同流之间则没有层次关系，每个都能够独立保证一定的视频质量，接 收到的流越多，视频质量越高，适合高误码率的信道传输，但m d c 编解码的代 价较高。 其它的编码技术中典型的有网络编码。网络编码( n e 觚o r kc o d i n g ，n c ) p 刈技 术在p 2 p 流媒体上的主要应用方式是源节点在发送时把视频流分成小段数据后， 对多个块进行编码后发出。接收节点只有在收到足够的线性无关数据包并解码之 后才能获得原始数据。网络编码技术和p 2 p 流媒体传输相结合能够提高网络的吞 吐能力，同时又因为经过编码之后的每个块中都包含了多个原始块的信息，在一 个视频段内不存在需要先后调度的问题，这样就解决了分段传输的调度问题。但 同时，网络编码也会引入编解码的开销，并会带来额外的延迟，这是因为需要收 集到该段所有块才能解码。 ( 3 ) 数据传输调度机制 支持p 2 p 流媒体应用的系统需要两个主要部分：一是覆盖网络的构建，二 是内容的传送，目前第二部分关注得较少。而如何调度多个节点的数据请求对于 需要高q o s 的p 2 p 点播流媒体系统来说仍然是一个很大的挑战。 多媒体流在参与节点之间的传输是个很重要的问题。由于参与节点间的异构 性和不对称性，一个提供节点往往不能给接收节点提供保证其服务质量的输出带 宽。因此，一个接收节点常常需要多个提供节点来提供所需的服务质量，而多个 提供节点之间的数据块检索以及速率分配都是数据传输调度中的基本问题。 1 4 西北大学博士学位论文 ( 4 ) 复制策略 p 2 p 流媒体网络中数据存取的性能问题被认为是影响其q o s 的一个关键问 题。许多已有的研究表明，分布式服务及其数据的可用性可以通过将数据在彼此 相连的多系统上备份来提高，尤其是当系统和网络失效的时候。显然有越多的副 本，针对该内容就有更好的传输质量。但考虑到每个节点存储能力的限制，确定 保存多少个副本以及在何处保存非常重要，将对系统性能造成很大的影响。 在基于p 2 p 点播系统的研究中，针对v o d 点播中异步的用户请求，人们提出 了多种解决方案，其核心是让节点缓存部分流媒体数据，从而为其它节点提供数 据服务。根据每个p e e r 节点缓存的目标节目数据范围，我们把现有研究划分为三 类：初始数据缓存1 2 2 】、最近数据缓存【2 l 】以及全局指定缓存【3 5 1 ，其中初始数据 缓存是指在每个节点上只缓存目标节目开始部分的数据，最近数据缓存指每个节 点均缓存其最近所接收到的一段数据，全局指定缓存是指每个节点所缓存的数据 范围由某些中心节点根据全局策略来指定。 ( 5 ) 激励机制 p 2 p 流媒体系统呈现出比传统的p 2 p 文件共享系统更多的挑战和机遇。它不 仅需要文件有高可用性，而且要求媒体流有高传输质量。因此，不同于传统的 p 2 p 文件共享系统，p 2 p 流媒体系统无法仅依靠一小部分无私的节点来维持。 近年来，研究者们提出了多种p 2 p 流媒体中基于q o s 考虑的节点协作机制。 包括基于信誉的激励机制、基于市场的激励机制以及基于社会福利的激励机制 盘莹 号手o 1 3 3p 2 p 流媒体产业的现状 p 2 p 技术的出现可以说是对原有c s 模式的一种变革，尤其是在流媒体开始 普及的今天意义深远。2 0 0 6 年中国的互联网p 2 p 流媒体市场进入初步发展时期。 根据艾瑞咨询的研究发现，未来5 年该市场将保持一个快速上升的态势。2 0 l o 年 市场规模将超过4 亿元，所服务的网民数量也将达到1 4 亿。国内主流运营商也纷 纷在该领域推出新的举措，中国网通的宽带门户c n c m a x 推出商业性演出的直 播和转播服务；中国电信将互联星空打造成视频服务的聚合器；中国移动则将视 频作为移动新媒体战略的实现手段；中国联通的“视讯新干线 则利用3 g 实现 流媒体播放。国外运营商也在重点打造该领域的新业务，如：美国v e r i z o n 在2 0 0 5 西北大学博士学位论文 年就提出通过视频服务在未来转型成为一家传媒公司，西班牙t e l e f o n i c a 也加大 了在d s l 上开展宽带视频业务的力度。 基于p 2 p 技术的流媒体业务，尤其是直播业务部署迅速、成本低廉，一些新 兴的p 2 p 流媒体运营商也因此迅速崛起，如p p l i v e 、q q l i v e 、u u s e e 、p p s t r e 锄、 j o o s t 等，其中p p l i v e 号称目前为止已发展7 5 0 0 万用户。进入2 0 0 6 年，p 2 p 流媒 体技术成为风险投资界关注的焦点。u u s e e 、光芒国际、千橡互动、p p l i v e 、 p p s t r e a m 、土豆网、m v s e e 等知名p 2 p 技术网站先后获得风险投资的眷顾。动辄 成百上千万美元的投入，终于使p 2 p 技术摆脱了草莽身份，开始迈向前途光明的 未来。然而，在p 2 p 技术呈现爆发性增长的同时，其发展瓶颈也开始显现，技术 不成熟、盈利模式不确定、商业模式不健全、版权争端等问题都在困扰着这个产 业的持续发展。 基于p 2 p 的流媒体业务主要包括：直播或轮播的流媒体观看方式、用户可以 根据喜好随意拖动时点进行观看的点播方式、用户下载后观看方式。目前直播和 下载方式在技术上比较成熟，p p l i v e 等流媒体运营商目前主要实现的是p 2 p 直播 业务；点播方式由于需要一定量的p 2 p 用户同时观看，并且需要保证所有用户在 观看不同片段时的播放质量以及应对用户频繁的加入退出，技术实现和网络支持 的难度较大，目前还处于发展阶段；下载后再观看的方式，从严格意义上来讲属 于文件共享下载。 本文试图解决p 2 p 点播流媒体系统的技术难题。 1 4 问题分析与研究内容 对已有研究成果的分析表明，p 2 p 点播流媒体的研究存在以下几个问题： 1 ) 对p 2 p 流媒体q o s 的研究集中在解决q o s 的某一个方面。例如相当多的研究认 为p 2 p 流媒体中的q o s 问题主要是带宽的问题，因此仅围绕带宽问题提出解 决方案；有的研究只解决了数据可用性的问题等。 2 ) 很多方案没有考虑或没有充分考虑节点异构的问题。如在激励机制中没有考 虑d s l 用户上下行带宽的不对称性等，造成解决问题时片面追求公平性。 3 ) 一些方案没有考虑功能和开销之间的权衡，造成提高一种q o s 指标的同时导 致其它q o s 指标下降。如使用随机选择提供节点的模式，降低了系统复杂度， 西北大学博士学位论文 提高了系统的可用性和鲁棒性，但却无法保证节点收到数据的带宽和延迟。 4 ) 一些研究对p 2 p 流媒体系统的动态性考虑不足，尤其是对于流媒体点播服务， 用户的兴趣可能很快转换，一些使用应用层组播树的协议由于没有充分考虑 到用户的频繁退出，造成严重的单点失效。 5 ) 已有的很多相关研究工作并不是以确保系统的q o s 为出发点。 针对以上问题，确定本文研究的主要内容如下： 1 ) 适合p 2 p 点播流媒体的覆盖网络拓扑结构 如何根据p 2 p 点播流媒体应用的特点，有效地构建和管理覆盖网络的拓扑 结构是解决p 2 p 流媒体q o s 问题的基础。目前提出的拓扑构建方式很多，但大 多没有考虑q o s 保障的问题。在分析和仿真典型方案的基础上，重点研究节点 加入时支持q o s 感知的邻居选择问题；研究在高度变化和动态的p 2 p 网络中， 如何选择、管理和在单一会话期间转换发送节点，以使会话能保持最大可能的流 传输质量；提出新的拓扑生成算法。 2 ) 数据传输调度机制 研究如何在p 2 p 网络上提供一个有效的、可扩展的流媒体分发服务。由于 节点的服务能力有限，一般的媒体文件必须同时从多个节点传输。研究( 1 ) 如 何确定一组发送节点以获得最大输出；( 2 ) 如何协调多发送者；( 3 ) 如何建立质 量适配流媒体调度模型。 3 ) 缓存机制 为了提高媒体传输质量并提供高服务可用性，研究数据块的缓存机制，根据 需求的动态变化，确定在播放期限之前能被成功前摄的数据块集；研究缓存管理 策略，重点是缓存的更新。 4 ) 节点协作机制 f r e e 打d i n g ( 搭便车) 的问题在p 2 p 系统中由来已久，由于p 2 p 流媒体的实时 性本质，舶er i d i n g 对q o s 的影响非常显著。本文依据对p 2 p 点播流媒体特点的 分析，对p 2 p 流媒体系统中节点的协同工作机制进行研究。 本论文研究的总目标是对p 2 p 点播流媒体进行针对q o s 方面的基础研究， 研究保证q o s 的p 2 p 流媒体系统的拓扑生成、传输调度、缓存和激励机制，为 支持q o s 的p 2 p 点播流媒体系统建立理论分析模型和关键支撑技术。 1 7 两北大学博士学位论文 1 5 论文研究工作的意义和主要贡献 本论文对p 2 p 流媒体q o s 支持技术的研究，主要集中在覆盖网络拓扑构建、 传输调度、缓存管理和激励机制等四个方面，旨在提高流媒体服务的性能，降低 内容服务器的处理负载，提高流传输网络的效率，保证用户的观看质量。 论文总结了作者在该领域的主要研究成果，研究了对等网结构下流媒体系统 的体系结构，提出了一种两阶段节点选择算法，并设计了基于多解析环的节点定 位框架；设计了有效的视频内容分发与缓存策略，并根据需要的内容协调多发送 者之间的调度；提出了一种基于响应度的激励模型；对上述算法和框架进行了仿 真验证和性能分析。 1 6 论文组织结构 本文共分七章。 第一章为绪论，引入p 2 p 流媒体的概念与背景、研究现状( 包括p 2 p 流媒 体系统的研究现状和p 2 p 流媒体q o s 的研究现状) 、产业发展情况以及拟研究的 主要问题，指出研究工作的意义，并说明了论文结构。 第二章提出了本文分析研究的基础典型的p 2 p 点播流媒体系统框架以及以 后各章讨论中用到的基本假设。 第三章研究了p 2 p 点播流媒体系统中的节点选择问题和节点定位方法，即 q o s 敏感的覆盖网络构建问题。其中针对节点选择问题，提出了两阶段节点选择 算法t s p s ，针对节点定位问题，在多解析环的基础上考虑到覆盖网络和物理网 络的不匹配问题，提出了r n l s 节点定位方案，并通过仿真验证了本章提出的算 法和方案的有效性。 第四章对p 2 p 点播流媒体系统中的数据传输调度问题进行研究，首先给出 针对多提供者调度问题的数学模型，然后提出了两种不同的解决方案：基于纯拉 方式的解决方案和推一拉结合的解决方案，并通过仿真对比两种方案的性能。 第五章研究了p 2 p 点播流媒体系统中的分布式缓存管理机制，提出了基于 紧迫等级和贡献度的缓存机制，其中包括一个前摄方案和一个缓存替换算法，并 讨论了流媒体目标的初始缓存时间，也即启动延迟的问题，通过仿真对提出的缓 存机制进行了评价。 西北大学博士学位论文 第六章研究了p 2 p 点播流媒体系统中的激励机制。首先分析了激励机制对 p 2 p 流媒体q o s 的影响，然后在分析已有激励机制相关工作的基础上，提出一种 针对p 2 p 点播流媒体系统的基于响应度的激励机制i 出i m 。 第七章对本文的工作进行了总结和展望，包括：论文的主要创新工作以及下 一步的研究方向。 1 9 西北大学博士学位论文 和纯分布式框架相比，结合中心服务器和分布式网络的混合媒体流系统可以 更快地分发内容和更快地响应请求。本文的研究模型采用越来越流行的混合式覆 盖网络构建模式。 2 2 系统模型 本文研究点播流媒体应用。模型系统的主要成员有三种：媒体源服务器、 t r a c k e r 服务器以及对等客户节点。其中t r a c k e r 服务器是知名的汇聚点，其作用 是帮助新节点加入网络。媒体源服务器是指一组分布在不同自治域中的一个或多 个源服务器。当一个新对等节点加入网络时，t r a c k e r 服务器为其定位一个最近 的源服务器并给新节点一个初始邻居列表。为了讨论方便我们将源服务器和 t r a c k e r 服务器合二为一。对等客户节点是最复杂的组成部分，不仅需要从其源 服务器处请求数据包，还要和其它对等客户节点交换数据。每个节点缓存最近观 看的媒体数据，并周期性地给所有邻居公布其缓存图。同时，它调度数据请求以 获取其需要的媒体数据，从而支持连续回