（计算机软件与理论专业论文）基于综合策略的启发式应用层组播设计与应用.pdf

摘要 近年来发展起来的应用层组播继承了传统i p 组播的一些特点， 但是由于作用位置由路由器转移到了终端主机上，通过在网络层采用 i p 单播实现数据传输，从而取消了对组播路由器的依赖，有效地避开 了阻碍i p 组播发展的致命弱点，已经开始被广泛应用。 本文首先对于当前主要的一些应用层组播协议进行了介绍，并对 于这些组播的性能进行了比较和分析，然后讨论了应用层组播路由的 两种常见问题，以及两种贪婪启发式算法和协议设计原则。在总结了 现有的应用层组播系统特点的基础上，提出了一种适用于多个发送端 的组播通信，并且可以同时维护多个成员数量不大的组播组的应用层 组播协议c a im 。该协议采用集中式策略，通过组播会话成员之 间相互监视，有效地减小控制负荷。对于过分依赖控制点的问题，通 过引入冗余控制点的办法，提高了系统的稳定性和容错性。对于延时 和带宽平衡，我们通过一个启发式进行综合的考虑。通过实验仿真表 明，c a l m 组播树在效率上比较接近于i p 组播树。最后我们讨论了 关于c a l m 的应用，对于多发送端音频会议，在使用了音频合并技 术以后，应用程序可以有效地减少节点之间传输的数据量，从而减少 组播生成树节点之间的带宽消耗。 本文提出的应用层组播协议，结合了当前主要的一些应用层组播 的特点，是一种部署快速、配置简单、易于访问控制的解决方案，并 且已经在应用方面做出了一些尝试。 关键词应用层组播，路由算法，音频会议，音频流合并 a p p l i c a t i o nl a y e rm u l t i c a s td e v e l o p e di nr e c e n ty e a r sw h i c hi n h e r i t s s o m ec h a r a c t e r i s t i c so ft r a d i t i o n a li pm u l t i c a s t ，w o n td e p e n do nt h e s u p p o r t o fm u l t i c a s tr o u t e r sd u et o p e r f o r m i n g o i le n dh o s t sa n d t r a n s p o r t i n gd a t aw i t hi pu n i c a s ti nn e t w o r kl a y e r s oi ta v o i d st h ef a t a l d r a w b a c k ss u c c e s s f u l l yw h i c ho b s t r u c tt h ed e v e l o p m e n to fi pm u l t i c a s t a n db e g i n st ob e i n g a p p l i e dw i d e l y t h i sd i s s e r t a t i o ni n t r o d u c e ss o m eo fm a i n a p p l i c a t i o nl a y e r m u l t i c a s t sf i r s t ，c o m p a r e sa n da n a l y z e st h ep e r f o r m a n c eo ft h e mi nd e t a i l s e c o n d l y ，i td i s c u s s e st w og e n e r a la p p l i c a t i o nl a y e r m u l t i c a s tr o u t e p r o b l e m s ，t w og r e e d yh e u r i s t i c sa l g o r i t h ma n dp r o t o c o ld e s i g np r i n c i p l e s b a s e do nt h ec h a r a c t e r i s t i c so fp r e s e n ta p p l i c a t i o nl a y e rc a s ts y s t e m s ，i t p r o v i d e s an e wa p p l i c a t i o n l a y e r m u l t i c a s t - - - c a l mw h i c h a d a p t s c o m m u n i c a t i o n sw i t hm u l t i p l es e n d e r sa n dc a nm a i n t a i ns e v e r a lm u l t i c a s t g r o u pw i t hm i d d l es i z en u m b e ro fm e m b e r ss y n c h r o n o u s l y t h i sp r o t o c o l u s e sc e n t r a ls t r a t e g ya n dl o w e r sc o n t r o ll o a dw i t hm o n i t o r i n gb e t w e e nt h e m e m b e r so fm u l t i c a s ts e s s i o ng r o u p f o rt h ep r o b l e mo fe x c e s s i v e l y d e p e n d i n gc e n t r a lc o n t r o l l e r , w eu s et h ew a y o fr e d u n d a n c yc o n t r o l l e r st o s o l v ei t f u r t h e r m o r e ，w ed e s i g nah e u r i s t i ct ob a l a n c ed e l a ya n d b a n d w i d t he f f i c i e n t l y t h es i m u l a t i o ne x p e r i m e n ts h o w st h a tc a l m m u l t i c a s tt r e ei sc l o s et oi pm u l t i c a s tt r e ei n e f f i c i e n c y f i n a l l yi t d i s c u s s e sa l la p p l i c a t i o no fc a l mt h a ta p p l i c a t i o nc a nr e d u c et h em o u n t o fd a t at r a n s p o r t e db e t w e e nn o d e se f f i c i e n t l yt ol o w e rb a n d w i d t hu s eb y u s i n ga u d i om e r g i n gt e c h n i q u e i na u d i oc o n f e r e n c ew i t hm u l t i p l es e n d e r s o v e rc a i ，m t h en e wa p p l i c a t i o nl a y e rm u l t i c a s tp r o v i d e di nt h i sd i s s e r t a t i o n , c o m b i n e dw i t hs o m ec h a r a c t e r i s t i c so fm a i na p p l i c a t i o nl a y e rm u l t i c a s t ，i s as o l u t i o nw i t hq u i c kd e p l o y m e n t ，s i m p l es e t u p ，e a s ya c c e s sc o n t r o la n d h a sd o n es o m e w o r ki na p p l i c a t i o n k e yw 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 ，r o u t ea l g o r i t h m , a u d i o c o n f e r e n c e ，a u d i os t r e a mm e r g e 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢 的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不 包含为获得中南大学或其他单位的学位或证书而使用过的材料。与我 共同工作的同志对本研究所作的贡献均已在论文中作了明确的说明。 作者签名：盔褴 日期：笔岫之日 关于学位论文使用授权说明 本人了解中南大学有关保留、使用学位论文的规定，即：学校 有权保留学位论文，允许学位论文被查阅和借阅；学校可以公布学位 论文的全部或部分内容，可以采用复印、缩印或其它手段保存学位论 文；学校可根据国家或湖南省有关部门规定送交学位论文。 硕士学位论文 第一章绪论 第一章绪论 本章首先介绍一下应用层组播的起源与发展，然后讨论应用层组播的数据模 型和技术特征，以及本文工作的基本内容和论文的基本结构。 1 1 应用层组播技术概述 1 1 1 应用层组播的产生与发展 随着i n t e m e t 的不断发展，网络用户的大量增加，各种多媒体业务的大量应 用以及越来越多的新兴业务的涌现，例如视频点播、电视电话会议、远程教学等， 由于严重的带宽浪费和低效率，传统的点到点的单播通信方式已经不能适应这些 要求了。于是人们提出了组播的概念。组播是一种通过单一的发送操作将数据报 从一点传送到多点的通信方式。9 0 年代初d r i n g 在他的一篇论文【”中提出了利用 网络层实现组播的架构。在这个架构中路由器分布式地定义了一个组播树，当数 据包从树的根节点即数据源发出后，数据包在不同的树节点路由器上进行复制， 最后到达每个接收终端。由于能有效地减少数据包的复制到最小的限度，口组播 一直以来被认为是最有效的一种用来实现数据的群分发的方法，这也正是当初 d e e r i n g 提出i p 组播的原因。 然而，十多年过去了，虽然对坤组播的研究一直都在进行，但是由于口组播 本身所带来的缺点，使得m 组播至今并没有能够得到广泛的应用： ， ( 1 ) 技术上的原因。球组播要求路由器为每一个组播组保留状态信息。这样路由 器的路由和转发表将需要对每一个不同的组播地址保留一个相应的路由表 项，但是组播地址并不像单播地址一样容易集成，因此增加了路由器的系统 开销和复杂性而且m 组播目前许多的协议都还没有实现，对其监控、管理 比较复杂，如对组的管理、组播地址的分配、安全方面的、支持网络管理方 面的问题 伫) 市场上的原因。打破了传统的计费模式，当前的组播的服务模式没有支持组 播的付费，要在当前的服务模式和协议体系结构下普遍化和商业化，口组播 会遇到很多困难。口组播是一种尽力而为( b e s te 肋n ) 的服务。当要提供高层 的特性时，例如，可靠传输、拥塞控制、流量控制以及安全管理等，就会比 简单的单播要更困难，以至于因特网服务提供商( i s p s ) 不愿意提供口 m u l t i c a s t 的支持。虽然目前已经出现了针对上面这些特性的研究，但是这些 解决方案目前在i n t e r a c t 上的影响并不明确，需要在大范围应用前进行更好的 研究。口组播需要对现有网络做底层的改变。同时由于在收费机制方面的技 硕士学位论文第一章绪论 术无法突破，使得目前只有少数的因特网服务提供商支持m 组播。 近几年来，p 2 p 覆盖网络技术的出现为基于无集中控制结构的分布式应用提 供了新的思路，同时也引发了对“m 层是否为部署组播功能的最佳位置”这一问 题的再思考。结合d 组播的发展现状，研究人员试图借鉴口组播的基本设计思想， 在应用层建立组播机制，作为口组播的替代实现技术。应用层组播研究旨在直接 在组成员之间建立数据传递树，将组播相关功能( 包括组成员管理、报文复制、 数据分发等) 实现于终端主机，在网络层仍采用口单播实现数据传输，从而取消 对网络基础设施( 如组播路由器) 的依赖。应用层组播的配置、部署毋需更改现有 i n t e m e t 基础设施，可解决m 组播中所面临的大多同题，近年来受到学术界的广泛 关注。 1 1 2 数据传输模型 应用层组播的基本思想是屏蔽底层物理网络的拓扑细节、将组成员节点直接 自组织成一个逻辑覆盖网络( o v e r l a yn e t w o r k ) ，并在应用层提供组播路由协议来 构建和维护该网络，为数据传输提供高效、可靠服务【2 0 l 。应用层组播将所有组 播功能完全集成在主机中，由应用层软件具体实现。图1 1 给出了应用层组播与 传统网络层数据传输模式的对比示意图。图中主机a 为发送源，主机b 、c 、d 为 接收者集合，r i r 5 为路由器。图1 1 ( a ) 显示了单播方式下的报文传输路径，该 方式下发送者为每个接收者分别建立从发送源到目的地的传输路径，因而在上游 路径易于产生重复报文，而且越靠近发送源冗余量越大( 如图1 k a ) 中的a r 1 段) ，容易造成链路拥塞、形成服务瓶颈。图1 1 ( b 瑚绘了典型的讲组播流程，为 加入组播组，接收者与组播路由器联系，由路由器负责组成员的管理和组播树的 创建与维护。传输过程中，数据沿着组播树流向接收者，报文复制由中间路由器 根据需要自动处理。由于组播路由器拥有链路级的组播树分枝路径信息，因此， 基于路由器的报文复制、转发机制使得任何物理链路上只可能存在一个数据拷 贝，可有效避免冗余传输，节省网络带宽，因而有很好的协议性能。应用层组播 ( 如图1 1 ( d 、图1 1 ( d ) ) 将所有组播功能迁移到终端主机，传输网络的构建完全独 立于口层的物理链路，数据流向及报文复制由终端主机控制，具体的报文传输仍 然依赖于i l i 单播传输机制。这种基于主机控制的报文复制方法使得在覆盖网络分 支节点所对应的物理链路( 如图1 1 ( d ) 中的a r 1 段) 及中间转发节点与路由器之 间的迂回路径( 如图1 1 ( d ) 中的b r 2 段) - = - 7 能会存在同一报文的多个副本，由此 可见，应用层组播对带宽的利用率不及口组播。图1 1 ( c ) 和图1 1 ( d ) 显示了两种不 同的应用层组播传输模式。 2 硕士学位论文第一章绪论 凰凰 a 单播 bi p 组播 k 疑 c 应用层组播( 令牌组播) d 应用层组播一般情况) 田1 - 1 典型数据传输模型 从部署位置上来看，应用层组播试图将组播功能推向应用上层，通常可用以 下两种系统结构来实现应用层组播1 2 l ： ( 1 基于p e e r - t o - p e e r i n g 系结构。这是一种基于动态节点的覆盖组播技术，系统 中组成员节点状态动态变化且完全分布，节点之间通过特定算法、协议自组 织成为控制网络和数据分发树。每个节点仅维护自身参与组的状态信息，所 有组播相关功能以软件实体形态集成于参与组播会话的节点中。基于p 2 p 结 构的组播协议设计强调如何在动态网络环境下提供有效的组播传输机制，保 证协议的可靠性，提高协议的自适应性。 ( 2 ) 基于代理的体系结构。这是一种基于固定节点配置的覆盖式组播技术，一般 由增值服务提供商根据一定策略在i n t e r n e t 的某些位置部署应用层代理节点， 代理节点之间的数据传输路径和传输方式也由增值服务商预先确定。终端主 机通过接入距自身最近的代理节点获取数据。代理方案实质上是一种中继技 术，在终端主机和代理之间建立临时通道，也常被称作隧道化方式( t u n n e l i n g a p p r o a c h ) 。该方法的主要优点是代理节点相对固定，组播树比较稳定，容易 针对具体的应用需求提供特定的o o s 保证。但所提供的组播服务缺乏伸缩性， 容易在代理节点形成服务瓶颈。此外，还常常需要i s p 的支持。 1 1 3 技术特征 应用层组播是建立在应用层之上的一种虚拟网络，与口组播相比，协议设计 韵主要差异包括： ( 1 ) 报文转发位置。应用层组播的数据转发节点可以是覆盖网络中的终端主机或 专有服务器，而疋组播的报文转发必须由核心路由器来处理。 ( 2 ) 网络拓扑的创建方法。应用层组播树是由节点直连而成的覆盖网络，该网络 3 硕士学位论文第一章绪论 的构建和优化常依据在部分或全部节点之间建立的一些度量尺度，完全隐藏 物理网络拓扑特征；构造口组播树的所有路由协议( 包括域内路由、域问路由 协议1 都依赖于具体的网络链路，与m 链路信息密切相关。 ( 3 ) 组管理模式。口组播的组成员关系信息分布于组播路由器，组管理由路由器 负责；而应用层组播的成员关系可由系统中的会聚点( r p ) 集中控制，也可由 各节点根据自身维护的局部状态信息协作管理。应用层组播由于节点及网络 状态动态变化，一般通过建立一个与数据传输网络有别的控制拓扑来管理， 要求控制拓扑能在异常条件下替代传输网络提供数据传输服务。 从功能特征来看，疆组播设计强调时效性，有较好的传输效率和资源利用率。 但受路由器存储空间限制，因此可跨越空间位置、而不能跨越时间维传输信息1 3 1 。 通常要求接收者同步接收数据。m 组播非常适合具有严格时间要求、且能容忍一 定丢包率的实时应用( 如视频服务、网络游戏) 。应用层组播将组播功能实现于上 层，具体的报文传输仍然由传统的m 单播机制负责。由于覆盖网络与物理网络分 离，因此协议效率不及口组播。但应用层组播可充分利用节点的存储能力，结合 m 层和应用层的q o s 机制，有效避免和解决口组播中存在的拥塞控制、可靠传输 等问题，提供端到端的服务质量保证应用层组播的实现不需要网络中路由器提 供任何特殊支持，可以类库形式被调用或直接内嵌于应用代码之中，因而操作方 便、易于广泛部署。此外，应用层组播能同时跨越时间维和空间维进行数据传输， 更适合能容忍一定程度延迟的商可靠应用，如电子邮件、文件传输。 1 1 4 应用层组播和m 组播的比较 应用层组播的优点： ( 1 ) 应用层组播能够很快就进入应用，不需要改变现有网络路由器。 f 筋接入控制更容易实现。由于单播技术在这方面比较成熟，而应用层组播是通 过终端系统之间单播来实现的，所以差错控制、流控制、拥塞控制容易实现。 ( 3 ) 地址分配问题也就可以有相应的解决方案。 应用层组播的缺点： ( 1 ) 可靠性：终端系统的可靠性比路由器差。 ( 2 ) 可扩展性：底层的路由信息对应用层组播来说是隐藏起来的，可扩展性不好。 ( 3 ) 延迟比较大；口组播主要是链路上的延迟，而在应用层组播中，数据还要经 过终端系统，因而延迟相对要大一点。 ( 4 传输效率不如球组播：应用层组播在数据传输过程中会产生数据冗余，因 此它们比m 组播的效率差。 4 硕士学位论文第一章绪论 1 2 相关研究进展 应用层组播将组播功能实现于终端主机中，组成员的动态性对组播有很大影 响。应用层组播协议不仅要提供有效的数据组播分发树，还要针对节点的动态性 提供可靠的组管理算法。协议设计强调在动态网络环境下维持网络的稳定性。应 用层组播路由协议设计面临的主要问题是，如何在广域环境下，针对节点的动态 性、在节点上建立必要的状态信息，并根据这些信息构建优化的组播路由协议。 图1 2 根据协议构造算法的差异对现有应用层组播路由协议的构造方法进行了分 类。 1 2 1 集中式算法 图1 - 2 应用层组播协议分类 集中式算法在协议中引入全局会话控制点，集中管理所有组成员的状态变化 仂入1 罱开) 及成员之间的位置( 距离) 关系信息，负责组播树的创建和维护，并定 期计算、优化覆盖拓扑。集中式方法具有较好的可靠性，而且能减少控制过载， 易于维护组播树的一致性和效率。但由于控制点要维护全局信息，受单点失败的 限制，因而缺乏可伸缩性，比较适合小规模稀疏型的组通信应用。根据协议优化 所依赖信息的不同，集中式算法又可分为基于全局信息和基于局部信息两种组播 树优化策略。i - i b m | 4 1 、n i m # l 都属于集中式应用层组播协议 i - i b m 将组成员分成核心成员和非核心成员两类，核心成员形成数据分发树 的主干节点，非核心成员只能作为叶子节点组播中的所有活动都由一个集中汇 聚点( r p ) 控制，汇聚点管理会话中所有成员的分类信息以及相互距离。覆盖拓扑 的优化完全依赖于l i p 中的全局信息，较a l m i 而言，较容易得到最优化的网络 拓扑 5 a l m i 的每个会话包括一个会话控制器和若干个会话成员。会话控制器控制 覆盖网络的全局信息，具体处理组成员的注册请求和维护组播树。为保证协议效 率，会话控制器根据所有组成员反馈的最新链路信息定期重新计算并生成最小生 成树( m s t ) ，该组播树是一个具有双向链路的共享树( s h a r e dt r e e ) 。为降低控制负 载，a l m i 协议采取基于局部信息的优化算法，对每个节点所监视的邻居节点数 进行限制。因此，a l m i 构建的组播树是次优的。 1 2 2 分布式算法 分布式算法中没有集中的会话控制点，组成员的管理、数据传输网络的控制 通过各节点维护的局部信息协作完成。分布式算法可避免集中式算法受单点约束 的限制，有更好的可伸缩性。然而，在动态分布环境中，频繁的加入，离开操作、 节点及网络条件的异常变化使组播树极为动态因此，基于分布式算法的组播协 议设计更为复杂和困难，通常需要协调和衡量协议设计所引起的每节点维护状态 信息量、控制过载、通信代价等开销。为适应系统的动态性，保证组播传输的有 效性，分布式算法常将组成员组织成为控制拓扑和数据拓扑两种有不同功能目 标、但均覆盖所有成员的网络结构。控制拓扑一般是基于局部信息的连通图，负 责监视节点变化、维护网络的连通性。数据拓扑是一个开环树，主要为数据传输 提供高效的组播路径。现有协议大多把数据拓扑看作是控制拓扑的一个真子集。 根据控制拓扑与数据拓扑建立顺序的不同，分布式算法又可分成网格优先 ( m e s h - f i r s o 、树优先( t r e e 融t ) 、隐式( i m p l j c i t ) 建立等3 种不同方法嘲。 1 、网格优先法 首先将组成员自组织成一个连通的覆盖m e s h ，该m e s h 中任意两个节点之间存 在多条路径，每个节点都要维护全部( 或部分) 其他成员信息，并借助一定算法来 避免和检测网络分区。然后通过路由算法在m e s h 上建立以指定源为树根、涵盖 所有组成员的单独树( p * s r t r e o 。网格优先法通常显式生成m e s h 拓扑，而组 播树的建立依赖于具体的路由算法和m e s h 拓扑，并且m e s h 的选择直接影响着组 播树的性能。高质量的m e s h 应满足以下两个属性： ( 1 ) 任意节点对之间的m e s h 路径质量( 带宽、延迟) 应与其对应的单播路径质量类 似。 ( 2 ) 每个节点应只拥有少量m e s h 邻接节点。 属性1 与组播树的数据传输效率密切相关，属性2 决定了节点需维护的状态信 息量及平均控制负载。网格优先方法可为分别不同的发送源建立优化的单独树， 还允许在m e s h 上建立抽象的组管理功能和负载均衡的路由算法，具有较好的数 据传输效率。该方法的一个主要缺点是，由于在控制网络上建立了多源覆盖树， 6 硕士学位论文第一章绪论 每个节点都需要花很大代价来维护、优化多个组播树图1 3 0 ) 给出了基于网格 优先方法的覆盖拓扑结构示意图。n a r a d a 2 1 、s c a t t e r c a s t l 7 都采用了基于网格优先 法的协议构造方法 8 网格优先 一控制路径 b 层次型优先 一一一一数据路径 图1 - 3 覆盖式组播网络 n a r a d a 被认为是最早的应用层组播协议之一。新成员首先通过r p 获取部分 成员，并试图作为这些成员的邻接节点加入m e s h 组成员定期与m e s h 中的邻接 节点交换信息，及时检测失败节点，维护m e s h 的连通性。n a r a d a 采用逆向路径转 发路由算法( 如d v m r p ) 在m e s h _ l 分别为各个发送源建立数据分发树。为提高数 据传输质量，n a r a d a 采用分布式启发算法，由每个节点周期性探测与其他成员的 相互位置关系，并根据探测结果决定是否添加新链路，从而优化m 鹤h 拓扑。n a r a d a 中每个成员所需维护状态信息为o ( n ) ，缺乏可伸缩性，适用于中小规模稀疏型 组播应用。 基于m e s h 网的构造，是因为需要进行多源的服务。, m e s h 网允许我们为每个 发送源构造最优树，可以将成员的管理抽象到m e s h 层。我们在构造分发树时还 可以使用已有的路由算法。以下我们介绍m e s h 网的构造； ( 1 ) 新成员加x m e s h 网 当有成员要加入组时，n a r a d a 假设该成员可以利用外部引导机制获得组成员 的列表。这个列表并不需要非常的完全和准确，但至少要包含一个当前活动的组 成员。该成员从它的列表中随机的选择一些组成员和给他们发送加入邻居的信息 请求。重复这个过程直到从列表成员中获得响应。一旦获得加入，成员开始与 它的邻居交换刷新信息，使成员之问能相互的了解。 ( 2 ) 成员离开和失败 7 硕士学位论文 第一章绪论 当成员要离开组时，它就通知邻居，这个信息通过m e s h 网传送到其他的组 成员。假设c 成员失效了，m e s h 网中c 的邻居卿g 接收不到c 的刷新信息，他们 独立地发送探测消息n c ，所以每个发送信息( 与c 的回应) 都丢失的可能性很小。 如果是这种情况，a 和g 就假定c 失效，因此把这个信息发送到整个m e s h 网。如 果节点a 失效，那就造成m e s h 网的分离，就要运行一定的算法进行验证，一旦确 认，就要加上链路，将两个分开的m e s h 网重新连接起来。1 。 每个成员需要保留有失效的组成员，这样才能区分是新成员的刷新，还是失 效的成员的重申，失效的成员能在满足一定的时闻重新被激活。 ( 3 ) m e s h 网分离的修复 成员的失效可能导致m e s h 网的分离。例如在图1 - 4 中，如果成员a 失效，到 达一定的时间，m e s h 网的两边就不再接收成员之间的刷新信息，m e s h 网就分离 了。在此情况下，成员必须首先检测到m e s h 网分离的存在，然后用至少添加一 条覆盖链路去重新连接。 图1 - 4m e s h 网的失效情况 每个成员保持有劬时问，在这段时间内没有收到成员的更新信息，并利用一 定的算法，计算出失效点是否是头节点，是否还有链路连接在它的上面，并添加 链路进行恢复。 以下原因使n a r a d a 构造的m e s h 网并不一定是最优的： o ) 新节点的加入并没有考虑网络拓扑。 ( 2 ) 分离和修复可能产生多余的链路。 ( 3 ) 组成员之间因加入、离开是不断变化。 ( 4 ) 底层的网络环境、路由、负载情况不尽相同。 所以n a r a d a 利用一定的策略算法对链路进行评估，添加和去除链路优化性 能。在m e s h 网上运行距离向量协议和构造最短路径剪枝树。分发树的质量取决 于所构造的m e s h 网的性能。因为分发树是在m e s h 网的基础上进行剪枝构造的， 所以m e s h 网的构造是极为关键的。 2 、树优先法1 2 1 1 基于树优先法的组播协议首先根据各节点的局部信息创建一个共享树，随 后，各组成员从覆盖树中寻找非邻接节点，根据一定算法建立并维护到这些节点 的控制链路，从而使控制拓扑得到加强。与网格优先方法不同，树优先法中的控 制网络与组播树分离，组播树不一定是m e s h 的子集。该方法的优点是赋予用户 8 硕士学位论文 第章绪论 对组播树更多的直接控制能力，可以控制节点的最大出度，选择适合的父节点。 树优先法的主要缺点是对组播树的回路检测和避免处理比较复杂，而且对组播树 的优化也比较困难【4 。y o i d 3 1 、h i v i t p s 都采用了树优先方法。 y o i d 、h h f r p 都能集成现有口组播技术并向非m 组播区域提供组播服务， 两者组成员加入机制非常相似。y o i d 为应用层组播的实现提供了完整的应用框 架，可看作是一个协议集。包括拓扑管理协议y t m p ，传输控制协议y d p ，身 份识别协议y i d p ，传输层协议f r o , 、y r t p 、y m t c p 、y m r t p 。y 0 i d 的控制 m e s h 和组播树由y t m p 分别创建，但两者的优化目标不同。前者优化主要是为 了提高健壮性，而后者以提高协议效率为目的。控制m e s h 除了维护正常的组管 理功能外，还对网络分区情形下的数据传输服务提供支持。为加入组播树，新成 员首先通过r p 来获取部分组成员列表，然后从中选择具有可用度且不会产生闭 环路径的节点作为父节点。 y o i d 是通过一个共享树来进行数据分发的。进行数据传输的组成员可以位 于组播树的任何一个位置( 可能是在叶节点上，或者是根节点上，也可能是在其 他的分枝上) 。一个组成员可以从树上的任何一个邻接节点上接收内容帧，再将 接收到的帧转发给其他所有的邻节点。我们之所以使用“帧”来代替“包”，是 由于组成员接收，复制和转发的内容是以应用帧为单位的，而每一帧都可能包含 有多个m 包。 图l - 5 就是一个y o i d 组播树，其中包含了许多与之相关的术语。树上的每 一个方框代表一个成员，实线箭头表示树的链接，但是箭头所指的方向并不代表 数据帧的传输方向，即数据帧的传输方向和箭头的指向无关。( 也就是说一棵树 上的哪些节点可以进行数据传输是有限制的，这种限制在一个成员申请加入组播 树的时候就由汇聚节点告知的，对于所有的成员来说都是强制约束的。 目1 - 5 y o i d 树及其术语 9 硕士学位论文第一章绪论 组成员既可以通过口单播来进行数据帧的接收和转发，也可以在一定的范 围内通过口组播来接收和转发数据帧。通过口单播连接的两个邻居成员是 p a r e n t c h i l d 的关系。成员总是试图寻找离他们最近的邻居成员( 成员之间的这种 距离是通过两个成员之间的延时来决定的) 。i p 组播将一组成员组成一个群， 并将该群当中的一个成员提升为首领节点，并负责通过m 单播来去寻找相邻的 父成员，以此实现群和树的其他部分的连接。群的其他成员被称为群足，他们无 论是从组播树上接收数据帧，还是向组播树发送数据帧都需要通过群的首领节 点。群组成员被认为是紧密相邻的，因为他们共享一个坤组播。在图中孩子通 过实线箭头指向父成员，群足指向首领节点。 每一棵组播树都只能有一个根节点，这个根节点是不能有父节点或者群首领 节点的。( 当然在组播树发生变化的过程当中可能有多个根节点或者没有根节点， 但是当组播树处于稳定状态的时候，只能由唯一的一个根节点。) 所有的其他成 员也只能有一个父节点或者一个群首领节点。每一个成员，在一个特定的时候是 传输成员，还是叶成员，取决于他所拥有的邻居成员的个数。如果他拥有多个邻 居成员，那么他就是传输成员，而如果只有一个邻居成员，那他就是叶成员。如 此，一个成员可能通过限制自己的邻居成员的个数，使自己始终只扮演叶成员的 角色。如果抛开树的拓扑不提，那么一个成员可以是一个终端，或者是一个y o i d 代理服务器( 或者本身就是服务器) 。这两者之间的区别在于终端包含了用于树 操作的应用，而服务器没有。如图1 5 ，服务器就是被安装在网络中只是单纯扮 演传输成员的方框。 所有基于数据拓扑优先方法的组播协议都会创建一个共享的数据传输拓扑 树，每个成员的任务就是找到合适于自己的父节点。既然y o i d 是直接建立的数据 分发树，那么为了使组播达到更好的性能，它就会对树的结构给出直接的限制， 例如每个成员节点的度、邻接点的选择等。当有新成员需要加入时，首先会查询 r p 得到的已加入成员的信息，然后通过这些信息找到合适的父节点。一个节点 如果要成为这个新成员的合适的父节点必须满足两个条件：如果选其做新成员的 父节点，数拓扑上将不会出现循环；如果选新成员做其子节点不会超过其度的要 求。如果新成员找到了多个合适的父节点，那么它将根据具体实际量度的要求来 找出最合适的一个父节点由于每个成员都会自己选择合适的度即子节点的个 数，则很有可能导致树的深度加深，使得数据传输出现比较长的传输路径。 为了防止由于某个非叶节点的意外断开而使得整个数据传输树被分割，y o i d 中的每个成员会在数据传输拓扑上随机选取一些其他节点填加到连接中，这样便 组成了控制拓扑。 h m t p ( h o s tm u l t i c a s tt r e ep r o t o c 0 1 ) 主要处理组播的配置问题，协议将组播 硕士学位论文第一章绪论 服务覆盖区分成若干个正交区域，并为每个区域选择一个指定成员s ) 。所有的 d s 通过h m t p 自组织成双向共享树。h m t p 为每个组会话定义一个引导点 h m r p ，新成员首先通过h m r p 获取树根地址，并从根节点开始由上向下逐层寻 找，选取一个距自己最近、且有可用度的节点作为自己的父节点。为检测闭环， h m t p 中的每个成员都要维护到根节点的路径。h m t p 不要求显式生成m e s h ，协 议让每个节点周期性探询和缓存组播树中部分成员信息来避免、解决网络分区。 与y o i d 相似，删口中成员的主要目的便是查找合适的父节点。当有新成员 n 加入时，其基本步骤如下， ( 1 ) 通过查询r p 获得树的根节点信息。 ( 2 ) 从根节点开始，在每一层n 都会找到离自己最近的节点x 。如果x 的子节点数 小于其度的上限，那么n 就选择x 作为其父节点加入。否则，n 就会到x 节点 的子节点中寻找合适的父节点。如图1 6 ，给出了示例，其中假设a 的最大度 值为3 ，d 的最大度值为2 。 新成照舞成盟ii成奠if成员 图1 - 6 h m t p h m t p 中的成员都会保留它到根节点路径上的所有节点的信息。为了适应网 络环境的变化，每个成员会周期性地通过重新启动上述的新节点加入程序，为自 己寻找更优化的父节点，从而对树的结构进行优化。 与y o i d 不同的是，h m t p 并不显示地构成一个控制网状拓扑，而是每个节点 都会缓存部分其它节点的信息，并周期地进行更新。这样，即使在r p 点不可甩 时，整个数据传输拓扑可以在意外情况下进行修复。 3 、隐式方法 隐式法中控制拓扑和数据拓扑的定义没有严格的先后顺序，成员之间也不需 要额外交互。协议的控制拓扑一般要求满足一定的属性需求，数据传输路径通常 要求是建立在报文转发规则之上、能平衡控制拓扑属性的开环组播路径。根据控 制拓扑建立方法的不同，隐式法又可分为层次型、p 2 p 路由等几种类型。 ( 1 ) 层次型方式 协议将组成员分成若干层，并由下向上为每个层顺序编号( 最低层编号为t o ) ， 1 l 硕士学位论文第一章绪论 每层都包含若干个簇，所有成员都一定属于h ，图2 2 描述了层次型网络结构 示意图。层次型拓扑构建通常从k 层开始按如下方法递归定义：协议依一定规则 将l 层的组成员划分成若干个具有一定大小限制的簇，并选取簇的图论中心节点 作为簇头，k 层的所有簇头形成l “l 层。随后根据该层次结构定义控制和数据传 输的覆盖拓扑。新成员加入系统时，首先从最高层向下在每层探测距自己最近的 成员，并加入1 1 0 相应簇1 3 7 1 。 基予层次结构的应用层组播可扩展应用层组播( n i c l ) 唧是一种可扩展 的应用层组播，主要针对大量接收者的低带宽、数据流应用，它基于分层的结构， 同时具有较小的控制负荷，有利于它的扩展性。n i c e 的数据拓扑隐含在它的控 制拓扑中，因而还可以支持不同源的数据分发树；并且由于它的分层，进行错误 检测较为迅速。 n i c e 的控制拓扑和数据拓扑 成员怎么进行分层呢? n i c 嘴每个成员赋予不同的层。如图1 - 7 所示，从b 到l 1 层在每个层中，成员被分为多个群集，每个群集的数量k 3 k - 1 。 l 。层集群中的领导成员 l 0 屡集群中的领导| 髭贝 所有的成员 图1 - 7 n i c e 成员的分层 控制拓扑的图形，将每层群集中的领导节点连接起来，每个节点只包含一定 常数量的成员信息，这样有更好的扩展性。数据拓扑、图形，可以在控制拓扑上， 单源进行方便的构造，分发树隐含在控制拓扑中，可以方便地构造多个分发树。 控制拓扑：每个层中群集的成员可以很快地清楚其对等成员的变化信息。如 图1 8 中b 0 可以知道l 0 层上a 0 ，a 1 ，a 2 ，还有h 层上b l ，b 2 ，c o 的信息，邻居之 间信息的交换在控制拓扑上交换。 数据拓扑；组播数据的分发路径需要防止循环。数据的分发是一个具有确定 源的树。如图1 9 所示，从源a 0 发送数据的情况我们可以看出数据拓扑隐含于控 制拓扑中。 硕士学位论文第一章绪论 图1 - 8n i 的控制拓扑图i - 9n i c e 的数据拓扑 n i c e 协议的描述 ( a ) 成员的加入。当一个成员要加入组播组的时候必须映射到b 层的某个群集上。 从高层开始向汇聚点进行提出查询，寻找最近的成员，然后顺序查询至k 层 ( b ) 群集的维持和精简。 成员的分裂和聚合：群集中的领导成员定期地检测群集中成员的数目。如果 群集的数目超过3 k - 1 ，那么就将这个群集分裂成两个数量相同的群集；如果群集 的数目少于k ，那么就将群集进行聚合。 群集的优化：因为成员的加入不一定加到最近的群集中( 可能由于查询和响 应信息的丢失等1 ，所以成员定期地检测他的上层，寻找最近的群集。 ( c ) 成员的离开和领导节点的选择 正常离开：发送离开信息到它所属的群集中的所有成员。 突然离开：群集中的其他主机接收不到离开主机的刷新信息，经过一定的时 间就认为该成员失效了。如果离开的主机是这个群集中的领导成员，那么就在剩 下的成员中选择一个作为新的领导成员。 ( 2 ) p 2 p 路由方式 b a y e u x 埘、s c r i b e u l 、c a n - m u l t i c a s t 1 2 1 都建立在p 2 p 的路由设施之上的应 用层组播协议。b a y e u x 以应用层路由协议t a p e s t r y 为基础，采用显式途径分别 为每个发送源建立和维护组播树t a p e s t r y 中。每个节点都有一个不依赖位置和 语义属性，并由固定长度的位序列组成的标识符。每个节点都维护一个多级邻接 表，为消息传递提供增量路由均衡、提高带宽利用率提供支持为加入组播，新 成员首先发送。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 中每个成员的加 硕士学位论文 第一章绪论 入，离开都要经过根节点，因此，在根节点受单点失败限制。s c r i b e 建立在p 2 p 对象定位和路由协议p a s t r y 之上，其控制拓扑与p a s t r y 的控制拓扑相同，每个成 员都包含路由表、邻接点集和叶子集入口等信息。s c r i b e 的组播树通常由p a s t r y 覆盖网络的子集组成，协议为每个组定义一个唯一标识符，与该标识最近的成员 成为该组的r p ，负责组成员的注册管理，新成员通过组标识发送消息到r p 加 入会话。组播会话的数据传输拓扑由不同组成员到r p 的p a s 时单播路径联合而 成。b a y e u x 、s c r i b e 都支持单独树，但前者组播树包含从根节点到每个目标节点 的路由信息，而后者则包含从每个目标节点到根的信息。与b a y e u x 相比，s c r i b e 中每个节点维护的状态信息较少，而且成员的请求操作由本地处理，因此，s c r i b e 有更好的伸缩能力。 c a n - m u l t i c a s t 以覆盖网络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 ) 为基础，c a n 将组成员组织成一维笛卡儿坐标空间，每个成员占据一定空间与其他协议不同 的是，c a n - m u r i c a s t 不需要创建组播树，而是通过为每个会话分别建立c a n 子 网络来为数据传输提供服务。每个节点只需要维护自己所属组的信息，而与组大 小、数据发送源无关。组播报文通过泛洪方法向邻接节点发送。协议采用哈希函 数为每个组播组映射一个引导节点，新成员通过该引导节点加入会话组，随后的 节点加入、离开操作由常规c a n 维护算法处理。c a n 中每个成员只需维护2 d 个邻节点信息( 其中d 为坐标维数) ，但为每个组分别维护一个c a n 覆盖网络需 要一定的代价。 1 3 亟待解决的问题 在当前的应用层组播的应用中，延时( d e l a y ) 和带宽( b a n d w i d t h ) 是两个重要 的度量指标。延时是指从源发出的应用层数据到达某一节点所花费的时间。而带 宽指的是单位时间内可以从父节点接收到的数据量，以k b s 秒为单位。对应用 层组播来说，它在节点之间构建组播树来传输数据。 由于在实际的应用中，各个组播会话节点的网络状况各不相同，对于带宽比 较富余的宽带用户而言，带宽的限制可能