（控制理论与控制工程专业论文）面向流媒体的应用层组播原型系统的研究与实现.pdf

摘要 摘要 随着i n t e r n e t 和计算机技术的飞速发展，i n t e r n e t 中的用户和应削表现出了新的特 点：端用户的计算能力不断增强与之相对应的麻用需求也发生了变化，其中最显著的是多 媒体业务如流媒体，视频会议和视频点播等应用日益广泛。这类应用通常具有一对多，多 对多的通信特点，同时要求网络提供服务质量的保证。目前i p 组播的服务模型和协议存在 着一些不足，使得它至今没能在i n t e r n e t 上得到厂1 泛的部署。在i p 组播无法满足应用需 求的情况下，人们开始把目光转向充分利用i n t e r n e t 端用户的计算资源，在应用层上实现 组播服务。 应用层组播将组播功能从路由器转移到端系统，由端系统完成所有组播组通讯的功能， 如组播树的构建，数据包的复制与分发等。从而摆脱了传统的i p 组播对路由器的依赖，充 分发掘端用户的计算资源，并且可以灵活的添加各种功能。 本论文主要研究了面向单源流媒体非交互式应用的应用层组播系统。首先在充分分析 已经提出的各种应用层组播协议的基础上，依据本论文所研究的应用背景对已经提出的协 议作出了相应的改进使其满足本应用的需求，并对其进行了仿真分析。其次，设计并实现 了基于这个协议的原型系统，该系统实现了组播组的创建，组播组的加入和退出以及节点 失效的处理，同时对其性能在局域网中进行了测试。具体的本论文主要工作有： ( i ) 阅读了大量国内外与应用层组播相关的文献资料，分析它与i p 组播相比具有的优势， 对现有的应用层组播系统进行研究分析，归纳并总结了他们各自的特点及存在的问题。 ( 2 ) 在分析现有应用层组播协议的基础上，提出了一个针对非交互式流媒体应用的改进型 应用层组播协议- - s s a l m p ，该协议主要解决了在带宽异构的情况下待加入节点如何 选择合适的父节点的问题。 ( 3 ) 对于提出的改进型协议进行了仿真分析，并与其他已经提出的协议进行了比较，说明 了它的优点。 ( 4 ) 实现了基于改进型协议的应用层组播原型系统，其中提出了消息优先级的方法大大提 高了系统的响应速度。 ( 5 ) 对原型系统在局域网中进行了测试，主要澳4 试内容包括组播组的创建，组播组的加入 和退出以及节点失效的处理，测试结果表明原型系统基本达到了设计要求。 关键字 应用层组播组播树动态哈希路由f r e e p a s t r yj m f 摘要 a b s t r a c t w t 1t h eh j 【曲s p e e dd e v e l o p m e n to fi n t e r n e tt e c h n o l o g ya n dc o m p u t i n g t e c h n o l o g y , a p p l i c a t i o n sa n du s e r si nt h ei n t e r a c ta p p e a rn e wc h a r a c t e r s ，e n d - s y s t e m u s e r sc o m p u t i n ga b i l i t yi na c c o r d i n g 、i t ht h en e e do fa p p l i c a t i o nh a v ec h a n g e d ， e s p e c i a l l yt h es e r v i c eo f m u l t i m e d i a , f o re x a m p l es t r e a m i n gm e d i a ，v i d e oc o n f e r e n c e ， a n dv o da r eb e c o m i n gm o r ea n dm o r ew i d e l yu s e d t l l i st y p eo fa p p l i c a t i o nh a v e s o m ec o m m o nc o m m u n i c a t ec h a r a c t e r so fo n et oo n eo rm o r et om o r e ，a tt h es a m e t i m e n e t w o r ki sa s k e df o rt op r o v i d eq o sr e s t r i c t i o n s a tp r e s e n t t h es e r v i c em o d e l o fi pm u l t i c a s ta n dp r o t o c o lh a v es o m ed e f i c i e n c yw h i c hm a k ei tn o tb ew i d e l y a p p l i e di nt h ei n t e m e t u n d e rt h i sc o n d i t i o n ，p e o p l ec h a n g et h e i rr e s e a r c hw o r kt o h o wt oa sf a r 够u s et h ec o m p u t i n gr e s o u r c eo fe n d - u s e r ss y s t e mi nt h ei n t e r a c t a n d t r yt or e a l i z ea p p l i c a t i o nl a y e rm u l t i c a s t a p p l i c a t i o nl a y e r m u l t i c a s t c h a n g e s m u l t i c a s tf u n c t i o nf r o m r o u t e r st o e n d s y s t e m s e n d s y s t e mi st ob e u s e dt or e a l i z ea 1 1c o m m u n i c a t ef u n c t i o n so f m u l t i c a s tg r o u p ，f o re x a m p l e ，t h ec o n s t r u c t i o no fm u l t i c a s tt r e e ，c o p ya n dd i s t r i b u t e o fd a t ap a c k e ta n ds oo n i nt h i sw a y , i td i s p o s e st h eb u n d l eo fd e p e n d i n go nr o n t e r s w h i c ht r a d i t i o n a li pm u l t i c a s tm u s tb en e e d ，c o m p u t i n gr e s o u r c ea r ef u l l ye x c a v a t e d a n da 1 1k i n d so ff u n c t i o n sc a nb ea d d e df l e x i b l y t l l i sp a p e rm a i n l ys t u d i e si r r e c i p r o c a la p p l i c a t i o nl a y e rm u l t i c a s ts y s t e mf a c i n g s i n g l es o u r c es t r e a m i n gm e d i a f i r s t l y , o nt h ea n a l y z eo fa l l k i n d so fa p p l i c a t i o n l a y e rm u l t i c a s tp r o t o c o l sw h i c hh a v eb e e np r o p o s e d ，am e n d e dp r o t o c o li st ob f i n g f o r w a r d ，a l s ow ea n a l y z ei tb ys i m u l a t i o n s e c o n d l y ，a r c h e t y p a ls y s t e ma r ed e s i g n e d b a s e do nt h i sn e wp r o t o c 0 1 i nt 1 1 i ss y s t e m w er e a l i z et h ec o n s t r u c t i o no fm u l t i c a s t g r o u p ，j o i na n dl e a v em u l t i c a s tg r o u pa n dt h ed i s p o s eo f n o d ef a i l u r e a tl a s t ，w et e s t t h ep e r f o r m a n c eo f t h i ss y s t e mi nl a n t h ei d i o g r a p h i ct a s ki n e l u d e ： ( 1 ) ih a v er e a dp l e n t yo fl i t e r a t u r ea b o u ta p p l i c a t i o nl a y e rm u l t i c a s t ，a n a l y z i n gi t s a d v a n c ec o m p a r et ot r a d i t i o n a li pm u l t i c a s t a tt h es a m et i m es t u d i e da p p l i c a t i o n l a y e rm u l t i c a s tp r o t o c o la n di n f r a s t r u c t u r et h a th a v eb e e np r o p o s e d ，c o n c l u d e d a n ds l i mu pt h e i rc h a r a c t e ra n dp r o b l e m ( 2 ) b a s e do nt h i s ，p r o p o s e dam e n d e da 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 lt h a tc a n b eu s e dt os o l v ei r r e c i p r o c a la p p l i c a t i o nl a y e rm u l t i c a s ts y s t e mf a c i n gs i n g l e s o u r c es t r e a m i n gm e d i a - s s a l m p i tm a i n l ys o l v e dh o wp e r - j o i nn o d ef i n db e s t p a r e n tn o d ea td i f f e r e n tb a n d w i d t hc i r c u m a s t e n c e ( 3 ) s i m u l a t i n gt h i sp r o t o c o la n dc o m p a r i n g t op r o p o s e d p r o t o c o l ，e x p l a i n g i t s a d v a n c e ( 4 ) r e a l i z i n ga r c h e t y p a ls y s t e mb a s e do nt h i sp r o t o c o l ，e s p e c i a l l yp r o p o s e dm e s s a g ep r i o r i t y m e t h o dt h a tc a ni n c r e a s et h es y s t e m sr e s p o n s et i m e ( 5 ) t e s t i n g t h e a r c h e t y p a ls y s t e mi nl a n ，m a i n l yi n c l u d em u l t i c a s tg r o u pc o n s t r u c t e d ， m u l t i c a s tg r o u p j o i na n dl e a v ea n dn o d ef a i l u r ed i s p o s a l t e s t i n gm s u l t si n d i c a t ei ta c h i v et h e d e s i g nr e q u e s t k e y w o r d s a p p l i c a t i o nl a y e r m u l t i c a s tm u l t i c a s tt r e e d y n a m i ch a s hr o u t i n g j m f i i 东南大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研e 作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，沦文一书不包禽 其他人已经发表或撰写过的研究成果，也不包含为获得东南大学或j i 它教育机构 的学位或证书而使用过的材料。与我同工作的同志对本研究所做的任何贞献均 已在论文中作了明确的浣明并表示了埘意。 研究生签名：逢撬 日 期：兰鱼 东南大学学位论文使用授权声明 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位 论文的复印件和电子文档，可以采用影印、缩印或其他复制手段保仃沦文。本人 电于义档的内容和纸质论文的内容相致。除在保密期内的保密论文外，允许沦 文被查阅和借阅，。叮以公布( 包括刊登) 论文的全部或部分内容。论迁的公布( 包 括刊髓) 授权东南大学研究生院办理。 研究生签名：釜丝：导师签名：墨墨：釜 期：扫五；、j 东南人学硕上学位论文 第一章研究背景 第一章研究背景 随着i n t e m e t 和计算机技术的发展，i n t e m e t 中的用户和应用表现出了新的特点：具体 表现在，端用户个人计算机计算能力的不断增强和与之对应的应用需求的变化。如今个人 计算机的计算能力、存储能力、接入带宽都有了飞速的提高。举例来说，如今一台个人计 算机的计算能力已超过当年美国登月飞船上所有计算机计算能力的总和。而全球个人计算 机的数量也在飞速增长。截至2 0 0 4 年底，全球互联网用户的数量已达到7 亿。随着计算机 计算能力的不断增强，用户已经不再满足于仅仅在i n t e m e t 上浏览网页，收发邮件等基本 功能。新出现的一类麻用需求包括在i n t e m e t 上进行实时的音视频交流，网络直播和交互 式游戏等。这类应用通常具有一对多，多对多的通信特点，同时要求网络提供服务质量保 证。 传统的i p 组播方案是针对一对多，多对多的通信模型而设计的。然而由于l p 组播方 案的技术性问题( 包拓组管理，组地址分配，安全组播，q o s 等问题) 和i p 组播所带来的市 场问题( 包括路由器换代成本，i s p 间组播管理的成本) ，使得i p 组播方案在提出1 0 年以后 仍然没有在i n t e m e t 上成功的部署起来。因此在i p 组播难以部署，无法满足新出现的应用 需求的情况下，需要寻求新的方案和技术，来满足应用的需求。 1 1 咿组播技术简介川 在i p 网络上，主机之间的通信可采用三种方式：单播、广播和组播。在i p 组播方式中， 不论组成员数晕的多少，数据源只发送一次数据包，并且组播只向那些需要数据包的主机和 网络发送包，在共享链路上，相同的信息只需要一个组播流，从而能够很好的控制流量，减 轻主机和网络的负担，节省了宝贵的网络带宽。图1 1 显示了在单播与组播两种通信模式下， 对于“一点发送、多点接收”应用的实现方式。 ( a ) 单播 ( ”组播 图1 1 单播与组播 1 1 1 i p 组播的服务模型 i p 组播是种开放的服务模型，模型中具有发送者和接收者两个概念。主机通过i g m p 报文与本地路由器交互，成为接收者。发送者只需将报文的目的地址指定为多播组地址就可 实现组播数据发送。i p 组播使_ i j d 类i p 地址作为组地址。 p 组播没有提供相应的技术用来限制用户创建一个组播组，接收组中的数据和向组发送 数据。它不提供任何的访问控制，为了收到一个组播组的数据，用户只需用i g m p 协议与本 地路由器联系。当一个主机变成组播组的接收者之后，它可以收到组播组中的所有数据报文， 而不管数据报文的发送者是谁，是否是恶意的发送者。发送者不需要成为组的接收者，只需 将报文的地址指定成组播组地址，就可以实现向组播组发送报文。发送者不能对自己使用的 组地址进行保留，也不能限制别的用户使用与自己相同的组地址发送数据。 东南大学硕上学位论文第一章研究背景 总之，i p 组播服务模型没有提供完善的组管理功能。i p 组播数据报文底层传输使用u d p 协议，提供尽力而为的服务，没有可靠性的保证。i p 组播传送功能是通过在相应的网络设备 上运行组播路由协议实现的。 1 1 2 口组播的体系结构 图1 2 右侧部分给出了当前i p 组播的体系结构。体系结构自上而下分为四个层次，最低 层为域间路由层，实现跨域的组播路由，采用的协议有m s d 睇i b g m p 。上一层为域内路由层， 实现域内的组播路由，即我们通常说得组播路由协议，目前i p 组播路由协议主要有d v m r p ( 距 离向量组播路由协议) 、m o s p f ( 开放式组播最短路径优先协议) 、c b t ( 有核树) 、p i m - d m ( 协议 独立组播一密集模式) 、p i m - s m ( 协议独立组播一稀疏模式) 等。 麟：! 谴喇溉：鬟饕熬篓臻糍嚣蕊辫夥嚣麓鍪；熏 r t p ，d c p d - 6 凌习r d + a b j e 靠 m a d c 6 l 0p m a 5 甜c pi a 牲a s o p 磊0 ： u d p t 纾 ：。 f 。二t l 例r 髓 嗍一 0 s p f ，刑p r 嚣。 p i m - $ m , i q m - d m | m 。s 旰 e 1 6 静，e t c 。， d v m r p 刑九e j g r p0 s p f ，| y j ? m s d p 。b g m p m b g p ( b g p 4 + ) 嘶p 图1 2 组播的体系结构 第三层是主机一路由器之间的交互协议i g i m p 。最上层是主机服务层，包括了组播地 址分配机制，组播会话目录协议，实时传输协议等。 i 1 3 口组播路由协议分类”1 i p 组播路由协议通常指域内组播路由协议，这些协议可以分为两类：一类是用于稠密 模式的组播路由协议，另一类是_ h j 于稀疏模式的组播路由协议。 稠密模式假定组播组成员密集的分布在网络中，几乎所有的子网都有组成员。稀疏模 式假定组播组成员稀疏的分布在网络中。由于稠密模式假定几乎所有的子网都有组成员， 因此通常允许协议消耗较多的带宽和控制开销，包括路由器状态开销和控制开销，通常采 用广播技术将组播数据推向网络中的所有路由器。稀疏模式则考虑尽可能减少不必要的带 宽消耗和其他控制开销，通常依赖于某种路由选择技术来建立组播树，而不是使用广播技 2 东南人学硕十学位论文第一章研究背景 术。 稠密模式的组播协议通常构造基于源的组擂树，稀疏模式的i p 组播通常构造共享 组播树。基于源的组播树对于组播组中的每一个源，都要构造一颗组播树；共享组播树是 整个组播组共享一颗树，组内的所有源都使用这颗树。 基于源的组播树的i p 组播路由协议有d v m r p ，m o s p f ，p i m d m ；共享组播树的i p 组播路由协议有c b t 。p i m s m 。 d v r m p 协议使用“反向路径广播”( r e v e r s ep a t hb r o a d c a s t i n g ) 机制，结合泛洪与裁剪 技术来构建组播树，反向路径广播保证构造的多播树中不会出现环，并且源到每个接收者 都是最短路径。 c b t 协议只构建一颗树给组中所有成员共享，这颗组播树也就称之为共享树。整个组 播组的组播通信都在这个共享树上进行，而不论发送源有多少或者在什么位置。 1 1 4i p 组播面临的问题 目前i p 组播的服务模型和协议存在着一些问题，使得i p 组播至今没能在i n t e m e t 上得 到广泛部署。一方面，从i s p 的角度来看，目前m 组播不能很好的适应商业应用的需求， 具体有以下几点： ( 1 ) 组播数据包的复制和转发都需要路由器的参与才能完成，这就需要路由器支持组播功 能，如果现有的路由器不支持组播，就需要更换设备，这样就增加了商业的运营成本。 ( 2 ) 一些使用共享树的组播路由协议，如p i m s m 和c b t 的i s p 面临跨域组播管理的问题： 如果r p 和其他组播源点不在同一个域内，难以进行流量控制和拥塞控制；i s p 对其他 域中的r p 没有控制能力；当要进行跨域组播服务时，i s p 之间必须进行协调，因此只 有当应用组播所节省的带宽大大超过它的实施代价时才具有商业价值。 另一方面，i p 组播服务模型还存在一些有待解决的技术问题： ( 1 ) i p 组播要求路由器保存每个组的状态，这样带来了巨大的复杂性，同时也限制了系统 的可扩展性。 ( 2 ) i p 组播服务模犁没有完善的组播组管理机制，如缺乏组创建的管理，没有对接收者和 数据发送者的权限认证机制，发送者可以随意的发送数据而不需要任何的身份验证和 注册工作，主机可以随意的加入和离开组播组，发送者也不能阻止其他发送者使用相 同的组播地址，从而无法避免组地址的冲突和恶意的攻击。 ( 3 ) 组播服务质量问题。i p 组播基于u d p 协议，只是提供一种尽力而为的服务，要想在它 之上实现更高质量的服务，例如拥塞控制和流控制等这些功能，比在p 单播上实现要 困难的多。 ( 4 ) 可扩展性差。l p 组播要求路由器保存每个组播组的状态信息，而这些d 类地址不能很 好的聚合，组播组的数量一旦增加，必然增加路由器的存储和处理开销。 ( 5 ) 缺乏灵活、可扩展的地址分配机制。节点不能有效的发现一个立即可用的组播地址， 而是随机选取一个来使用，这样随着组数目的增加，组播地址冲突的可能性也随之增 大。使用d 类地址作为组播地址，面临着地址空间耗尽的问题。 ( 6 ) 域间组播路由协议对组播技术大规模实施具有重要的作用，它使1 s p 可以将他们的网 络互连，同时隐藏各自的网络拓扑结构。但是，i p 组播还没有成熟有效的域间组播路 由协议。 东南大学硕十学位论文第一章研究背景 1 2 应用层组播 4 , s i 随着各种新兴的具有一对多、多对多通信特点的应用的出现，对组播提出了更高的要 求，而i p 组播却由于种种原因没有实现广泛的部署。同时i n t e m e t 的端用户的计算能力不 断增强，而端用户的计算资源常常处于闲置状态。研究者开始考虑利用i n t e m e t 端用户的 资源在应h j 层实现组播服务。应用层组播的基本思想是屏蔽底层物理网络的拓扑细节， 将组成员节点直接自组织成一个逻辑覆盖网络( o v e r l a yn e t w o r k ) ，并在应用层提供组播路 由协议来构建和维护该组播网络，为数据传输提供高效、可靠的服务。它将转发树构建在 应用层上。两个主机实际的链路是底层的单播i p 路径。具体来讲：组播源准备数据，查询 组播路由表，获得子节点的单播i p 地址，再分别打包、转发。这一过程重复进行，直到所 有节点都收到数据包。查询、打包、接收和转发工作都在网络终端主机的应用层上完成。 通过在主机上安装相应的应_ ；i 层组播软件就可以实现广域网范围内的组播服务。 应用层组播与i p 组播相比优势主要在以下几点： ( 1 ) 应用层组播不需要路由器支持，也不需要改变底层网络，组播服务的部署相对容易。 ( 2 ) 不需要在路由器上维护组播组的状态，可以支持大量的组，解决i p 组播扩展性差的问 题。 ( 3 ) 可以根据网络条件的变化，动态优化组播树的结构，同时可以方便的实现拥塞控制、 服务定制等i p 组播很难完成的工作。 ( 4 ) 应用层组播可以很好的解决组播组地址分配不足的问题。 图1 3 对组播和应用层组播的数据传输方式进行了比较。 ( a ) m 组播 图1 3i p 组播与应用层组播比较 ( b ) 应用层组播 图中a 、b 、c 、d 为主机，r 1 ，r 2 为路由器，带箭头的线代表数据包的发送方向。图1 3 ( a ) 为i p 组播，a 为发送者，数据包从a i j r l ，再由r 1 转发给b 和r 2 ，r 2 再将收到的数据包转发给c 和d 。图1 3 ( b ) 为戍用层组播，a 发送两份相同的数据包分别给b 和c ，再由c 复制一份给d 。 从图1 3 中可以看出应用层组播存在的一些固有问题，比如传输的效率问题。应用层组 播的效率比i p 组播的效率要低，因为不可避免的会有组播路径重复的经过同一条底层链路， 也就必然带来冗余的流量，例如在图1 3 ( b ) r 2 _ c 这条链路上有两个相同的数据包重复经 过同一条底层链路，而图1 3 ( a ) 的i p 组播则只有一次。另外，两个端系统之间的通信，可能 要通过中间其他端系统的转发来实现，这也不可避免的造成两个通信节点之间延时的增加。 1 2 1 应用层组播的研究现状 应用层组播的研究现在已经是下一代互连网络研究中的热点话题之一，许多研究机构都 提出了自己的应用层组播协议。 2 0 0 0 年，y c h u 等人提出基于n a r a d a 协议的e s m ( e n ds y s t e mm u l t i c a s t ) 。j a n n o a i 提出 4 东南大学硕士学位论文 第一章研究背景 o v e r c a s t ，它通过尽量将新加入的成员放到远离根的位置上，最大化发送者到接收者之问 链路的带宽，提供了一种可靠的，可扩展的组播系统，适合于对带宽要求较高的应用。y a t i n d i l i p c h a w a t h e 在他的博士论文中提出s c a t t e r c a s t 系统，提出了基于服务器和客户端两层结 构的应用层组播系统。 2 0 0 2 年，由d i m i t r i o s 等人提出一种集中式应用层组播架构a l m l ( a p p l i c a t i o n l e v c l m u l t i c a s ti n f r a s t r u c t u r e ) ，它适用于较小规模的组播组，建立共享组播树，新成员的加 入只获得部分组成员的信息。h b m 由r o c a 等人于同年提出，这也是一种集中控制的协议， 但是加入者必须知道全部组成员的信息。s q z h a n g 发表基于p e e r - t o p e e r 网络的应用层组 播系统b a y e u x ，它给每个p 2 p 节点分配一个唯一的节点号，从节点号的最后一位向前，按 顺序一位一位的匹配来进行报文路由。l m a t h y 提出t b c p ，加入者计算与每个可能父母节 点之间的配置方案，取最优的方案加入，同时考虑到尽鼍减少汇聚时间。s r a t n a s a m y 提出 了基于p 2 p 的应用层组播系统c a n 。它使用哈希函数，将组播组g 的地址映射剑笛卡儿 坐标空间，使每个组播组都对应一个小的c a n 网络，在小c a n 网络上通过泛洪实现组播 转发。 2 0 0 3 年，h m t p 被提出。s u m a na a n e o 发表了基于n i c e 的应用层组播的论文。 m c a s t r o 发表了s c r i b e ，它是建立在p 2 p 网络p a s t r y 之上的一个应用层组播系统，它通过 从第一位往后对节点号和组号按位匹配来确定组播树的路径，具有较好的可扩展性；另外， 它借助底层p 2 p 网络p a s t r y 可以进行动态的自组织来适应网络条件的变化。 2 0 0 4 年，m h e f e e d a 提出了p r o m i s e ，这也是建立在p a s t r y 网络之上的应用层组播系 统，它的实现思想是：一个接收者可以从多个发送着处得到需要的数据，它不需要构建组 播树，当节点需要数据时，由底层p 2 p 系统查找到一系列满足要求的发送者，接收者再从 中挑选一些较好的发送者，他们并行的向接收者发送组播数据。d t r a n 提出了基于p 2 p 的 层次型的应用层组播系统z i g z a g 。 在刚刚过去的一年中，a h m e ds o b e i h 提出一种基于环而非组播树的应用层协议v r i n g ， 与n i c e 相比，它减少了环的控制代价，与h m t p 相比，它能更好的探测出节点的失效， 并能更有效的进行修复，具有更强的鲁捧性。r o i em e l a m e a 也提出了适应于动态环境下的 应_ j 层组播系统a r a n e o l a 。 1 3 论文内容及相关工作 ( 1 ) 深入分析了各种已经提出的应用层组播系统的体系结构，确立了一种以p 2 p 网络 - - f r e e p a s t r y 为平台的，面向单源流媒体组播的麻用层组播系统。 ( 2 ) 分析了现有的各种应用层的组播协议，结合本课题的应用背景对其作出了相应的 改进，并且进行了仿真研究证实改进协议的有效性。 ( 3 ) 实现了基于改进协议的应用层组播原型系统。 ( 4 ) 对原犁系统的各个功能进行了相应的测试，如动态加入、成员退出、媒体定制、 数据转发及系统的鲁棒性等。 t 4 论文结构 本论文共分为六大部分，每部分的具体内容如下： 第一章为研究背景介绍，简单介绍了i p 组播的基本体系结构并且分析了它所面临的问 题。同时论述了应用层组播相对于i p 组播而言所具有的优势及缺点和近几年的研究情况。 最后阐述了论文的内容及相关工作。 东南大学硕士学位论文第一章研究背景 第二章对现有的应j j 层组播协议进行了分类讨论，并且详细分析了其中的几种。 第三章在第二章讨论的基础上，针对本课题的应用背景对原有的协议进行了改进，对 改进后的算法进行了仿真研究。 第四章详细讨论了应用层组播原型系统各个部分的实现。 第五章对原犁系统中所设计的各项功能进行测试 第六章对整篇论文作出总结，并对将来的工作作出展望。 6 东南大学硕士学位论文第二章应用层组播协议分析 第二章应用层组播协议分析 应用层组播将组播功能实现于终端主机中，组成员的动态性对组播有很大影响。应用层 组播协议不仅要提供有效的数据组播分发树，还要针对节点的动态性提供可靠的组管理算法 协议设计强调在动态网络环境下维持网络的稳定性。应用层组播路由协议设计面临的主要问 题是，如何在广域环境下，针对节点的动态性，在节点上建立必要的状态信息，并根据这些 信息构建优化的组播路由协议。图2 1 根据协议构造算法的差异对现有的应用层组播路由协 议的构建方法进行了分类。 2 1 集中式算法 n i c e ，z i g z a g b a y e u x ，s c d b e 图2 1 应用层组播协议分类 集中式算法在协议中引入全局会话控制点，集中管理所有组成员的状态变化( 加入离 开) 及成员之间的位置关系信息，负责组播树的创建和维护，并定期计算以优化其拓扑结构。 集中式算法具有较好的可靠性，而且能减少控制负载，易于维护组播树的一致性和效率。 但由于控制点要维护全局信息，受单点失败的限制，因而缺乏可伸缩性，比较适合小规模 稀疏型组通信使用。根据协议优化所依赖的信息不同，集中式算法又可分为基于全局信息 和基于局部信息两种组播树优化策略。a l m i 和h b m 都属于集中式应用层组播协议。 a l m i ”的每个会话包括一个会话控制器和若干会话成员。会话控制器控制覆盖网络的 全局信息，具体处理组成员的注册请求和维护组播树。为了保证协议效率，会话控制器根 据所有组成员反馈的最新链路信息定期重新计算并生成最小生成树。为降低控制负载， a l m l 协议采取基于局部信息的优化算法，对每个节点所监视的邻居节点数进行限制。因 此，a l m l 构建的组播树是次优的。 h b m 7j 将组成员分成核心成员和非核心成员两类，核心成员形成数据分发树的主干节 点，非核心成员只能作为叶子节点。组搔中的所有活动都由一个集中汇聚点( r p ) 控制，汇 聚点维护会话中所有成员的分类信息及相互距离。覆盖拓扑的优化完全依赖于r p 中的全 局信息，较a l m i 而言，较易得到最优化的网络拓扑。 7 东南大学硕卜学位论文 第二章应用层组播协议分析 2 2 分布式算法 分布式算法中没有集中的会话控制点。组成员的管理和数据传输网络的控制通过各节 点维护的局部信息协作完成。分布式算法可避免集中式算法受单点约束的限制，有更好的 可伸缩性。然而，在动态分布式环境中，频繁的加入离开操作、节点及网络条件的异常变 化会使组播树发生频繁的变化。因此，基于分布式算法的组播协议设计更为复杂和困难， 通常需要协调和衡量协议设计所引起的每个节点维护状态信息量、控制负载、通信代价等 开销。为适应系统的动态性，保证组播传输的有效性，分布式算法常将组成员组织成控制 拓扑和数据拓扑两种具有不同功能目标，但均覆盖所有成员的网络结构。控制拓扑一般是 基于局部信息的连通图，负责监视节点的变化、维护网络的连通性。数据拓扑是一个开环 树，主要为数据的传输提供高效的组播路径。现有协议多数把数据拓扑看作是控制拓扑的 一个子集。根据控制拓扑和数据拓扑建立顺序的不同，分布式算法又可分成网格优先 ( m e s h - f i r s t ) 嗍、树优先( t r e e - f t ) ”l 、隐式( i m p l i c i t ) ”1 建立等三种不同方法。 2 2 1 网格优先法 首先将组成员自组织成一个连通的m e s h 网，该m e s h 中任意两个节点之间存在多条路 径，每个节点都要维护全部或部分其他成员信息，然后通过路由算法在m e s h 上建立以指 定源为树根、涵盖所有组播成员的组播树。网格优先法通常显式生成m e s h 拓扑，而组播 树的建立依赖于具体的路由算法和m e s h 拓扑，并且m e s h 的选择直接影响着组播树的性能。 网格优先方法可为不同的发送源分别建立优化的组播树。具有较好的数据传输效率。该方 法的一个主要缺点是，每个节点都要花很大的代价来维护和优化组播树。图2 2 给出了基 于网格优先方法的覆盖网络拓扑结构示意图。 稠格镜毙 一整麓蓐麓 囤l 2 b 壤凌翌结构 ，簇褥露径 图2 2 网格优先方法的拓扑结构 最早提出的n a r a d a l 9 1 应用层组播协议就采用了基于网格优先的协议构造方法，新成员 首先通过r p 获取部分成员，并试图作为这些成员的邻居节点加入m e s h 。组成员定期与 m e s h 中的邻居节点交换信息，及时检测失败节点，维护m e s h 的连通性。n a r a d a 采_ i j 逆向 路径转发路由算法在m e s h 上为各个发送源分别建立数据分发树。为提高数据传输质量， n a r a d a 采用分布式启发算法，由每个节点周期性探测与其他成员的相互位置关系，并根据 8 东南大学硕士学位论文 第二章应用层组播协议分析 探测结果决定是否添加新链路，从而优化m e s h 拓扑。n a r a d a 中每个成员所需维护的状态 信息为o ( i , o ，缺乏可伸缩性。适应于中小规模组播应用。 2 2 2 树优先算法 基于树优先法的应用层组播协议首先根据各节点的局部信息创建一个共享树，随后各 组成员从组播树中寻找非邻接节点，根据一定的算法建立并维护到这些节点的控制链路， 从而使控制拓扑得到加强。与网格优先方法不同，树优先法中的控制网络与组播树分离， 组播树不一定是m e s h 的子集。该方法的优点是赋予用户对组播树更多的直接控制能力， 可以控制节点的最大出度，选择合适的父节点。树优先法的主要缺点是对组播树的回路检 测和避免处理比较复杂，而且对组播树的优化也比较困难。y o i d t ”j 、h m t p ! i l j 都采用了树 优先方法。 2 2 3 隐式法 隐式法中控制拓扑和数据拓扑的定义没有严格的先后顺序，成员之间也不需要额外交 互。协议的控制拓扑一般一般要求满足一定的属性要求，数据传输路径通常要求是建立在 报文转发规则之上、能平衡控制拓扑属性的开环组播路径。根据控制拓扑建立方法的不同， 隐式法又可分为层次型和p 2 p 路由等几种类型。层次型方式。协议将组成员分成若干层， 并由下向上为每个层顺序编号r 最底层编号为l 0 ) ，每层都包含若干个簇，所有成员都一定 属于l 0 。图2 2 ( b ) 描述了层次犁网络结构示意图。层次型拓扑构建通常从l o 层开始按如 下方法递归定义：协议依一定规则将l 层的组成员划分成若干个具有一定大小限制的簇， 并选取簇的图论中心节点作为簇头，l i 层的所有簇头形成l i + 1 。然后根据该层次结构定 义和控制数据传输的覆盖拓扑。新成员加入系统时首先从最高层向下顺序在每个层探测距 自己最近的成员，并加入l 0 相应簇。 n i c e 、z i g z a g 1 2 1 的层次型拓扑构建思想基本相同，都直接利用该拓扑做组管理机构， 但两者的数据传输机制不同。n i c e 中每个成员都可直接在层次拓扑上建立以自己为根节 点的组播树，状态信息的交换只在簇内进行。z i g z a g 的每个簇内还包括一个副簇头，簇 头用于监视簇内成员关系，副簇头负责数据分发。此外，z l g z a g 为规范组播树的创建定 义了c r u l e s 。与n i c e 相比，z i g z a g 最大优点是能将节点的状态信息量和失效恢复负载 限制在常量水平。 2 2 4p 2 p 路由方式 b a y e u x ”j 、s c r i b e 1 4 1 都是建立在p 2 p 路由协议之上的应用层组播协议。b a y e u x 以p 2 p 路由协议t a p e s t r y 为基础，采用显式途径为每个发送源分别建立和维护组播树。t a p e s t r y 中，每个节点都有一个独立于位置的语义属性，是由吲定长度的位序列组成的标识符。每 个节点都维护一个多级邻接表，为消息传递提供路由服务。b a y e u x 有良好的可扩展性和容 错能力，协议还通过复制根节点和群簇技术为实现负载均衡、提高带宽利用率提供支持。 为加入组播，新成员首先发送“j o i n ”消息通过t a p e s t r y 路由到发送源，发送源仍采用 t a p e s t r y 路由“t r e e ”给该节点，并在反馈路径的每个节点记录请求者身份，更新转发表信 息。请求离开的处理方式与此类似。b a y e u x 中的每个成员的加入和离开都要经过根节点， 因此受到根节点单点失效的限制。 9 东南大学硕十学位论文第二章府用层组播协议分析 2 3 典型应用层组播系统分析 2 3 1 a l m l ( a p p l i c a t i o nl e v e lm u l t i c a s ti n f r a s t r u c t u r e ) 1 6 1 a ) a l m i 的体系结构 a l m i 是一个使用集中式控制的应用层组播系统，它提出了集中式应用层组播系统的 框架，具体结构如下： 。 a l m i 的一个会话( s e s s i o n ) 包括一个会话控制者( s e s s i o nc o n t r o l l e r ) 汞l 若干会话成员 ( s e s s i o nm e m b e 0 。控制者处在成员都比较容易到达的地方。 会话控制者负责成员的加入和维护组播树，具体来说有两个功能：一是成员加入、离 开或失效时，确保组播树不断裂；二是通过周期性计算各成员的更新信息，保证组播 树的效率。控制者只作控制之用，而不负责数据在各个成员之间的传输。 每个成员监视它与其他部分成员之间的单播路径，向控制者提供所需的各种信息。 。 为了在成员发生变化后，各成员之间仍能维护统一的组播树结构，控制者周期性的发 布近期内几个版本的组播树结构，如果成员接收剑更新信息，则重新向控制者发出请 求获取新版本的组播树结构。 在a l m i 上可以比较方便的布置附加的服务内容，如端到端的可靠性、q o s 等。 b ) 加入组播树的过程 要加入的成员向控制者发送i o i n 报文。 每个成员受到度约束，所谓度约束就是规定父节点所能接收的孩子节点的数目。并检 测与所有它的邻居节点之间的延时，在满足度约束的条件下，选抒延时最小的路径， 使加入者连到最小生成树中。度的具体数值可根据网络的实际情况定义。 。 如果该成员可以被接受，控制者发送成员i d 和父节点的地址给加入者，加入者发送 g r a f t 报文给父节点。 c ) 节点失效的处理 由于控制者只有一个，所以存在单点失效问题。为此，a l m i 采用多个备份控制者， 在原控制者失效时代替它工作。另外，即使控制者失效，只要没有发生重大错误和成 员变更，不受影响的那一部分组播树仍可正常传输组播数据。 对于组播树上其他节点的失效处理：如果组播树上的孩子节点发现父节点失效，向控 制者发送r e j o i n 报文发起重新加入；如果父节点发现孩子节点失效，直接丢弃孩子。 m 端到端数据的可靠性 。 采用t c p 连接可以减少网络拥塞和网