（计算机应用技术专业论文）基于k叉树的应用层组播协议研究.pdf

摘要 摘要 互联网己成为当今信息交流的重要方式。由于网络计算能力和通讯技术的快 速发展，涌现出大量需要更多网络功能支持的新应用，例如多媒体会议、远程教 育、网络广播、数据复制、网络直播、在线游戏等。这类应用的出现意味着对组 通讯模式需求的增加。面对这些新的实际应用，人们提出了应用层组播技术。它 继承了组播的传输特性，如节约带宽、传输快捷，也可以脱离对底层基础网络提 升的依赖。用应用层组播可以实现较大范围的组播通信。 流媒体作为应用层组播的主要应用，要求接收端的信息在一个延迟允许的范 围内到达，而保证流媒体低延迟的关键是构建最小延迟应用层组播算法。其次， 考虑到一定范围内网络的相似性和节点度平衡分配的问题，需要对组播树节点的 度进行约束，从而简化网络异构性所产生的复杂性。本文提出了一种单源的基于 k 叉树的生成树组播模型及应用层组播协议。基于上面两个因素，本协议是基于 时延和度约束的。 关键词：应用层组播流媒体k 叉树最小延迟生成树 a b s t r a c t 3 _ 。- _ 。- 。_ - - _ _ - 。- _ _ - _ 。_ _ _ - _ _ _ - _ _ _ - _ _ _ _ _ _ _ - _ _ _ _ _ - _ _ 。- 。_ _ _ - _ _ _ _ _ _ _ _ _ - _ _ _ _ - _ _ _ - _ _ - _ _ _ _ - - - _ _ 。- _ _ _ _ _ - - _ - _ - - _ _ - _ - _ _ 。_ _ 。_ _ 。h _ 一 一 a b s t r a c t t h ei n t e m e th a sb e c o m ea l li m p o r t a n tm e t h o df o rt h ee x c h a n g eo fi n f o r m a t i o n n o w a d a y s w i t ht h ef m p r o v e m e n to fn e t w o r kc o m p u t i n ga b i l i t ya n dt h er a p i d d e v e l o p m e n to fc o m m u n i c a t i o nt e c h n o l o g i e s ，n e wa p p l i c a t i o n sa r ee m e r g e dw h i c h n e e ds u p p o r tf o rm o r en e t w o r k i n gc a p a b i l i t i e s ，s u c ha sm u l t i m e d i a c o n f e r e n c e ， d i s t a n c ee d u c a t i o n ，i n t e r n e tb r o a d c a s t i n g ，d a t ar e p l i c a t i o n ，n e t w o r kb r o a d c a s t ，o n l i n e g a m e s ，a n ds oo n t h ee m e r g e n c eo ft h o s ea p p l i c a t i o nm e a n st ot h ei n c r e a s ei nd e m a n d f o rg r o u p sc o m m u n i c a t i o nm o d e a p p l i c a t i o nl a y e rm u l t i c a s tt e c h n i q u e si sp r o p o s e dt o a d a p tt ot h o s en e wp r a c t i c a la p p l i c a t i o n s ，w h i c hc a ni n h e r i tm u l t i c a s tt r a n s m i s s i o n c h a r a c t e r i s t i c s ，s u c ha ss a v i n gb a n d w i d t h ，t r a n s m i s s i o ns p e e d ，b ea b l et or e d u c et h e d e p e n d e n c eo nu n d e r l y i n gn e t w o r ku p g r a d i n g t h ea p p l i c a t i o nl a y e rm u l t i c a s tc a n a c h i e v el a r g e s c a l em u l t i c a s tc o m m u n i c a t i o n f i r s t l y , s t r e a m i n gm e d i a ，a st h em a i na p p l i c a t i o no fa p p l i c a t i o nl a y e rm u l t i c a s t ， r e q u e s t st h a tt h ei n f o r m a t i o no ft h er e c e i v e ra r r i v ew i t h i nac e r t a i ne x t e n td e l a y w h i l e t h ek e yt oa s s u r et h el o w e rd e l a yo fm e d i as t r e a m i n gi st ob u i l da na l g o r i t h mo f m i n i m u md e l a ya p p l i c a t i o nl a y e rm u l t i c a s t s e c o n d l y ，t h es i m i l a r i t yo fac e r t a i ns c o p e n e t w o r ka n dt h ea l l o c a t i o no fn o d ed e g r e eb a l a n c ea r ec o n s i d e r e d ，t h ed e g r e eo fn o d e s s h o u l db ec o n s t r a i n e d ，a n dt h ec o m p l e x i t yo fh e t e r o g e n e o u sn e t w o r ki ss i m p l i f i e d a s i n g l es o u r c eo ft h es p a n n i n gt r e em u l t i c a s tm o d e la n dt h ea p p l i c a t i o nl a y e rm u l t i c a s t p r o t o c o lb a s e do nk a r yt r e ei sp u tf o r w a r dw h i c hc o n s i d e rt h et w of a c t o r sa b o v e t h e a l g o r i t h mi sb a s e do nt h ed e l a ya n dd e g r e ec o n s t r a i n t k e y w o r d ： a p p l i c a t i o n l a y e rm u l f i c a s ts t r e a m i n g - m e d i ak - a r yt r e e m i n i m u m d e l a ys p a n n i n gt r e e 西安电子科技大学 创新性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容外，论文中不包 含其它人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学或其 它教育机构的学位或证书使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中做了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名：耋熬 关于论文使用权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕 业离校后，发表论文或使用论文工作成果署名单位仍然为西安电子科技大学，学 校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全部 或部分内容，可以允许采用影印、缩印或其它复制手段保存论文。( 保密的论文在 解密后遵守此规定) 本学位论文属于保密，在年解密后使用本授权书。 本人签名：h 导师签名： 日期： 塑星翌：星 日期：型盔：季。莎 第一章绪论 第一章绪论 1 1 研究背景 自从a r p a n e t 与n s f n e t ( 雪家自然科学基金网) 互连之后，互联网的发展 以指数速度增长，1 9 9 0 年之后，互联网的规模几乎以每年翻一番的速度持续增长。 互联网的商业化为网络用户提供多种新型服务，如电子邮件、文件传输、新闻、 w b r l dw i d ew e b 等。上述应用都是通过单播( u 1 1 i c a s t ) 的方式在互联网中传送数 据，从一个源节点发送到另一个目的节点，即点到点的通讯方式。互联网的网络 层只负责实现最小限度的功能，即单播数据的尽力发送，其他诸如容错、拥塞和 流量控制的功能则由主机实现。互联网己成为当今信息交流的重要方式。由于网 络计算能力和通讯技术的快速发展，涌现出大量需要更多网络功能支持的新应用， 例如多媒体会议、远程教育、网络广播、数据复制，多媒体协作、分布式数据库、 在线游戏等等1 8 】。这类应用的出现意味着对组通讯模式需求的增加。针对组通讯 模式中的数据传输，如果采用单播( u n i c a s t ) 方式，已经不再能适应这一类业务传 输特性一“单点发送、多点接收 ，因为服务器必须为每一个接收者提供一份相同 内容的i p 报文拷贝，使得网络上重复传输大量相同内容的报文，占用了大量资源。 在这种情况下组播( m u l t i c a s t ) 应运而生，它的出现解决了网络数据冗余的问题，尤 其对于音频、视频数据，可以节省大量网络资源，解决一个主机向多个接收者发 送数据的问题，显示了在单播与组播两种通信模式下，对于“一点发送、多点接 收”应用的实现方式。 1 1 1 i p 组播 i p 组播将一个i p 报文向一个“组播组 传送，组播组可以包含零个或多个主 机，由一个单独的i p 地址( d 类地址) 标识。除了目的地址部分，组播报文与普通 i p 报文没有区别。i p 组播提供不可靠的、尽力而为的服务。 ， 传统的i p 组播基于开放的服务模型，对主机和用户创建组播组、发送、接收 组播数据没有限制。不提供任何接入控制。组播组的成员可以动态变化，主机有 权选择加入或者退出某个组播组。主机可以加入多个组播组，也可以向自己没有 加入的组发送数据。希望接收到组播数据的主机通过与运行i g m p ( i n t e m e tg r o u p m a n a g e m e n tp r o t o c 0 1 ) 协议的路由器交互加入组播组，加入之后就能接收到组播源 点发送的数据。 2 一 基丁k 义树的应用层组 番协议研究 组播数据沿一个连接所有组播组成员的树型结构发送，这个树型结构称为组 播树。组成员可以动态的加入和退出，组播树也必须同时动态更新。根据构造方 法的不同，组播树可以分为源点树( s o u r c e b a s e dt r e e ) 矛1 共享树( s h a r e dt r e e ) 。源点 树以组播源点为根构造到所有组播组成员的生成树，通常也称为最短路径树 ( s p t ，s h o r t e s tp a t ht r e e ) 。共享树也称为r p ( 汇聚点) 树或基于核心的树( c b t c o r e 。b a s e dt r e e ) ，它的构造方法是以网络中的某一个指定的路由器为根节点，该 路由器称为r p ，由此节点生成。使用共享树时，组播源需要首先把组播数据发送 到r p 路由器，再转发给其他的组成员。 组播路由协议的任务就是构造组播树，根据对网络中的组播成员的分布和使 用的不同，组播路由协议分为两类：密集模式( d m ，d e n s em o d e l ) 路由协议和稀疏模 式( s m ，s p a r s em o d e l ) 路由协议。 1 1 2i p 组播存在的问题 目前i p 组播的服务模型和协议存在着一些问题，使得i p 组播至今没有能在 i n t e m e t 上得到广泛部署【9 】。一方面，从因特网服务提供者( i s p ) 的角度看，目前的 i p 组播不能很好的商业应用的需求： ( 1 ) 组播数据包的复制和转发都由路由器来完成，这就需要路由器对组播功能 的支持，如果现有的设备不支持组播，就需要更换设备，增加了商业运营成本。 ( 2 ) 一些使用共享树组播路由协议，如p i m s m 和c b t 的i s p 面临跨域组播 管理的问题：如果r p 和其它组播源点不在同一个域内，难以进行流量控制和拥塞 控制；i s p 对其它域中的r p 的服务没有控制能力；当需要跨域的组播服务时，i s p 之间必须进行协调。 ( 3 ) 组播代价的问题，组播实施和管理比单播要复杂和困难的多，因此只有使 用它节省的带宽大大超过它的实施代价时才有商业价值。 ( 4 ) i p 组播还没有成熟的商业计费模型。 ( 5 ) i p 组播服务模型本身还存在一些有待解决的技术问题。 ( 6 ) 要求路由器保存每个组的状态，不仅破坏了最初网络设计的“无状态”原 则，也带来了巨大的复杂性，限制了系统的可扩展性。 ( 7 ) i p 组播服务模型没有组播组管理机制，如缺乏组创建的管理，没有对接收 者和数据传输的授权机制，发送者可以随意传输数据而不需要进行任何身份验证 和注册工作，主机可以动态加入或离开组播组，发送者也不能阻止其它发送者也 选用同样的地址。缺少访问控制机制会带来很多问题：比如恶意的泛洪攻击，当 大量无用的数据传输到组播组中会导致拥塞和报文丢失；因为没有组创建机制， 第一章绪论 组播地址可能发生冲突。 ( 8 ) 组播的安全问题。由于很多防火墙不能识别i p 组播使用的d 类i p 地址， 目前的解决办法是使用隧道技术来穿越防火墙，这样在部署组播服务的同时也造 成一些安全漏洞。 ( 9 ) 组播服务质量向题。i p 组播基于u d p 协议，遵循传统的在单播的情况下 得到很好执行的“路由与传输分离 的原则，只提供一种尽力而为的服务，要想 在它之上实现更高质量的服务，例如可靠性、拥塞控制和流控制等这些功能，比 在i p 单播上实现要困难很多。 ( 1 0 ) 可扩展性差。要求路由器保持每个组播组的状态信息，而这些d 类地址不 能很好的聚合，组播组的数量一旦大量增加，必然增加路由器存储和处理开销。 ( 1 1 ) 缺乏灵活、可扩展的地址分配机制。节点不能有效的发现一个立即可用的 组播地址，而只是随机的选取一个来使用，这样随着组数目的增加，组播地址冲 突的可能性也随之增加。使用d 类地址作为组播地址，可能面临着地址空间用尽 的问题。 ( 1 2 ) 域间组播路由协议对组播技术大规模的实施有重要的作用，它使i s p 可以 将他们的网络互连，同时隐藏各自网络的拓扑结构。但是，i p 组播还没有成熟有 效的域间组播路由协议。 ( 1 3 ) 为了降低复杂性，人们提出了单源点组播应用，e x p r e s s 和s s m 属于这一 个范畴，发送者使用一个本地唯一组地址加上自己的i p 地址来唯一的标识一个组。 它解决了组地址的分配问题。但不是所有的应用都是单源点组播，也不能简单的 将其转变成多个单源点的应用，因此人们仍然有必要寻求更加普遍适用的解决方 案。 1 1 3 应用层组播 1 9 8 9 年，d e e r i n g 在他的论文中提出，组播的功能应该放在i p 层来完成【l ， 然而，i p 组播存在的一系列问题使它不能大规模的实施。从体系结构上来说，被 加入到核，t l , 网络中的功能都应该是一些基础的、通用的功能。但是组播的应用主 要如视频会议、远程教学、分布式存储、多方游戏及视频播放等，它们可能是多 源点，也可能是单源点的：对扩展性、延时、带宽、可靠性以及组成员动态改变 的要求各不相同，很难将它们的共性抽象出来放到网络核心中实现i l 引。用户对组 播服务，尤其是多媒体组播服务有巨大的需求，然而i p 组播又不能很好的满足要 求，人们于是丌始把目光转向其它替代方案，而应用层组播就是其中重要的一种。 利用o v e r l a y 网络的技术优势，人们可以在应用层实现i p 组播的功能。i p 组 4 一 基于k 义树的应用层组播协议研究 播需要组播路由器的支持，而应用层组播将组播功能从路由器移到端系统，由端 系统完成所有组播组通讯的功能，如成员管理、数据包复制和分发。组成员之间 建立一个叠加在i p 网络之上的、实现组播业务逻辑的功能性网络。 应用层组播与i p 组播的基本区别是：在应用层组播中，包复制转发都是由主 机实现，而在i p 组播中，则是由璐由器实现。应用层组播解除了对路由器支持组 播功能的要求，因此可以克服i p 组播存在的阻碍其发展的很多问题： ( 1 ) 在推广的复杂度上，应用层组播比i p 组播有优势。在i p 层实现组播的直 接后果就是要求路由器支持最基本的组播模式，也就是说，需要改进路由器当前 的工作模式以提供组播功能。然而，经过二十多年的发展，路由器一般只包含一 些基本功能，这也是由于近几年互联网技术和应用发展的突飞猛进所导致，反过 来这些发展又坚定了路由器以现有模式继续发展，因此，服务供应商( i s p ) 也不愿 意对现有的路由器做出改变l l 引。另一方面，随着不断发展，路由器的负担越来越 重，并且很难将组播功能提取成一个小的、普适的功能集合融入到网络中，因此， 到目前为止，一直没有真正值得推广的域间i p 组播路由协议。而应用层组播是将 组播功能提升到应用层，底层网络只需支持简单的单播功能，因此，应用层组播 的推广仅由服务提供者来决定，由应用需求来驱动。 ( 2 ) 在q o s 控制方面1 4 j ，应用层组播也比i p 组播有优势。在互联网结构中， 尽力传输服务是由i p 层提供的，因此，i p 组播的执行应该与这些基本功能服务 保持一致，这意味着i p 组播不能保证组通信的q o s 性能。相反，应用层组播中 的数据是通过单播进行传输的，单播中的成熟算法，。比如流量控制、拥塞控制和 可靠传送服务，都可以直接应用到应用层组播中。 ( 3 ) 在路由的可扩展性上，应用层组播也更胜一筹。此处的路由可扩展性是指 传输一个组播数据所需要的路由信息量。在i p 组播中，每个组播组都有一个属于 d 类i p 地址的组播地址，i p 组播地址空间是平面的，既不包含拓扑意义，也不包 含地理含义【1 4 】。因此，i p 组播并不能采用像单播那样为了保持网络增长所采用的 地址聚集和分层路由的方法。另外，路由器要为每个组播组保存信息，随着组规 模的增长，尤其是多源应用组的增长所产生的大量信息让路由器无法承受。而在 应用层组播中，则不需要为组播组分配全局组i d ( 即组播地址) ，路由器并不需为 整个组维护路由信息，虽然这个责任需要由主机来承担，但主机们只负责为自己 的孩子成员维护路由信息，而不必负责全部的组成员。 1 2 研究现状 应用层组播思想提出后的短短几年内，多个研究机构开展了应用层组播体 第一章绪论 系结构的研究项目，如：e s m 、y o i d 、s c a t t e r c a s t 、o v e r c a s t 、a l m 、h m 等， 下面对这几个项目进行简单的介绍。 1 e s m 4 2 l e s m 是卡耐基梅隆大学开展的一个端系统组播研究项目，是目前为止最成 功的一个项目。2 0 0 0 年，e s m 的研究表明，在端系统中实现组播功能的体系结 构是可行的，可以支持组成员在几百范围内、分布稀疏的、较小规模的多方通信。 2 0 0 1 年，通过在因特网中实际运行基于e s m 的视频会议，验证了e s m 采用的自 组织协议可以在动态的、异构的因特网中支持较小规模的视频应用。 n a r a d a 1 5 j 是e s m 的组网协议。n a r a d a 协议首先在组播成员之间建立个网 状的覆盖网，然后在覆盖网上运行组播路由协议，建立一棵组播转发树。通过动 态探测网络状态，n a r a d a 动态地对覆盖网进行维护和改良。 2 y o i d t l 2 1 y o i d 是a c i r i ( a t & tc e n t e rf o ri n t e r n e tr e s e a r c ha ti c s i ) 研究中心在2 0 0 0 年 提出的，基于应用层组播的一整套内容分发的解决方案，包括了应用层组播之上 的可靠、安全、拥塞控制等机制。y m t ( y o i dm u l t i c a s tt r e ep r o t o c 0 1 ) 是y o i d 体 系的核心，是一种自组织的拓扑管理协议，将主机组织成网状网和共享的组播转 发树。 3 s c a t t e r c a s t 1 0 】 2 0 0 0 年，b e r k e l e y 大学的y c h a w a c h e 在其博士论文中提出了s c a t t e r c a s t 的体 系结构。这是一种基于应用层组播实现因特网大规模广播业务的体系结构。其思 想是在因特网中部署支持广播业务的服务器，称为s c a t t e r c a s tp r o x y 节点，应用层 组播将这些服务器组织成一个因特网广播业务的支撑网，支持用户规模巨大的 i n t e m e t 广播和软件分发应用。s c a a e r c a s t 体系结构包括应用层组播机制、应用层 组播之上的传输层机制以及内容请求的实现机制。g o s s a m e r 是s c a t t e r c a s t 体系结 构的自组织组网协议。 4 o v e r c a s t 4 5 】 o v e r c a s t 是在c i s c o 公司支持下开展的一个研究项目，是解决因特网内容分 布的一个体系结构，实现可靠的组播业务。通过在网络中战略性地部署o v e r c a s t 节点，然后由应用层组播机制将该节点组成一个骨干转发网络，能够以可靠的方 式实现内容的分发。o v e r c a s t 和s c a t t e r c a s t 思想类似，采用在网络边界部署应用 层组播节点组成一个业务网络的策略，两者实现应用层组网的机制不同，并且 o v e r c a s t 侧重于实现组播数据的可靠分发。 5 a l m i ( 4 6 】 a l m i 是美固华盛顿大学s t l o u i s 分校计算机系从2 0 0 0 年开始进行的研究项 目，提出了将应用层组插作为端系统基础服务功能的体系结构。a l m i 设计了在 6 一 基丁k 义树的应用层组播协议研究 操作系统的套接u l ( s o c k e t ) 之上，以中间件( m i d d l e w a r e ) 的形式向上层应用提供组 播服务的结构，中间件实现自组织组网、组播复制和转发功能，在组播成员节点 之间组成一个应用层组播网。a l m i 研究组以j a v a 代码实现了中间件的原型。 a l m i 的自组织协议在组成员节点之间建立和维护一棵共享的最小代价生成树 ( m i n i m u ms p a n n i n gt r e e ) ，支持组规模较小的多方通信a l m i 可以针对上层的应 用需求构建不同性能的覆盖网。 6 h m 1 3 】 美国密西根大学电子工程与计算机科学系2 0 0 0 年开始的端主机系统组播 ( e n d h o s tm u l t i c a s t ) 项目提出了h o s t m u l t i c a s t 体系结构。h m 的基本思想是通过 应用层组播来桥接网络层组播，连接分布在因特网中多个网络层组播岛中的组成 员，实现网络层组播跨越因特网的数据分发。同一个网的网络层组播组成员选举 一个成员作为代理，代理节点之间通过应用层组播机制建立一个连接各个网络层 组播网的骨干网，桥接进出网络的网络层组播数据。h m 框架的其它部分包括网 络服务的获取、网络层组播地址的转换等实现网络层组播桥接的功能体系。 在已经提出的各种应用层组播体系结构中，除了h m 之外，其它的方案都面 向特定的上层应用。此外，在因特网中，一些内容服务供应商采用的分布式内容 服务系统实际也采用了应用层组播技术，将内容服务器通过应用层组播连接成一 个分布式的系统。 表1 1 各研究项目比较 项目面向的上层应用 支持的组播规模选取链路时考虑的参数 e s m 实时和非实时较小带宽和时延，可以根据上层应用调整 y o l d 非实时，可靠巨大带宽，节点的逻辑连接数 s c a t t e r c a s t非实时，可靠大 带宽 o v e r c a s t 非实时，不可靠巨大带宽 a l m i 实时和非实时较小 带宽和时延，可以根据上层应用调整 h m 实时年n t l e 实时 巨大 ：育点的度 1 3 论文的主要工作和章节安排 本文简要地介绍了i p 组播技术的缺点，并对应用层组播作了阐述，然后对应 用层组播的三种典型的协议作出了详细的阐述，对流媒体服务及相关应用层组播 技术进行了介绍。同时对度约束和时延限制的组播路由算法进行了研究，为提高 该类算法的执行性能，提出了基于k 叉树的应用层组播算法。最后利用n s 2 网络 仿真软件，对所提出的算法进行了仿真。 本文的章节安排： ( 1 ) 第一章绪论简单的介绍了本文的研究背景，和研究现状。 第一章绪论 ( 2 ) 第二章首先介绍了应用层组播的分类，然后详细分析了每种分类中典型的 应用层组播协议，对应用层组播中最主要的实际应用一流媒体进行了介绍。 ( 3 ) 第三章提出了基于k 叉树的应用层组播算法，讨论了基于k 叉树模型的 性质。研究了最小延迟生成树的数据结构一节点树深度表( d e p t ht a b l e ) ，在考虑 到最大延迟路径和平均延迟路径的基础上提出了k t 最小生成树算法。给出了组 的成员的管理策略。 ( 4 ) 第四章详细的介绍了本文的仿真平台，基于n s 2 平台对算法进行了仿真， 并对仿真结果进行了分析。 ( 5 ) 第五章对本文做了总结，对本文所作的工作做了概括。然后未来的工作提 出了设想。 第二章应用层组播技术 第二章应用层组播技术 应用层组播又称为覆盖网络组播、端系统组播和基于主机的组播。应用层组 播是一种在o v e r l a y 上实现组播的特殊组播方式，它的组播功能是由主机来实现 的，组播数据的实际传输通过底层网络的单播链接来进行。应用层组播使用传统 单播提供的服务，在终端主机的应用层上实现组播的特征例如：组关系、寻址、 组播路由和报文复制，网络只需要提供尽力传输的单播功能。应用层组播的基本 思想入图2 1 所示。图2 1 a 是网络层组播的实现示意图，分组由网络中的路由器 进行复制，如果主机a 需要向主机b ，c ，d 发送分组，则分组在路由器l 处进行复 制，而在应用层组播中，分组在端系统处进行复制。端系统构成逻辑上的覆盖网 络，应用层组播的目标就是便于进行数据传输，构造并维护高效的覆盖网络。 口路由器( ) 主机 图2 i网络层组播和应用层组播 2 1 应用层组播的分类 本小节将会对目前几个比较受关注的协议做一个分类。应用层组播协议通常 把组成员组织成两个逻辑拓扑：控制拓扑和数掘传输拓扑。拓扑上的每条边都相 当于一条单播传输路径。控制拓扑主要用来在端系统| 白j 周期性的交换控制信息来 发现和恢复由于一些成员的非法离开造成的拓扑破坏或进行拓扑优化。数据拓扑 通常是控制拓扑的一个子集，主要用来表明数据包的传输路径。实际上，数据拓 扑一般是一棵树形结构，而控制拓扑要求有更多地连接，则通常是一个网状拓扑 结构。因此，根据构建控制拓扑和数据拓扑的顺序，可以将目前网络层组播协议 9 一 1 0 基丁k 义树的应用层组播协议研究 的实现方法分为：网状拓扑优先方法，树状拓扑优先方法以及隐式方法三大类。 1 网状拓扑优先方法 在基于网状( m e s h ) 的策略中，组成员首先自主地形成一个分布式的m e s h 拓 扑。在一对组成员之间可能存在多个路径。每个成员都要运行分布式的路由协议， 计算自己到其它节点的转发路径了可以采用被许多i p 组播路由协议采用的反向路 径转发机制创建面向源的组播树( s o u r c e s p e c i f i cm u l t i c a s t t r e e ) 。 2 树拓扑优先方法 基于树的策略直接采用分布式算法构造数据转发树。然后，每个组成员都主 动发现一些并不是自己邻居节点的组播树中的其它节点，并建立和维护这些节点 的控制链路。在基于树的策略中，数据转发树加上这些控制链路就构成了控制拓 扑。 2 隐式方法 基于隐含组播转发拓扑结构的策略使用面向大规模对等网络的路由机制创建 带有某些特殊属性的控制拓扑。在控制拓扑中就隐含定义了数据转发路径，一些 数据转发规则利用控制拓扑的特定属性构造没有环路的组播路径。在该策略中， 协议同时构造m e s h 和树，不需要额外的组成员的交互动作。 2 2 各类型应用层组播协议项目 2 2 1 基于网状拓扑优先的应用层组播协议 1 n a r a d a 协议 n a r a d a 1 5 1 【m 1 协议是由卡耐基梅隆大学计算机系较早提出的，它将组播功能 从路由器处转移到了主机，由主机负责组成员的管理和报文的复制等所有的组播 功能。仿真和i n t e m e t 实验显示端系统组播带来的性能损失很低，从而证明了在 应用层可以方便高效地实现组播功能。n a r a d a 协议中指定一个特殊的主机节点称 为聚集点( i u ) ，新加入的组成员通过这个节点来进行自举操作( b o o t s t r a p ) 。事实 上，所有的应用层组播协议都要使用一个和n a r a d a 中的r p 功能相近的实体来发 起加入操作机制。 ( 1 ) m e s h 网络的构造 n a r a d a 首先构造节点之间的m e s h 覆盖网络，然后基于某种路由协议在m e s h 网中构造以数据源节点为根节点的生成树。以图2 2 为例，图中a ，b ，c ，d 4 个节点 构成了m e s h 网，带箭头的虚线表示以b 节点为根节点的一棵数据生成树。 第二章应用层组播技术 图2 2m e s h 网和数据生成树 n a r a d a 采用基于m e s h 网的策略主要是为了更好地支持多个数据源的组播应 用，如果直接构造单源共享树则很容易出现单一故障点而且单源共享树很难针对 不同的节点进行优化。对每个可能的数据源节点都构造一棵数据转发树可以解决 这一问题，但是这会造成控制负载的增加并加大维护难度。而采用基于m e s h 网 的策略可以在m e s h 网范围内进行组管理，并利用标准的组播路由协议构造组播 生成树，从而很好地解决了这一问题。 在n a r a d a 中，生成树完全基于m e s h 网中的链路构造，因此为了获得一棵高 质量的生成树首先要获得高质量的m e s h 网。m e s h 网的质量由下面两类参数衡量， 一个是节点间路径的质量，包括展度、延迟、带宽等，另一个是每个节点的邻居 节点数量。 ( 2 ) n a r a d a 中的组管理 由于n a r a d a 的设计目标是不依赖于单个节点进行组维护，因此组维护的任务 就需要由各个节点共同承担。在n a r a d a 中每个节点都维护所有其它节点的信息。 由于n a r a d a 的目标是支持最大几百个节点的中等规模的组播应用，因此每个节点 都维护完整的组成员信息是可行的。每当有新成员加入或者原来的组成员退出时， 都需要对所有节点的组成员表进行更新。那么如何在组成员之间发布这些更新消 息是一个需要解决的问题，尤其是在底层不支持i p 组播的情况下。n a r a d a 利用 m e s h 网来发送成员更新消息从而解决了这一问题。但是必须考虑到在某种情况 下，某个节点退出会导致m e s h 网被分隔成几个互不连通的子网。为解决这一问 题，n a r a d a 让每个节点定期生成一条更新消息并附加一个单调增加的序列号，更 新消息将在m e s h 网的节点间传送。每个节点i 都要维护其它节点k 的下列信息： o k 的地址；k 发送来的最后一个序列号s i ( i ；i 收到s k i 的本地时间、如果经 过t m 时间后i 还是没有收到k 的更新消息，i 就认为或者是k 离开了系统，或者 是k 和自己被分隔了。于是i 就将执行系列动作来确定网络中是否出现了分隔 现象，如果出现了分隔则执行修复操作。 在m e s h 网中，如果每个节点都和其它所有节点交换更新消息，将会对网络 产生比较大的负担。因此，作者将其改进为只在m e s h 网的邻居节点之间交换更 新消息。从节点i 发送到节点j 的更新消息将包括多个数据项，每个数据项对应 基丁k 叉树的应川层组播协议研究 于i 知道的一个组成员k 的信息，包括下列数据域：k 的地址；k 发送给i 的 最新的一个序列号。当节点i 收到节点j 发来的消息时，将根据消息中的每个数 据项对自己的组成员列表进行更新。 当一个新成员希望加入组播组中时，它首先获得一个m e s h 网中组成员列表。 这些信息通常可以从r p 处获得，r p 维护所有己加入组播组的成员状态。新成员 随机地从这些组成员列表中选择一些组成员，并且作为这些组成员的邻居节点试 图加入到网格中来。当至少有一个组成员接收新成员为网格邻居时，加入过程就 获得了成功。加入成功后，该成员就可以与它的邻居节点交互更新消息。当组成 员主动离开组时，会通知它的邻居节点，然后该消息将传播给其它成员。另外一 种情况是节点突然失效，这就需要某种失效检测机制来发现节点的失效。 以图2 3 为例，假设某一时刻节点e 突然失效，那么d 和f 就不会再收到e 发送来的更新消息。超时之后d 和f 将会独立地向e 节点发送探测消息( 多个探 测消息同时丢失的概率很小) ，如果e 没有对任何一条探测消息进行响应，d 和f 就认为e 己经失效并把这一情况告诉其它节点。每个节点都需要把失效节点在自 己的组成员列表中保留一段时间，否则节点就不能区分收到的更新消息是宣布一 个新节点加入系统还是已经失效节点残留的更新消息。一段时间之后( 时间的设置 要保证系统中不会再有失效节点信息的更新消息) ，该表项可以从组成员列表中删 除。 图2 3 失效的检测与恢复 ( 3 ) 修复分隔的m e s h 网 仍然以图2 3 为例，假定节点d 失效，那么整个m e s h 网将被分隔成两个子 网。这时成员必须首先检测到出现分隔，然后通过增加成员之间链路的方式来修 复被分隔的m e s h 网。每个节点都会维护一个超时节点队列，队列中是经过t m 时 间仍然没有收到更新消息的节点。如果网络出现了分隔现象，那么被分隔开的节 点都会出现在其它节点的超时队列中，例如节点a 、b 和c 都会出现在节点e 、f 和g 的超时队列中。节点将采用某种基于概率的策略周期性地从队列头部取出一 个节点并对该节点进行探测，探测的结果或者是有节点已经失效或者是发现一个 分隔，这时通过在这两个节点之问增加一条链路就可以恢复分隔。 ( 4 ) m e s h 性能优化 生成树的质量决定于m e s h 网的质量，n a r a d a 构造的m e s h 可能并不是性能 第二章应刚层组 番技术 最优的，需要对m e s h 网进行周期性优化以提高生成树的质量。造成m e s h 网性能 下降的主要原因有： 新节点加入m e s h 时没有考虑网络拓扑结构信息； 分隔修复过程可能会增加不必要的链路； 组成员不断地加入或退出组； 底层网络条件不断发生改变。 图2 4 显示了对m e s h 网进行优化的必要性。通过在 之间增加一条路径 并去掉原先 之间的路径，大部分节点之间的距离都会减小( 假设每条链路的 长度均为1 ) ，例如原先 之间的距离为4 ，改进后减小到2 ，效果非常明显。 嘎理旧田m a h 一 图2 4 对m e s h 网的改进 通过增加和删除m e s h 网中节点间的链路束改善m e s h 的性能。首先定义了链 路利用率的指标，组成员随机地探测链路的利用率，如果某条链路的效用很低则 会被删除，如果某条链路的效用很高，接近饱和则需要增加其它的链路。 问题是如何设计反映m e s h 网质量的链路效用指标。一个高质量的m e s h 网必 须保证任意两个节点之间的路径性能都和这两个节点之问网络层的单播路径的性 能相当。精确的效用函数必须根据m e s h 性能参数来确定。下面的链路效用评价 算法给出了一个根据延迟计算链路效用的例子，n a r a d a 采用此策略进行链路评价 并据此执行链路的增加和删除操作。在这个例子中，效用最大值为n ，n 是i 所关 心的组成员的数量，每个成员m 最多为利用率贡献1 。 。 每个节点周期性地随机向不是自己的邻居节点发送探测报文，当节点i 探测 节点j 时，节点j 将把自己的路由表发送给节点i ，i 将根据j 的路由表计算如果在 i 和j 之间增加一条链路，效用增加值将会是多少。如果效用的增加值超过某个预 先设定的阀值，那么这条链路将被加入到m e s h 网。 e v a l u a t e u t i l i t y ( i ) 基丁k 义树的应用层组橘协议研究 b e g i n u t i l i t y = o f o re a c hm e m b e rm ( mn o ti ) b e g i n c l = c u r r e n tl a t e n c yb e t w e e nia n dm a l o n gm e s h n l = n e w l a t e n c yb e t w t e nia n dma j o n gm e s h i fe d g e ( i ，j ) w e r ea d d i f ( n l i 。 ( 4 ) 每个集群大小的限制是k 到3 k 一1 。集群领导是该集群理论上的中心。 ( 5 ) 分层结构最多有l o g k n 层，最高层上只有一个成员。 n i c e 的控制拓扑和数据拓扑： 在n i c e 中，成员间的层次关系可以用来定义控制拓扑和数据拓扑。在控制 拓扑中，每一个集群中的所有成员定期的和其它成员交换更新信息。很明显，对 控制消息需要一个高度互连的结构，这样可以使协议快速的聚合。 图2 8 说明了n i c e 是如何选择控制路径和数据路径的( 事先指定集群的大小 是4 ) 。图上的边表示在层次结构中一组成员之间的对等关系。在图中每四个成员 一组构成了l o 层的四个集群。主机b o ，b l ，b 2 和c o 分别是l o 层四个集群的集群领 导。而对于l i 层的唯一一个集群来说，c o 是该集群的集群领导。在这里我们使用 c l j ( x ) 来表示在l i 层的集群，当且仅当成员x 属于该集群。 第二章戍川层组橘技术 a 0 图2 8n i c e 协议两层层次结构的控制和数据路径 图2 8 显示了n i c e 协议的控制拓扑。控制拓扑是这样定义的：如果成员x 属于与l o ，l l ，l i 层，那么它在控制拓扑上的对等成员就是x 所在的每一层所属 的集群中的其它成员，例如c l o ( x ) ，c l j ( x ) 的成员。以图2 8 为例，成员a o 只属 于l o 层，因此它的控制拓扑路径上的对等成员是l o 层它所在集群的成员，例如： a l ，a 2 ，b o 对比下，成员b o 属于l o 层和l 1 层，因此b o 在控制拓扑路径上的成员 是l o 层和l l 层它所在集群的成员( l o 层有a o ，a l , 和a 2 ；l l 层有b l ，b 2 和c o ) 。在 控制拓扑中，集群中的每个成员和对等成员交换状态更新信息。这样所有的集群 成员能够快速判断出集群成员关系的变化，从而快速修改系列的参数，以免造 成冲突。 组播数据传输路径必须是没有环路的，否则就需要实现重复报文检测和抑制 机制来避免数据报文的重复。因此，在n i c e 协议中，数据的传输路径是一棵树。 更具体地说，给定一个数据源，那么数据传输路径就是一棵源树，并且这棵源树 是由控制拓扑隐式定义的。数据拓扑是由以下的转发规则所定义：源成员发送数 据报文到控制拓扑上所有的对等端。有一个中间成员h 它属于l o ，l l ，l j 层，并 且成员h 从另个成员p 这里接收数据。那么成员h 和成员p 属于某一层的同一 个集群，假设这一层是l i 。成员h 将转发数据报文到所有其它的成员，这些成员 属于集群c k ，k ，( c k 代表l k 层的集群) ，当且仅当成员h 是c k 的集群领导。 在收到数据后，每个成员执行如下所示的m u l t i c a s t d a t a f o r w a r d 过程： p r o c e d u r e - m u l t i c a s t d a t a f o r w a r d ( h ，p ) ( h l o ，l i 并且在集群c l o ( h ) ，c l i