（计算机软件与理论专业论文）p2p流媒体系统缓存及调度策略研究.pdf

摘要 近年来，采用p 2 p 模式解决流媒体服务系统的瓶颈问题受到越来越多的重视。如何 在充分利用p 2 p 网络中众多节点资源的前提下，确保流媒体服务质量、提高播放的性能， 成为p 2 p 流媒体技术研究的热点。 本文在分析和总结现有p 2 p 流媒体系统结构和应用特点的基础上，对p 2 p 流媒体点 播系统主要性能的优化问题进行了研究。主要工作如下： 首先，本文分析和归纳了影响节点启动延迟、播放连续度、服务器负载性能的主要 因素，论述了节点缓存管理和数据调度策略对p 2 p 流媒体性能优化的重要作用。 其次，本文对现有缓存管理相关内容进行了深入研究，从流媒体应用对缓存管理的 要求、缓存空间的用法等方面分析了概率缓存管理机制的优点，并针对现有概率缓存管 理机制中缓存替换策略的不足，提出了新的基于服务供需差、服务紧迫度的s d d u 替换 策略。 随后，在分析、归纳目前研究工作基础上，针对现有数据调度策略的不足，提出了 新的基于播放缓存偏移量的s s c o p 调度策略，并对该策略在概率缓存管理机制中的使 用方法进行了描述。 最后，对采用了s d d u 替换策略和s s c o p 调度策略的新概率缓存管理机制进行了 模拟实验，通过与原有概率缓存管理机制在启动延迟、播放连续度、服务器负载性能方 面的比较，证实了改进后的缓存机制对系统主要性能起到了优化作用。 关键词：p 2 p 流媒体，概率缓存机制，缓存替换策略，数据调度策略 a b s t r a c t i nr e c e n ty e a r s ，t h er e s e a r c ho ne l i m i n a t i n gt h eb o t t l e n e c ko ft h es t r e a m i n gm e d i as e r v i c e o fp 2 ps y s t e mh a sb e c o m eah o t s p o ti nt h ea p p l i c a t i o nf i e l d m o r e o v e r , h o wt og u a r a n t e et h e q u a l i t yo fs e r v i c eo fs t r e a m i n gm e d i a a n dp r o m o t et h es y s t e mp e r f o r m a n c eo nt h ep r e m i s eo f t a k i n gf u l la d v a n t a g eo ft h er e s o u r c e so fm a n yn o d e si nt h ep 2 pn e t w o r ki so n ei m p o r t a n t a s p e c ti nt h ef i e l d b a s e do na n a l y z i n ga n ds u m m a r i z i n gs y s t e ma r c h i t e c t u r ea n dt h ea p p l i c a t i o n c h a r a c t e r i s t i c so ft h ee x i s t i n gp 2 ps t r e a m i n gm e d i as y s t e m ，t h i sp a p e rs t u d i e st h eo p t i m i z a t i o n o ft h ep e r f o r m a n c eo ft h ep 2 po n - d e m a n ds t r e a m i n gm e d i as y s t e m t h ed e t a i l s a lea s f o l l o w i n g ： f i r s to fa l l ，t h ep a p e ra n a l y z e sa n ds u m m a r i z e st h em a i nf a c t o r st h a ta f f e c t i n gt h en o d e s t a r t u p l a t e n c y , p l a y b a c kc o n t i n u i t y , a n d t h es e r v e rl o a dp e r f o r m a n c e s t h ep a p e ra l s o d i s c o u r s e st h ei m p o r t a n te f f e c t so fn o d ec a c h i n gm a n a g e m e n ta n dd a t as c h e d u l i n gs t r a t e g yo n t h ep e r f o r m a n c e so fp 2 ps t r e a m i n gs y s t e m s e c o n d l y , t h ep a p e rs t u d i e st h ee x i s t i n gc a c h i n gm a n a g e m e n tp e n e t r a t i n g l y m e a n w h i l e ， t h ep a p e ra n a l y z e st h ea d v a n t a g e so ft h ep r o b a b i l i t yc a c h i n gm e c h a n i s mf r o mt h ev i e w so ft h e s t r e a m i n gm e d i ad e m a n d i n go fb u f f e rm a n a g e m e n ta n dt h eu s a g eo fb u f f e rm e m o r ys p a c e - m o r e o v e r , i no r d e rt oo v e r c o m et h ed r a w b a c ko fc a c h er e p l a c e m e n ts t r a t e g yo ft h ee x i s t i n g p r o b a b i l i t yc a c h i n gm e c h a n i s m ，an o v e ls t r a t e g yb a s e d o nt h es e r v i c e ss u p p l y 。d e m a n d d i f f e r e n c ea n du r g e n c y , w h i c hi sc a l l e ds d d us t r a t e g y , i sp r o p o s e dt of u r t h e ri m p r o v et h e s y s t e mp e r f o r m a n c e s s u b s e q u e n t l y , t oo v e r c o m et h ed r a w b a c ko ft h ee x i s t i n gd a t as c h e d u l i n gs t r a t e g y , t h e p a p e rp r o p o s e d an o v e ld a t as c h e d u l i n gs t r a t e g y , w h i c hi sb a s e do nt h ec a c h eo f f s e to f p l a y b a c ka n dc a l l e ds s c o p a f t e rt h a t ，t h ep a p e rd e s c r i b e sh o w t ou s et h en e ws t r a t e g yi nt h e p r o b a b i l i t yc a c h i n gm e c h a n i s m f i n a l l y , t h en e wp r o b a b i l i t yc a c h i n gm a n a g e m e n tm e c h a n i s mu s i n gs s c o p a n ds d d u s t r a t e g i e si ss i m u l a t e di nas i m u l a t o r i nt h es i m u l a t i o n ，t h ee x i s t i n gp r o b a b i l i t yc a c h i n g m a n a g e m e n tm e c h a n i s mi sa l s os i m u l a t e dw i t ht h es a m ep a r a m e t e r s t h r o u g hc o m p a r i n g t h e n e ww i t ht h eo l di ns t a r t u p l a t e n c y , p l a y b a c kc o n t i n u i t y , a n dt h es e r v e rl o a d ，t h ep a p e r c o n f i r m st h a tt h ei m p r o v e dp r o b a b i l i t yc a c h i n gm a n a g e m e n tm e c h a n i s mc a ne f f e c t i v e l y p r o m o t et h e s em a i np e r f o r m a n c e s k e yw o r d s ：p 2 ps t r e a m i n g ，p r o b a b i l i t yc a c h i n gm a n a g e m e n tm e c h a n i s m ，c a c h e r e p l a c e m e n ts t r a t e g y , d a t as c h e d u l i n gs t r a t e g y 西北大学学位论文知识产权声明书 本人完全了解西北大学关于收集、保存、使用学位论文的规定。 学校有权保留并向国家有关部门或机构送交论文的复印件和电子版。 本人允许论文被查阅和借阅。本人授权西北大学可以将本学位论文的 全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫 描等复制手段保存和汇编本学位论文。同时授权中国科学技术信息研 究所等机构将本学位论文收录到中国学位论文全文数据库或其它 相关数据库。 篡黧篓簦。雠拖吐学位论文作者签名：土邋指导教师签名；肥竺么_ 20 0 9 年石月，子日20 0 9 年厶编 西北大学学位论文独创性声明 本人声明：所呈交的学位论文是本人在导师指导下进行的研 究工作及取得的研究成果。据我所知，除了文中特别加以标注和 致谢的地方外，本论文不包含其他人已经发表或撰写过的研究成 果，也不包含为获得西北大学或其它教育机构的学位或证书而使 用过的材料。与我一同工作的同志对本研究所做的任何贡献均已 在论文中作了明确的说明并表示谢意。 学位论文作者签名：互文波 2 0 0 9 年6 月f 8 日 两北人学硕l j 学位论文 1 1 研究背景 第一章前言 随着i n t e m e t 的发展，用户对网络的期望和要求也越来越高，不再满足于单一的静 态媒体。将声音、文字、图像、视频等多媒体有机结合形成的媒体演示是i n t e m e t 的发 展重点，在动态多媒体方面由于存在带宽限制和数据同步等问题，于是出现了流媒体技 术。流媒体技术将数据流由音视频服务器向客户机实时传输，用户可以边下载边观看， 不用耗费漫长的等待时间，实现了媒体浏览的实时性。 以前，多媒体文件需要从服务器上下载后才能播放。由于多媒体文件一般都比较大， 下载整个文件往往需要很长的时间，限制了人们在互联网上使用多媒体数据进行交流。 另一方面，采用这种服务方式，用户无法观看到实时性较强的视频节目，比如体育竞赛 现场直播等。而流媒体技术的出现使得这种状况得以转变，流媒体应用的一个突出优点 是用户不必等待较长时间将多媒体数据全部下载到本地后再开始播放，而仅需将起始几 秒的数据先下载到本地的缓冲区中就可以开始播放了。 因特网上的传统流媒体系统是基于c s 模式的，如图卜1 所示，一般包括一台或多 台服务器，若干客户机。 源服务器 图1 - 1c s 流媒体分发系统示意 系统能同时服务的客户总数称为系统容量。c s 模式的流媒体系统容量主要是由服 务器端的网络输出带宽决定的，有时服务器的处理能力、缓存大小、i o 速率也影响到 系统的容量。在c s 模式下，由于传输流媒体占用的带宽大、持续时间长，而服务器端 第一章前言 可用的网络带宽有限，所以即使是使用高档服务器，其系统容量也不过几百个客户，根 本就不具有经济规模性。另外，由于因特网不能保证q o s ，如果客户机距服务器较远， 则流媒体传输过程中的延迟、抖动、带宽、丢包率等指标也将更加不确定。此外，服务 器要为每一个客户单独发送一次流媒体内容，导致网络资源的消耗十分巨大。 为克服上述缺陷，一些替代技术，如代理服务器、c d n 、i pm u l t i c a s t 等技术被提 了出来： ( 1 ) 代理服务器【14 】：在用户域附近部署代理服务器，缓存短期内访问过的数据， 以快速响应相同的请求。该方法优点是可以减轻源服务器负载、减小服务延时。其缺点 在于：由于流媒体文件通常较大，代理服务器只能缓存较少流媒体数据，无法充分满足 用户的需求，另外，采用此方法需要管理多个分布的代理，增加了系统的开销，而且并 没有从根本上消除瓶颈。 ( 2 ) c d n ( c o n t e n td e l i v e r yn e t w o r k ，内容分发网络) 1 5 - 8 1 ：c d n 是一个建立并 覆盖在互联网上，由分布在不同区域的节点服务器群组成的虚拟网络，如图卜2 所示。 图1 - 2c d n 系统示意图 与传统的口网络不同，在c d n 流媒体发布系统中，经常访问的内容会被“推到 与发出请求的用户距离较近的服务器，或者根据用户请求，数据从源服务器被下载到距 离用户最近的服务器。而用户则可以通过全局和局部策略实时地根据当前网络状态( 网 络流量，负载情况，用户位置等) 来选择合适的服务器。这种方法全面的解决了节点网 络带宽不同、用户访问量大、网络分布不均等问题，提高了用户访问的速度并有效的减 少了主干网的负载和传输延时，然而却增加了系统构建的总成本。 2 两北人学硕l 学位论文 ( 3 ) i pm u l t i c a s t ：在i p 层为请求相同流媒体数据的用户建立组播组，形成组播树， 避免了服务器通过多条单对单链接向用户传输重复的数据，降低了服务器以及主干链接 的负载，基于pm u l t i c a s t 的p 2 p 流媒体系统结构如图卜3 所示。采用口组播技术的流 媒体系统一般使用静态或动态服务器通道调度方案，大致分为以下几类：周期广播 ( p e r i o db r o a d c a s t i n g ) 方式【9 1 、批处理( b a t c h i n g ) 方案【l o 】、补丁( p a t c h i n g ) 方案【1 1 】、p i g g y b a c k 方案【1 2 】和流合并方案【1 3 】等。 i pm u l t i c a s t 系统中，组播树建立在支持组播功能的路由器上，因此具有相对较高的 效率。然而，对于采用口组播的流媒体系统，由于协议本身复杂性、网络异构性以及 缺乏有效拥塞控制机制等限制而难于大规模部署。 图l - 3 基于i pm u i t i c a s t 的系统示意图 在传统分发架构无法满足现有需求时，采用p 2 p 技术构建流媒体分发系统成为了比 较理想的候选方案，其主要原因在于通过这种方式不仅可以获得较好的系统性能，而且 不必改变现有网络结构。 p 2 p 网络的基本思想是充分利用因特网上分布在不同地理位置上的计算机的空闲资 源，采用分布式计算模式来为因特网上的用户提供各种服务。在纯p 2 p 网络中没有集中 的服务器，网络的每一个节点既可以作为客户接受其它节点的服务，也可以作为服务器 向其它节点提供服务。采用p 2 p 模式的流媒体系统正是基于这种思想进行流媒体内容的 分发传输的，其设计目标是充分利用众多客户节点的空闲资源，构建一个成本低、扩展 性好、并有一定q o s 保证的流媒体传输系统。 3 第一章前占 1 2 相关研究现状 p 2 p 网络以其分布式的设计和框架克服了中心化服务器的瓶颈缺陷，而且p 2 p 网络 是自治的，能很方便地对网络中的资源进行管理。但由于其动态的和异构的本质，使利 用p 2 p 技术在构建高效的流媒体应用时带来了一系列的挑战和问题。尤其是如何在充分 利用众多节点资源的同时能确保服务质量，成为p 2 p 流媒体技术研究的热点。 目前p 2 p 流媒体分发模型主要可以分为两大类：基于树状拓扑的协议及扩展和基于 g o s s i p 协议的。另外，由于i n t e m e t 的异构性，无法实现点对点传输稳定的视频流，因 此为了有效地进行流媒体内容分发、提高系统吞吐量、充分利用网络带宽、提供良好的 q o s 保证，需要减小调度分发数据的颗粒度以实现全局优化与部分优化的合理权衡。因 此，在许多解决方案中通常会采用对流媒体进行时间域或空间域分割的方法，这些方法 被称为流媒体编码技术，可作为p 2 p 流媒体系统的关键辅助技术有效改善流媒体o o s 。 1 2 1 基于树状拓扑协议及扩展的系统 基于树状拓扑协议及扩展( t r e e b a s e dp r o t o c o la n de x t e n s i o n s ) 的模型把参与p 2 p 分发 的节点组织成一棵组播树，树中的父节点负责为子节点传送数据。在这种模型中，树的 构建与管理需要解决如下问题： ( 1 ) 树的深度与宽度的平衡：节点离根节点越远，则数据的累积延迟就越大，因此， 树的深度应该尽可能小，可是每个节点的输出带宽限制了节点的宽度。树管理的目标就 是在深度和宽度之间实现有效地平衡，事实上，当所有节点的深度都为l 的时候就退化 成了传统的c s 模型了。 ( 2 ) 逻辑树的有效性：树的逻辑拓扑应尽可能的符合节点间的物理拓扑。 ( 3 ) 节点的快速加入和退出：节点的快速加入机制使新加入节点接收服务的延迟更 小。由于用户行为的不可预测性，任何节点都可能在任何时刻离开p 2 p 网络，因此在节 点退出后快速地修复树的结构对于服务质量也非常重要。事实上该约束和前两个约束是 相互矛盾的，需要做出一些权衡。 ( 4 ) 扩展性( ( s c a l a b i l i t y ) ：树的管理算法在节点数量非常大的时候应当仍然有效。 现有的p 2 p 分发模型中，p e e r c a s t 14 1 、z i g z a g 1 5 1 、s p l i t s t r e a m 16 1 、c o o p n e t 1 7 1 以 及p r o m i s e 1 9 1 均可归为基于树状拓扑协议及扩展的模型。 4 两北大学顾f ，学位论文 1 2 2 基于g o s s i p 协议的系统 g o s s i p 算法是目前流行的在p 2 p 系统中分发消息的算法，一个典型的g o s s i p 算法 中，节点随机地给系统中的部分节点发送消息，每个接收到消息的节点继续随机地向其 它节点发送消息，重复这个过程，直到消息被发送给系统中的所有节点。基于g o s s i p 协议( g o s s i p b a s e dp r o t o c 0 1 ) 的p 2 p 分发系统并不显式地构造节点之间的拓扑结构，而是 通过g o s s i p 协议，每个节点维护系统中部分其它节点的视图。每个节点动态地和其它节 点交换缓存信息，并根据缓存信息交换节点之间的媒体数据。在这种系统中，通常需要 比较大的缓存，系统的启动延迟相对较大。但是，由于每个节点的数据来源并不依赖于 某个特定的节点，因而系统有更强的健壮性。 典型的基于g o s s i p 协议的模型为d o n e t l 2 0 i 。 1 2 3 分层编码、多重描述编码、网络编码 分层编码( 1 a y e r e de o d i n g ，简称l c ) 2 1 】和多重描述编码( 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 ) 1 2 2 1 是两种最基本的在不可靠信道多路径传输的编码方式，其基本思想都是把 数据编码到多个字码流上，在播放时根据需要或网络状况，节点接收到全部或部分字码 流就可以播放。 l c 把视频流编码成一个基本层和若干个增强层，基本层包含最基本的服务质量， 可以单独编码；增强层的内容用于提高服务质量，而且各个增强层之间也具有层次关系， 即只有接收到所有底下的层才能解码上面的增强层。在i n t e m e t 中，不同网络中的节点 具有异质性( 能够接受的最大流量不同) ，因此需要采用不同的传输速率。对于流媒体而 言，l c 是一种不错的应用于多码率传输系统的编码方式。传输带宽大的节点可以接收 较多层的流量，带宽小的节点只能接收较少层次的流量。在不同层次的传输过程中，优 先照顾底层的传输要求，如若带宽不足，则优先抛弃较高的层，这样能够保证大部分节 点的正常观看，具有一定的公平性。 m d c 的不同流之间则没有层次关系，每个都能独立地保证一定的视频质量，接受 到的流越多，视频质量越高，适合高误码率的信道传输。但m d c 编、解码的代价较高。 网络编码( n e t w o r kc o d i n g ，简称n c ) 2 3 1 技术在p 2 p 流媒体上的典型应用方式是：源 节点在发送前首先将视频流分成段，每个段包含多个数据块，对段内的多个块进行编码； 接收节点只有在收到足够的线性无关数据块并解码之后才能获得原始数据。网络编码技 术结合p 2 p 流媒体传输能够提高网络的吞吐能力，同时又因为经过编码之后的每个块中 5 第一章前苦 都包含了多个原始块的信息，在一个视频段内不存在需要调度的先后问题，这样就很好 地解决了分段传输的调度问题。但同时，网络编码也会引起较大的编、解码开销问题以 及由于需要收集到段所有块才能解码而造成的播放延迟问题。 不同的p 2 p 分发策略根据需要，采用不同的编码方式，如c o o p n e t 【1 7 j 采用的是m d c 编码方式，而文献和p a l s t 2 5 】采用的是l c 编码方式，c o d e d s t r e a m t 2 6 1 则是一种混合了 m d c 与网络编码的传输策略。 1 3 研究目的及主要内容 通过对已有p 2 p 流媒体相关技术的研究和分析，本文试图在目前的技术背景下，为 提高流媒体系统的主要性能节点播放启动延迟、节点播放连续度以及服务器负载提 出优化方案，具体内容如下： ( 1 ) 对现有p 2 p 流媒体系统网络结构和应用特点、衡量p 2 p 流媒体系统的三个主 要性能进行描述和分析，对影响主要性能的相关因素进行分析与归纳，将节点缓存管理 和数据调度策略确定为改善系统性能的突破点，并对节点缓存管理和数据调度策略的重 要性进行了讨论，建立一个基于混合式网络结构的p 2 p 流媒体点播系统模型，为进一步 研究提高系统性能的机制确定问题域。 ( 2 ) 从逻辑缓存范围与实际缓存空间的“映射关系以及“连续性 和“非连续 性”并存两个方面讨论概率缓存机制的特点，针对现有概率缓存机制中“最多可用丢弃 策略存在的问题，提出了新的基于服务供需差和紧迫度的替换策略一s d d u 策略，并 提供了相应的算法描述。 ( 3 ) 对已有p 2 p 流媒体系统中使用的数据调度策略进行分析和归纳，针对现有策 略不能准确反映数据分发过程中供需状况变化的问题，提出了新的基于播放缓存偏移量 的调度策略s s c o p 策略，并给出了概率缓存机制中使用s s c o p 策略的具体处理过 程。 ( 4 ) 对采用了上述s d d u 替换策略以及s s c o p 调度策略的概率缓存机制进行了模 拟实验，实验测量并统计了新的概率缓存机制在播放启动延迟、播放连续度、服务器负 载三个方面的相关数据，通过与原有概率缓存机制的对比，论证了新机制的可行性、有 效性。 6 两北人学硕士学位论义 1 4 论文结构和章节安排 本论文分为六章： 第一章，主要介绍了论文的研究背景和论文的主要工作，并简单介绍了论文的组织 结构。 第二章，介绍了p 2 p 流媒体系统的网络结构以及两种应用的特点，分析了p 2 p 流媒 体系统主要性能及其影响因素，讨论了缓存管理及数据调度策略对提高系统性能的重要 性，提出了本文研究的系统模型，确定问题范围。 第三章，从新的角度阐述了概率缓存方案的特点，分析其缓存替换策略的不足，提 出了新的基于服务供需差和紧迫度的替换策略s d d u 策略。 第四章，分析并归纳现有p 2 p 流媒体系统中使用的数据调度策略，提出新的基于播 放缓存偏移量的调度策略s s c o p ，并以概率缓存方案为策略实施背景论述了s s c o p 的实现过程。 第五章，在n s 2 模拟平台上对改进过的概率缓存方案进行了实验，从节点播放启动 延迟、节点播放连续度、服务器负载三个方面论证了新方案的可行性。 第六章，总结全文，并展望下一步研究设想。 7 第二章p 2 p 流媒体系统概述 第二章p 2 p 流媒体系统概述 本章简要介绍p 2 p 网络的技术框架以及两种p 2 p 流媒体应用方式，分析了p 2 p 流 媒体系统主要性能及其影响因素，并给出本文研究的点播系统模型假设。 2 1p 2 p 网络结构 从网络层次来看，p 2 p 网络是一个构建在底层网络( 如m 网) 上的基于应用层的逻 辑覆盖网( o v e r l a yn e t w o r k ) ，该逻辑覆盖网通过定义逻辑邻域关系形成自己的网络拓 扑，对逻辑邻域关系的描述主要包括：节点自身信息、邻居节点信息、节点资源信息、 邻居节点资源信息等。p 2 p 网络技术发展大致经历了三个阶段，分别采用了不同的资源 定位和路由模型。基本上可以分为以下三种结构。 2 1 1 集中式p 2 p 网络 n a p s t e r t 2 7 】是第一个通过i n t e m e t 获得大规模应用并取得成功的p 2 p 网络系统。如图 2 - 1 ，在n a p s t e r 系统中，每个节点向中心目录服务器提交本地存储的资源目录，并由目 录服务器编制资源的索引。资源搜索是通过目录服务器完成的，节点向目录服务器提出 搜索请求，服务器返回拥有该资源的节点列表，请求节点则根据延迟、带宽等条件选择 合适的资源节点进行数据传输，数据传输无需中心目录服务器的参与。 r 请求响应 图2 - 1 集中式p 2 p 网络 由于采用了中心目录服务器，节点对资源的查找搜索效率较高，并且系统容易部署 8 婀北人学硕卜芦位论文 和管理。集中式p 2 p 网络的主要缺点足中心服务器容易成为系统瓶颈、造成单点失效。 2 1 2 分布式p 2 p 网络 ( 1 ) 基于消息广播的分布式p 2 p 网络 g n u t e l l a 2 8 1 是分布式p 2 p 网络中的典型系统，由于采用了非中心化的方法来查找文 件资源，因而系统中不会出现集中式p 2 p 网络中心服务器那样的系统瓶颈，整个网络的 可扩展性得到加强。如图2 - 2 所示，g n u t e l l a 网络中，节点通过将搜索请求转发给尽可 能多的邻居节点进行资源搜索，并通过设置t t l ( t i m e t o l i v e ) 值来限制搜索请求传播 的范围，避免引起过多的网络流量。 g n u t e l l a 网络具有极强的可扩展性，但由于通过洪泛的方式搜索资源，效率较低， 并且搜索过程会产生大量的转发消息，易形成消息泛滥，增加网络的负担。 q 资源请求 r 请求响应 图2 - 2 分布式覆盖网络 ( 2 ) 结构化的分布式p 2 p 网络 结构化的p 2 p 网络是一种采用纯分布式消息传递机制以及根据关键字准确定位资 源的p 2 p 网络，它与非结构化p 2 p 网络的根本区别在于节点是否能够按照全局方式组织 起来，这种网络同样没有中心服务器。目前主流的方法是采用分布式哈希表( d i s t r i b u t e d h a s ht a b l e ) d h t 技术实现节点和资源的全局化组织。 结构化p 2 p 对等网络的优点在于可在o ( 1 0 眇) 跳数( n 表示系统中的节点数) 内完成 资源的路由和定位。其主要问题是结构的维护机制较为复杂，尤其是当网络波动较大时， 维护代价显著提高。 9 第一二章p 2 p 流媒体系统概述 2 1 3 混合式p 2 p 网络 混合式p 2 p 网络结合集中式和分布式两种方式的优点，网络中的节点同时利用两种 方式获取其它节点的信息。k a z a a l 2 9 1 模型是混合式p 2 p 网络模型的典型代表，如图2 3 ， 它在p 2 p 分布式网络基础上引入超级节点的概念，综合了集中式p 2 p 快速查找以及分布 式p 2 p 去中心化的优势。k a z a a 模型中，节点被分为普通节点和超级节点两类。其中， 超级节点与位于其附近区域的普通节点构成自治簇，簇内采用基于集中目录式的p 2 p 模 式，而簇间则采用分布式p 2 p 的相关技术将超级节点连接起来。 普通节点搜索资源时首先在本地簇内进行，当搜索无结果时再通过超级节点间有限 洪泛进行搜索。这种方式可有效降低网络流量、提高搜索效率并在一定程度上提高网络 的负载均衡。另一方面，由于在簇内超级节点承担了类似于集中式目录服务器的任务， 因此超级节点容易成为局部瓶颈。 2 2p 2 p 流媒体系统应用 图2 - 3 混合式覆盖网络 请求 响应 当前p 2 p 流媒体系统按播放类型划分，可分为直播系统和点播系统，下面分别进行 分析和讨论。 2 2 1 基于p 2 p 的流媒体直播系统 p 2 p 流媒体直播是指基于应用层组播的有时序同步要求的流媒体技术。在直播系统 中，视频节目首先要被压缩、编码，形成适合于在目前i n t e m e t 上传输、播放的流媒体。 直播源服务器将编码后的内容送入覆盖网中，通过在线节点对流媒体数据进行中继传 1 0 西北大学硕i j 学位论文 输，当节点收到流数据后即可解码观看。目前现有的直播系统主要有：c o o l s t r e a m i n g l 2 们、 p p l w e l 3 0 】等。 p 2 p 流媒体直播系统主要的性能包括：节目同步丢失延迟、节点播放启动延迟、节 点播放连续度、服务器负载等。其中，节目同步丢失延迟是指：在节目同步丢失( 即流 媒体内容视频帧在多个节点播放时出现的不同步现象) 的情况下，当前节点播放初始视 频帧的时刻与源服务器输出该帧的时刻之间的时间差。节点播放启动延迟是指节点启动 播放操作后至节目正式开始播放之间经历的延迟。节目播放连续度是用来描述节点上播 放的视频平滑、顺畅程度的指标，节点从覆盖网中获得的有效数据( 即未超过其播放期 限的数据) 越多，观看到的视频越流畅。以上三个性能对用户体验影响较大。服务器负 载主要用于衡量直播系统可扩展性。 从内容分发的角度分析，已有p 2 p 流媒体直播系统采用的分发方式包括了基于树状 和基于网状( 即基于g o s s i p 协议) 拓扑的分发方式。其中，早期的系统多采用单组播树 方案，所有访问同一流媒体的节点被组织成树状形式，根为数据源服务器。这种内容分 发方案在服务者和消费者之间形成一对多的模式。由于单组播树方案中叶子节点带宽资 源得不到有效利用并且中间节点的行为对子节点影响较大，因此基于多组播树的内容分 发方案被引入到p 2 p 直播技术中。在基于多组播树的数据分发方案中，流媒体在源服务 器处被分割成多条子流，每一条子流在一棵组播树上分发，节点可同时位于多棵组播树 上，从而获得适应带宽状况的q o s 。然而，基于多组播树的方案需要较高的维护代价， 系统的可扩展性较差。在近期p 2 p 直播系统中，更多地采用了基于网状拓扑数据分发方 案，在服务者和消费者的数量对比上形成多对多的模式，并且节点获取数据基本是以 “拉 方式( 即接收端驱动方式) 实现的。基于网状拓扑的分发方案在系统的可扩展性、 鲁棒性方面表现较好，但播放启动延迟性能较差。 2 2 2 基于p 2 p 的流媒体点播系统 相比于直播系统，p 2 p 流媒体点播系统表现出明显的异步时序特征，即不存在同步 丢失现象，节点播放时序仅与用户播放操作行为相关。用户可进行v c r 操作，即暂停、 快进、快退操作。 与p 2 p 直播系统类似，点播系统的主要性能亦包括：节点播放启动延迟、播放连续 度、服务器负载。前两项性能直接与用户体验有关，服务器负载则与系统的可扩展性、 负载均衡有关。 第一二章p 2 p 流媒体系统概述 p 2 p 点播系统需要解决的核心问题是如何对用户异步播放操作实现快速响应，该问 题产生的原因在于用户异步操作使不同节点具有独立的播放时序，节点间播放时序重合 度较低，在节点缓存空间有限的条件下，数据共享几率远远低于同等规模的直播系统。 针对该问题，常用的解决方案是优化节点流媒体数据缓存和数据定位算法。通过对缓存 算法的优化，提高被缓存数据的可用性；通过对数据定位算法的优化，降低搜索数据消 耗的时间。在普遍存在节点扰动以及带宽变化不可预测的p 2 p 网络环境中，多数p 2 p 点播系统采用了基于网状拓扑的结构实现数据传输。 在p 2 p 点播系统中，根据节点缓存的目标数据范围，可将现有系统划分为三种类型： ( 1 ) 初始数据缓存型【3 ，采用此类方案，系统实际上将整个流媒体文件按节点加入的 时刻划分成多个子节目，为每个子节目建立组播树，每个节点只缓存目标节目初始段部 分的数据，节点所需的其它数据则来自于组播树。此类方案要求节点拥有较多的缓存空 间以及较大的输入带宽。( 2 ) 最近数据缓存型【3 2 1 ，节点维护一个f i f o 队列，用于缓存 最近收到的流数据。在采用该类方案的系统中，节点按加入到系统的时间被分为“代 ， 位于同一“代”的节点缓存的数据块起始序号相同，故节点的f i f o 队列长度是不等的。 此方案要求有足够的点播请求密集度，否则数据共享几率会大大降低。( 3 ) 全局指定缓 存型3 3 】，使用该类方案，节点有等长的f i f o 缓存，系统则提供中心索引服务器记录每个 节点缓存的数据信息，以便于节点请求流媒体对象任意位置的数据，但该方案存在单点 失效的问题。 2 3 系统主要性能及其影响因素 采用传统架构的流媒体系统可扩展性较差，源服务器及其输出带宽往往成为系统瓶 颈，但对于已经加入到系统中的客户端而言，可以获得较好的服务质量。相比之下，基 于p 2 p 技术的流媒体系统能够有效降低源服务器负载，因而可有效提高系统的扩展性。 但是，由于p 2 p 网络中节点及链路存在较大的异构性；并且，p 2 p 技术本身没有q o s 控制机制，不提供q o s 保证，而i n t e m e t 只能提供b e s t e f f o r t 型服务。因此，p 2 p 架构 特征和i n t e m e t 现状使得为节点提供理想q o s 成为难点，必须要在可用带宽、传输延迟、 拥塞控制等方面予以加强，即只有根据具体的p 2 p 应用特征设计特定的增强机制才能保 障相应q o s ，此类问题可归入p 2 p 增强机制【3 4 j 研究范围。 p 2 p 系统有多方面的性能表现，如：播放连续度、播放数据率，启动延迟，带宽利 用率，定位效率，数据吞吐量，拓扑一致性，可扩展性服务器负载，系统维护开销等， 1 2 两北大学硕i ：学位论文 并且这螳性能还具有交叉影响的特点，例如，启动延迟就要受到带宽利用率、定位效率 性能的影响。 在p 2 p 流媒体应用中，用户能够直接体验到的应用系统性能是播放启动延迟、播放 连续度，由于此二性能相互间交叉影响较小( 如，启动延迟较小的系统未必能实现较为 平滑的播放效果，反之亦然) ，故本文将它们作为p 2 p 流媒体应用的主要性能进行分析。 另一方面，从系统全局角度出发，在保证较好的播放启动延迟和连续度的前提下，如何 降低服务器负载( 或提高系统可扩展型) 无疑是最为关键的研究内容，所以本文也将这个 性能列入分析范围。下面对此三个性能进行说明并分析影响它们的主要因素。 2 3 1 播放启动延迟 ( 1 ) 播放启动延迟 p 2 p 流媒体系统中，当新节点加入到系统并发出播放请求后，用户无法立即观看到 视频，需要经过一段时间才能正式播放。这一段等待时间是无法避免的，因为，即使 p 2 p 节点直接从流媒体源服务器处下载流数据也至少需要经过两个网络传输延迟的时 间：节点请求消息传送到服务器所经历的网络传输延迟、服务器提供的流数据抵达节点 所经历的网络传输延迟。这一等待播放的时间段被称为节点的播放启动延迟( p l a y b a c k s t a r t u pl a t e n c y ) 。 通常p 2 p 流媒体系统中请求节点下载的大部分数据是来自网络中其它节点。而且在 基于g o s s i p 协议及其扩展的p 2 p 流媒体系统中，节点加入到系统后往往直接从邻居节点 处下载立刻要播放的数据，即节点很少从服务器处获取立刻要播放的数据。此外，由于 节点的异构性、网络带宽变化的不可预测性等因素，邻居节点间的网络传输延迟难以计 算。因此，不同节点的播放启动延迟未必相同，同一节点关于不同流媒体对象的启动延 迟也未必相同，甚至同一节点在不同时刻请求同一流媒体对象的启动延迟也不相同。 系统中存在的节点异构性、网络抖动还迫使节点必须预取并缓存一部分尚未播放过 的数据块，以确保流媒体能够平滑播放。这一保障机制是从节点发出播放请求的时刻就 开始运行的，因此，播放启动延迟还要包括这一部分初始预取时间。 显然，启动延迟越小，用户等待时间就会越短。用户的观看效果则更好。我们无法 消除播放启动延迟，只能设法尽可能地降低启动延迟。 ( 2 ) 影响播放启动延迟的主要因素 在基于g o s s i p 的p 2 p 流媒体系统中，从节点启动的过程来看：节点首先要与一个正 1 3 第二章p 2 p 流媒体系统概述 在运行的节点建立联系，从这个“接入”节点处拷贝其当前邻居节点列表，然后通过多 次g o s s i p 消息转发最终与合适的节点集( 带宽和内容两方面) 建立邻居关系，这是一个 节点选择的过程。是否能够建立恰当的邻居关系，不仅影响节点的播放启动延迟，而且 对节点整个会话期间的数据传输都会造成一定的影响。当邻居关系建立后，节点要从这 些邻居中选择恰当的节点下载恰当的数据块，这是数据调度要解决的问题。节点在正式 播放流媒体数据之前，一定要缓存一部分内容( 通常为十几秒至一分钟的内容) 。所以， 播放启动延迟一般包括两个时间段：节点选择所耗时间和下载部分数据块消耗的时间。 另一方面，节点的播放启动延迟还与节点的整体行为有关。当大量的节点在较短时 间内加入到系统时，会产生“蜂拥”现象。由于对相同数据块请求的频率较高而整个系 统中数据块的副本数较少，节点可能会在相当长的时间内无法下载到足够的数据块，导 致较大的启动延迟。这个现象在p 2 p 流媒体直播系统中比较突出。 综上所述，影响节点播放启动延迟的主要因素包括：节点选择、数据调度、节点行 为。其中，由于节点行为具有相当大的不可预测性，因此解决这个问题的一般方案是根 据流媒体的“热度 动态调整系统的服务资源，即在源服务器上为“热度”高的节目分 配更多的缓存空间和输出带宽。关于节点选择，在我们先前的工作中已经对此做过大量 的研究和分析【3 5 3 6 】，此处不再赘述。对于已经建立确定邻居列表的节点而言，恰当的调 度决策能够有效改善启动延迟性能。 2 3 2 播放连续度 ( 1 ) 播放连续度 与其它网络业务不同，流媒体业务中流数据具有严格的时间相关性，即流媒体数据 具有一个播放期限的约束，对于播放期限已过的流数据，由于播放器会将其丢弃，所以 即使被下载到本地节点，也不再具有任何播放意义，从而造成空间域信息丢失，影响用 户观看效果。 在流媒体系统中，节点获取的有效流数据( 即在播放期限到达前被下载的数据) 越 多，用户观看的视频就越流畅、平滑。因此，通常将流媒体的播放连续度量化为数据丢 失率，数据丢失率越低播放连续度越好。 与同样具有较强时间相关性的语音业务相比，流媒体业务还有带宽需求高、持续时 间长的特征。所以，系统服务器的吞吐能力和网络带宽容易成为流媒体系统性能瓶颈。 而在基于p 2 p 技术的流媒体系统中，虽然流媒体源服务器的负载被大大缓解，但节点的 1 4 西北人学硕卜位论义 异构性、节点的动态性( 节点动态加入与退i 叶j ) 等对流数据的时效性会造成极大影响。 另外，在底层网络中流数据以包的形式进行断续的异步传输，不同的包可能会经历不同 的路由，导致传输延迟的不同；底层网络的丢包现象也会导致流媒体数据的丢失。 总的来看，播放连续度是衡量p 2 p 流媒体系统的重要指标，它与系统的可用性密切 相关；影响播放连续度的两个直接原因是：被请求的数据未下载到、下载到的数据块失 效( 超过了其播放期限) 。其深层原因则是：p 2 p 流媒体系统固有的带宽瓶颈和内容瓶颈 3 7 限制。 ( 2 ) 影响播放连续度的主要因素 在影响播放连续度的两种瓶颈中，带宽瓶颈是指：拥有请求节点所需数据的服务节 点( 邻居) 集提供的汇聚带宽未达到请求节点输入带宽的下限。节点输入带宽的下限值 一般以流媒体的播放速率来确定，如果服务节点提供的汇聚带宽超过这个下载，那么请 求节点就有能力在保证q o s 的前提下利用额外带宽下载并缓存更多的有效数据：若汇聚 带宽与该下限值相等，请求节点能够正常播放流媒体，但无法预取数据；若汇聚带宽低