（计算机科学与技术专业论文）p2p流媒体系统中多源协同技术研究.pdf

国防科学技术大学研究生院硕士学位论文 摘要 近年来，p 2 p 流媒体服务正以前所未有的速度占领着i n t e m e t 上传统流媒体的 市场分额。p 2 p 流媒体是将p 2 p 技术应用于流媒体系统中，可以依靠大量对等节 点自身的能力来减轻服务器负载和主干网络压力，解决了传统流媒体系统的海量 并发用户的可扩展性问题。 多源协同技术是非结构化p 2 p 流媒体技术的重要组成部分。由于当前i n t e m e t 上单个源节点的网络传输速率难以满足媒体文件的播放的速率要求，因此p 2 p 流 媒体点播系统需要实时调度多个源节点协同地为一个请求节点提供流服务，即多 源协同技术。多源协同技术主要包括三个方面：数据分配算法、节点选择算法和 准入控制算法。 本文主要研究p 2 p 流媒体系统的多源协同技术中的数据分配和节点选择算法， 其中创新性的研究工作主要包括两部分：( 1 ) 动态数据分配算法和( 2 ) 半成熟 节点的完善选择算法。 对于数据分配算法，本文首先分析了现有数据分配算法的局限性：然后提出 了实际网络环境下的动态数据分配算法( d d a ) ；再将该算法应用到我们自主开 发的p 2 p 流媒体系统进行测试。测试得出该算法可以使得活动源节点的实用度之 和在9 4 的服务时间内始终保持在播放速率以上波动，能够提供连续稳定的流服 务。 对于节点选择算法，本文首先分析了现有较优的节点选择算法f a s t 漏选大 量半成熟节点的不足；然后提出了半成熟节点的完善选择算法( s p c s ) ：再通过 模拟试验验证了这种节点选择算法优越性，结果表明在流服务前期，s p c s 平均启 动延迟比f a s t 缩小了大约1 5 ，如果在有v c r 的系统中，效率会更高。 在本文的最后还对我们开发的p 2 p 流媒体系统v s h o w 中总体结构进行了介 绍，并详细阐述了其中逻辑功能层模块的设计，以期在下一阶段加入更复杂的多 源协同策略进一步提高该系统流服务的质量。 关键词：p 2 p 流媒体，多源协同，数据分配，节点选择 第i 页 国防科学技术大学研究生院硕士学位论文 a b s t r a c t i nt h er e c e n ty e a r s ，、 ，i t hu n e x p e c t e ds p e e dp 2 pm e d i as t r e a m i n gs e r v i c eh 髂t o k e n u pt h em a r k e t so fi r a d i f i o n a lm e d i as t r e a m i n gs e r v i c e p 2 pm e d i as t r e a m i n gi sw h a tw e u s ep 2 pt e c b _ r t i q u ei nm e d i as t r e a m i n gs y s t e m i np 2 pm e d i as t r e a m i n gs y s t e m 1 a r g e a m o u n to fp e e r sc a nu s et h e i ro w nc a p a c i t i e st or e d u c es e v e r s l o a da n dr e l i e v e b a c k b o n en e t w o r k s p r e s s u r e i ta l s o c o p e sw i t h t h es e a l a b l e p r o b l e mo fn l a s $ i n t e r e u r r e n te l l s t o m e r sw h i c ht r a d i t i o n a lm e d i as t r e a m i n gs y s t e m sa l w a y sh a v e m u l t i s o u r c et e c h n i q u ei so n e ：o ft h ei m p o r t a n tp a r t si nu n s t r u c t u r e dp 2 pm e d i a s t r e a m i n gt e c h n i q u e o w i n gt h a to n ep e e r su p l o a dr a t ec a l ln o tm e e tt h ed e m a n do f t h e p l a y b a c k , f 2 pm e d i as t r e a m i n gs y s t e mh a st os c h e d u l em o l et h a n es o u l l c ep e e r st o c o o p e r a t ef o r0 1 1 er e q u e s tp e e r t h a t sw h a tw ec a l l e dm u l t i s o u r c et e c h n i q u e w h i c h m a i n l yi n c l u d e s3a s p e c t s ：d a t aa s s i g n m e n ta l g o r i t h m , p rs e l e c t i o na l g o r i t h ma n d a d m i s s i o nc o n t r o la l g o r i t h m i nt h i sp a p e r , o u rr e s e a r c h e sa r ec o n c e n t r a t e d0 1 3d a t aa s s i g n m e n ta l g o r i t h ma n d p e e rs e l e c t i o na l g o r i t h mf o ra p 2 pm e d i as t r e a m i n gs y s t e m 。a n do u ri n n o v a t i v ew o r k s i n c l u d e s ：( 1 ) d y n a m i c a ld a t aa s s i g n m e n ta l g o r i t h ma n d ( 2 ) s e m i - m a t u r ep e e rc o m p l e t e s e l e c t i o na l g o r i t h m f o rd a t aa s s i g n m e n ta l g o r i t h m ，w ef i r s t l ya n a l y z et h el i m i t a t i o no fp r e s e n td a t a a s s i g n m e n ta l g o r i t h m t h e nw ep r o p o s et h ed y n a m i c a ld a t aa s s i g n m e n ta l g o r i t h m ( d d a ) w h i c hc a r lb eu s e du n d e rp r a c t i c a ln e t w o r kc i r c u m s t a n c e a n dw e l u l ld d ai na p 2 pm e d i as t r e a m i n gs y s t e md e v e l o p e db yo u r s e l v e s t e s tt e l l si l l st h a ti n9 4 o ft h e s e r v i c et i m ed d ac 8 1 1m a k et h et o t a lu t i l i t yo ff l u c t u a n ta c t i v ep e e r s a b o v et h e p l a y b a c kr a t e ，w h i c hc a l lp r o v i d er o r k s e c u t i v ea n ds t a b l es t r e a m i n gf , e l v i ( c e f o rp e e rs e l e c t i o na l g o r i t h m ，w ef i r s t l ya n a l y z et h ed e f e c to f p r e s e n tp e e rs e l e c t i o n a l g o r i t h mf a s t ，w h i c hw o u l dm i s sl a r g ep a r to ft h es e m i m a t u r ep e e r s t h e nw e p r o p o s es e m i - m a t u r ep e e rc o m p l e t es e l e c t i o na l g o r i t h m ( s t c s ) a n dw ev a l i d a t e dt h e s u p e f i o r i t yb ye x p e r i m e n t s ，a n dr e s u l ts h o w st h a ti ne a r l yt i m e ，t h ea v e r a g e i n i t i a ld e l a y o f s p c si s1 5 l o w e rt h a nt h a to f f a s t i f t h e r ea r cv c r o p e r a t i o n s ，t h es y s t e mc o u l d b em o r ee f f e c t i v e i nt h ee n do ft h i sp a p e r w ei n t r o d u c et h em a c r oa r c h i t e c t u r eo fo u rp 2 pm e d i a s t r e a m i n gs y s t e mv s h o w a n dd e t a i l e d l ye x p l a i n st h ed e s i g no fm o d u l eo fl o g i c a l f u n c t i o nl a y e rw eh a v ed e v e l o p e di no r d e rt oi m p r o v eo u rq o s b yu s i n g i n o r ee f f e c t i v e a l g o r i t h mi nt h el l e x tp h a s e k e yw o r d s ：p 2 pm e d i as t r e a m i n g , m u l t i s o u r c t ! c o o p e r a t i o n , d a t aa s s i g n m e n t ， p e e rs e l e c t i o n 第i i 页 国防科学技术大学研究生院硕士学位论文 表目录 表5 1p e e r 节点软件模及其依赖关系 表5 2 信息管理模块类成员说明 表5 3 监视调节模块类成员说明 表5 4 策略模块类成员说明 表5 5 数据下载模块类成员说明 4 0 4 3 第1 1 1 页 国防科学技术大学研究生院硕士学位论文 图目录 图 图 图 图 1 2 3 4 图2 1 图2 2 图2 3 图2 4 图2 5 图3 1 图3 2 图3 3 图3 4 图3 5 图4 1 图4 2 图4 4 融合示意图3 支持流媒体的c d n 服务4 应用层组播示意5 d o n e t 中的组成员关系( 源节点a ) 7 不同的媒体数据分配导致不同的缓冲延迟1 1 算法o t s 11 传输调度方案1 3 f a s t 节点选择算法1 5 c o l l e c t c a s t 拓扑感知选择得到的最好活动集是 p 2 ，p 3 ，p 6 ) 1 6 d d a 算法中节点功能结构图2 3 候选源节点信息列表2 5 候选源节点信息列表初始化2 7 候选源节点信息列表中数据的更新2 8 活动源节点总实用度比较2 9 f a s t 节点选择算法原理3 1 f a s t 算法充分性的原因3 1 s p c s 节点选择算法3 5 图4 4 平均延迟比较3 5 图4 5 成熟节点增长比较。 图5 1v s h o w 系统结构图 3 6 3 7 图5 3 数据、消息传递流向图4 0 图5 4v s h o w 中用户界面4 1 图5 5 候选源节点信息列表4 2 图5 6 节点信息管理模块类图 图5 7 监视调节模块类图 4 3 4 6 图5 9 策略模块类图4 7 图5 9 数据下载模块类图 图5 1 0 数据发送模块类图 4 9 5 0 第页 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含 其他人已经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示谢意。 学位论文题目：里! 速蕴焦丞红主垒疆进固楚盔堑壅 学位论文作者签名： 錾些 日期：砂卯z 年，月，严日 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留，使用学位论文的规定。本人授权 国防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子 文档，允许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据 库进行检索，可以采用影印，缩印或扫描等复制手段保存。汇编学位论文。 ( 保密学位论文在解密后适用本授权书。) 学位论文题目： ! ! 里逾搓逛丕缝主垒塑选国挞垄盈庭 学位论文作者签名： 瘟丝 作者指导教师签名：盈篁丝 日期：即6 年f 月芦日 日期：铭年，月，弘日 国防科学技术大学研究生院硕士学位论文 第一章绪论 流媒体( s t r e a m i n gm e d i a ) ，是指在网络上按时间先后次序并以流水方式实时 传输并同步播放的连续音频、视频等多媒体数据流。流媒体不同子一般文件下载 的网络传输应用，它不必等到全部媒体文件都传输完毕了才开始播放，而具有边 传输边播放重要特性。主要形式包括视频直播、视频点播和视频会议等实时性较 强的应用。 1 1 研究背景及意义 近年来随着互联网的飞速发展，越来越多的用户不再满足于浏览网页、收发 邮件和下载文件，他们希望享受在线的媒体服务。据统计：到2 0 0 6 年1 月我国的 宽带网民6 4 3 0 万人中在线收看影视节目和下载媒体文件的比重高达3 7 1 ，而且 还呈现增长趋势。在流媒体业务市场分额不断扩大的情况下，传统的媒体服务系 统由于采用c 愿服务模式，产生了明显的媒体服务器负载重、价格高，主于网络 的压力大等问题，可扩展性受到了严重限制，不能满足并发海量用户的需求。 媒体用户数的增长一方面导致传统媒体服务系统弊端显露无疑，另一方面使 得互联网边缘上存在大量闲置可用的计算，存储和带宽等资源。如何有效利用这 些闲置资源来解决传统流媒体服务系统的问题，正是基于这样的背景，p 2 p 技术被 应用到流媒体服务系统中来，产生了一种新兴的流媒体体系结构p 2 p 流媒体。 p 2 p 是一种利用广泛分布的自治资源来完成特定功能的新兴技术，它能较好地 适应面向海量伸缩性的应用系统的需求。其资源包括计算、存储、网络带宽等， 所完成的特定功能可以是分布计算、数据内容共享、通信协作以及流媒体服务等。 与传统的c s 模式不同，在p 2 p 中分布的各个对等节点地位平等，直接交换共享 计算、存储、信息等资源和服务，每个节点在享受服务的同时，还为其它节点提 供服务。这样，通过廉价节点的协作就能产生巨大系统增益。 将p 2 p 技术的思想应用于流媒体系统中，请求节点不仅可以由媒体服务器提 供服务，而且可以由其他先前已被服务或直接拥有该媒体文件的对等节点提供服 务，这样就可以依靠大量对等节点自身的能力来减轻服务器负载和主干网络压力。 近年国内也涌现出了许多较为成熟的p 2 p 流媒体系统，如p p s t r e a m 、p p l i v e 、 c o o l s t r e a m i n g 。p 2 p 漉媒体系统较传统流媒体系统实现了在同成本的情况下，并发 用户量的几个数量级的提高，并且基本上实现了p 2 p 原理中用户越多服务质量越 好的效果。我们的研究内容也是如何利用p 2 p 技术更有效地构建新型的流媒体系 第1 页 国防科学技术大学研究生院硕士学位论文 统，使得较低的成本水平就可使系统具有良好的扩展性、健壮性和适应性，并且 能够满足用户对视频直播点播服务质量的基本需要。 1 2 国内外研究现状 1 2 1 传统流媒体服务技术 从传统流媒体服务系统发展历程来看，传统流媒体服务器体系结构经历了三 个阶段：第一阶段是1 9 9 5 1 9 9 9 年左右的单服务器体系结构，由单一的媒体服务 器向客户提供服务，其瓶颈是服务器；第二阶段是1 9 9 9 - - 2 0 0 2 年左右的并行或集 群多服务器体系结构，由相对紧耦合的服务器群向客户提供服务，服务器群的接 入网络以及主干网络的带宽是瓶颈；第三阶段是2 0 0 1 - - 2 0 0 3 年左右的多服务器加 代理缓冲服务器体系结构，由相对客户较近的代理缓冲服务器通过缓冲预取策略 从多服务器获取数据再向客户提供服务，能满足的并发用户数与代理缓冲服务器 的数量和位置相关。 随着流媒体服务系统经历到不同阶段，相应的实现方式和传输技术应运而生， 下面将对这些经典的技术做逐一介绍。 1 2 1 1 广播和组播 在广播方式中，无论用户需要与否，每个数据包将发送给网络上的所有用户。 它减小了网络的负载，但广播方式只有在底层支持广播的网络上才能实现，使得 广播方式通常只能在小范围内使用。而在组播方式中，数据包将发送到一组地址， 所有加入该组的用户都可以收到。目前，组播已经得到了广泛的应用，很多实时 的多媒体会议及教育系统都是基于组播开发的。 1 2 1 2 广播式点播 广播式点播是以广播的方式满足点播需求。其基本思想是将一个节目划分为 若干段，每一段单独占用一个广播频道并在该广播频道上循环广播。用户在点播 时，先等待至第一段的开始；在播放某一段时，可以同时接收下一段的视频内容 以达到段段之间的不间断播放。由于视频输出采用广播模式，且分段循环，因此 用户在任意时刻想观看该节目时，只要稍作等待便可，达到点播观看的目的。该 模式一般应用于热门节目的播放中。 1 2 13 分组技术 在点播应用中，由于大多数请求集中在少数的热门节目上，而且经常集中在 一个黄金时段，在此黄金时段中每一个短的间隔时间内都可能有对同一节目的大 第2 页 国防科学技术大学研究生院硕士学位论文 量请求。分组技术的做法是，将黄金时间段平均分成许多小的时间间隔，针对每 一个时间间隔，收集所有的用户请求并加以分组，相同请求的用户在同一组中。 然后服务器为不同的请求各分配一个信道，同一组的用户共享一个信道上的相同 的媒体节目流。这种策略虽然使一些用户的时延增大，但却可能大大提高服务器 的服务能力。 1 2 1 4 融合技术 融合技术在于将针对于同一节目请求的时间比较接近的多个媒体节目流合并 为一个流以减少开销。融合技术同分组技术的基本出发点是相同的。都是为了使 得多个用户共享同一媒体节目流。与分组技术不同的是，融合技术首先保证即时 响应用户请求，然后根据情况，对相同节目且时间接近的多个媒体节日流，在时 间相对较快媒体节目流中插入些本不必要的帧( 如重复帧) 以减慢其步伐，相 反，在时间相对较慢媒体节目流中丢弃一些帧( 如不重要的帧) 以加快其步伐， 一旦出现媒体节目流同步时，就让它们共享一个信道，从而达到节约带宽资源目 的，以让更多的用户能得到服务。 1 2 1 5 分组融合技术 分组融合技术是分组技术和融合技术的结合物。一方面，使用分组技术，对 用户进行分组，同组用户共享信道：另一方面，使用融合技术，将节目相同且时 间接近的不同信道进行融合，使小组成为大组。这样，将更加提高网络带宽的利 用率，也减少系统开销。如图1 1 t 在【0 ，f 1 】时段请求q l l 、q 1 。，共享流从时刻 t l 发出的为，在【f 1 ，r 2 】时段请求q 2 】、q 2 。，共享流从时刻t 2 发出的岛，在时刻 赴开始对s l 和岛进行融合，直至它们速度相同，这时恢复至正常速度，去掉， 让两组请求一起共享蜀。 图1 1 融合示意图 1 2 16 镜像服务器技术 随着i n t e m e t 的迅速发展，媒体网站和企业网站的业务都急剧增加，因此，网 站必须拿出应付的策略。并行服务器结构，从局部来看它是一种很好的策略，但 从整体上看，还是存在很大的问题：i n t e m e t 难堪重负。因为，传统的媒体发布系 第3 页 国防科学技术大学研究生院硕士学位论文 统采用标准的集中式的客户机服务器技术实现内容的传送，每个客户端都需要创 建一个直接连接服务器的信道。镜像服务器技术是一种“送货上门”的技术。一 些门户网站在需求量很大的地方建立镜像服务器，它既分担服务器的网络流量， 同时也给i n t e r n e t 减轻了很大的压力。 1 2 1 7 边缘服务器技术 在这种架构中，发布服务器由多台位于核心的广播服务器和位于网络边缘的 服务器组成，形成种可伸缩的应用级内容传送解决方案。任何一台广播服务器 都可以向边缘服务器发布内容，而由边缘服务器向客户提供服务。这种新的架构 具有很好的扩展性。随着企业的发展，网络的流量不断增加，可以在网络的边缘 增加这类服务器。 1 2 1 8c d n 技术 c d n ( c o n t e n td e l i v e r yn e t w o r k ) 技术也是提供边缘服务。与边缘服务器不同 的是，c d n 服务由独立的运营商提供。c d n 可简单理解为网络缓存、网络代理。 它的工作方式是将网站的内容发布到最接近用户的网络边缘，使用户可以就近取 得所需的内容。c d n 主要用来减少骨干带宽的负担，提高骨干网的利用率。 如图所示，流媒体的c d n 服务主要有两方面的用途：一是用于处理访问量比 较大的网站的日常流量，例如c c t v 网站；二是用来应付重大事件所产生的爆发 流量，例如企业所做的重大活动的网上直播。 图1 2 支持流媒体的c d n 服务 1 2 2p 2 p 流媒体服务技术 随着流媒体在网络上的应用越来越广泛，基于p 2 p 技术的流媒体系统正以前所 未有的速度占领着传统流媒体系统的市场分额。从2 0 0 2 到2 0 0 6 ，p 2 p 流媒体成为 研究人员讨论的热点，大量的论文和成果在这一时期发表和公开。p 2 p 流媒体服务 技术的研究主要集中在2 个方面：p 2 p 应用层组播树技术和非树型结构p 2 p 流媒 第4 页 国防科学技术大学研究生院硕士学位论文 体技术。 1 2 2 1p 2 p 应用层组播树技术 应用层组播技术的核心思想是在所有参与节点之间，构建应用层上的树型逻 辑拓扑结构。树的根节点是数据源，树上每个节点在接收数据的同时转发数据， 通过每个父子节点对的单播转发形成组播。如图1 3 所示。所有在应用层组播树 上的节点都是请求同一节目，且只从唯一的父节点来获取节目。 图1 3 应用层组播示意 应用层组播技术适合于架构视频直播服务系统或应用到视频点播系统中某热 门节目的服务策略，即适合于节目请求率高、并发请求量大的媒体应用需求。由 于组播树中节点与节点之间服务能力差距比较大同时也是有限的，因此当节点服 务其他节点时不能有太多的子节点，子节点过多会造成该节点负载过重：另外节 点与服务器之间的距离不能过长，过长会导致媒体播放时延迟太大，影响服务质 量，即树的高度是有限制的。 应用层组播技术能够基本解决i p 层组播需要路由器保持每个组播组的状态信 息和需要在基础架构层有相应改变两大缺陷。具有三大优势： ( 1 ) 所有数据包都 是通过单播传输的，无需路由器的支持，使得广泛配置的速度加快：( 2 ) 底层物 理网络无需保存状态信息，而终端节点仅需要保存该组少量与其邻近成员的信息； ( 3 ) 利用单播可以有效地采取适合媒体应用特点的错误恢复、流量控制、拥塞控 制等策略。 但是应用层组播技术也有其缺点：( 1 ) 效率不高，一条应用层链路可能会反 复经过同一条物理网络链路；( 2 ) 延迟大，两个终端节点之间的通讯可能要通过 其它节点，这使得所有节点之间很难同步接收数据：( 3 ) 丢包概率大。 目前主要的研究成果有：基于隐含构架的应用层组播，如具有结构化的资源 第5 页 国防科学技术大学研究生院硕士学位论文 定位算法p a s t r y 、t a p s t r y 及组播树协议c a n ：基于m e s h 构建的应用层组播，如 交互方式媒体流应用的架构方式n a r a d a 和应用层组播协议s c a t t c r c a s t ：基于直接 构建的应用层组播，如应用层组播协议n i c e 、z i g z a g 、y o i d 及应用级组播系统 o v e r c a s t ；还有一部分研究是基于传统的流调度策略的应用层组播，如多媒体传输 协议o s t r e a m 、l a y e r e dp e e r - t o p e e rs t r e a m i n g 、p 2 c a s t 1 2 2 2 非树型p 2 p 流媒体技术 所谓非树型p 2 p 流媒体技术，是指服务节点和请求节点之间的逻辑拓朴结构 不再是树型结构，请求节点不再通过树的中间节点中转得到数据。新加入的请求 节点首先找到能为其提供服务的节点集合，然后制定相应的多源协同策略，最后 直接向这些服务节点请求数据。对于视频点播系统中请求率相对不高、并发请求 少的节目，可以采用非树型服务策略。 非树型p 2 p 流媒体技术研究涉及三个基本问题：( 1 ) 是非结构化资源定位技 术，即在没有建立树型或者其他结构化拓扑的前提下如何找到所需的媒体数据。 目前该方面的研究成果主要有n a p s t e r 、c - n u t e l l a 、f r e e n e t 等p 2 p 系统。( 2 ) 是媒 体流调度与控制技术，主要是指的是多源协同技术，即多个源节点之间采用什么 策略将媒体数据传输到请求节点才能保证用户的基本服务质量需要。目前主要的 研究成果集中在l o o k u ps u b s t r a t e 、c o u e c t c a s t 、c o o l s t r e a m i n g 等系统中。( 3 ) 是 媒体数据布局与存储技术，即由于媒体文件数据量大，而节点的存储资源有限， 需要研究如何将媒体数据切分并在已被服务节点中冗余布局来保证教小的播放启 动延迟和拖动延迟。三个层次并非相互独立的，而是相互依赖、紧密联系的。 多源协同服务技术作为本文的研究重点是对于在当前网络环境下单一源节点 速率无法提供稳定的流媒体服务的一种有效解决方案，其核心思想是参与节点之 间没有固定的逻辑拓扑结构，数据被划分为数据块，所有正在下载的节点可从共 享数据的源节点，或更多地从其他节点协同地获取它所需要的数据块，从不同的 节点获取不同的数据块，从而协同地获取到整个数据。多源协同技术主要分为三 个方面：( 1 ) 数据分配算法；( 2 ) 节点选择算法( 3 ) 准入控制算法。本文对前 两个方面做了做详细的研究。 第6 页 国防科学技术大学研究生院硕士学位论文 图1 4d o n c t 中的组成员关系( 源节点a ) 互联网上第一个p 2 p 网络电视c o o l s t r e a m i n g 中的节点问的组成员关系如图 1 4 所示，各个节点都会从多个邻居节点协同地获取数据。 多源协同技术的优点在于：能充分利用所有节点的带宽资源，使得并行下载 能力得到极大拓展。但缺点在于：缓冲机制是必不可少的，播放的起始延迟较大； 节点间的流调度是多对一的，相对较复杂。 1 2 3 p 2 p 点播系统与直播系统的技术比较 近年来国内出现了较多的p 2 p 流媒体系统，如p p s t r e a m 、p p l i v e 、c o o l s t r e a m i n g 等，但是这些系统都是致力于流媒体直播方向。直播可以用少数的媒体流来带动 大量的用户，因为用户不能主动选择所需要的媒体播放进度，而只能被动的接收 数据来观看，因此可以将现有研究得较成熟的应用层组播树技术应用到直播系统 中来，这样在理论上讲直播系统没有人数的限制，带来更多的并发用户量的同时 可以保证q o s 。与直播系统相关的技术归结为几个方面： ( 1 ) 系统的可扩展性， ( 2 ) 有限实时b u f f e r 管理策略，( 3 ) 组播树协议，( 4 ) 同一网段的判断策略。 研究表明点播系统中用户的访问具有“访问局部性”特点，这种局部性有两 种形式：时间局部性，即大部分的访问都集中于某些黄金时间段，如周末晚上访 问量高于工作日等，新节目刚投入市场时访问量很大，随后逐渐下降等；节目局 部性，即大部分的访问都集中于- - + 部分热门节目上，因此在黄金时间段的热门 节目点播上可以应用与直播类似的组播树技术来扩大并发用户量。但是点播较之 直播，有其自身的更人性化的特点：点播中用户观看时间和节目内容是事先不可 精确预测的，并且用户对某一节目内容可以直接定位到想要播放的帧，即点播必 须具有v c r 功能。因此在点播系统中会以较少的比例利用p 2 p 组播树技术，而需 要更多地用到非树型p 2 p 流媒体服务技术。 我们就已有的传统点播系统和p 2 p 直播系统的分析得出基于t 2 p 技术的点播 系统需要研究以下几个方面技术： ( 1 ) 热门节目点播中组播技术的使用，( 2 ) 第7 页 国防科学技术大学研究生院硕士学位论文 媒体数据的分配策略，( 3 ) 有限实时b u f f e r 管理策略，( 4 ) p e e r 节点的传输选 择策略，( 5 ) 索引服务器的传输调度策略。点播系统的核心问题归结为：( 1 ) 播放前的缓冲延迟，( 2 ) 播放过程中的v c r 延迟，( 3 ) 稳定连续的流服务。 就国内现有的网络状况来分析，p 2 p 流媒体点播系统比直播系统具有更多技术 难点，也具有更大的挑战性。至今国内还没有一个完善的p 2 p 流媒体点播系统， 我们正是基于这样一种应用需求，来自主研发p 2 p 点播软件。目的是将优良的多 源协同策略应用到我们的系统中，保证较高的服务质量。 1 3 主要工作 本文主要研究p 2 p 流媒体多源协同技术，其中创新性的研究工作主要包括两 方面：p 2 p 流媒体系统中的数据分配算法和半成熟节点完善选择算法。 在数据分配算法方面，我们针对现有经典理论上的数据分配算法的局限性提 出了动态数据分配算法d d a ，该算法能够应用在实际网络环境下的p 2 p 流媒体系 统中，并减小了由于节点平均传输速率的波动或节点的退出对流服务质量造成的 不良影响，能够使得活动节点子集中的源节点的传输速率之和在9 4 的流服务时 间内始终保持在播放速率以上的一个范围内波动。 在节点选择算法方面，我们采用了针对需求的选择思想，提出了半成熟节点 的完善选择算法s p c s 。该算法能够进一步减小半成熟节点的漏选，扩大了节点的 选择空间，统计表明在流服务前期，s p c s 平均启动延迟比f a s t 缩小了大约1 5 ， 如果在有v c r 的系统中，效率会更高。 在文章的最后，本文对我们在v s h o w 流媒体系统所做的工作进行了总结。对 逻辑功能层的分析和设计作了详细的阐述，以期加入更加有效的策略提高整个系 统服务的质量。 1 4 论文结构 全文共分六章： 第一章介绍课题的研究背景、国内外研究现状以及本文的主要研究工作。 第二章对国内外p 2 p 多源协同技术基础进行深入讨论，从现有的经典数据分 配算法、节点选择算法和准入控制算法三方面入手，分析了这些算法 的基本原理。 第三章提出了动态数据分配算法，减小了节点传输速率下滑和节点退出对服 务质量造成的影响，具有更好的鲁棒性。 第四章提出了半成熟节点的完善选择算法，该算法减小了播放的启动延迟， 第8 页 国防科学技术大学研究生院硕士学位论文 扩大了节点的选择空间。 第五章阐述了v s h o w 流媒体系统中p e e r 节点软件的逻辑功能层的详细设计 方案，以期加入更加有效的策略提高整个系统服务的质量。 第六章总结全文，并阐述了进一步的研究方向。 第9 页 国防科学技术大学研究生院硕士学位论文 第二章p 2 p 流媒体系统多源协同技术基础 由于当前i n t c m e = t 上单个源节点的网络传输速率难以满足媒体文件的播放的速 率要求，而且是动态变化的，因此p 2 p 流媒体点播系统需要实时调度多个源节点 协同地为一个请求节点提供流服务，即需要使用多源协同流调度技术。多源协同 技术主要包括3 个方面：数据分配算法、节点选择算法和准入控制算法。近年来 有许多研究多源协同技术的文章，也提出了很多经典的数据分配算法和节点选择 算法，下面我们将逐一来分析它们。 2 1 现有数据分配算法 2 1 1 最优分配算法o t s 文【1 】提出的算法是基于一个具有以下特点的p 2 p 流媒体系统：( 1 ) 系统流容量 动态增长；( 2 ) 对等节点不具有类媒体服务器的行为：( 3 ) 各个对等节点上传带宽是 不同的；( 4 ) 每个流会话包含多个源节点。本小节将概要地介绍文1 1 中提出的媒体 数据分配算法o t s 的p 2 p 流媒体模型定义和算法思想。 2 1 1 1p 2 p 流媒体模型定义和假设 o t s 的p 2 p 流媒体模型及其假设陈述如下： ( 1 ) 节点带宽用岛表示媒体数据的播放速率，假设每个请求节点b 愿意也能 够留出下行带宽r 。( p ，) = r o 来接受流服务。一个源节点只所提供的输出带宽r 。 c 只) 具有下面形式中的一个：r 0 2 、r o 4 、j v 8 、r 以“，其中为自然数。 ( 2 ) 节点分类根据节点提供输出带宽的个值，将所有节点分成级。即， 一个提供的输出带宽为r 以”( 1 蔓r sn ) 的节点称为胛级节点，行越小，级别越高。 ( 3 ) p 2 p 系统容量定义为系统能同时提供的p 2 p 流会话总数。理论上，系统 在时刻f 的容量为( f ) ：l 至羔掣l ( 以f ) 是系统在时刻r 的源节点集合) 。 l j ( 4 ) 媒体数据段假定媒体数据能够分成等大小且连续段，并且是c b r 的媒体 流，因此，假设每小段的播放时间8 t 相同( 万t 以秒为数量级) 。 2 1 1 2 数据分配算法o t s 基于上面的模型，问题可表达为：对于一个请求节点只和一个源节点集护1 ， 产，” ( 一般称为活动节点子集) ，如果，置o = r 。( p ，) ，那么，确定( 1 ) 由每个 第l o 页 国防科学技术大学研究生院硕士学位论文 源节点尸“( 1 j m ) 传输的媒体数据段；( 2 ) p ，的播放缓冲延迟。目标是：保证播 放的连续性，并且在p ，的缓冲延迟最小。 定义缓冲延迟为：媒体数据段传输开始到p ，开始播放之间的时间间隔。如图 2 1 所示不同的媒体数据分配策略导致不同的缓冲延迟。请求节点为p ，其活动 节点子集中源节点分别为p l 、产、，、p ，它们的输出带宽分别是r d 2 、r d 4 、r 0 ，s 和r d 8 。在分使用分配方案i ，只的播放开始时间是5 8 t ，即缓冲延迟是5 6 t 。 然而，如果使用分配方案，缓冲延迟将降低为3 j ，。 ， p ， ol23 45 6 7 ， ， ，i ， ol37 2 6 5 4 5 &3 乱 图2 1 不同的媒体数据分配导致不同的缓冲延迟 o t s 算法由请求节点执行：在计算媒体数据分配后。它将按照分配结果与活 动节点子集中的源节点进行流会话。然后源节点将开始传输分配弱的媒体数据段。 算法o t s 的伪代码下所示： 假设脚个源节点已经按它们提供的输出带宽的降序排列，并且其中最低级为 。算法对前2 疗个段的分配进行计算，对媒体文件的其余部分，按这个分配来重 第1 1 页 国防科学技术大学研究生院硕士学位论文 复。事实上，图2 1 中分配方案i i 正是由o t s 算法计算出来的。有定理可以保证： 给出一个有m 个源节点的活动节点子集 p 1 ，产，p “) 和一个请求节点p r ，如果 有r f 勋lc p r ) = ：，兄。( ，m 那么，算法o t s 将计算出最优媒体数据分配，它 获得的缓冲延迟是噶? = ( 掰一1 ) 艿- t 2 1 2 数据分配算法f s s 文【2 】集中研究p 2 p 流媒体系统的两个问题： ( 1 ) 多源协同的流会话传输调度，即数据分配问题。提出固定长度槽调度方案 ( f i x e d - l e n g t hs l o t t e ds c h e d u l i n g ，f s s ) 。与上面介绍的o t s 不同，f s s 采用可变长 度数据段，其大小由每个源节点上传带宽决定。 ( 2 ) 媒体内容的快速分布。对于一个给定的到达速度，在一个短的时间内将请 求节点变成源节点是非常重要的。提出了一种提高p 2 p 系统容量增长速度的机制， 称为f a s t 。将在下节现有的节点选择算法分析中详细介绍。 2 1 2 1p 2 p 流媒体模型定义和假设 文f 2 】中提出的f s s 算法，基本沿用了o t s 中的模型：将索引服务器选出的能 够提供媒体内容的源节点集合称作为一个候选节点集合。请求节点从候选节点集 中选择它需要的源节点组成活动节点子集，并为子集中每个源节点都开辟一个信 道。请求节点根据数据分配策略从这些信道获取媒体数据，并将其存储在它的本 地缓冲中，然后成为该节目的源节点而被索引服务器选中，加入其他请求节点的 候选节点集合中。注意，f s s 与o t s 不同，f s s 算法假设一个源节点能够将媒体 文件提供给多个请求节点，即一个源节点同时可以对应多个流会话。假设一个请 求节点能够通过一个合适的搜索机制获得候选节点集和每个节点资源使用的有关 情况。假设y 是媒体数据播放速度，每个请求节点p ，有输入带宽r 。( b ) 和输出带 宽r 。( p ，) ，节点的输入和输出带宽上是不同的。并假定o sy 且兄。 ( p ，) 0 2 1 2 2 固定长度槽调度算法f s s 基于上面的模型和假设，问题可表达为：对一个请求节点b 和门个信道，决 定在每个信道上传输的数据段和这些段的传输次序。目标与缓冲延迟的定义沿用 o t s 算法。如何获得p ，的候选节点集合的问题，已经在上一小节得以说明。如 果数据传输在带宽低于r 且可变的信道上，那么缓冲延迟是不可避免的。因为数 据传输次序同播放次序不同。因此，设计好的数据分配方案对降低缓冲延迟是必 要的。 第1 2 页 国防科学技术大学研究生院硕士学位论文 函数p ( o 表示开始播放后t 秒内所播放的媒体数据总量，d ( o n 是从请求节点缓 冲媒体数据时刻开始t 秒内收到的连续数据位移量函数。假定媒体数据为c b r 流， 数据总量可用秒为单位表示。显然，下面条件满足： v f20 ，d ( f ) p ( f ) 公式2 1 图2 3 分别以o t s 和f s s 的调度方案为例说明了p ( f ) 和吠f ) 的增长曲线。图中 有信道带宽分别为y 2 、y 4 、r 8 和y 8 的4 个源节点来为请求节点只提供服务。 ( a ) o t s ， - 。 ，留 ， 黟 7 乌 费 & t l倍 201 01 4 i 2 l e 图2 3 传输调度方案 c o ) f s s 如图2 3 所示，根据o t s ，请求节点在这些信道上向源节点分配了8 个r 8 秒的段，缓冲延迟要万求满