（计算机科学与技术专业论文）一种面向p2p流媒体的应用层组播协议算法.pdf

中文摘要 中文摘要 摘要：随着i n t e r n e t 和计算机技术的迅猛发展，以视频点播、远程教育为代表 的流媒体业务不断涌现，在i n t e r n e t 上开展流媒体直播或点播业务是未来的发展方 向。为满足流媒体对带宽、实时性的要求，已有的技术主要是内容发布网络( c d n ) 和i p 组播。然而由于c d n 技术的昂贵成本以及l p 组播技术的自身的种种限制， 阻碍了流媒体技术的大规模部署。由于应用层组播在节约网络资源方面相对于i p 组播有其巨大的优势，组播技术的研究学者把眼光转到了应用层组播上来。对于 一个p 2 p 流媒体系统来讲，基于应用层组播的协议设计关系到整个系统的稳定性 和高效性，因此，设计一个合理的应用层组播协议是一件很有意义的事情。 本文主要研究了一种面向p 2 p 流媒体系统的应用层组播协议算法。在充分分 析了已有的应用层组播协议的基础上，设计了一种面向流媒体系统的应用层组播 协议，提出了一个基于效用因子的应用层控制拓扑构造和数据转发树的构造算法， 并给出了数据转发树的维护机制和数据传输的同步机制。 本文首先研究了已有的应用层组播协议的设计方法，介绍了p 2 p 流媒体技术 和组播原理，分析了应用层组播比i p 组播技术具有的优势，在此基础上给出了面 向p 2 p 流媒体的应用层组播协议的总体设计，包括信息交换协议和数据传输协议， 以及源节点端和普通节点端的具体模块设计。根据设计的模块分别给出了控制拓 扑构造算法和数据转发树的构造算法，提出了数据传输的同步机制。最后对该协 议进行了仿真实验，并与已有的n i c e 协议进行了性能对比。本论文的研究结果是 实现了一种能有效防止拓扑不匹配和具有良好性能的流媒体系统的应用层组播协 议算法。 关键词：应用层组播；p 2 p ；流媒体；同步机制 分类号：t p 3 9 3 1 北京交通人学硕士学位论文 a bs t r a c t a b s t r a c t ：w i t ht h e d e v e l o p m e n to fi n t e m e ta n dc o m p u t e rt e c h n o l o g y , t h e s t r e a m i n gm e d i ac o m e so u to n ea f t e ra n o t h e rl i k ev o d ( v i d e oo nd e m a n d ) a n d l o n g - d i s t a n c ee d u c a t i o n i ti st h ef u t u r ed i r e c t i o nt od e v e l o pv o d o rv i d e ob r o a d c a s to n t h ei n t e m e t t h ec d n ( c o n t e n td i s t r i b u t e dn e t w o r k ) a n di pm u l t i c a s tt e c h n o l o g yh a v e m e tt h er e q u i r e m e n to fs t r e a m i n gm e d i as y s t e mo nb a n d w i d t h b u tt h e yh a v em a n y d i s a d v a n t a g e sw h i c hh i n d e r e dt h ed e v e l o p m e n to fs t r e a m i n gm e d i at e c h n o l o g y a tt h i s t i m e ，a p p l i c a t i o nl a y e rm u l t i c a s tc o m e si n t ob e i n gt oo v e r c o m et h es h o r t c o m i n g s i ti s i m p o r t a n tf o ras t r e a m i n gm e d i as y s t e mt od e s i g nan i c ea p p l i c a t i o nl a y e rp r o t o c 0 1 i nt h i sp a p e r , a na p p l i c a t i o nl a y e rm u l t i c a s tp r o t o c o la l g o r i t h mw h i c hi sp 2 p s t r e a m i n gm e d i a - o r i e n t e dw a sp r o p o s e d a f t e rt h ea n a l y s i so fe x i s t i n ga p p l i c a t i o nl a y e r m u l t i c a s tp r o t o c o l s ，a na p p l i c a t i o nl a y e rm u l t i c a s tp r o t o c o lw h i c hi sp 2 ps t r e a m i n g m e d i a - - o r i e n t e dw a sd e s i g n e d a na l g o r i t h mi sp r o p o s e dt oc o n s t r u c tc o n t r o lt o p o l o g y a n dd a t af o r w a r d i n gt o p o l o g y i ti sb a s e do nau t i l i t yf a c t o r a tt h es a m et i m e ，t w o m e c h a n i s m sw e r ea d v a n t a g e dn a m e dd a t a f o r w a r d i n gm a i n t e n a n c ea n dq o s s y n c h r o n i z a t i o nr e s p e c t i v e l y t h ee x i s t i n ga p p l i c a t i o nl a y e rm u l t i c a s tp r o t o c o l si sa n a l y z e da tf i r s t ，t h e np 2 p s t r e a m i n gm e d i at e c h n o l o g ya n dm u l t i c a s tt h e o r yw a si n t r o d u c e d ，b a s e do nw h i c han e w p 2 ps t r e a m i n gm e d i a - o r i e n t e d a p p l i c a t i o nl a y e rm u l t i c a s tp r o t o c o lw a sd e s i g n e d i t c o n c l u d e sm e s s a g e - e x c h a n g ep r o t o c o l ，d a t a t r a n s m i tp r o t o c o la n dc o n c r e t em o d u l e s t h e na na l g o r i t h mi sp r o p o s e dt oc o n s t r u c tc o n t r o lt o p o l o g ya n dd a t a f o r w a r d i n g t o p o l o g y a tl a s t ，o u rp r o t o c o lw a ss i m u l a t e da n dw a sc o n t r a s t e dw i t hn i c ep r o t o c 0 1 t h er e s u l ti san e w a p p l i c a t i o nm u l t i c a s tp r o t o c o lw a sp r o p o s e dw h i c hc a np r e v e n tt h e t o p o l o g yn o tm a t c h i n ga n dh a sf i n ec a p a b i l i t y k e y w o r d s ：a p p l i c a t i o nl a y e rm u l t i c a s t ；p 2 p ；s t r e a m i n gm e d i a ；s y n c h r o n i z a t i o n m e c h a n i s m c l a s s n o ：t p 3 9 3 1 北京交通人学硕十学位论文 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的研 究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表或 撰写过的研究成果，也不包含为获得北京交通大学或其他教育机构的学位或证书 而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作 了明确的说明并表示了谢意。 学位论文作者签名：孝- 嗖青刁哼签字日期：切7 年匆月，日 学位论文版权使用授权书 本学位论文作者完全了解北京交通大学有关保留、使用学位论文的规定。特 授权北京交通大学可以将学位论文的全部或部分内容编入有关数据库进行检索， 提供阅览服务，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。 同意学校向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名： 刘责孽予 签字同期：泗夕年舌月矽日 聊繇彩堵彼 签字日期：泐夕年多月夕同 致谢 本论文的工作是在我的导师张晋豫副教授的悉心指导下完成的，张晋豫副教 授严谨的治学态度和科学的工作方法给了我极大的帮助和影响。在此衷心感谢两 年来张晋豫老师对我的关心和指导。 张晋豫副教授悉心指导我们完成了实验室的科研工作，在学习上和生活上都 给予了我很大的关心和帮助，在此向张晋豫老师表示衷心的谢意。 张晋豫副教授对于我的科研工作和论文都提出了许多的宝贵意见，在此表示 衷心的感谢。 在实验室工作及撰写论文期问，王玉柱、李强、周正、吴建林、阎筑峰、王 连生、田东凯、赵虹、马文琳等同学对我论文中的校对、研究工作给予了热情帮 助，在此向他们表达我的感激之情。 另外也感谢我的家人，他们的理解和支持使我能够在学校专心完成我的学业。 绪论 1 绪论 本章首先阐述了课题的选题背景及意义，然后针对基于应用层组播的流媒体 系统的国内外发展现状给出了相应的介绍，最后是本文的组织结构及创新点。 1 1 课题的研究背景及意义 截至2 0 0 8 年1 2 月3 1f l ，中国网民规模达到2 9 8 亿人，普及率达到2 2 6 ， 超过全球平均水平；网民规模较2 0 0 7 年增长8 8 0 0 万人，年增长率为4 1 9 。中 国网民规模依然保持快速增长之势【l 】。i n t e m e t 在人们的生活学习中起到越来越重 要的作用，网民对于i n t e r n e t 信息的需求也越来越多，特别是现在正在流行的 i n t e m e t 上的视频直播、点播等更生动、直观、形象的视频信息越来越受到广大网 民的喜爱。计算机及通信技术的空前发展为流媒体技术的发展奠定了良好的基础， 创造了良好的应用环境，而流媒体技术的进步又推动和促进了计算机及通信技术 向更高的水平跃进。目前以文字和静态信息为主的i n t e r n e t 悄然朝着以流媒体为主 的“新媒体 形式演进。在i n t e r n e t 上开展流媒体直播或点播业务是未来的发展方 向。 流媒体对带宽、实时性和性能都提出了很高的要求。但是在传统的c s 模式 下，由于流媒体占用的带宽大，持续时间长，而服务器可利用的网络带宽资源有 限，所以即使使用高档服务器，其系统的容量也不过几百个用户，根本就不具有 经济规模性，服务器的性能以及服务器的带宽往往成为限制系统服务能力的“瓶 颈”，导致一些实时性流媒体业务( 如语音、视频等) 无法保证实时性和传输质量， 极大地影响了用户的收看效果，严重地阻碍了业务容量的扩大。另外，由于i n t e m e t 不能保证流媒体的服务质量( q o s - q u a l i t yo f s e r v i c e ) ，如果客户端主机距离服务 器较远，那么流媒体传输过程中的延时、抖动、带宽、包丢失率等指标也将更加 不确定，服务器为每一个客户都要单独发送一次流媒体内容，从而网络资源的消 耗也非常大。 因此在当前网络资源有限的条件下，如何满足彳断增长的用户的需求，并在 北京交通人学硕士学位论文 确保服务质量的同时，降低流媒体的服务门槛，就成为流媒体研究中的重要课题。 对于这些问题现有的解决办法主要是采用i n t e m e t 内容发布网络( c d n ) 和i p 组播技术等。c d n 技术主要是通过代理服务器的复制，将流媒体数据分散到各地， 用户进行就近访问，但是其昂贵的成本，始终是阻碍其大规模部署的主要因素。i p 组播将i p 数据包传输到构成组播群组的主机集合，在视频传输中，即使用户数量 成倍增加，主干带宽不需要随之增加，这样可以大大降低网络运营商的投资成本。 而i p 组播技术由于自身的种种限制，比如很难实现可靠性组播和捌塞控制及其协 议的复杂性等，并没有得到广泛的应用。 于是人们把眼光转移到应用层组播的研究上来。而p 2 p 网络的出现又给流媒 体的传输问题提出了新的解决办法。在p 2 p 网络( 即对等网络) 中，每个对等实 体既是服务的提供者，又是服务的享用者，将服务器的负载分散到对等节点中， 从而有效地减轻了服务器的负载和对网络带宽的占用，极大地提高了系统的可扩 展性。 目前流行的视频直播系统大都是基于应用层组播的p 2 p 系统。应用层组播在 节约网络资源方面相对于i p 组播有其巨大的优势。i p 组播在传送数据分组时，指 派路由器需要构造一个包含所有组播组成员的分布树，根据这个树得到数据转发 分组的一条唯一路径，但是i p 组播采用的是“尽力而为”的u d p 协议，因此它天 生就是不可靠的。i p 组播要求组播路由器的支持，现实的情况是网络中很多路由 器不支持组播功能，另外，在口组播协议中控制层面和转发层面设计不分离的情 况也很容易造成负载不均衡，正是由于i p 组播以上的缺点限制了大规模组播的开 展。应用层组播的良好的扩展性和负载均衡使得研究学者们开始把眼光转到了应 用层组播上来。对于一个p 2 p 流媒体系统来讲，基于应用层组播的协议关系到整 个系统的稳定性和高效性，因此，设计一个合理的应用层组播协议是一件很有意 义的事情。 1 2 国内外相关现状 1 2 1 国外发展现状 2 绪论 目前，视频直播点播的产品已经有很多，大部分是基于应用层组播的。2 0 0 0 年，美国c m u 大学的华人科学家张辉带领的团队率先实现了第一套p 2 p 视频直播 系统的原型e s m t 2 】( e n ds y s t e mm u l t i c a s t ) 获得的极大成功，于是基于p 2 p 和流 媒体的原型系统的研究铺天盖地地产生。2 0 0 0 到2 0 0 3 年各种应用层组播协议席卷 而生。本文试图从不同角度对它们进行分类介绍，由于各个算法都有自己的优缺 点，想从单一标准对它们进行划分是很困难的p 】。 ( 1 ) 按规模大小分有小规模网络中使用的e s m 和a l m i 4 1 。 e s m 协议采用网状的拓扑结构，先在应用层构造一个控制信息拓扑网，再以 控制拓扑网的每个数据源为根构造一个组播树。 该协议的缺点：这样构造出来的网络具有很强的可管理性，但是为了提高系 统的可靠性，组播组的每个成员都有一个维护所有成员的列表，导致系统开销很 大，不利于大规模网络拓扑的构建，因此，只适用于小规模的多源网络。 a l m i 协议也是小规模网络拓扑的代表。它试图在组播组成员之间维护一个最 小生成树。 该协议的缺点：在维护最小生成树的同时也限制了网络规模的扩展。 ( 2 ) 按照组播组系统的数据管理方式可以将组播协议分为集中式和分布式两 种。集中式的代表如前文所讲的a l m i 。在此不再赘述。分布式组播协议又可以分 为树优先( t r e e f i r s t ) 和转发网( m e s h f i r s t ) 优先和隐式构建组播树( i m p l i c t ) 。树 优先的结构一般会比转发网优先结构的延时大，但是网优先结构的可扩展性不高。 其中树优先的代表为y o i d i s l 和o v e r c a s t 引。 y o i d 协议先构造了一棵数据转发树，再与不是父节点的节点建立控制连接以 维护网络的可靠性和容错能力。在支持i p 组播的小规模网络中使用i p 组播，在不 支持口组播的网络中，以及口组播形成的岛之间仍然采用应用层组播。该协议充 分利用了口组播的优点，是将i p 组播和应用层组播结合起来的很好的例子。 o v e r e a t 与y o i d 类似，也是先构造数据转发树，但是它没有采用i p 组播和 应用层组播结合的方式，而是使用自己的专用服务器来控制和管理组播组的成员， 这与完全依赖于用户主机的网络相比显然提高了稳定行和可靠性。 其中转发网优先的代表协议是n a r a d a 7 1 。 当获得若干成员之后，n a r a d a 形成它们的连接构造出一个有冗余链路的转发 控制网，该转发控制网是连通网，但是每个节点的连接小于一定的数量，然后通 3 北京交通人学硕士学位论文 过周期性地检测删除多余的连接，周期性地检测新节点增加连接，再通过组播路 由协议构造数据转发树。 n a r a d a 的缺点是：将带宽要求放在第一位，节点请求加入时首先考虑所有其 它节点中带宽最大的，在带宽相等的情况下才考虑延时。这样导致最大路径长度 没有上限，协议的延时较大。 基于隐式的组播协议有s c r i b e 【8 】等。隐式构建组播树的方式是通过一种特性隐 式地构建控制网和数据转发树。 ( 3 ) 层次化的典型代表是n i c e t 9 1 协议和z i g z a g t l o 】协议。 n i c e 协议和z i g z a g 协议都是基于分层分簇的思想，也是现在的应用层组播 中较常采用的思想。该思想的优点是便于组播成员的管理，分群主要是为了实现 分层分布式控制，节约网络资源。 因为每个网络拓扑都由控制拓扑和数据转发拓扑组成，因此我们从这两方面 详细介绍一下n i c e 协议。图1 1 为n i c e 协议的垂直结构控制拓扑图。 ：二二 t o c p 。o u l 啦o g 略i c a l l 町c r j ，一l i 一；二三二i l a y e r l 图1 - 1n i c e 协议结构图 f i g u r e1 - 1t h es t r u c t u r eo f n i c e p r o t o c o l 所有的组播成员位于层次化结构的最底层，在最底层依照兴趣或者i p 地址邻 近程度划分为不同的群体，每个群体内选出一个代理节点进入上一层，每个群体 的数量在k 到3 k 一1 之f h j 。图1 2a 为n i c e 协议的控制拓扑图。图1 2b 是n i c e 4 绪论 协议的数据转发拓扑图。 a 控制拓扑图 b 数据转发拓扑 图1 - 2 n i c e 协议 f i g u r e1 - 2t h en i c ep r o t o c o l n i c e 协议的控制拓扑将所有的代理节点( 领导节点) 集中起来，每个节点只 存储一定常数量的节点信息，这样既便于组成员的管理又有利于网络的扩展。 每个层中群集的成员可以很快地清楚其对等成员的变化信息。如图1 2a 中 b 0 可以知道l o 层上a 0 ，a 1 ，a 2 ，还有l 1 层上b 1 ，b 2 ，c o 的信息，邻居之间信 息的交换在控制拓扑上交换。 n i c e 的数据转发拓扑则是一棵有固定源的树，这样是为了防止数据下载时出 现路径循环。从图中对比可以看出，数据转发拓扑是隐含在控制拓扑中的。 n i c e 协议的缺点是：因其采用基于树状的控制拓扑，因此造成网络的延时较 大。 z i g z a g 与n i c e 都适合于构建大规模网络的组播树，两者唯一的不同在于 z i g z a g 中簇的管理与数据转发功能由不同节点来完成，而在n i c e 中它们是由同 一个节点来完成的。 ( 4 ) 按照组播树的数目来划分，一种基于多树的c o o p n e t 】方案值得一提。它的 基本思想是在网络中构建和维护多个组播树，利用m d c 编码将多媒体数据分割成 5 北京交通人学硕士学位论文 n 个媒体流，节点可以从多个组播树同时下载，即使下载途中有节点退出或死机 也不会对网络中其它节点造成太大影响，因为一个节点只要下载n 个媒体流中的 m ( m n ) 个就可以完成解码。但是这种思想需要维护多个组播树造成的开销太 大，在媒体流从不同节点同时下载的过程中l 司步机制也很重要。 ( 5 ) 其他的应用层组播协议还有按照特定逻辑结构对组播节点进行映射或编址 的b a y c u x 1 2 1 和c a n t l 3 】；以及运用应用数学的方法构建拓扑结构的d t 1 4 1 等等。 最后从给出各种协议之i 、日j 的一个优缺点对比，如表l l 所示： 表1 1 各种应刚层组播协议对比 t a b l e1 - 1t h ec o n t r a s to fv a r i o u so f a p p l i c a t i o nl a y e rm u l t i c a s tp r o t o c o l 选取链路时 协议名称类型支持的组规模 延时 可扩展性 考虑的参数 e s m 基于网带宽和延时 较小小低 a l m i 基于网 带宽和延时较小小低 带宽、节点 y o i d基于树的逻辑连接巨大 大 高 数 o v e r c a s t 基于树 带宽巨大大局 带宽，同带 n a r a d a基于网宽下考虑延 较小较大低 时 n i c e 基于树带宽 巨大较大局 1 2 2 国内发展现状 ( 1 ) a n y s e e 1 5 】 a n y s e e 是华中科技大学自主研发的视频直播系统，支持n a t 和防火墙的穿 越，而且很好地利用了近播思想，有较好的q o s 保证。 在a n y s e e 系统中，所有对等节点连接成一个以节目源节点为根的组播树。每 个节点从树中的父节点接受多媒体数据，同时提供给自己的子节点。节目源节点 6 绪论 与其它节点之间是一种对等关系。编码服务器把捕获到的视频信号编码为合适的 流媒体格式，发送给节目源节点。黄页服务器收集节目源节点的相关信息，如频 道名称、频道介绍、在线人数等，并把这些信息发送给每个参与者。历史信息服 务器收集系统中每个节点的活动信息，如在线状态、收看频道等。a n y s e e 的这种 树结构保证了媒体数据的一次路由，减少了网络负载，保证了系统的可靠性和可 扩展性。 a n y s e e 系统的实现有3 个关键技术：应用层组播、l a n d m a r k 路标算法和数据 缓冲机制。应用层组播和l a n d m a r k 路标算法结合起来构建一棵稳健的组播树。当 一个新的节点申请加入时，使用l a n d m a r k 算法来把新节点就近加入到一棵已经存 在的组播树中去。这种算法也可以保证在网络出现问题时只影响局部地区，不会 造成大范围的网络瘫痪。数据缓冲机制是指每个节点都会缓存一定时间段内的流 媒体数据，以保证质量。a n y s e e 的缓冲区管理机制主要有以下几条：( 1 ) 每个节点 的数据缓冲区以时间间隔为单位进行管理；( 2 ) 缓冲区缓存最近4 0 s 长度的媒体数 据；( 3 ) 缓冲区占用的空间随时间动态变化；( 4 ) 对数据包头和数据内容分别进行管 理；( 5 ) 每个节点缓冲的数据长度达到一定阈值才向子节点发送。 但是这个系统也有它自身的缺陷体现在：第一，没有考虑到客户的意愿，对 f r e e r i d i n g 的防范能力不够；第二，当一个节点离开后，a n y s e e 采用的基本原则是 连接到父节点，这显然不是最优的，而且q o s 也可能得不到保证。如果离开的节 点存在很多的儿子节点，则容易引起系统的动荡；第三，缺乏对q o s 的讨论。 ( 2 ) c o o l s t r e a m i n g t 16 】 2 0 0 4 年5 月欧洲杯期间，香港科技大学张欣研开发的c o o l s t r e a m i n g 原型系统 在p l a n e t 上进行试用。由于c o o l s t r e a m i n g 系统是第一个真正将高可扩展和高可靠 性的网状组播协议应用在p 2 p 直播系统当中的系统，后期出现的p p l i v e 、p p s t r e a m 等也大多都沿用了c o o l s t r e a m i n g 的网状组播模式。 在系统中包括三个基础的组件：成员关系管理者( m e m b e r s h i pm a n a g e r ) ， 它维持部分o v e r l a y 视图。伙伴关系管理者( p a r t n e r s h i pm a n a g e r ) ，它建立和维 护同其它p e e r 的t c p 连接或伙伴关系。 s t r e a mm a n a g e r ，它是数据传输的关键 组件。除了提供流数据到媒体管理者，它也管理怎么获得流数据。 这套系统使用g o o s i p 1 7j 协议在用户之问传播控制信令，使用类似于b t 的多 点对多点数据传播协议在用户之间传送媒体数据包。视频流被分割成等体积的小 7 北京交通人学硕士学位论文 块，节点可以从其他不同的合作者那罩搜索小块。这比其它传统的方法获得更高 的效益。 这个系统的中心设计是基于数据驱动的概念，每一个节点周期性地同伙伴集 交换f 可用的数据，同时，提供可用的数据给其他人。 但是该系统也存在一个缺点，那就是它通常需要比较大的缓存，系统的启动 延时相对比较大【1 8 】。 1 3 本文的主要工作及创新点 1 3 1 本篇论文的主要工作 本课题主要针对当前流行的p 2 p 流媒体系统的应用层组播协议进行了研究， 提出了一种新的能解决组播的拓扑不匹配问题和具有良好性能的应用层组播协议 算法并予以仿真。 本文共由七部分组成： 第一章为绪论，本章首先阐述了课题的选题背景及意义，然后针对p 2 p 流媒 体系统和面向流媒体系统的应用层组播协议的国内外发展现状给出了相应的介 绍，最后是本文的组织结构及创新点。 第二章p 2 p 流媒体技术与组播原理介绍了关于p 2 p 流媒体技术及组播相关知 识。分析了应用层组播相对于p 组播的优势。 第三章u a l m p 的总体设计提出了一种基于效用因子的应用层组播协议 u a l m p ，介绍了u a l m p 的设计思想，设计了协议的总体结构、管理数据包的结 构和缓冲区的结构。 第四章u a l m p 拓扑控制协议设计研究了应用层的控制拓扑构造过程，给出 了应用层拓扑的定性定量分析，提出了m 邻近度和效用因子的概念，实现了控制 拓扑构建算法。 第五章u a l m p 数据传输协议研究了u a l m p 数据传输协议，研究了数据转 发树构造算法的原理、构造过程，提出了改进的最小费用最大流算法、数据转发 树的维护算法和摹于p o l l i n g 的同步机制。 绪论 第六章u a l m p 的仿真实验对本文提出的应用层组播协议进行了仿真，并与 n i c e 协议进行对比分析，证明了其在解决拓扑不匹配问题等方面的优势。 第七章是对论文的主要工作的一些总结，并提出了进一步的工作及展望。 1 3 2 本篇论文的主要特色及创新点 利用p 2 p 网络技术发展流媒体业务也存在许多需要克服的问题。如，应用层 的覆盖网络与实际的物理网络之间逻辑拓扑与物理拓扑不匹配的问题；由于p 2 p 网络本身的随意性，即用户可以自由地加入和退出网络所造成的网络拓扑的不可 控制问题；网络延时、带宽的可管理性问题；用户的上、下行带宽不匹配问题以 及安全性问题等。本文从研究具有组播功能且可以防止拓扑不匹配的p 2 p 网络拓 扑生成机制出发，提出了一种基于效用因子的应用层组播协议叫a l m p 。它主 要面向实时流媒体系统，采用分层分簇的拓扑结构。已有的应用层组播协议大都 采用不变的“度”数来约束每个节点最多申请的父节点数目，而实际上每个节点 的性能不同，它所能承受的子节点数目以及它能申请的父节点数目都是不同的。 该协议将基于i p 邻近度、带宽和节点出度的效用因子作为衡量节点之间拓扑链路 性能的标准，对不同性能的节点采取不同的拓扑策略，使带宽充足、延时较短的 链路能得到充分利用，尽量避免在带宽过窄、性能较差的链路上传输数据。总的 来说，该协议具有以下优点： ( 1 ) u a l m p 的拓扑构造协议采用了一个基于i p 邻近度和带宽的效用因子来 衡量每个节点的性能，并且以此为标准选择父节点和子节点。这有效地解决了以 往应用层组播协议的拓扑不匹配问题。 ( 2 ) u a l m p 的控制拓扑是一个稳定的、有出入度约束的、基于效用因子的、 分层分簇的结构，它的数据拓扑在此基础上采用了改进的最小费用最大流算法。 这使得u a l m p 具有较高的链路强度。它将源节点r p 和超级节点作为网络的核心 管理普通成员节点，使得网络具有较好的可管理性。 ( 3 ) 数据传输的同步机制采用基于p o l l i n 甙轮询) 的下载方案，有效解决了数 据传输的不同步问题。 9 北京交通人学硕十学位论文 2p 2 p 流媒体技术与组播原理 p 2 p 、组播和流媒体是三个互相关联的概念，因为p 2 p 和组播技术都是解决流 媒体数据传输的有效解决方法。本章将从它们各自的概念和特点入手讲解p 2 p 流 媒体技术和组播技术原理。 2 1p 2 p 流媒体技术 2 1 1p 2 p 网络的概念 p 2 p ( p e e r - t o p e e r ) 是对等网络的意思。i n t e m e t 上传统的应用模式为 c l i e n t s e r v e r 模式，相比于传统模式，p 2 p 有着不可替代的优越性。在c s 模式中， 数据的转发采用专门的服务器，便于数据的统一管理，但是服务器的c p u 能力、 内存大小有限，可扩展性差，而且容易造成系统瓶颈。而对等网络中的成员的地 位都是对等的，每个成员既充当服务器又充当客户端，在自己享受网络资源的同 时也为网络中的其它成员提供服务。p 2 p 技术的这种结构避免了c s 模式的瓶颈问 题，有效利用了带宽，随着系统服务需求的增加，相应的资源提供和服务能力也 在增加，因此有很强的可扩展性。 对于p 2 p 的定义，不同研究者有着不同的理解，但是从本质上讲它们是相通 的，从不同侧面给出了p 2 p 的定义，我们也能通过这些定义看出p 2 p 网络的特点 【1 9 】。p 2 p 的定义如表2 1 所示。 表2 1p 2 p 的定义 t a b l e2 1t h ed e f i n i t i o no f p 2 p 定义者 定义 利用因特网边界的存储c p u 内存现场等资源的一种应 用；访问这些非集中资源意味着运行在不稳定连接和不可预 c s h i r k y 知i p 地址环境下，p 2 p 节点必须运行在d n s 系统的外边；具 备有效或伞部的自治。 1 0 p 2 p 流媒体技术与组播原理 定义者定义 通过3 个关键条件定义： 1 具有服务器质量的可运行计算机 r 1 g r a n h a m 2 具有独立于d n s 的寻址系统 3 具有与可变连接合作的能力 k i n d b e r g 独立生存的系统 通过在系统之i 日j 直接交换来共享计算机资源和服务的一 i n t e l 工作组 种应用模式 d j m i l o j i c i c 给对等组提供或从对等组获得共享 a w e y t s e l 在因特网周边以非客户地位使用的设备 2 1 2p 2 p 网络的拓扑结构分类 拓扑结构是指分布式系统中各个成员之间的物理或逻辑关系，成员之间的拓 扑结构决定了系统的类型。根据网络的拓扑结构可以将p 2 p 网络分为四类。 ( 1 ) 集中式拓扑 集中式p 2 p 网络形式上有一个中心服务器来负责记录共享信息以及回答对这 些信息的查询。每一个对等实体对它将要共享的信息以及进行的通信负责，根据 需要下载它所需要的其他对等实体上的信息。这种形式具有中心化的特点，但是 它不同于传统意义上的c l i e n t s e r v e r ( 客户端服务器) 模式。 以n a p s t e r 为代表的集中式拓扑结构具有便于管理的优点，但是缺点是服务器 承担着所有资源的检索工作，网络对服务器依赖性大，一旦服务器瘫痪整个网络 也将瘫痪，不完全符合p 2 p 的理念。n a p s t e r 的典型结构如图2 1 所示。 ( 2 ) 完全分布式非结构化拓扑 完全分布式非结构化拓扑采用了随即图的组织方式来形成一个松散的网络。 这种结构对网络的动态变化有很好的容错能力，因此具有较好的可用性。同时， 这种结构支持复杂查询，比如带有规则表达式的多关键字查询、模糊查询等。图 2 2 给出了定性的分布式非结构化拓扑模型。 北京交通大学硕士学位论文 图2 - 1n a p s t e r 系统结构图 f i g u r e2 - 1t h es y s t e mf r a m e w o r ko f n a p s t e r 图2 - 2 分布式1 f 结构化拓扑模型 f i g u r e2 - 2t h em o d e lo fd i s t r i b u t e dn o n s t r u c t u r a lt o p o l o g y 以g u n t e l l a 为代表的完全分散式文件共享模型，网络中没有服务器，搜索资 源需要遍历整个网络，虽然避免了单一服务器瓶颈，但是搜索耗费了大量带宽， 而且不便管理。 ( 3 ) 完全分布式结构化拓扑 1 2 p 2 p 流媒体技术与组播原理 完全分布式结构化拓扑又叫d h t 网络，主要是采用分布式散列( d i s t r i b u t e d h a s ht a b l e 简写成d h t ) 技术来组织网络中的节点。d h t 是一个由广域范围大量 节点共同维护的巨大散列表。散列表被分割成不连续的块，每个节点被分配给一 个属于自己的散列块，并成为这个散列块的管理者。通过加密散列因子，一个对 象的名字或关键词被映射为1 2 8 位或1 6 0 位的散列值。分布式散列表起源于s d d s ( s c a l a b l ed i s t r i b u t ed a t as t r u c t u r e s ) 研究，g r i b b l e 等实现了一个高度可扩展，容 错的s d d s 集群。d h t 类结构能够自适应节点的动态加入退出，有着良好的可扩 展性、鲁棒性、节点i d 分配的均匀性和自组织能力。由于重叠网络采用了确定性 拓扑结构，d h t 可以提供精确的发现。只要目的节点存在于网络中d h t 总能发现 它，发现的准确性得到了保证，代表性网络有t a p e s t r y ，p a s t r y ，c h o r d 和c a n 。 t a p e s t r y 提供了一个分布式容错查找和路由基础平台，在此平台基础之上，可 以开发各种p 2 p 应用。t a p e s t r y 的思想来源于p l a x t o n 。在p l a x t o n 中，节点使用自 己所知道的邻近节点表，按照目的i d 来逐步传递消息。t a p e s t r y 基于p l a x t o n 的思 想，加入了容错机制，从而可适应p 2 p 的动态变化的特点。o c e a n s t o r e 是以t a p e s t r y 为路由和查找基础设施的p 2 p 平台。它是一个适合于全球数据存储的p 2 p 应用系 统。任何用户均可以加入o c e a n s t o r e 系统，或者共享自己的存储空间，或者使用 该系统中的资源。通过使用复制和缓存技术，o c e a n s t o r e 可提高查找的效率。最近， t a p e s t r y 为适应p 2 p 网络的动态特性，作了很多改进，增加了额外的机制实现了网 络的软状态( s o f ts t a t e ) ，并提供了自组织、鲁棒性、可扩展性和动态适应性，当 网络高负载且有失效节点时候性能有限降低，消除了对全局信息的依赖、根节点 易失效和弹性差的问题。 p a s t r y 是微软研究院提出的可扩展的分布式对象定位和路由协议，可用于构 建大规模的p 2 p 系统。如图2 3 所示，在p a s t r y 中，每个节点分配一个1 2 8 位的 节点标识符号( n o d e l d ) ，所有的节点标识符形成了一个环形的n o d e l d 空间，范围 从0 到2 1 2 8 1 ，节点加入系统时通过散列节点i p 地址在1 2 8 位n o d e l d 空间中 随机分配。 北京交通人学硕士学位论文 图2 - 3p a s t r y 的消息路由 f i g u r e2 - 3t h ed a t ar o u t eo fp a s t r y c h o r d 项目诞生于美国的麻省理工学院。它的目标是提供一个适合于p 2 p 环 境的分布式资源发现服务，它通过使用d h t 技术使得发现指定对象只需要维护 o ( 1 0 9 n ) 长度的路由表。在d h t 技术中，网络节点按照一定的方式分配一个唯一 节点标识符( n o d ei d ) ，资源对象通过散列运算产生一个唯一的资源标识符( o b j e c t i d l ，且该资源将存储在节点i d 与之相等或者相近的节点上。需要查找该资源时， 采用同样的方法可定位到存储该资源的节点。因此，c h o r d 的主要贡献是提出了一 个分布式查找协议，该协议可将指定的关键字( k e y ) 映射到对应的节点( n o d e ) 。 从算法来看，c h o r d 是相容散列算法的变体。c h o r d 的拓扑结构如图2 4 所示。 c a n ( c o n t e n ta d d r e s s a b l en e t w o r k s ) 项目采用多维的标识符空间来实现分布 式散列算法。c a n 将所有节点映射到一个n 维的笛卡尔空间中，并为每个节点尽 可能均匀的分配一块区域。c a n 采用的散列因子通过对( k e y , v a l u e ) 对中的k e y 进 行散列运算，得到笛卡尔空间中的一个点，并将( k e y , v a l u e ) 对存储在拥有该点所 在区域的节点内。c a n 采用的路由算法相当直接和简单，知道目标点的坐标后， 就将请求传给当前节点四邻中坐标最接近目标点的节点。c a n 是一个具有良好可 扩展性的系统，给定n 个节点，系统维数为d ，则路由路径长度为o m d ) ，每节 点维护的路由表信息和网络规模无关为o ( d ) 。 1 4 p 2 p 流媒体技术与组播原理 d h t 这类结构最大的问题是d h t 的维护机制较为复杂，尤其是节点频繁加入 退出造成的网络波动( c h u m ) 会极大增加d h t 的维护代价。d h t 所面临的另外 一个问题是d h t 仅支持精确关键词匹配查询，无法支持内容语义等复杂查询。 图2 - 4c h o r d 的拓扑结构 f i g u r e2 - 4t h et o p o l o g ys t r u c t u r eo fc h o r d ( 4 ) 层次化拓扑 以m b o n e 为代表的层次化模型将网络中性能较好的节点作为超级节点存储 索引信息，这样便于信息检索同步，避免了集中式结构产生的瓶颈，但是超级节 点的离开会对网络造成很大影响。 ( 5 ) 混合式拓扑 混合式拓扑结构将网络中的超级节点采用完全分散式模型联结，每个超级节 点又管理许多普通节点。它吸取了中心化结构和全分布式非结构化拓扑的优点， 选择性能较高( 处理、存储、带宽等方面性能) 的节点作为超级节点( 英文表达 为s u p e r n o d e s 或者h u b s ) ，在各个超级节点上存储了系统中其他部分节点的信息， 发现算法仅在超级节点之间转发，超级节点再将查询请求转发给适当的叶子节点。 半分布式结构也是一个层次式结构，超级节点之间构成一个高速转发层，超级节 点和所负责的普通节点构成若干层次。混合式拓扑结构如图2 5 所示。采用这种结 1 5 北京交通人学硕士学位论文 构的最典型的案例就是k a z a a 。 图2 - 5 混合式拓扑结构图 f i g u r e2 - 5t h es t r u c t u r eo fm i x e dt o p o l o g y k a z a a 是当前世界最流行的几款p 2 p 文件共享软件之一。根据c a 公司统计， 全球k a z a a 的下载量超过2 5 亿次。使用k a z a a 软件进行文件传输消耗了互联网 4 0 的带宽。之所以它如此的成功，是因为它结合了n a p s t e r 和g n u t e l l a 共同的优 点。从结构上来说，它使用了g n u t e l l a 的全分布式的结构，这样可以是系统更好 的扩展，因为它无需中央索引服务器存储文件名，它是自动的把性能好的机器成 为s u p e r n o d e ，它存储