（计算机应用技术专业论文）应用层组播重构技术研究与应用.pdf

摘要 近年来，随着i n t e m e t 不断发展，组播技术越来越受到重视。相 比单播，组播实现了一对多的通信方式，并且可以节省带宽、减轻网 络负担和提高数据传输率。与传统的口组播不同，应用层组播在终 端主机上而不是路由器进行数据的转发，它提供了种代价更低、更 容易部署的多点通信，这也解决了互p 组播由于技术和市场的原因而 没有被推广开来的问题。但是由于终端主机是不稳定的，它可以自由 的离开组播树或随时可能失效，当组播树中的非叶子节点离开组播 树，该节点的所有下游节点都将受到影响，因此，应用层组播需要考 虑节点失效或离开组播树后如何快速重构组播树的问题。另一个被忽 视但同样重要的因素是主机的容量限制，如果不考虑主机的容量限 制，就有可能使某个节点连接过多的孩子节点，从而导致整个组播系 统性能的急剧下降。 为了实现组播树的重构，本文首先提出了一个具有度约束特性的 应用层组播树构建算法。它采用节点的可用网络带宽来描述节点容量 ( 度数) ，该算法主要是为节点找到一颗具有最小直径的生成树。然后， 在此最小直径生成树的基础上，提出了一种度约束的应用层组播树预 先式重构方法。其核心思想是：组播树的每个非叶子节点在它离开或 失效之前提前为它的孩子节点寻找各自的备用父节点，一旦节点离开 或失效，它的孩子节点立即连接它们各自的备用父节点。 本文使用c + + 语言，在v c + + 6 0 的平台上，实现了一个基于该 构建和重构组播树算法的原型系统。该系统具有构建组播树覆盖网、 检测邻接节点失效、节点失效后重构组播树、以组播的形式传输文件 等基本功能，我们在局域网中对该系统进行了反复测试，证实了系统 的性能。 关键词应用层组播，度约束，最小直径树，重构，备用父节点 a bs t r a c t i nr e c e n ty e a r s ，w i t ht h ed e v e l o p m e n to ft h ei n t e r n e t ，m u l t i c a s t t e c h n o l o g y i s r e c e i v i n gi n c r e a s i n ga t t e n t i o n c o m p a r e dw i t hu n i c a s t , m u l t i c a s t ，w h i c hi sac o m m u n i c a t i o nw a yo fo n ep o i n tt om a n yp o i n t s ， c a ns a v et h eb a n d w i d t h 1 i g h t e nt h en e t w o r kb u r d e na n di m p r o v et h ed a t a t r a n s m i s s i o nr a t e u n l i k et r a d i t i o n a li pm u l t i c a s t ，a p p l i c a t i o n l a y e r m u l t i c a s ti m p l e m e n t st h em u l t i c a s tf u n c t i o n a l i t ya te n dh o s t sr a t h e rt h a n r o u t e r s ，p r o v i d e s a n i n e x p e n s i v e ，d e p l o y a b l em e t h o do fp r o v i d i n g o n e t o m a n yc o m m u n i c a t i o na n df i n d sas o l u t i o nt ot h ep r o b l e mo f t r a d i t i o n a li pm u l t i c a s tw h i c hh a s h tb e e np o p u l a r i z e df o rt h er e a s o no f t h em a r k e ta n dt h et e c h n o l o g y h o w e v e r , e n dh o s t sa r en o ts t a b l ea n dm a y l c a v et h em u l t i c a s tt r e eo rf a i la ta n yt i m e m e nan o n 1 e a fe n dh o s t l e a v e st h em u l t i c a s tt r e e a l lo ft h i sn o d e sd o w n l o a dn o d e sa r ea f f e c t e d s o ，i ti sn e c e s s a r yt oc o n s i d e rh o wt or e c o n s t r u c tt h em u l t i c a s tt r e ea f t e r t h en o d ef a i l so rl e a v et h em u l t i c a s tt r e ei na p p l i c a t i o nl a y e rm u l t i c a s t a n o t h e rn e g l e c t e db u te q u a l l yi m p o r t a n tf a c t o ri st h eh o s to fc a p a c i t y c o n s t r a i n t s i fw ed on o tc o n s i d e rt h eh e s t sc a p a c i t yc o n s t r a i n t s i ti s p o s s i b l et om a k ean o d et oc o n n e c tt o om a n yc h i l d r e nn o d e s ，t h i sw i l l l e a dt ot h er e s u l tt h a tt h ep e r f o r m a n c eo ft h em u l t i c a s tt r e ea saw h o l ew i l l g e tp o o rd r a m a t i c a l l y i no r d e rt or e c o n s t r u c tt h em u l t i c a s tt r e e ，an e wa p p l i c a t i o nl a y e r m u l t i c a s ta l g o r i t h mw i t hd e g r e e c o n s t r a i n e df u n c t i o ni sp r o p o s e d u s i n g t h ea v a i l a b l eb a n d w i d t h af u n c t i o ni sd e f i n e dt oc o m p u t et h ec o n n e c t i o n c a p a c i t yo ft h en o d e n i sa p p l i c a t i o nl a y e rm u l t i c a s ta l g o r i t h mt r i e st o f i n das p a n n i n gt r e ef o ran u m b e ro fn o d e sw i t has h o r t e s tt r e ed i a m e t e r t h e n ，ap r o a c t i v ea p p r o a c ht or e c o n s t r u c t i n gd e g r e e c o n s t r a i n e d a p p l i c a t i o nl a y e rm u l t i c a s tt r e eb a s e do nt h em i n i m u md i a m e t e rt r e ei s p r o p o s e d i t sc o r et h o u g h ti st h a te a c hn o n l e a fn o d ei nt h em u l t i c a s tt r e e c o m p u t e sp r e v i o u s l yap a r e n t - t o b en o d ef o re a c ho fi t sc h i l d r e nn o d e b e f o r ei tf a i l so rl e a v e s ，o n c et h ed e p a r t u r eo ft h en o d er e a l l yh a p p e n ，a l l o fi t sc h i l d r e nc a nc o n t a c tt h e i rr e s p e c t i v ep a r e n t - t o b en o d ei m m e d i a t e l y w i t hc + + l d t ，w ea l s od e v e l o pam u l t i c a s tc o m m u n i c a t i o np r o t o t y p e u s i n g t h e p r o p o s e da l g o r i t h m t h i sc o m m u n i c a t i o np r o t o t y p e c a n c o n s t r u c tm u l t i c a s tt r e e ，d e t e c tt h ef a i l u r eo ft h en e i g h b o r s ，r e c o n s t r u c t t h em u l t i c a s tt r e ea f t e rs o m en o d e sf a i lo rl e a v ea n dt r a n s m i tf i l eb y m u l t i c a s t w ed or e p e a t e dt e s t si nt h el o c a la r e an e t w o r ka n dh a v et e s t e d i t sp e r f o r m a n c e k e yw o r d sa p p l i c a t i o nl a y e rm u l t i c a s t ，d e g r e e c o n s t r a i n e d ，m i n i m u m d i a m e t e rs p a n n i n gt r e e ，r e c o n s t r u c t ，p a r e n t - t o - b en o d e i l l 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢的 地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包 含为获得中南大学或其他单位的学位或证书而使用过的材料。与我共 同工作的同志对本研究所作的贡献均已在论文中作了明确的说明。 作者签名： 日期：丝卫年月上日 学位论文版权使用授权书 本人了解中南大学有关保留、使用学位论文的规定，即：学校有 权保留学位论文并根据国家或湖南省有关部门规定送交学位论文，允 许学位论文被查阅和借阅；学校可以公布学位论文的全部或部分内 容，可以采用复印、缩印或其它手段保存学位论文。同时授权中国科 学技术信息研究所将本学位论文收录到中国学位论文全文数据库， 并通过网络向社会公众提供信息服务。 作者躲避聊签斡嗍俎年如上日 硕士学位论文 第一章绪论 1 1 应用层组播概述 1 1 1 组播技术的发展 第一章绪论 随着互联网的迅速发展，网络用户也随之成倍增长，各种多媒体业务也大量 涌现，如视频会议，远程教学，在线游戏，在线直播等，而这些应用的出现也意 味着用户对带宽的要求将越来越高。传统的单播( u n i c a s t ) 技术存在着严重的带宽 浪费和低效率问题，已经不能满足用户的需求，因此对组通讯模式的需求不断地 增加，针对这种需求，产生了一种更有效的传输方式一组播( m u l t i c a s t ) 。组播是 一种通过单一的发送操作将数据从一点发送到多点的通信方式，适用于在时间上 具有集中性、而在空间上具有分布性的应用。 s d e e r i n g 在八十年代末率先提出域间组播模型1 1 ，这标志了m 组播的出现。 在s d e e r i n g 后，组播骨干网( m b o n e ) f 2 】的诞生标志着组播技术在i n t e m e t 上第一 次广泛使用。口组播技术在网络层来实现组播的功能，它是对网络层协议的扩 展，数据包在路由器上进行复制，并且通过路由器分发到终端用户。i p 组播扩 展了单播( u n i c a s t ) 的“尽力传输模式，可以有效的支持互联网上的一对多和多 对多的通讯方式。由于口组播比单播更有效，使得很多研究人员对其进行了大 量的研究，出现了很多经典的i p 组播协议如：距离矢量组播路由协议 d v m r p ( d i s t a n e ev e c t o rm u l t i c a s tr o u t i n gp r o t o c 0 1 ) ，核心树c b t ( c o r eb a s e d t r e e s ) ，协议独立组播p i m d m ( p r o t o c o li n d e p e n d e n tm u l t i c a s td e n s em o d e ) 和扩展 最短路径优先组播协议m o s p f ( m u l t i c a s t e x t e n s i o n st oo s p f ) 等1 3 j 。 虽然对口组播的研究一直都在进行，但是由于口组播本身存在着很多的缺 陷，使得一直没有得到广泛的推广【5 训，主要原因是：i p 组播需要路由器为每 一个组播组保留状态信息，这不仅破坏了网络设计的初始无状态原则，而且导致 网络的规模伸缩性集聚下降；由于组播地址不容易集成，增加了路由器的系统 开销和复杂性；i p 组播是一种尽力而为( b e s te f f o r t ) 的服务，当要提供高层特性 如可靠传输、涌塞控制、流量控制的时候，就会比单播困难，以至于因特网服务 提供商( i s p s ) 不愿意提供口组播功能；最后，i p 组播需要对现有网络底层做出改 变，这减慢了m 组播部署的步伐。 为了解决m 组播的问题，研究人员开始寻找新的解决办法。一些学者认为： 组播功能应该尽量推向高层来实现，除非底层实现可以抵消底层实现带来的额外 硕上学位论文第一章绪论 复杂度。于是h c h u f 4 1 等人提出应用层组播( a p p l i c a t i o nl a y e rm u l t i c a s t ) 的概念。 应用层组播的基本思想是屏蔽底层物理网络的细节，将组成员节点自组织成一个 逻辑覆盖网络( o v e r l a yn e t w o r k ) ，并在应用层提供组播路由协议来构建和维护网 络，为数据传输提供高效、可靠服务。广义上来讲，应用层组播的数据实际上都 是以单播方式传输的，不再需要网络层的组播支持，所以应用层组播可以快速推 广。 相比i p 组播，应用层组播把组播的功能从网络层转移到了应用层，由客户 端实现数据的复制和转发功能。由于不需要路由器的支持和不需要对网络的底层 做出改变，因而应用层组播相对于i p 组播更容易部署。而正是由于应用层组播 不需要全球范围的网络支持，很多研究者认为应用层组播在实现全球范围内的组 播功能i 维持i n t e m e t 的灵活性和多样性等方面将有更大的发展空间。目前应用 层组播研究已成为研究热点之一。 1 1 2 应用层组播技术 应用层组播将组播的功能完全集成在端系统上，由应用层软件来实现数据的 复制和转发，终端主机也负责对组播成员的管理。终端主机在逻辑上形成一个逻 辑覆盖网( o v e r l a yn e t w o r k ) 【5 2 ，5 8 】，而应用层组播协议的主要目标就是构建并维护 一个有效的传输数据拓扑结构。覆盖网是一个位于一个或者多个网络拓扑上的虚 拟网络，覆盖网通过使用物理网中的单播来实现主机之间的通信，它的优点在 于它在架构不需要改变，不需要改变底层网络结构，因而可以加快网络的部署。 应用层网络也叫覆盖网络，应用层网络是一个通过主机物理网络完全连接的虚拟 网络，如因特网就是应用层网络，图1 1 为一个实际的网络结构与覆盖网拓扑结 构。一般来说，主机之间的权值将标记为通信延时。覆盖网链路从本质上来说是 一个物理链路。图1 1 ( b ) 中，在( a ) 代表了物理链路 a ，h 1 ，r 1 ，h 2 ，c 而e 在( a ) 代表了 b ，h 1 ，r 1 ，r 2 ，h 3 ，o ，它们有一部分是重叠的，但从表面上看 来它们是没有关联的。 2 硕士学位论文 第一章绪论 ( a ) 覆盖网的物理结构 ( b ) 覆盖网拓扑结构 图1 - 1 物理结构与其覆盖网拓扑结构 在覆盖网基础上实现组播功能，就是把组播的功能在应用层实现。端系统实 现组播的思想是将组播作为一种叠加的服务，实现为应用层的服务。目前主要有 两种结构体系实现应用层组播，一种是基于p e e r - t o p e e r 体系结构，在p 2 p 网( p 2 p o v e r l a y ) 基础上，节点通过特定算法、协议构建组播树。这种建树的方式比较灵 活，但如果设计不好，将导致网络涌塞和网络利用率低：并且端系统的处理能力 不强的话，将造成延时较大。基于p 2 p 结构的组播协议强调如何在动态网络环 境下提供有效的组播传输机制，保证协议的可靠性，提高协议的自适应性。另一 种是基于代理( b a s e d p r o x y ) 的体系结构，它通过部署若干服务节点构成一个传输 基础结构，其特点代理节点相对固定，组播树结构稳定，针对具体的应用能够提 供q o s 保证。缺点是提供的组播缺乏伸缩性，可能在代理节点会出现瓶颈，而 且一般需要i s p 提供的支持。 硕十学位论文第一章绪论 1 1 3 组播技术的数据传输方式 从数据传输来分析口组播( i vm 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 ，a l m ) ，这两种组播技术有不同的实现方式。i p 组播传输数据是：在 主干网上尽量减少数据的传输，数据达到路由器后，由路由器来实现数据的复制 和转发。这种方式减少了主干网的数据量，但是增加了路由器的负担。应用层组 播的数据是在端系统( e n ds y s t e m ) 复制并转发的，同时端系统也负责组播成员的 管理。端系统在逻辑上组成了一个覆盖网络拓扑，而应用层组播协议的目标就是 构建并维护一个有效的拓扑。 ( a ) 网络拓扑( b ) 单播 ( c ) i p 组播( d ) 应用层组播 图1 - 2 三种传输方式的比较 图l 一2 比较了单播，i p 组播和应用层组播中数据的传输方式的差别，( a ) 是一 个网络的物理拓扑结构，其中节点1 ，2 ，3 ，4 表示了四台主机，并且l 是数据 发送源，2 ，3 ，4 是数据接收端；链路上的数字表示链路延时，r l 和i 毪表示了 路由器。图1 2 ( b ) ( c ) ( d ) 中的黑箭头表示数据的传输方向。通过图1 2 ( b ) 的单播 模式数据传输可以看到，发送者要为每个数据接收者建立一条传输路径，因而在 节点1 到路由器r 1 上要重复传输3 次，这样造成了源端点附近的链路冗余传输 4 硕士学位论文第一章绪论 比较大，以单播模式传输的缺点是：造成链路资源浪费，容易造成链路拥塞、形 成服务瓶颈。图1 2 ( c ) 是一个口组播的数据传输模型，m 组播由路由器负责组 成员的管理和组播树的创建和维护，数据在传输中沿着组播树指向的方向传到接 收端。从图中可以看到，数据在任何链路上都只传输一次，数据在路由器上进行 了复制并且负责转发给接收端，因此i p 组播可以有效地避免冗余数据传输，节 省网络带宽。图1 2 ( d ) 是一个应用层组播的数据传输模型，应用层组播将组播的 功能转移到终端主机，传输网络的构建完全独立于物理链路，数据流向及报文复 制由终端主机控制，具体报文传输依靠于单播传输机制，与单播方式相比，源主 机附近的冗余情况有所缓解；与口组播方式相比，应用层组播对带宽的利用率 不如口组播。 1 1 4 应用层组播的优点和缺点 应用层组播有其自身固有的一些优点和缺点。与单播相比，应用层组播虽然 无法避免数据冗余，但可以大大减少数据传输冗余。而口组播虽然可以避免数 据冗余，但由于自身的一些缺陷，无法在全球范围内部署。应用层组播采用了覆 盖网络，不需要路由器的支持，避免了m 组播推广中遇到的问题。下面将通过 与口组播的比较，来分析应用层组播优点和缺点。 应用层组播主要存在以下优点： ( 1 ) 应用层组播比口组播容易推广。应用层组播由于不需要路由器的支持，能 很快的推广和应用，因而可以避免组播在推广中遇到的问题。p 组播由 于需要路由器的支持，而服务提供商( i s p ) f l t 于各种原因不愿意对现有的路 由器做出改变，因而阻碍了i p 组播的推广。应用层组播把组播的功能提升 到应用层，底层只需要提供单播功能，因而应用层组播可以在不改变现有底 层网络架构的情况下进行推广。 ( 2 ) 接入控制比口组播容易实现。由于单播技术在接入控制上已经比较成熟， 而应用层组播是通过终端主机之间单播来实现的，屏蔽了底层网络的实现细 节，所以差错控制、流量控制、拥塞控制更容易实现。 ( 3 ) 比口组播有更好的扩展性。在i p 组播，每个组播组需要一个d 类地址，这 个地址在空间上是平面的，并不包含拓扑意义和地理含意。而且m 组播需 要路由器为每个组保存信息，因此限制了组的规模，使得组的增长不能超过 路由器可以承受的范围，因而不利于规模的扩展。而在应用层组播，组成员 的维护放在终端系统中，每个终端系统只需要维护自己相关的一部节点信 息，因此应用层组播具有更好的扩展性。 应用层组播的缺点： 硕十学位论文第一章绪论 ( 1 ) 应用层组播的可靠行比口组播要差。i p 组播中负责数据的复制和转发是路由 器，而应用层组播负责数据的复制和转发是终端主机。路由器在网络中相对 稳定，而终端主机可能随时离开。 ( 2 ) 链路的数据冗余比口组播要多。应用层组播在数据传输上由于采用单播机 制，因而会在链路上造成数据冗余传输。因此，在链路的利用率上应用层组 播不及i p 组播。 ( 3 ) 数据传输延时( d e l a y ) i ：li p 组播大。数据传输延时比较大由三个原因造成： i p 组播数据的复制和转发在路由器中完成，应用层组播数据的复制和转发 在终端主机上完成，显然，路由器的处理能力要比终端主机强；由于数据 在链路上冗余传输，冗余传输将造成增加了传输的路径的长度，因而造成额 外的延时；由于路由器是一个三层网络结构，而终端主机是一个七层网络 结构，因而造成额外的层延时。如图1 3 ，( a ) 是i p 组播，( b ) 是应用层组播， 从图中可以看到，在转发节点这个环节上，应用层组播将增加在传输层，会 话层，表示层和应用层上的传输时间，而在发送端和接收端传输时间则相同， 因而总的看来，应用层组播将产生额外的层延时。 发送端 转发者( 路由器) 接收端 发送端 转发者( 终端主机) 接收端 ( a ) i p 组播( b ) 应用层组播 图1 - 3 相同情况下，数据传输的额外层延时比较 ( 4 ) 应用层组播中存在着主机容量( d e g r e e c o n s t r a i n e d ) 的限制。造成这个问题的 主要原因是由于转发节点是终端主机和存在着本地网的容量限制。首先，路 由器一般连接在大容量的骨干网，而终端主机连接在本地网，本地网的带宽 远远小于骨干网。另外，终端主机由于受自身的可用内存大小，c p u 处理速 度等影响，限制了可以连接的孩子节点数目。在保证某些性能的前提下，可 6 硕士学位论文 第一章绪论 以加入组播组的主机数目将减少，因而应用层组播中在扩展的时候必须考虑 每个主机的容量限制。 1 2 应用层组播的研究进展 应用层组播将组播的功能放在终端主机中，覆盖网络是构成应用层组播的必 须部分1 6 。覆盖网需要跟踪物理网络的拓扑信息，建立与物理网络相匹配的逻 辑拓扑结构，这关系到应用层组播树的质量。组成员的动态性对组播有很大的影 响，因此应用层组播设计面临的主要问题是：如何针对节点的动态性，在节点上 建立必要的状态信息，并根据这些信息构建优化的组播协议。 根据构建的差异，现有应用层组播协议主要分为两大类：集中式构建算法和 分布式构建算法。集中式构建算法引入了集中控制点，集中控制点首先收集组播 组中各成员的信息，然后依据收集的信息来建立覆盖网，并负责组播树的建立和 维护，制定每个节点的路由表并分发给每个节点，并定期计算优化覆盖网络。以 集中式构建算法为基础的组播协议目前主要有：a l m l 5 1 ，p b m l 6 1 ，a m c a s t l 7 ， a p p r o x m d m i s j 等。分布式构建算法没有集中控制点，组成员的管理、数据的传 输网络控制通过各节点维护的局部协作完成。而分布式算法又分为：网格优先 ( m e s h f u s t ) 卜7 。、树优先( t r e e f i r s t ) 和隐式( i m p l i c i t ) 建立这三种方法。目前以分布式 构建算法为基础的应用层组播协议主要有：基于网格优先的n a r a d a f 4 、 s c a t t e r c a s t l 9 1 和c a n b a s e dm u l t i c a s t 1 0 j 等；基于树优先的y o i d 、s p r e a d l t 、h m t p 、 o m n i 和o v e r c a s t 等”1 5 1 ；基于隐式的协议的n i c e 、z i g z a g 和b a y e u x 等【1 每1 8 l 。 相比集中式算法，分布式算法应用更加广泛。但是分布式算法的实现方式不 同：基于网格优先构建一般是分两步：首先在节点分布的自治的构建一个网格结 构拓扑结构，然后在这个网格结构上运行d v m r p 反向路径转发算法等来构建根 节点不确定的组播树。基于树优先的构建算法：直接在组成员之间挑选父节点， 从而自治地构成了组播树；每个组播树中的成员根据一定算法于组播树的非邻接 点保持联系，组播树与这些额外的联系就构成了控制拓扑。基于隐式控制拓扑和 数据拓扑的定义没有严格的先后顺序，成员之间也不需要额外的交互，协议的控 制拓扑一般要求满足一定的属性要求，数据传输路径通常要求建立在报文转发之 上，能平衡控制拓扑属性的开环组播路径。 从应用层组播的研究发展过程来看，应用层组播的研究主要分为两个阶段， 前一阶段没有考虑主机容量的限制，这个阶段应用层组播协议主要关注于鲁棒 性，高效性和可扩展性等方面。后来研究者为了获得更好的性能开始考虑主机容 量这个因素，这一阶段的应用层组播都是基于度约束的。 7 硕士学位论文第一章绪论 1 2 1 不考虑主机容量阶段 这一阶段从第一个应用层组播协议n a r a d a n 提出，一直到s s h i 等人【1 9 】提出 均衡的应用层组播之前。这阶段应用层组播协议的主要设计目标是鲁棒性，高效 性和可扩展性等，并没有考虑主机的容量问题。这一阶段产生了很多经典的应用 层组播协议。下面重点介绍一些主要的协议： ( 1 ) n a r a d a n a r a d a 协议最早提出了e s m ( e n ds y s t e mm u l t i c a s 0 机制，因此n a r a d a 是最 早提出的应用层组播协议。n a r a d a 协议是采用分布式算法，基于网格优先的应 用层组播协议。n a r a d a 首先构建一个所有节点之间的m e s h 结构的控制拓扑，然 后用d v m r p 反向路径转发算法构建源指定数据传输拓扑。n a r a d a 采用分布式 启发算法来构建和维护m e s h ，主要工作包括组成员的管理和m e s h 的修复。下面 重点介绍这两步工作的实现过程： 组成员的管理过程 组成员的管理主要是新成员的加入和组成员的离开与失效。当有新成员要加 入组播组的时候，新成员首先通过外带机制如r p ( r e n d e z v o u sp o i n t ) 获取其他组 成员的节点信息列表，新成员通过列表信息反复连接列表中的节点直到连接成 功。连接成功后将与邻接节点定期交换列表信息，交换成功后刷新信息，更新组 成员之间信息。当m e s h 中某个节点要离开，它首先通知它的邻接点，这个消息 将传到其它组成员。当某个节点失效后，它的邻接点都收不到刷新信息，邻接点 就会发送消息来探测该节点，如果节点没有回应，说明该节点失效。一旦确认节 点失效，邻接点就会刷新自身节点信息，并发到其他的组成员。 m e s h 的修复过程 成员的失效可能导致m e s h 的分离，每个节点都会维护一个失效节点列表， 然后定期对列表中的节点进行探测，如果节点没有响应则说明该节点失效。如果 节点响应，则说明m e s h 分裂，所以要通过加上一条边的方式来修复m e s h 。 由于每个节点都要维护组播组中其他成员的信息及路径状态信息，并定期刷 新信息列表，因此总的开销为d ( 玎z ) ，因此只适合小规模组播组的应用。n a r a d a 通过一个路由代价临时转发( t r a n s i e n tf o r w a r d ) 的方法来避免路由表不一致的时 候就出现分组丢失的问题。n a r a d a 用延时作为生成树性能评价函数的参数，改 进后，在距离矢量法中把带宽和延时作为函数的参数，但带宽优先于延时。也就 是先选择带宽大的节点，如果带宽相同则选择延时小的节点。n a r a d a 分发树的 取决于m e s h 网的质量，m e s h 网是构建分发树的基础，所以m e s h 网的构建非常 关键。 8 硕士学位论文第一章绪论 ( 2 ) s c a t t e r c a s t s c a t t e r c a s t 协议是属于分布式算法中基于网格优先的应用层组播协议。它使 用h e a r t b e a t 机制来检测网格分区。在构建组播树上，采用与n a r a d a 类似的方法， 通过执行逆向最短路径算法在网格为每个源节点建立组播树。在建立控制拓扑 上，首先将组成员分成若干个组，每个节点由一个网络上事先部署的代理节点来 提供服务，新加入的节点通过代理节点加入组播会话中，代理节点之间采用 g o s s a m e r 协议联系和定位。代理节点还会定期探测彼此之间的距离，并寻找近 的节点作为连接点。s c a t t e r c a s t 还可以通过使用应用层的语义为组成员分组和调 整传输内容来适应异构化环境。 ( 3 ) y o i d y o i d 是出现得比较早的应用层组播协议，它属于分布式算法中基于树优先 的应用层组播协议。y o i d 可以看成一个协议的集合，它包括拓扑管理协议 y t m p ，身份识别协议y i d p ，传输控制协议y d p ，传输层协议y t c p ，y r t p ， y m t c p ，y m r t p 。 如果有节点要加入，该节点首先申请并获得r p ( r e n d e z v o u sp o i m ) 来获得候 选父节点的列表，然后通过算法从中找出一个合适的父节点。新节点能否加入组 播树中要满足两个基本原则：第一，新节点加入组播树后，组播树中不能形成环。 第二，新节点加入，父节点的度不能超过限制。由于每个节点可以自己选择合适 的度，可能造成树的深度加深，使得数据的传输路径过长。y o i d 中每个节点都 会定期访问r p ，根据r p 不断更新侯选父节点信息，并测量到候选父节点的延时 和丢包率，如果候选父节点延时或丢包率比当前父节点小，则选择候选父节点作 为新的父节点。为防止非叶子节点的意外断开或者失效而使得组播树被分割，组 播树中的每个节点都会随机的添加一些其他节点信息，主要就组成了控制拓扑。 ( 4 ) h m t p 、 h m t p ( h o s tm u l t i c a s t ) 协议属于分布式算法中基于树优先的应用层组播协 议，h m t p 采用了i p 组播与应用层组播结合的方式。它提供了口组播的功能区 域，对于不支持口组播的区域节点采用单播机制来实现组播的功能。每个支持 i p 组播的区域选择一个成员d m ( d e s i g n a t e dm e m b e r ) 通过主干网连接。而构建组 播树后，组播树中的每个节点都可以成为源节点。 h m t p 中成员主要的主要目的是查找合适的父节点，这点与y o i d 是一致 的。具体为：当新节点在加入之前，首先是查询r p 获取组播树根节点信息，把 根节点作为候选节点，然后从候选节点及其孩子节点中找到离自己延时最近的 点。如果最近点不是候选节点，则把最近点作为候选节点，然后重复刚才的过程， 如果最近点就是候选节点，则判断候选节点是否达到度的限制，如果达到就选择 9 硕上学位论文第一章绪论 候选节点的父节点作为候选节点，如果没有达到限制，则加入。另外，与y o i d 类似，h m t p 也不允许形成环，检测的方法是每个节点保存到根节点的路径上的 所有节点信息来判断是否有环。为了适应网络的变化，每个节点会周期的重复上 面节点的加入过程，从而能够寻找到更优化的父节点，达到优化树的目标。每个 节点还会缓存部分其他节点信息，并周期的更新，因此可以在r p 不可用的情况 也能对整个数据传输拓扑进行修复和优化。 ( 5 ) o v e r c a s t o v e r c a s t 属于分布式算法中基于树优先的应用层组播协议，它提供了一种可 随网络条件变化而有效调节的组播流协议，适用于规模比较大的应用。o v e r c a s t 以增加延时为代价来优化源节点到所有节点之间的带宽。组播树中节点由代理节 点组成，当有新节点请求加入的时候，把新节点放在离根节点尽可能远的位置， 这样就不会对根节点造成影响，但会增加新节点的延时。具体为：当有新节点准 备加入时，该节点首先向根节点提出请求，根节点选择一个与新节点带宽最接近 的孩子节点，并把该孩子节点信息发送给新节点，然后新节点重新向这个根节点 的孩子节点请求，重复这个过程，直到最后某个节点没有孩子节点可以发送给新 节点，就选择这个节点加入。 ( 6 ) n i c e 可扩展应用层组播n i c e 属于分布式算法中基于隐式构建的应用层组播协 议。基于隐式法构建的应用层组播中控制拓扑和数据拓扑没有严格的先后顺序， 成员间不需要额外的交互。协议的控制拓扑一般要求满足一定的属性要求，数据 的传输路径通常要求是建立在报文转发规则之上。n i c e 协议将端点组织成一个 分层结构，协议的基本操作就是构建和维护分层。 n i c e 的分层如图1 _ 4 ，首先将所有的成员作为最底层l o 层的成员，然后将 该层分成若干个群，每个群有k 到3 k 1 个成员，为每个群选出一个首领节点， 这些首领节点又形成了l 1 层；在l 1 层又以k 到3 k - 1 个成员为一个群重复分群， 并选首领节点，继续形成下一个高层直到最后只选出一个最高首领节点。当有新 节点要加入的时候，它必须从高层向底层查询，直到找到最近点。如果节点加入 后造成群大于3 k 1 ，这时候群要发生分裂，分裂的原则是节点数目平均分，形成 两个新群；节点的离开分为两种情况：一种是正常的离开，它会发送消息通知自 身所在群中的所有节点；还一种是节点的失效，这种要到通过同一个群中相互发 送消息并等待答复，如果在一个规定时间内没有收到答复，就认为该节点失效了： 节点离开后，如果造成群中成员数小于k ，则要进行聚合，发生聚合的原则比较 保证聚合后的群大于k 小于等于3 k 1 。 n i c e 协议由于采用了如上述的分层分群的方法，所以它的可扩展性很好。 1 0 硕上学位论文第一章绪论 由于只在同一个群内进行通讯，因此节点维护的状态信息相对比较少，并能生成 低延时的分布树，因此比较适合多源应用。 l l 图卜4n i c e 成员的分层 ( 7 ) z i g z a g z i g z a g 与n i c e 类似，属于分布式算法中基于隐式构建的应用层组播协议。 z i g z a g 提供了更完整的构建组播树规则，保证了树的深度在o ( 1 0 9 n ) ，n 为系统 中总的节点数。z i g z a g 的节点数目可以任意多，而且当有节点离开只需要在局部 进行修复，控制开销也比较低，节点在最坏的情况下需要和o ( k l o g n ) 个节点交 互信息，平均为o ( k ) 属于轻量级协议。 z i g z a g 在最底层包含所有的节点，从最底层到次高层节点以k 到3 k 形成簇， 而在最高层只有一个簇，节点数为2 到3 k 。在第j 层的某个节点会被第j + 1 层的 某个簇选为头节点，服务器是节点所在的所有簇中的头节点，头节点的作用是用 来监视簇内的成员关系，非服务器中一个节点将会选为簇的副节点，副节点的主 要功能是负责数据的转发。系统初始时，由于节点数量比较少，所以这个时候簇 的上界是2 k ，节点超过上界时，簇将会分离成两个簇，分离的原则是平均分。 节点的加入过程和退出过程为：节点加入遵守c r u l e s 规则，当新节点请求 加入时，首先向服务器提出请求，如果此时只有一层，则新节点直接连接在服务 器上，直到簇节点数目超过3 k 。如果有若干层，则新节点从最高层服务器开始 提出请求，最高层服务器选择一个延时最小的孩子提供给新节点，新节点继续申 请，直到没有节点可以提供孩子节点给新节点，然后新节点就加入了最底层的某 个簇中。节点的退出分为两种情况：一种是正常的离开，它会发送消息通知自身 所在簇中的所有节点；另一种是节点的失效，这种要到通过同一个簇中相互发送 消息并等待答复，如果在规定时间内没有收到答复，就认为该节点失效。 1 2 2 考虑主机容量阶段 硕十学位论文第一章绪论 由于主机容量可能在主机负担较重的主机处引起瓶颈，所以很多研究者开始 考虑了主机容量这个问题。s s 1 1 i 等人提出了一种集中式启发算法中最早考虑了 主机容量这个因素【1 9 j 。将接入带宽作为主要的路由参数，在满足个体会话端到 端延迟性能的前提下，寻找使组播服务点( m u l t i c a s ts e r v i c en o d e ) 的接入带宽利用 最大化的路由选择策略。目前这个阶段主要的应用层组播协议有： ( 1 ) o m n i o m n i 属于集中式算法的应用层组播协议。在该协议中，每一个组播服务节 点( m u l t i c a s ts e r v i c en o d e ) 都有带宽接入限制。该协议是使得到所有节点的平均延 时最小的前提下来构建一棵组播树。另外该协议可以使构建好的组播树进行自我 调整，而调整的目标是减少从源节点到其他节点的延时。在节点的加入上，由于 每个节点都根据带宽限制来计算好一个出度数，因此不能超过节点的出度限制。 节点加入后，将构建的是有向树，每条链路的方向指向也就是数据的传输方向， 因此它主要是针对单源组播。 o m n i 虽然考虑了主机容量，可以减少系统的延时，但是它没有考虑到多源 组播的应用，不适合交互系统如视频会议，多人游戏等。另外它可能出现环，因 为它可能出现某个节点同时被几个节点选为孩子节点，从而造成多余的链路传 输，浪费了系统资源。 ( 2 ) a p p r o x m d m a p p r o x m d m 属于集中式算法的应用层协议，主要解决了最小组播延时问 题。使用的算法如下：给定一个有向完全图，每个节点都有一定的处理延时，每 条边都有通信延时，要构建一棵使得源节点到所有节点发送的消息延时最小的生 成树。每个节点的处理延时指处理一条消息所需要的时间，父节点按线性的顺序 转发消息到不同的子节点。 它构建组播树的原贝| j 是：在满足主机度约束的前提下，使得整个组播树的传 输延时最小。并且这种构建组播树的算法被证明是一种近似最优的算法，但它也 只适合单源组播的应用。 1 3 应用层组播树重构技术的研究进展 1 3 1已有重构组播树方法 重构是指在组播树中发生节点失效或者离开后，重新构建一棵新的组播树的 过程。目前主要的组播树重构方法有两大类：响应式方法( r e a c t i v ea p p r o a c h ) 和预 先式方法( p r o a c t i v ea p p r o a c h ) 。 响应式方法【3 5 j 6 1 是在一个节点离开它原来的父节点后再开始为它的子节点 1 2 硕士学位论文 第一章绪论 寻找一个新父节点的方法。这种方法通常需要花较长的时间去修复组播树。如 p e e r c a s t 3 6 】使用响应式方法来重构组播树，在节点失效后，将在失效节点的祖父 节点或根节点为受到影响的节点寻找一个新的合适的位置重新连接。 预先式方法【3 7 3 8 ，3 9 1 即组播树中的非叶子节点事先计算好备份路径，一旦发生 节点离开，所有该节点的孩子节点将按备份路径找到新的父节点。目前主要的预 先式重构方法有：杨式方法，t e t s u y a 方法等1 3 s , 3 9 1 。 1 3 2 组播树重构的