（计算机应用技术专业论文）基于p2p覆盖网络的应用层组播研究和应用.pdf

中文摘要 随着网络技术与计算机技术的飞速发展，越来越多的多媒体应用出现在了 i n t e r n e t 中，例如网上直播、视频会议、远程教育等。对于这类对带宽和延时 都有很高要求的应用，组播被认为是一种有效的解决方案。但由于技术和市场的 原因，i p 组播一直未能在i n t e r n e t 上得到大规模的部署。为了解决i p 组播的 部署问题，近年来研究人员提出了应用层组播的思想。 本文以基于p 2 p 覆盖网络的应用层组播为研究对象。在论文中，研究了现有 的一些应用层组播协议和实现方案，比较了它们的优势和不足，分析了基于p 2 p 的应用层组播所具备的特点和优势。在这些研究的基础上，设计了一种基于p 2 p 覆盖网络的应用层组播系统方案，描述了原型系统的模块构成、体系结构和运行 流程。原型系统使用结构化的p 2 p 协议p a s t r y 生成p 2 p 覆盖网络，利用树优先 的组播协议实现组播转发树的生成、组成员的管理、组状态的维护及组播数据的 转发。为了验证该方案，采用离散事件仿真工具o m n e t + + 建立相应的组播仿真模 型，对原型系统进行仿真实验，模拟组播环境下实时流媒体传输的场景，以测试 在不同规模的组成员参与时系统的性能。 实验结果表明，这种基于p 2 p 的应用层组播系统能够以较低的延时和较小的 控制开销实现实时媒体的传输，具备一定的可靠性和容错能力，可以在不改变下 层网络结构的基础上，实现可扩展的组播应用。 关键词：应用层组播p 2 pp a s t r yo 心e t + + 仿真 a b s t r a c t w i t ht h er a p i dd e v e l o p m e n to fn e t w o r ka n dc o m p u t e rt e c h n o l o g y ，m o r ea n dm o r e m u l t i m e d i aa p p l i c a t i o na p p e a ri nt h ei n t e m e t f o re x a m p l e ，l i v i n gb r o a d c a s t s ，v i d e o c o n f e r e n c e s ，l o n gd i s t a n c ee d u c a t i o na n ds oo n f o rt h i sa p p l i c a t i o n ，m u l t i c a s t i s c o n s i d e r e dae f f i c i e n ts o l v i n gw a y b u ta st h er e s u l to ft h et e c h n o l o g ya n dm a r k e t , t h e i pm u l t i c a s tc a nn o tb em a s s i v ed e p l o y e do nt h ei n t e r n e t i no r d e rt o s o l v et h e d e p l o y m e n ti s s u eo fi pm u l t i c a s t ，r e s e a r c h e r sg i v eo u tt h ei d e a0 1 1t h ea p p l i c a t i o n l a y e r m u l t i c a s ti nr e c e n ty e a r s t h et h e s i sm a i n l ya i m sa tr e s e a r c ho nt h ea p p l i c a t i o nl a y e rm u l t i c a s tb a s e do n p 2 ei nt h ep a p e r , w es t u d ys o m er e a l i z a t i o np r o j e c t so ft h ee 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 ta n dc o m p a r et h ea d v a n t a g e sa n dd i s a d v a n t a g e s t h e nw er e s e a r c hs o m e p r o j e c t so ft h ea p p l i c a t i o nl a y e rm u l t i c a s ti m p l e m e n t e db yu s i n gp 2 pt e c h n o l o g y b a s e do nt h er e s e a r c h ，w ed e s i g nak i n do fp r o t o t y p es y s t e mo ft h ea p p l i c a t i o nl a y e r m u l t i c a s tb a s e do np 2 po v e r l a yn e t w o r kt e c h n o l o g y , d e s c r i b em o d u l ec o m p o s i n g ， a r c b i t e c t u r e a n db a s i cf l o wo fs y s t e mc i r c u l a t i o n i nt h ep r o t o t y p es y s t e m ，n o d es e l f o r g a n i z a t i o nao v e r l a yn e t w o r ku s i n gs t r u c t u r e dp 2 pp r o t o c o l ，a n du s i n gt r e e 。f i r s t p r o t o c o li m p l e m e n tg r o u pm e m b e rm a n a g e m e n t ，g r o u ps t a t u sm a n t a ma n d m u l t i c a s t d a t af o r w a r d t ot e s tt h ec a p a b i l i t yo f t h es y s t e m ，w eu s et h ed i s c r e t ee v e n ts i m u l a t i o n t o o i so m n e t _ ht oc o n s t r u c ts i m u l a t i o nm o d e l ，s i m u l a t es t r e a mm e d i at r a n s m i s s i o n i n t h e m o d e l f r o mt h er e s u l to ft h es i m u l a t i o ne x p e r i m e n t ，t h ep r o j e c tc a nc a r r yo u tr e a lt i m e m e d i u mt r a n s m i s s i o nw i t hl o w e rt i m e - d e l a ya n dl o wc o n t r o l l e dc o s t t h ep r o t o t y p e s y s t e mh a sf a u l tt o l e r a n c ea n de x p a n s i b i l i t y , i tc a l li m p l e m e n t m u l t i c a s ta p p l i c a t i o n w i t h o u tc h a n g i n gt h eu n d e rl a y e rn e t w o r ks t r u c t u r e 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 , p a s t r y , o m n e t h ，s i m u l a t i o n 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得墨鲞盘堂或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均己在论文中 作了明确的说明并表示了谢意。 学位论文作者签名： 签字日期：z 印夕年舌月阳 学位论文版权使用授权书 本学位论文作者完全了解叁叠盘堂有关保留、使用学位论文的规定。 特授权墨鲞盘堂可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校 向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作 签字日期： 导师签名：之辞7 签字日期：_ 7 年占月，日 纽一 垄阳 名 压 鹕矿 者 第章绪论 1 1 研究背景及意义 第一章绪论弟一早三百t 匕 当代社会已经进入了信息时代，网络技术在飞速发展。随着网络的日益普及， 越来越多的实时应用出现在了互联网上，网上直播、视频会议、远程教育、多媒 体交互式应用等新兴的应用层出不穷，这些新兴的应用都依赖于一对多或多对多 的数据传输模式，而在互联网上分发信息的主机数目非常大，依靠单播技术会占 用大量的网络带宽，增加端到端的延时，无法满足应用的需求。对于这类应用， 组播是一种减少传输冗余、充分利用带宽的有效方式。组播是指从一点到多点或 多点到多点的传输方式。最早的组播是在网络层实现的i p 组播砼儿引，在i p 组播 中由路由器构造组播转发树，数据包从转发树的根节点出发，沿着转发树在不同 的结点路由器上进行复制和转发，最后到达组中的所有成员，同一数据包在物理 链路中只传输一次。i p 组播减少了数据包在网络传输中的冗余，节约了带宽，提 高了传输效率。 虽然i p 组播的出现对于解决实时性要求高的多用户应用起到了非常有效的 推动作用，但i p 组播在大规模应用时也存在着以下一些问题：在技术层面上i p 层组播存在着组播组管理、地址管理、q o s 等问题。在i n t e r n e t 上大规模部署i p 组播，要求网络中的路由器都要支持相应组播协议，这增加了在全网部署i p 层组 播的成本；另外在市场运行机制方面也缺乏有效的运营模式。基于这些原因，使 得i p 组播从被提出到现在也无法在i n t e r n e t 上进行大规模部署。 为了解决i p 组播的部署问题，近年来研究人员提出了应用层组播的思想 ( a p p l i c a t i o nl a y e rm u l t i c a s t ) 钔5 3 6 1 7 1 邮。应用层组播又称覆盖组播( o v e r l a y m u l t i c a s t ) ，与i p 组播相比，在应用层组播中，组播的功能从路由器移到了终端 主机。应用层组播不改变下层网络的基本结构，不需要除单播以外的其他能力， 而单播通讯是互联网的基本功能之一，所以应用层组播比i p 组播更易于部署。在 应用层组播的实现过程中，成员主机之间建立一个叠加在i p 网络之上的，实现组 播业务逻辑的功能性网络，称为覆盖网络( o v e r l a yn e t w o r k ) ，成员主机使用自 组织算法建立和维护覆盖网络，在覆盖网络上实现组播组管理及其他组播功能。 在应用层组播中，覆盖网络的构建直接或间接影响组播的效率，因此如何构造高 效的覆盖网络是当前应用层组播研究中的一个主要问题。 第一章绪论 近些年来，基于p 2 p 技术的研究进展非常快。由于p 2 p 协议本身可以使参与节 点自组织成一个大规模的、支持成员动态变化的覆盖网络。b h p 2 p 系统构成的覆 盖网络具备白组织、健壮性等特点，使得在p 2 p 覆盖网络上更容易开展组播应用。 对应用层组播来说，覆盖网络的构建是组播的基础，直接或间接影响组播的各项 性能。因此，基于p 2 p 覆盖网络的应用层组播成为了应用层组播技术研究的热点 之一，在p 2 p 覆盖网络上实现应用层组播具有重大的意义。 1 2 组播技术研究现状 1 2 1i p 组播简介 1 ip 组播概述 1 9 8 9 年，s o e e r i n g 在他的博士论文中指出，现有i p 网络的体系统结构可以 支持i p 组播( i pm u l t i c a s t ) ，在文中给出的i p 组播定义是：i p 组播是一个i p 报 文到一个“主机组”的传输，“主机组”是指若干个有确定i p 地址的主机。在 以后的r f c 文档中也相继定义了一组用于i p 组播的协议，用于在i n t e r n e t 上实现 i p 组播的功能。 在图1 - 1 中，我们可以看到在i p 组播中，由路由器构成组播转发树，数据 包从组播源发出，经过组播转发树被发送到了组中的每一个用户，同一个数据包 在组播转发树中的每条链路上只被发送一次。 图1 - 1i p 组播示意 2 组播地址和组播协议 在i p 组播中，组由特殊的i p 地址来标识。在i p v 4 的体系结构中，使用d 类地址来表示一组主机，范围从2 2 4 0 0 0 到2 3 9 2 5 5 2 5 5 2 5 5 。 在i p 组播中的协议主要有：在主机和路由器之间用于组成员关系维护的因特 网组管理协议( i g m p ) 和路由器之间运行的组播路由协议怕1 。常见的组播路由协 议有以下几种： 第+ 章绪论 ( 1 ) 距离向量组播路由协议( d v m r p ) 叫 ( 2 ) 开放式组播最短路径协议( m o s p f ) ( 3 ) 协议无关组播路由协议( p i m ) 。p i m 又分为密集模式( d m ) 以及稀疏模式( s m ) 【t 2 【1 3 】 ( 4 ) 有核树协议( c b t ) b 1 3 1 p 组播存在的问题 虽然i p 组播在一对多或多对多的传输中有着很高的效率，但它也存在很严重 的部署问题引。要在i n t e r n e t 中大规模的部署i p 组播需要网络中的所有路由器都 支持i p 组播协议，这种要求很难实现；另外，现有的i p 组播也没有很好的运营模 式，难以得到运营商的支持，这些问题导致了i p 组播在被提出来十几年后仍然无 法在i n t e r n e t 中大规模部署。 1 2 2 应用层组播的介绍 为了解决i p 组播的部署问题，应用层组播的思想被提出州6 m m 副。应用层 组播( a p p l i c a t i o nm u l t i c a s t ) 也称覆盖组播，它不像传统的i p 组播需要网络 层设备的支持，而是由参与应用层组播的节点在逻辑上自组织成一个覆盖网络 ( o v e r l a yn e t w o r k ) ，在这个覆盖网络中完成组播组管理、组播管理、组播转发 树的构建和其他组播的功能。与i p 组播不同的是，在i p 组播中，由网络层的路由 器实现组播；而在应用层组播中，组播是由终端主机来实现的，数据包的路由、 复制、转发由终端主机来完成，所以应用层组播的部署要l 卜, i p 组播相对容易。应 用层组播的示意图如图1 - 2 所示。 1 2 3 应用层组播的分类 图1 - 2 应用层组播示意图 目前，关于应用层组播的协议和算法有不少，所涉及的技术相当广泛，我们 可以从不同的角度对应用层组播进行分类。按照应用层组播路由的构造方式，可 第章绪论 将应用层组播路由分为网状优先( m e s h - f i r s t ) 和树优先( t r e e - f i r s t ) 两类6 1 。 其中，m e s h - f i r s t 方式首先由端系统构成一个网状的拓扑结构( m e s h ) ，然后基 于m e s h 构造组播转发树：而树优先方式，则由端系统直接构成一棵组播转发树。 按照应用层组播系统的结构，应用层组播可分为基于终端主机的应用层组播和基 于代理的应用层组播。 1 按照拓扑设计进行分类 。 ( 1 ) m e s h - f i r s t 协议 在网状优先的覆盖组播中，组内成员首先自我组织成一个网状的拓扑，即控 制拓扑，在任意两个成员之间有多条路径。在这个网状拓扑中，每一个成员都会 保存这个组中其他所有成员的状态信息，而这个信息将会得到周期性的刷新，以 保证成员间了解彼此的状态。常见的网状优先应用层组播系统有e s m ( e n ds y s t e m m u l t i c a s t ) ，n a r a d a 是e s m 的组网协议，它是由c m u 组播通信组开发的最早的应用 层组播协议之一，也是目前为止应用最成功的应用层组播系统之一畸1 。但它的缺 点是由于泛洪所产生的冗余数据太多，当节点规模扩大时，效率较低，可扩展性 差，只适用于小规模的应用层组播。 ( 2 ) t r e e f i r s t 协议 与网状拓扑优先不同的是，基于树状拓扑优先的应用层组播协议首先会建立 起一个共享的数据转发树。然后，根据这个树状拓扑会增加一些成员间的连接， 便可组成控制网状拓扑。树状优先的协议有y o i d 和h m t p 等，其中y o i d 也是一个出 现较早的应用层组播协议哺引。 2 按应用层组播系统的结构来分类 按照应用层组播系统的结构，应用层组播可分为基于主机的应用层组播和基 于代理的应用层组播： ( 1 ) 基于主机的应用层组播 在基于主机的应用层组播系统中，由参与组播的终端主机( h o s t ) 构建覆盖 网络，前面介绍的几种应用层组播都属于这一类。 ( 2 ) 基于代理的应用层组播 基于代理的应用层组播是在参与组播的主机中插入一组用于覆盖网络构建 和组播服务的代理服务器，其它的主机通过这些代理服务器间接的获得组播服 务，通常代理服务器具有较高的性能和稳定性，因此基于代理的应用层组播可靠 性高、具有良好的可扩展性，在已有的应用层组播方案中s c a t t e r c a s t 、o v e r c a s t 、 o m n i 就属于这一类力n 引。 第一章绪论 1 2 4 应用层组播的研究热点和度量标准 1 应用层组播研究的主要问题 应用层组播通过在t c p i p 模型中的应用层中构建一个虚拟的覆盖网络，在这 个覆盖网络中实现组播的各项功能，它不改变现有的网络结构，也4 i 要求网络中 的所有路由器都支持组播，所以它被认为是目前i n t e r n e t 上支持组播通信的最简 单、可行的方式。在由终端主机构成的应用层组播系统中，如何构建一个有效的 应用层组播架构，需要考虑以下问题啦引： ( 1 ) 性能方面的要求：数据传输的延迟，特别是对实时传输的业务，要求 延迟尽可能的小或者能满足一定的延时要求。所消耗的网络资源最少，通常要求 覆盖网络拓扑尽可能的接近于底层真实网络的拓扑，减少在底层连接上的重复， 最大化的利用资源。 ( 2 ) 异构性：互联网上的主机千差万别，由终端系统构成的应用层组播系 统要充分的考虑主机的异构性，包括主机性能的异构性和接入带宽的异构性。组 播服务需要满足不同处理或接收能力的成员节点的需求。 ( 3 ) 健壮性：当组成员或链路失效时，可以快速有效的恢复。在应用层组 播系统中，节点的失效或链路的故障会使组播系统出现不稳定，尤其在大规模的 应用中，通常会出现大量节点的动态变化。应用层组播系统只有具备较强的健壮 性，才能保证系统的可用性。 ( 4 ) 可扩展性：对于大规模的应用，可扩展性是非常重要的因素之一。这就 要求应用层组播系统在构建、管理和维护方面的开销尽可能的小，如可采用分布 式的管理和维护，或者只维护本地的、局部的信息，这有利于提高组播架构的可 扩展性。 2 应用层组播的评价标准 一个好的应用层组播协议除了要有高效性、良好的资源利用率外，还要能够 满足用户接收数据的性能要求。为了评价应用层组播系统的质量，通常采用以下 性能评价指标哺，。 ( 1 ) 链路压力( 1 i n ks t r e s s ) 相同的数据包在一条物理链路重复传输的次数称为链路压力。 ( 2 ) 路径延伸比( s t r e t c h ) 从源节点到某个组成员的路径长度与使用单播从源传输到该节点的路径长 度之比。 ( 3 ) 控制开销( c o n t r o lo v e r h e a d ) 应用层组播中，用于维护覆盖网络所产生的控制信息的总数。 第章绪论 ( 4 ) 组播树传输延时( d e l a y ) 组播数据包从组播源出发的时间与数据包到达组成员节点的时间之差。 1 3 本文的研究目标和研究内容 本文研究的目标是采用p 2 p 覆盖网络的技术，设计一种基于p 2 p 覆盖网络的 应用层组播系统，为大规模组播应用提供支持，改进已有组播通信中存在扩展性 和可伸缩性方面的不足，使面向实时的应用能够在组播的环境下实现。 本文的研究内容包括： ( 1 ) 研究和对比现有的应用层组播系统及其组播路由协议和算法。 ( 2 ) 研究结构化p 2 p 协议的运行机制和基于p 2 p 覆盖网络的应用层组播方案。 ( 3 ) 在分析了各种应用层组播方案和协议的基础上，设计一种基于p 2 p 技术 的应用层组播原型系统方案。 ( 4 ) 对原型系统进行仿真，并根据仿真结果对系统的性能进行了分析和评 价，得出研究结论。 1 4 论文的组织结构 本文的组织如下： 第一章绪论，主要介绍了应用层组播的研究背景、i p 组播和应用层组播的 基本概念、组播技术的研究现状、论文的研究目标和研究内容以及论文的组织结 构。 第二章介绍应用层组播中存在的一些不足，分析p 2 p 网络与应用层组播结合 所能产生的优势，其中包括了目前p 2 p 网络所采用的主要技术以及在p 2 p 覆盖网 络上开展应用层组播的一些方案。 第三章提出了一种基于p 2 p 网络的应用层组播原型系统方案，其中包括系统 的总体设计、相关的协议的实现、系统的模块组成及运行流程。 第四章对提出的基于p 2 p 覆盖网络的组播方案进行仿真，其中包括了仿真工 具o 洲e t + + 的介绍，仿真实验计划和步骤以及仿真结果的分析，并根据仿真结果 对原型系统的各项性能做出评价。 第五章对论文工作进行了总结，并对未来的工作进行了展望。 第_ 幸p 2 p 与应用层组播 第二章p 2 p 与应用层组播 2 1 应用层组播所面临的问题 虽然应用层组播能够解决i p 组播的部署难问题，但它也面临着一些问题和不 足。在应用层组播中，应用层组播协议将组成员节点自组织成覆盖网络，在终端 主机上实现组播的功能。将组播功能从路由器迁移到终端主机上能够有效解决许 多与i p 组播有关的问题，但同时也带来了一些新的问题。在应用层组播中，组成 员节点的状态动态变化且完全分布，节点间通过自组织算法、自组织成覆盖网络， 组成员的动态性对组播有很大影响。应用层组播协议不仅要建立有效的组播数据 转发树，还要针对节点的动态性提供可靠的组管理算法6 1 。因此构建一个可扩 展的、具备容错能力的、能够适应节点动态变化的通用组播结构仍然是应用层组 播所面临的挑战啦2 。 近年来p 2 p 覆盖网络技术的出现为应用层组播的研究提供了新的思路。由于 p 2 p 技术本身所具备的分布动态性、自组织性、健壮性等特点，使得由p 2 p 系统 构成的覆盖网络能够适应大规模的、节点状态动态变化的分布式应用。所以基于 p 2 p 覆盖网络的应用层组播成为构建可扩展的、适应节点动态变化的通用组播架 构的途径之一。 2 2p 2 p 技术概要 2 2 1p 2 p 简介 p 2 p 是一种分布式网络，网络的参与者共享他们所拥有的一部分硬件资源( 处 理能力、存储能力、网络连接能力、打印机等) ，这些共享资源能被其它对等节 点( p e e r ) 直接访问而无需经过中间实体。在p 2 p 网络中的参与者既是资源提供 者，又是资源的获取者，每个节点将接收的内容缓存并提供给其他请求节点，这 充分挖掘了i n t e r n e t 上被忽视的客户机资源，在利用率、扩展性、容错等方面 具有巨大潜力。 在p 2 p 网络中的各个节点在逻辑上是对等的，没用集中的服务器，p 2 p 网络 中的每个节点( 加入p 2 p 网络的计算机) ，既可以作为服务器响应其他节点的请 求：也可以作为客户端，请求其他的节点提供服务。结构如图2 - 1 所示。 第_ 章p 2 p 与应用层组播 随着p c 技术的迅猛发展使得处在网络边缘的终端用户具备了更强大的计 算能力，而普通用户网络连接带宽的提升也为p 2 p 应用的开展提供了必要的网络 条件。在此背景下，p 2 p 再一次受到了广泛的关注，近年来逐渐成为了网络应用 和研究的热点。 p e e r p e e rp e e r 图2 1p 2 p 结构示意图 2 2 2 目前p 2 p 网络中采用的技术 p e e r 根据p 2 p 网络的检索模型和机制，可以将现有的p 2 p 实现分为三种类型瞳3 1 。它 们分别是：基于目录模型的p 2 p ，非结构化的p 2 p 和结构化的p 2 p 。 1 基于目录模型的p 2 p 在目录模型的p 2 p 中，一台或多台具有特殊用途的服务器为对等点提供目录 服务，在目录服务器中保存用户节点的地址信息和该用户节点上共享文件的描述 信息。为了使可扩展性最大化，对应用程序进行了结构化设计，以便使少量的目 录就可以为数量众多的对等点服务。对等点向目录服务器注册关于自身的信息 ( 名称、地址、资源和元数据) ，并通过在目录服务器中信息进行查询，使用目 录服务来定位其他对等点。文件本身被存放在分散的节点上，文件传输实际上是 在对等节点之间进行的，而未通过目录服务器。 目前最典型的目录型p 2 p 系统是n a p s t e r ，n a p s t e r 是s h a w nf a n n i n g 和 s e a np a r k e r 于1 9 9 9 年5 月共同创办的文件共享社区网站，同名软件n a p s t e r 使用 p 2 p 技术提供免费m p 3 、文件下载服务m 1 。曾因遭到美国唱片业协会( r i a a ) 控 告侵犯版权而被关闭，现在n a p s t e r 以收费方式重新开通。 2 非结构化的p 2 p 以g n u t e l l a 为代表的非结构化p 2 p 系统中，文件索引不再由集中式的目录服 第_ 章p 2 p 与应用层组播 务器存储管理，而是分布在网络中由节点自己保存犯引。g n u t e l l a 是n u l l s o f t 公 司的j u s t i nf r a n k e l 于2 0 0 0 年推出的一款开放源代码的音乐文件共享工具，现在 有多种基于g n u t e ll a 协议的软件，如g n u e l e u s 、l i m e w i r e 、b e a r s h a r e 等，国内 的o p e n - e x t 的文件共享功能也是基于g n u t e ll a 协议的。最初的g n u t e ll a 是分散 式、非结构化的文件共享网络。现在，g n u t e l l a 已经发布了有超级节点的版本。 在g n u t e l l a 网络中，对等结点a 在初始化时知道已经在g n u t e l l a 网络中的对等 结点b 的i p 地址，当a 和b 连接后，a 可以获得b 所知道的所有系统结点信息， 这样a 就可以和它所感兴趣的结点建立直接的连接。 g n u t e l l a 网络也存在很多弊端，主要表现在以下方面：随着网络规模的扩大， 通过扩散方式定位对等点及查询的方法将造成网络流量急剧增加，从而导致网络 拥塞。因此，网络的可扩展性不好，对于大型网络也不适合。但是，如果在该网 络中存在一些所谓的超级实体( 即该实体拥有大量的资源信息) ，则可以显著减少 带宽的浪费。另外，其安全性也不高，易遭受恶意攻击，如攻击者发送垃圾查询 信息，会造成网络拥塞等。 3 结构化的p 2 p 由于非结构化的p 2 p 系统中随机搜索造成的不可扩展性以及泛洪产生的大量 网络流量，人们将大量的研究集中在如何构造一个高度结构化的系统。为此，近 年来许多研究人员在设计可扩展的查找机制方面做了大量的研究工作，提出了 c h o r d 、p a s t r y 、t a p e s t r y 、c a n 等用于构建结构化p 2 p 的分布式哈希表系统 ( d i s t r i b u t e dh a s ht a b l e d h t ) 乜力啪儿驯。在这些结构化的系统中，o v e r l a y 的 拓扑将被严格控制，资源存放在确定的位置上。这类系统提供从文件标识符到文 件存放节点标识的映射服务，然后将查询请求路由到该节点。目前常见的结构化 p 2 p 协议有以下几种： ( 1 ) c h o r d c h o r d 是麻省理工学院设计的一种分布式、可扩展的查找协议，c h o r d 项目的 目标是提供一个适合于p 2 p 环境的分布式资源发现服务，它使用分布式的哈希表 ( d i s t r i b u t e dh a s ht a b l e ，d h t ) 技术使得查找对象只需要维护l o g 。n 长度的路 由表。在c h o r d 中，网络节点按照一定的方式分配到一个节点标识符( n o d ei d ) ， 资源对象通过哈希运算h a s h ( k e y ) 得到一个唯一的资源标识符( o b j e c ti d ) ，且 资源将存储在节点标识符与资源标识符相等或相近的节点上。需要查找该资源 时，采用同样的方法可以定位到存储该资源的节点。 第_ 章p 2 p 与应用层组播 ( 2 ) c a n 0 ( o 5 o 7 5 ，o ，5 - 1 o ) ， o 图2 - 2 c a n 的杏找守间 r 0 7 5 一1 0 0 5 1 0 1 内容访问网络( c o n t e n t a d d r e s s a b l en e t w o r k ，c a n ) 是伯克利和a t & t 设计 的一种分布式查找协议，它的独特之处在于采用了多维坐标空间来实现分布式哈 希算法髓9 1 。在任何时候，整个坐标空间动态地分配给系统中的所有节点，每个节 点负责维护独立的互不相交的一块区域( z o n e ) 。c a n 中的节点自组织成一个代表 这个虚拟坐标空间的重叠网络( o v e r l a yn e t w o r k ) 。每个节点要了解并维护相邻 区域中节点的i p 地址，用这些邻居信息构成自身的坐标。 ( 3 ) t a p e s t r y t a p e s t r y 是u cb e r k e l e y 提出的一种新型的p 2 p 网络查找和路由算法，是 o c e a ns t o r e 项目的基础网络模块乜引。该算法可以对消息进行与位置无关的路由， 把查询消息传递到最近的存储有目标对象拷贝的节点。t a p e s t r y 具有自组织、容 错和负载平衡等特点。每个t a p e s t r y 节点只需维护0 ( 1 0 9n ) 大小的路由表信息， 路由最多在0 ( 1 0 9 n ) 跳数内完成。 t a p e s t r y 从一个标识符空间中为每个节点随机分配一个节点标识符 n o d e i d n o d e l d ，对象也从同一个标识符空间中分配一个全局唯一标识符g u i d ( g l o b a l l yu n i q u ei d e n t i f i e r ) t a p e s t r y 使用s h a 一1 来产生标识符，使得 n o d e l d n o d e i d 和g u i d 均匀分布在标识符空间中。 ( 4 ) p a s t r y p a s t r y 是m i c r o s o f t 研究院和r i c e 大学共同提出的用于广域范围p 2 p 应用的 分布式查找和路由协议幢7 。由p a s t r y 节点自组织成高度结构化的覆盖网络，其中 第二章p 2 p 与应用层组播 的每个节点都被分配一个1 2 8 位的节点号( n o d e i d ) 。每个节点在加入覆盖网络 时，都通过p a s t r y 网络所规定的哈希函数随机生成一个自己的n o d e i d ( n o d e i d 可以通过计算节点i p 地址的哈希函数值来获得) ，随机分配的结果是使得所有的 n o d e i d 在1 2 8 位的节点标识符空间中均匀分布。在p a s t r y 中，文件存放在确定的 位置上，系统提供文件标识符到文件存放节点标识符n o d e i d 的映射服务。每条消 息都有个关键字，k e y 与n o d e i d 使用相同的名称空间( 卜2 1 2 8 - 1 ) 。根据关键字， p a s t r y 可以把消息路由至l j n o d e l d 和关键字在数值上最接近的那个节点。 为了使网络具有可扩展性，每个p a s t r y 节点都只维护覆盖网络中的部分拓 扑。为此，每个p a s t r y 节点都需要维护状态表：一张路由表，一个邻居节点集和 一个叶子节点集。其中路由表r 用于p a s t r y 节点的路由，在p a s t r y 采用类似c i d r ( 无类别的域问路由技术) 中的前缀路由b 叭，在路由表中包含2 b _ 1 列和1 2 8 b 行，其中第1 3 行的2 6 一1 个值表示它们与本地节点的相同的前缀有n - 1 位。邻居集 表示在覆盖网络中与本地节点距离最近的m 个节点，m 表示邻居集的大小。叶子集 用于与本地节点的n o d e i d 在数值绝对值上最接近的n 个节点，有一半小于本地 n o d e i d ，另一半大于本地n o d e i d ，通常用于最后一跳路由。图2 - 3 中给出了一个 节点中的数据结构： n o d e i d10 2 3 3 10 2 l e a f s e tjg l i l a | i ri ii a r 汪ri 1 0 2 3 3 0 3 3i1 0 2 3 3 0 2 1 _ 1 0 2 3 3 1 2 0i i1 0 2 3 3 1 2 2 1 0 2 3 3 0 0 1 r1 0 2 3 3 0 0 0i1 0 2 3 3 2 3 0 1 0 2 3 3 2 3 2 r o u t i n gt a b l e 旬一2 2 12 1 0 2 - 2 2 3 0 1 2 0 3 3 1 2 0 3 2 0 3 ial 1 3 0 1 2 3 3 1 - 2 2 3 ( 1 2 0 3 1 _ 3 - 0 2 1 0 2 2 。1 0 0 - 3 1 2 0 3t 让1 - 3 2 1 0 2l2l o - 3 - 2 3 3 n 2 1 0 2 0 - ( t z 3 0f1 0 2 1 1 3 0 21 0 2 2 2 3 0 23 。1 0 2 3 - 0 - 3 2 2 。，l1 0 2 3 - 14 3 0 0l1 0 2 3 - 2 - 1 21kj 3 j 1 0 2 3 3 一。旬1ll0 2 3 3 2 3 2 io。l 0 2 3 3 1 2 加 iii2i n e i g l t o r h o o ds e t 1 3 0 2 10 2 2 l1 0 2 0 0 2 3 0 ”3 0 1 2 1 3i i 3 13 0 1 2 3 3 0 2 2 1 2 1 0 2i - 2 2 3 0 1 2 0 3 1 i 3 1 2 0 3 2 0 3i i 3 3 2 1 3 3 2 1 图2 - 3p a s t r y 节点的数据结构 在p a s t r y 覆盖网络中，假设包含n 个节点，p a s t r y 可以把一个给定关键字 的消息路由到n o d e i d 和该关键字最接近的节点。正常情况下，消息经过l o g n 步， 就可到达。即使同时发生节点失效，p a s t r y 也可以保证关键字送达目标节点。 除非n o d e i d 和关键字临近的节点中机ili 2 扑同时失效( ili 是配置参数，典型 值取1 6 或3 2 ) 为了进行路由，p a s t r y 把n o d e i d 和关键字表示为一串以2 为基 第二章p 2 p 与应用层组播 的数，查询消息被路由到n o d e i d 和关键字在数值上最接近的节点。方法是：每个 节点把查询消息转发给下一个节点时，要保证这个节点的n o d e i d 和关键字的相 同前缀至少要比当前节点的n o d e i d 和关键字的相同前缀长一个数位( 即b 个比 特) 。如果找不到这样的邻居节点，消息转发给前缀长度相同但节点号数值更接 近关键字的节点。 2 - 3 在p 2 p 覆盖网络上实现的应用层组播 正如上一节所分析的那样，p 2 p n 络本身具有支持自组织和成员动态变化的 特性，而在应用层组播的实现过程中，构造覆盖网络是前提。因此，在p 2 p 网络 上开展应用层组播越来越为人们所关注瞳2 1 。 2 - 3 1p 2 p 网络中的应用层组播技术 基于p 2 p 覆盖网络的应用层组播方案在覆盖网络的构造方面较其他的应用层 组播方案有优势，因为p 2 p 协议本身可以使参与节点自组织成一个大规模的、支 持成员动态变化的、健壮的覆盖网络，p 2 p 网络还对上层的应用屏蔽了下层物理 网络的各种特性；其次，由于p 2 p 网络协议的通用性，因此可在p 2 p 网络上实现具 有不同特性的应用层组播方案陴m 1 。p 2 p 网络可支持两种模式的应用层组播，服 务接入点模式和终端用户模式。 实际上为了支持大规模的组播应用，减小建立和维护开销，增加健壮性，研 究人员早已提出建立在特定逻辑结构的( d h t b a s e d ) 应用层组播n 6 儿2 羽。代表是 c a n ，s c r i b e ，b a y e u x ，其中c a nm u l t i c a s t 是在c a n 上实现的，s c r i b e 是在p a s t r y 上实现的，b a y e u x 是在t a p e s t r y 上实现的。通过基于d h t 的覆盖网络，可以将大 规模的节点按照特定的逻辑关系有效的组织起来，在其上建立源驱动或接收端驱 动的组播树，组播协议不需要进行复杂的成员管理和维护，而由底层的逻辑结构 完成。 2 3 2 基于p 2 p 覆盖网络的应用层组播方案 1 、采用c a n 的应用层组播 这种系统采用了c a n 覆盖网络架构，提供了一种应用层组播的解决方案，组 播控制的实现方法是泛洪n 帕。它的基本思想是，在c a n 覆盖网络上，将组中的成 员组成一个小的c a n 网络，在这个小的c a n 网络中，每个节点根据路由表泛洪一条 消息，以f l o o d 方式实现组播。c a n 的组播如图2 - 4 所示： 第_ 章p 2 p 与应用层组播 。4 p 1 r + 1” 一 - f 一 i f 1 i 一t 1 一 - 4 - 1 一上一 - l1 l 4 - l j i 一 一 f 一 l 一 i1 图2 - 4 c a n 泛洪多播不图 该方案实现过程如下： 多播组所对应的d x c a n 形成 假设在现有的c a n 空间c 中，将多播组的地址映射到c a n 中的一点( x ，y ) ，它 的归属点为m ，则将m 作为多播g 的引导节点。多播组中成员节点通过m d h 入到多播 组所对应的d x c a n 网络c g 中。组成员加入多播组g 的过程，就是加入g 所对应的小 c a n 网络c g 的形成过程，当所有的组成员都加入g 后，c g 组成完毕。 多播转发 因为多播组g 所对应的d x c a n 网络c g 中的所有节点都是组成员，因此可以在c g 网络上通过泛洪来实现组播，如图2 - 4 所示。 在c a n 中，来自多个源的多播是可能的。它的缺点是在组播成员构成的d 、c a n 网络中不创建转发树，不可避免的有泛洪所引起的流量，会产生较大的延时和链 路压力。 2 、b a y e u x 组播方案 b a y e u xm u l t i c a s t 是建立在t a p e s t r y 上的应用层组播方案，它通过建立有源 树进行组播数据的分发，所采用的组播控制方法是通过前缀匹配路由确定往组播 根结点的方向，从而构造组播转发树n 叼。 该方案的实现过程如下： 组播会话的公告 在b a y e u x 组播方案中，使用t a p e s t r y 的数据定位服务来公告b a y e u x 的组播会 话。首先使用哈希函数s h a 一1 将会话名称映射为1 6 0 位的标识符u i d ，然后以该标 识符为文件名创建会话文件，并将其保存在根节点。想要加入该组播会话的 t a p e s t r y 节点，必须知道该会话的唯一标识对 ，然后通过相 同的哈希函数映射产生文件名，并且使用t a p e s t r y 进行查询。 组播转发树的维护 第_ 章p 2 p 与麻用层组播 构造一棵有效且健壮的转发树以传送数据到组播会话的成员是应用层组播 系统有效操作的核心。在b a y e u x 中，由t a p e s t r y 节点构成的网络中使用专用服务 器以构造更加有效的组播转发树。在构造转发树时有四种类型的消息：j o i n 、 l e a v e 、t r e e 、p r u n e 。一个成员通过向根发送j o i n 消息加入到组播会话，然后根 回复一个t r e e 消息，以形成组播树的分支。图2 - 5 显示了一个例子。 标识为7 8 7 6 的节点是组播树的根，节