（计算机科学与技术专业论文）p2p实时流媒体传输调度技术研究.pdf

摘要 流媒体应用是推动未来宽带应用的主动力，但流媒体对带宽的高占用特性使其在 i n t e r n e t 上大规模应用面i 临诸多困难。几乎所有现有的流媒体系统都是基于客户端丑艮务 器( c s ) 模式，如果使用单播c s 模式，那么服务器网络带宽就会很快用光。单源组播是 一种解决办法，它用单一的流提供给所有客户。由于有关可扩展性以及对诸如拥塞控制 和可靠性等较高层功能支持方面的难题，i p 组播应用发展缓慢。c d n ( c o n t e n td e l i v e r y n e t w o r k ) 通过把服务和内容“推”向网络的“边缘”，也能减轻服务器和网络负载，但 其昂贵的费用使得一般i c p s 无法承担。 p 2 p 模式是解决服务器链路瓶颈问题的理想模式。在p 2 p 模式中，媒体内容通过使 用客户们自己的带宽分发。p 2 p 系统中客户贡献资源给群体，反过来又使用其它客户提 供的资源。节点为了共享内容而合作，数据通信量不会固定在某个特定的地方。典型的 情况是，没有掌管内容的中心服务器，节点处在平等地位。近几年，已经有许多p 2 p 系 统方面的研究，这些研究主要是一般p 2 p 系统中数据查找、存储管理和应用层组播。在 p 2 p 网络上分布式流媒体方面的问题也已经有了一些研究。然而，可以说p 2 p 流媒体系 统方面的研究仍处于初期，其性能改善和模型一般化仍然有一些研究余地。 本文，主要研究了两个问题：( 1 ) p 2 p 流媒体中多供应者流会话媒体数据的传输调度： ( 2 ) p 2 p 实时流媒体中的节点选择。对于问题( 1 ) ，本文深入研究和分析了两个现有的数据 分配算法o t s 和f s s ，进一步提出了三个新的数据分配算法，其中z b s 算法具有比o t s 和f s s 更好的适应性和更低的缓冲延迟，同时也减轻了接收者对流接收的维持开销。模 拟实验表明z b s 算法使系统容量增长更快。对于阀题( 2 _ 本文深入研究了一个新型的 p 2 p 实时流媒体服务模型c o l l e c t c a s t ，指出了其节点选择问题模型及其算法中存在的问 题，并对它们做出了修改或提出了改进方案。模拟实验结果表明，改进的方案使接收者 得到质量更高的流。 关键字：p 2 p 流媒体媒体数据分配节点选择 第1 页 竭翰科学拄术九学研究生虢擎缸上 a b s t r a c t m e d i as t r e a m i n gw i l lb e c o m et h em a i n l yd r i v i n gf o r c ef o rf u t u r eb r o a d b a n dn e t w o r k a p p l i c a t i o n b u tm e d i as t r e a m i n gi m p o s e sah i g hl o a do nt h eu n d e r l y i n gn e t w o r ka n dt h e s t r e a m i n gs e r v e r , a n dt h e r es t i l le x i s t sm a n yd i f f i c u l t i e sf o rd e p l o y i n gi ti nal a r g e s c a l e a 1 m o s ta l lo ft h ee x i s t i n gw o r k so nm u l t i m e d i as t r e a m i n gi sb a s e do nc l i e n t s e l v e l - m o d e l s s e r v e rn e t w o r kb a n d w i d t hf u n so u tr a p i d l yi fu n i c a s tc l i e n t s e r v e rm o d e li su s e d s i n g l e s o u r c em u l t i c a s ti so n eo ft h es o l u t i o n st h a tu s eas i n g l es t r e a mt of e e da l lt h ec l i e n t s t h e d e p l o y m e n to fi pm u l t i c a s th a sb e e ns l o w e db yd i f f i c u l ti s s u e sr e l a t e dt os c a l a b i l i t y , a n d s u p p o r tf o rh i g h e rl a y e rf u n c t i o n a l i t yl i k ec o n g e s t i o nc o n t r o la n dr e l i a b i l i t y c d n ( c o n t e n t d e l i v e r yn e t w o r k ) p u s ht h ec o n t e n ta n ds e r v i c et ot h ei n t e m e te d g e ，w h i c hc o u l da l l e v i a t e b u r d e no nm e d i as e r v e r sa n dn e t w o r ki n f r a s t r u c t u r e b u tn o r m a li c p sc o u l dn o ta f f o r dt h e e x p e n s i v ec h a r g e a p e e r t o - p e e r ( p 2 p ) m o d e li si d e a la sam o d e lt os o l v et h es e r v e rl i n kb o t t l e n e c k p r o b l e m i nt h ep 2 pm o d e l m u l t i m e d i ac o n t e n t sa r ed i s t r i b u t e db yu s i n gt h eb a n d w i d t ho ft h e c l i e n t st h e m s e l v e s t h ec l i e n t si np 2 ps y s t e m sc o n t r i b u t er e s o u r c e st ot h ec o m m u n i t ya n di nt u r nu s et h e r e s o u r c e sp r o v i d e db yo t h e rc l i e n t s d a t at r a f f i ci sn o tl o c a l i z e do nas p e c i f i cs i t es i n c et h e p e e r sc o o p e r a t ef o rs h a r i n gc o n t e n t s i ti st y p i c a lt h a tt h e r ei sn oc e n t r a ls e r v e rt h a th o l d st h e c o n t e n t s ，a n dp e e r sw o r ko na ne q u a lf o o t i n g t h e r eh a sb e e nm u c hw o r ko np 2 ps y s t e m si n r e c e n ty e a r s t h o s ew o r k sd e a l tm a i n l yw i t hd a t al o o k u pa n ds t o r a g em a n a g e m e n ta n d a p p l i c a t i o nl e v e lm u l t i e a s ti nag e n e r a lp 2 ps y s t e m h o w e v e r , i tc a nb es a i dt h a tt h ew o r ko n p 2 pm e d i as t r e a m i n gs y s t e m si ss t i l li nt h ee a r l ys t a g e ，a n dt h e r ei ss t i l ls o m er o o mf o r i m p r o v e m e n t o fp e r f o r m a n c ea n dg e n e r a l i z a t i o no fm o d e l i nt h ep a p e r , w ef o c u so nt w op r o b l e m sa sf o l l o w ：( 1 ) t h et r a n s m i s s i o ns c h e d u l i n go ft h e m e d i ad a t af o ram u l t i s u p p l i e rs t r e a m i n gs e s s i o ni np 2 pm e d i as t r e a m i n g ，a n d ( 2 ) p e e r s e l e c t i o ni np 2 pr e a l t i m em e d i as t r e a m i n g t ot h ep r o b l e m ( 1 ) ，w es t u d ya n da n a l y s ed e e p l y t w oe x i s t i n gm e d i ad a t aa s s i g n i n g a l g o r i t h mo t sa n df s s ，a n df u r t h e rp r o p o s et h r e em e d i a d a t aa s s i g n i n ga l g o r i t h m s ，i nw h i c h ，z b sa l g o r i t h mi sb e t t e ra d a p t a b i l i t ya n dl o w e rb u f f e r i n g d e l a yt h a no t sa n df s s ，a n da l l e v i a t e st h eo v e r l e a dm a i n t a i n i n gt a k i n go v e rs t r e a m i n gi n r e c e i v e l - t h es i m u l a t i o nr e s u l t sd e m o n s t r a t et h a tz b sa l g o r i t h mr e s u l t si na c c e l e r a t i n gs p e e d a tw h i c ht h es y s t e m ss t r e a m i n gc a p a c i t yi n c r e a s e s t ot h ep r o b l e m ( 2 ) ，w es t u d yd e e p l ya h o v e lp 2 pr e a l t i m em e d i as t r e a m i n gs e r v i c ec a l l e dc o l l e c t c a s t a n dp o i n to u tt h ef a u l t so f p e e rs e l e c t i o np r o b l e mm o d e la n di t sa l g o r i t h mi nc o l l e c t c a s t w em o d i f yo ri m p r o v et h e m t h es i m u l a t i o nr e s u l t sd e m o n s t r a t et h a tt h ei m p r o v i n gs c h e m er e s u l t si n h i g h e rq u a l i t y s t r e a m i n g i nr e c e i v e r k e yw o r d s ：p 2 p m e d i as t r e a m i n g ，m e d i ad a t aa s s i g n i n g ，p e e rs e l e c t i o n 第1 1 页 图目录 图1 1 当前流媒体体系结构示意图，所有客户都由流服务器服务 图2 1 流式传输示意图 图2 2 分组融合示意图 圈2 _ 3 支持流媒体的c d n 服务 图2 4c o l l e c t c a s t 的不同组件和它们之问的相互作用 图2 5 不同的准入控制导致不同的流容量增长一 图3 1 不同的媒体数据分配导致不同的缓冲延迟一 图3 2 算法d 弼函一 图3 3 传输调度方案 图3 4o t s 算法分配总量为l 的数据，段大小为u 3 2 一 图3 5o t s 和f s s 分配3 2 个数据段( 段大小一致) 图3 6o t s 与f s s 在请求节i 点维持肝销的比较 图4 1o t s 算法对虚拟节点集分配数据段 图4 2f s s 分配1 6 个段到例4 1 的供应节点集p = f p l ，p 2 图4 3 算法一对p - - p 1 j 璐分配1 6 个数据段 图4 4 虚拟节点到实际节点数据段的分配及时间变化( 算法一) 图4 5 针对模型一的数据分配算法一一 图4 6 虚拟节点到实际节点数拭一段的分配及时间变化( 算法二) 图4 7 针对模型一的数据分配算法二 图4 8 针对模型二数据分配的z b s 算法 图4 9z b s 算法对虚拟节点集3 进行数据分配 图4 1 0z b s 将接收缓冲开销降至最低 图4 1 1z b s 算法对实际节点集f 1 进行数据分配 图4 1 2z b s 对带宽比为7 ：6 ：3 的供应节点集的数据分配 图4 1 3f s s 对带宽比为7 ：6 ：3 的供应节点集的数据分配 图4 1 4o t s 、f s s 、z b s 性能比较。 图4 1 5 使用o t s 、f s s 和z b s 情况下系统容最增长 图5 1c o l l e c t c a s t 拓扑感知选择得到的最好活动集是 v 2 ，p 3 ，p 6 图5 2 节点可用性：模拟为离散时间随机过程凡( f ) 图5 3 仅两个供应节点且共享路段的预期总速率 图5 4 选择最好节点集的伪代码 圈5 5 一个段的发送过程( 使用f e d l 2 5 ) ，8 = 1 1 5 ) ， 第i i i 页 j 灌均n h怕伸加挖斟笛豁驷”驼弛弭舛弘弘l盆於弱弘 蝤 目酗 。 # 投蕾凡f ：tj ij 。1 i 二院 沧上 图5 6 拓扑感知选择问题模型找不到解 图5 7 网络拓扑实例( 有窄的段和共享拥塞段) 图5 8 改进后的拓扑感知活动集选择算法伪代码 图5 9 接收者感知到的总丢失率。 图5 1 0 接收者的总流速率 4 6 ，4 7 4 9 j j ， 5 1 第i v 页 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含 其他人已经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它 教育机构的学位或证书而使用过妁材料与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示谢意 学位论文题日：! 塑塞吐遣瑾佳接熊强度挂苤盈窀 学位论文作者签名：壶l 查照 日期：诉多月i | 日 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留、使用学位论文的规定。本人授权 国防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子 文档，允许论文被查阅和借阕；可以将学位论文的全部或部分内容编入有关数据 库进行检索，可以采用影印、缩印或扫描等复剿手段保存、汇编学位论文 ( 保密学位论文在解密后适用本授权书) 学位论文题目： 堡塞鲢巍搓链黄捡遵。廑挂盔! 受益一 学位论文作者签名：盎i 鲨三坠日期：枷p 年弓月1 1 碍 作者指导教师签名：盈! 垒! 茎 日期：矽r 年多月1 1 日 第1 章概述 1 1 课题背景及选题依据 计算机技术特别是网络技术的飞速发展，深刻地改变着人们的工作、生活和思维。 随着单机处理能力的增强和宽带网络的普及，人们不再满足于传统的网页测览、文件f 载、聊天等i n t e r n e t 呆板的表现形式，流媒体以其特有的娱乐性和交互性将成为推动未来 宽带应用的主动力。 目前主流的流媒体系统结构仍然是客户端服务器( c s ) 结构。其流服务器实体可 以是一个服务器、一组服务器、一个服务器和缓存或者一组服务器和代理。图l 1 描述了 一个典型的流体系结构。流服务器实体负责为所有客户提供请求的媒体文件。系统能够 支持并发的客户总数( 称为系统总容量) 受限予流服务器实体的资源。这种限制主要来 自网络输出带宽，但也受限于服务器机器的处理能力、内存大小或i o 速度。c s 结构方 式都有可靠性和可扩展性的限制。可靠性限制是因为一个实体服务所有客户，这容易造 成单点失效。可扩展性限制是因为要增加更多的用户请求，就需要增加相当数蹙的供应 服务器f 1 】。 ( 1 i c n t 图1 1 当前流媒体体系结构示意图，所有客户都由流服务器服务 第1 页 因为，多媒体需要高的带宽，所以，如果使用单播a s 模式，服务器网络带宽很快 就会用光。单源组播是一种解决办法，它用单一的流提供给所有客户。i p 组播技术1 2 f 以其多路复用的方式能够减缓服务器和网络的负载，但其在实现方面的复杂性使其在未 来几年内仍难以广泛实施。 近年兴起的c d n 3 i ( c o n t e n td e l i v e r yn e t w o r k ) 服务通过在i n t e r n e t 上广泛部署服 务节点( 如a k a m a i 公司已在全球部署了1 0 ，0 0 0 + 个节点) ，把服务内容“推”向网络的 “边缘”，并把客户请求路由到距客户最近的服务节点，从而减轻了服务器的压力和剥 骨干网络的带宽消耗。然而，为了增加系统总容量而使用代理和缓存，这增加了系统总 成本( 如，c d n 按字节收费的方式使一般流媒体内容提供商无法承担其租赁费用) ， 并且也带来了许多诸如缓存一致性和负载平衡等管理难题。系统总容量仍然受限于缓存 和代理总的资源。这只是将瓶颈从一个中心点转移到少数分散点上，而不是消除了瓶颈。 将媒体文件流向大量客户给底层网络和流服务器增加了很大的负载。多媒体数据量 大的特性连同它的时间性限制，使得在当| ； i n t e m e t 上开发大规模、有成本效益的流媒 体系统结构成为流媒体技术研究中一个挑战性的课题! 上世纪9 0 年代末开始，p 2 p ( p e e r - t o p e e r ) 这项新技术被应用到了i n t e r n e t 上以来， i n t e r n e t 应用又得烈了巨大的推动力。p 2 p 模式是解决服务器链路瓶颈问题的理想模式。 在p 2 p 模式中，媒体内容是通过使用客户们自己的带宽而不是中心服务器来分发的，从 系统中获得媒体内容的节点反过来又为系统中其它节点提供服务，因此p 2 p 系统的容量 是自增长的。 从2 0 0 1 年开始，针对基于p 2 p 模式的媒体服务系统的研究逐步引起众多研究者的 关注，2 0 0 2 - - 2 0 0 4 年发表了许多该领域内的论文，其研究技术可分为两类： 应用层组播树应用层组播树适合于架构视频直播服务系统或应用到视频点播系 统中某热门节目的服务策略，即适合于节目请求率高、并发请求量大的媒体应用需求。 其思想是在各对等节点之间、在应用层之上构建树型层叠结构。树的根节点是直播源， 直播源可以是实时压缩的媒体数据流或流化的热门节目，树的每个节点在接收数据的同 时转发数据。 非树型p 2 p 媒体服务系统对于视频点播系统中请求率相对不高、并发请求：的节 日，可以采用非树型对等模式媒体服务的服务策略。所谓非树型，就是指在服务节点和 请求节点之间的逻辑拓扑结构不再是树型结构，请求节点不再通过树的中间节点中转得 到数据，而是首先找到为其提供服务的服务节点集合，然后制定相应的多源流调度策略， 最后直接由这个服务节点集合中的节点提供服务。由此该类研究涉及三个基本问题： 一是媒体内容搜索，即如何找到所需的完整的媒体数据；二是媒体流调度与控制，即在 保障o o s 前提下，采用什么策略将媒体数据传输到本地；三是媒体数据布局与存储，即 由于媒体文件数据量大，研究如何将媒体数据切分并在已被服务节点中冗余布局的策 略。采用这种模式进行服务，既可能是传统c s 模式视频点播系统的候 者，即在视频 服务器不能满足用户需求的情况下，由对等节点提供服务；也可能是其替代者，完全由其 第2 页 圉翰科学妓术凡j t j i ) 。i 沉。】世泠上 提供服务，无需视频服务器，只需普通视频源节点即可。 无论是应用层组播或是非树型p 2 p 媒体服务系统，它们都可能采用层蒋( o v e r l a y ) 结构，所谓层叠结构，就是架构在物理网络基础1 - 的逻辑结构，该逻辑结构表现为终端 节点及其相互逻辑关联关系形成的边的集合，它能表现出物理网络不具备的、适应应用 需求的属性。其优点在于： 易配置叠结构无需对已有网络基础设施进行改变。 自适应节点加入层叠结构时，它能根据应用需求q o s 参数，如延迟或带宽等，选 择4 i 吲的咋| i - 口j 常点路由以控制其在物理网络巾数掘 输的路径，以实现自适应优化的、 适应p 2 p 环境的异构性。 健壮性即能对层叠结构的架构实施控制并具有自适应性，层叠结构与物理网络相 比，就具有更好的健壮性。例如，如果节点服务能力充足，则可在任何两个节点之间建 立多条完全独立的路径。 用户化层叠结构的节点是用户计算机，所以能够很容易地使用其任何有价值的功 能。例如，可以充分使用磁盘空间。 标准化层叠结构中节点之间的数据传输可以采用t c p 或u d p 等标准协议，而针 对它们都有相对标准的可靠传输协议。 但其缺点是： 管理复杂层叠结构的管理者和被管理者在物理网络中可能距离很远。如果例行的 管理工作随着层叠网络的规模扩大而复杂度也相应增大的话，则会导致管理复杂，控制 开销大。 效率不高层叠结构不能像路由器一样高效，可能多条层叠结构的边会经过物理网 络的同一链路，或者层叠机构中两节点之问形成的路径j 其物理网络q ，形成的路径相 比，走了许多弯路。而且层叠结构建立i p 物理网络之上，可能大量的工作会花费在推 测物理网络的拓扑结构上。 实施困难真实i p 网络不能保证全连通性，大部分机器都在防火墙后。 由于存在以上的优点，才吸引了国内外众多研究者的关注，但也正是由于还存在着 许多缺点，目前采用层叠结构来架构媒体服务系统还没有得到广泛的应用。 在p 2 p 的研究热中，p 2 p 实时流媒体技术却较小地得到人们的注意，而最近几年来， 美国印第安纳州普度( p u r d u e ) 大学计算机系的研究人员却将他们的研究集中于p 2 p 实 时流服务技术，并获得了许多研究成果1 1 】1 4 1 1 5 】6 1 1 7 1 1 8 1 1 9 】f 捌。 由于人们对p 2 p 技术领域的广泛研究，新的p 2 p 结构、原型系统和应用系统不断推 出。然而，许多应用系统是在市场迫切需求的情况下研究开发的，这些系统包括其理论 基础存在许多的问题和不足，它们都需要加以完善。例如，普度大学研究人员对p 2 p 实 时流媒体的研究中就有许多值得进一步研究和探讨的问题。 普度大学研究人员研究的p 2 p 实时流媒体，其模型假设一个流会话中包含多个发送 节点( 也称供应节点) 和一个接收节点，其技术包括三个主要内容：( 1 ) 供应节点选择， 第3 页 ( 2 ) 数据分配，( 3 ) 系统容量快速增长。针对( 1 ) ，提出了拓扑感知选择技术，它推断并利 用底层网络拓扑，用可用率和丢失率标记网络拓扑，并考虑节点共事拥塞路段情况，明 智地从拥有接收节点所请求的媒体文件的候选节点集中挑选出“最好的”活动节点集来 为接收节点提供流服务。针对( 2 ) ，提出所谓o t s 的媒体数据分配算法，使得接收暂缓 冲延迟最小。针对( 3 ) ，提出了所谓d a c 的区分准入控制协议，它优先服务输出带宽高 的请求节点，使系统容量能快速增长，从而更快地服务所有请求节点。 通过本人的研究发现，普度大学研究人员对p 2 p 实时流服务的研究中有两个：e 要内 容值得进步椰f 宄和探讨。其是，拓扑感知选择问题模型及相关内奋，行伍- 曼问题。 其二是，数据分配算法o t s 对供应节点的假设有很大的研究余地。 所以，本文选择“p 2 p 实时流媒体传输调度技术研究”作为研究课题。 1 2p 2 0 网终及流媒体应用研究现状 p 2 p ( p e e r - t o p e e r ) 作为一种应用技术是上世纪9 0 年代术提出的，它能利用i n t e m e t 中的各个节点进行对等计算，充分挖掘了i n t e r n e t 上空闲资源，在利用率、扩展性、容 错等方面具有潜在的巨大优势，并在文件共享、分布式计算、协同工作、i n t e m e t 存储 等方面已经取得了初步的良好应用。如果把p 2 p 引入到流媒体服务中，就可以充分发挥 以往被忽略的众多客户机的作用，让客户机缓存一部分信息，充当一部分服务器的功能， 使服务分散化，从而减轻服务器的负载和网络带宽的占用。所虬，p 2 p 技术艮有潜在的 应用前景。 p 2 p 系统中客户贡献资源给群体，反过来又使用其它客户提供的资源。特别，供应 节点可以将拥有的某一媒体文件流传送给请求节点。这样，节点为了共享内容而合作， 数据通信量不会固定在某个特定的地方。典型的情况是，没有掌管内容的中心j 拔务器， 节点处在平等地位。 1 2 1 第一代p 2 p 系统 第一代p 2 p 系统主要有三个：n a p s t e r l l 、g n u t e l l a 1 2 】和f r e e n e t t l 3 1 。 n a p s t e r 是为著名，它为用户提供了共享m p 3 格式音乐文件的下载。n a p s t e r 实质上 并非纯粹的p 2 p 系统，它通过一个中央服务器保存所有n a p s t e r 用户上传的占乐曲目和 存放位置的信息。n a p s t e r 的不足主要是存在单点失效问题。 g n u t e l l a 是一个纯粹的p 2 p 文件文件共享系统，它没有中心服务器，所有查询都是 通过在网络中以有限洪泛( f l o o d i n g ) 的方式进行，通过t t l ( t i m e t o l i v e ，存活时间) 限制消息转发次数。g n u t e l l a 可能找不到系统中存在的信息，但它主要的不足足在网络 中产生了很大的流量。 p e e r ，意为同等体，在此译为对等节点，本文简称节点。 第4 页 f r e e n e t 是一个基于j a v a 的跨平台分布文件存储系统，其最大的特点就是匿名。文 件发布者、查询者以及文件持有者在f r e e n e t 中都是匿名的。为了实现匿名，f r e e n e t 存 路由上降低了效率，路由中的每个节点不能判断前一个节点是否是文件的请求者，也不 能判断后一个节点是否是文件的持有者。 第一代p 2 p 系统的最大问题是查询的不可扩展性。n a p s t e r 的中央服务器是系统的 瓶颈，g n u t e l l a 和f r e e n e t 在物理网络拓扑之上叠加了一层级虚拟的逻辑拓扑，虚拟逻辑 拓扑中每个节点与其它若干个节点相连。由于数据的存放与虚拟逻辑拓扑毫无关系系 统中搜索几乎是随机进行的。 1 2 2 第二代p 2 p 系统 为了解决第一代p 2 p 系统不可扩展性问题，大量的研究集中在如何构造。个高度结 构化的系统，在这些结构化的系统中，叠加拓扑被严格控制，文件存放在确定的位置上。 系统提供从文件标识符到存放该文件的节点标识符的映射服务，然后将查询请求路由到 该节点。通过以上方法，系统提供了一个可扩展的方案，实现了文件查询的“精确匹配”。 近年来许多研究成果都是基于d h t ( d i s t r i b u t e dh a s ht a b l e ，分布式哈希表) 的分布式 查询和路由算法。 将d h t 算法引入大规模的p 2 p 系统能提高资源定位查询的效率和系统可扩腮性。 d h t 的基本原理是：每个节点有唯一的标识符( n o d e l d ) ，每个消息( 或资源) 也订 个与n o d e l d 属于同一名字空间( n a m e s p a c e ) 的标识符( k e y ) ，k e y 和n o d e l d 在名字空 间中是相对一致均匀分布的：根据消息的k e y ，节点能够将消息路由到n o d e l d 与k e y 最 为“接近”的节点。d h t 可以作为各种大规模分布式应用的底层基础设施，它提供了 统一的简化碰用接口应用程序町以从d h t 获得内在的负载均衡、鲁棒性等优点。 典型的d h t 算法有：c h o r d l l4 1 、c a n t l5 1 、p a s t r y 16 j 和t a p e s t r y t l 卅。 d h t 算法也存在一些问题，比如，基本上没有考虑实际网络拓扑与虚拟逻辑拓扑 之问的关系，没有考虑安全问题，不能支持多关键字查找。 1 - 2 3p 2 p 流媒体服务系统 近年来，基于p 2 p 网络的流媒体服务体系已经引起了许多大学( 如s t a n f o r d u n i v e r s i t y i 1 6j 、p u r d u e u n i v e r s i t y | 1 1 、m a r y l a n du n i v e r s i t y i2 ”j 、c e n t r a lf l o r i d a u n i v e r s i t y l 2 1 1 、c h i n e s e u n i v e r s i t y o f h o n g k o n 9 1 2 2 l 等) 、研究机构( 如m i c r o s o f t r e s e a r c h i 训 等) 以及公司( 如v t r a i l s l 2 4 、a l l c a s t l 2 5 l 等) 的重视并纷纷开展研究。 一般的p 2 p 系统与p 2 p 流媒体系统之问的主要区别在于节点问的数据共享模式：静 者使用“下载后打开”的模式，而后者使用“边下载边播放”的模式。特别，在p 2 p 流 媒体系统中，节点的一个子集拥有某个媒体文件，它们将媒体文件流传送到清求节点。 另一方面，请求节点在流会话期间回放并存储媒体数据，在流会话结束后，它们也成为 第5 页 媒体文件的供应节点。一般的p 2 p 系统通常具有f n 特性： ( 1 ) p 2 p 流媒体系统是自增长的。随着请求节点后柬成为供应节点，系统的总容璧将 扩大：系统服务的节点越多，它的容量将更大。 ( 2 ) p 2 p 流媒体系统是无服务器的。一个节点假定不呈现像服务器一样的行为，比如， 打开大量并发连接。 ( 3 ) 节点在它们贡献给系统的输出带宽上是异构的。造成这种异构性的原因可能是连 接到节点的接入网络不同，或者节点贡献的意愿不同。 特别，p 2 p 流媒体系统还具自特性： ( 4 ) 供应节点与请求节点的关系最典型的足多对一，而不象一般的p 2 p 系统的一对一。 因为，一个供应节点提供的输出带宽可能小于媒体数据的播放速度，所以，在一个实时 流会话中包含多个供应节点是必需的。 由于p 2 p 服务体系需要让某些节点暂时发挥服务器功效，而这些节点与传统的服务 器相比存在一定差异，如提供服务的节点位置不固定、服务能力有强有弱、节点频繁u 入和离开等。而流媒体本身又有其独特性质，如数据存储量大、带宽占用高、持续服务 时间长、高q o s 要求等。因此，在p 2 p 流媒体服务体系中，如何在充分而又合理地利 用众多节点资源的同时并能确保服务质量，面临着许多挑战。 1 3 本文的工作 奉文，主要研究p 2 p 网络实时流媒体传输调度技术。研究工作主要包括两大部分： 数据分配问题和节点选择问题。 对数据分配问题，做了如下工作：( 1 ) 对文f 4 1 中数据分配问题及其算法o t s 和文 2 6 1 中数据分配算法f s s 进行了深入的研究，对o t s 和f s s 进行了客观台理的比较；( 2 ) 放 宽了o t s 算法对数据分配问题的假设，并相应地设计了两个数据分配算法，它们利用 了o t s 算法，进一步提出了一个更好的数据分配的算法z b s ( 零缓存调度) 算法， 它对节点带宽有更低限制，因而具有更好的适应性，同时也有良好的延迟特性，特别， 减轻了接收者对流接收的维持开销。 对节点选择问题，对文【6 】针对有节点异构性、拥塞、丢失率等条件下的多源流调度 技术，尤其是拓扑感知节点选择问题及选择算法做了深入研究，指出了存在的一些问题， 并做出了改进。研究发现，文【6 】拓扑感知节点选择模型以下一些不足之处：( 1 ) 活动爷 点选择问题描述与其算法不一致，( 2 ) 选择问题在某些情况下会导致死循环，( 3 ) 选择问 题在某些情况下找不到解而实际却存在合理的解，( 4 ) 节点权与友好性定义不切实际，( 5 ) 在活动节点集包含共享拥塞路段的节点时速率分配出错。通过深入的研究分析后发现， 上述问题都是在活动节点集包含共享拥塞路段的节点的情况下产生的。本文对文【6 1 拓扑 感知节点选择模型主要做了三个改进：( 1 ) 修改了节点权与友好性定义，( 2 ) 修改了节点 选择模型的约束条件，f 3 修改了节点速率分配公式。 本文的创新工作是：提出了三个数据分配算法，尤其是z b s 算法，它在最小化了 第6 页 国胁科学技术人、，埘兀7 院；位论z 接收节点缓冲延迟的同时，还最大限度地减少了流接收开销；对拓扑感知节点选择模型 及其求解算法做出了很大的改进。 全文共分六章，各章的组织结构如下：第1 章介绍了课题研究背景、p 2 p 网络及p 2 p 流媒体系统和本文主要研究内容：第2 章介绍了传统流媒体传输技术和p 2 p 媒体流传输 技术：第3 章对两个p 2 p 流媒体数据分配算法o t s 和f s s 进行了研究分析；第4 章对 放宽o t s 算法对供应节点带宽假设的更一般的数据分配问题进行了研究，并提出了三 个算法；第5 章深入研究了文【6 1 的拓扑感知节点选择问题，找出了一些不足之处，并做 出r i l ，的改进。第6 章总结了全文，并指出了未来的研究力i _ 。 第7 页 第2 章流媒体传输调度技术 本章简单介绍了传统的流媒体传输技术和p 2 p 网络媒体流传输技术。首先介绍流媒 体的流量控制和内容传送技术，然后介绍p 2 p 流媒体服务的应用层组播树协议和非树型 p 2 p 流媒体，后者包括一个典型的p 2 p 实对流媒体服务模型c o ll e c t c a s t 和一个实现p 2 p 系统容量快速扩大的删c 1 协议。 2 1 传统媒体流传输调度流置控制 多媒体数据包括文字、图形、语音、图像等等，计算机对多媒体数据进行处理，要 解决信息采集、编码、压缩、存储、传输、解压缩、解码、信息重现等等一系列的问题， 当然，在这些方面，现在已经有了许多很好的技术和标准。由于图像所包含的信息量太 大，像电影、电视等节目的视频文件仍然需要很大的存储空间，这使得视频文件在 i n t e r n e t i n t r a n e t 上进行传输有更多的技术困难。随着时代的进步，这些技术问题也 不断地得到解决。 在早期，人们要观看i n t e r n e t i n t r a n e t 上的视频节目需下载整个视频文件。近年 来，流媒体技术。：( 电称流式传输技术) 的诞生和逐步成熟使得人们只需等待很短的时 间就能以边接收边播放的方式欣赏视频节目。流式传输消除了以往下载方式的过长的等 待时间。流式传输中，服务器将原视频文件分解成一个个小的数据包，按照特定的顺序， 以比较平稳的速度发送到网络上，客户端的播放程序可边接收数据边播放，如图2 1 。 用户不必等到文件整个内容全部到达后，才开始播放，数据包也不保存到硬磁盘上，播 后就丢。流式传输还带来另外两大好处：一是，只占用很少的用户端资源；二是，对音 像产品的版权进行了有效的保护。 - _ _ i i 一i 专一h 。卜圈鲤一i 源文件 发送 接收 瑷冲区播教 图2 i 流式传输示意图 对一些热门节目，尤其是大型体育赛事、文艺演出、重大事件等直播节目，用户需 求量特别大，过多的访问要求容易导致服务器崩溃。因此，必须进行流量控制，但同时 又要尽可能地满足客户的要求。这就需要有好的流量控制策略。 第8 页 虮千r 生术人学仙究生院学位沦上 2 1 1 广播和组播技术 在广播方式中，数据包的单独一个拷贝将发送给网络上的所有用户( 无论用户需 要否) 。无疑它减小了网络的负载和发送者的负担。但是，广播方式，只有在支持r 播 的网络上才能实现。因此，广播方式通常只在小范围内使用。 组播”类似于广播。在组播方式中，数据包的单独一个拷贝将发送到一个组地址 所有加入该组的用户都可以收到。目前，组播已经得到了广泛的应用，很多实时的多媒 体会议及教育系统都是基j 组播t 发的。 2 1 2 广播式点播技术 广播式点播是以广播的方式满足点播需求，其目的在于一个节目支持所有愿意观看 该节目的所有用户。其基本思想是将一个节目划分为若干段，每一段占用一个广播频道 并在该广播频道上轮循广播。用户在点播时，先等待至第一段的开始；在播放某一段时， 可以同时接收下一段的视频内容，以达到段段之间的不问断播放。出于视频输出采用广 播模式，且分段轮循，因此用户在任意时亥b 想观看该节目时，只要稍作等待便可，达到 点播观看的目的。该模式般应用于热门节目的播放中。 2 1 3 分组技术 分组在于集中访问时减少系统开销。在v o d 应用中，由于大多数请求集中在少数 的热门节目上，而且经常集中在一个黄金时段，在此黄金时段中每一个短的间隔时问内 都可能有对同节目的人量请求。分组技术1 的做法是，将黄金时问段平均分成计：多，j 、 的时间间隔，针对每一个时间间隔，收集所有的用户请求并加以分组，相同清求的用户 在同组中。然后服务器为不同的请求各分配一个信道，同一组的用户弛享个信道卜 的相同的视频流。这种策略虽然使一些用户的时延增大，但却可能成百上千倍地满足大 量的用户需求。只要时间间隔选取适当，加上网络造成的时延，用户能接受就可以。 2 1 a 融合技术 融合技术在于将针对于同一节目请求的时间比较接近的多个视频流合并为一个流 以减少开销。融合技术1 同分组技术的基本出发点是相同的，都是为了使得多个用户共 享同一视频流。与分组技术不同的是，融合技术首先保证即时响应用户请求，然后根据 情况，对相同节目且时间接近的多个视频流，在时问相对较快视频流中插入一些本不必 要的帧( 如重复帧) 以减慢其步伐，相反，在时间相对较慢视频流中丢弃一些帧( 如不 重要的帧) 以加快其步伐，一旦出现视频流同步时，就让它们共享一个信道，从丽达到 节约带宽资源目的，以让更多的用户能得到服务。 第9 页 2 1 5 分组融合技术 分组融合技术口8 1 是分组技术和融合技术的结合物。一方面，使用分组技术，对用户 进行分组，同组用户共享信道；另一方面，使用融合技术，将节目相同且时蛳接近的f ： 同信道进行融合，使小组成为大组。这样，将更加提高网络带宽的利用率，也减少系统 歼销。如图2 2 ，在【o ，t 1 】时段请求q 1 l 、q l m 共享流从时刻t 1 发出的s 1 ，在【l l t 2 】 时段请求q 2 1 、q 2 i l ，共享流从时刻t 2 发出的s 2 ，在时刻t 2 开始对s 1 和s 2 进行融 合，直至它们速度相同，这时恢复s 1 至n 二常速度，去掉s 2 ，、止两组请求一起共事s l 。 图2 2 分组融合示意图 2 2 内容传送技术 随着i n t e r n e t 的迅速发展，媒体网站和企业网站的业务都急剧增加，因