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

重庆邮电大学硕士论文 摘要 摘要 随着计算机技术和网络技术的发展，以视频会议、计算机协同计算以及大规模 分布交互仿真等为代表的组通信应用不断涌现，这些组通信应用迫切需要i n t e m e t 提供更好的服务。为了适应这些组通信的要求，研究人员针对口组播技术进行了近 二十年的研究，然而由于d 组播存在可扩展性等方面的问题。口组播要在i n t e r n e t 中进行大规模配置还需要相当长时问。近年来，基于应用层的覆盖网络组播服务方 案得到了越来越多的研究注意，应用层组播不需要底层设备的升级和功能扩展，能 够实现组播服务功能随需配置。 目前大部分应用层组播协议仅仅关注于如何减少源主机和目的主机问端到端的 延迟，而忽略了覆盖网络的带宽问题。由于两条看似互不相连的覆盖树路径可能共 享相同的底层链路，从而会减小覆盖网络的带宽，因此，在构建一个覆盖网络时， 底层链路的拓扑结构显得很重要。本文首先针对应用层的覆盖网络进行了研究，分 析了目前基于覆盖网络的应用层组播协议的特点，提出了一种新的方法构建覆盖网 络。新方法构建组播树的过程中，采用距离估计技术测量目标主机的坐标，通过一 种启发式算法推断出底层链路信息构建底层链路拓扑图，并在此基础上构建覆盖网 络。仿真结果表明新方法可避免过高负载的链路，充分利用网络的带宽。 岛播( i s l a n dm u l t i c a s t ) 是一种将口组播与应用层组播相结合的思想，域间运行应 用层组播，域内运行口组播。本文通过将构建覆盖网络的方法应用到域间应用层组 播上对岛播进行改进，详细描述了组播组成员的运行机制，成员节点的加入、离开、 选举及覆盖网络的恢复机制。仿真结果表明该方法通过牺牲少量的端到端延迟对链 路的平均负载有了较大程度的提高。 关键词：应用层组播，覆盖网络，岛播 重庆邮电大学硕士论文 a b s t r a c t w i t ht h ee n o r m o l l sa d v a n c ei nn e t w o r kc o m p u t i n ga n de o m m t m i e a t i o nt e c h n o l o g i e s ， ad i v e r s er a n g eo fa p p l i c a t i o n st h a ti n h e r e n t l yr e q u i r eg r o u pe o m m u n i e a t i a n d c o l l a b o r a t i o nh a v ea r i s e i lt h e s ea p p l i e a t i o mi n c l u d ev i d e o a u d i oe o n f e r e n e i n g , c o m p u t e r c o l l a b o r a t i o n , l a r g e r - s c a l ed i s t r i b u t e ds i m u l a t i o n , e t c t h ed i v e r s i t yo ft h e s ea p p l i e a t i o m d e m a n d sv e r s a t i l es u p p o r tf r o mt h eu n d e r l y i n gn e t w o r ki nm a n yd i m c 珊i o n s i no r d e rt o s u p p o r tt h e s ea p p l i c a t i o n si no u i c u r r 锄ti pn e t w o r k s , r e s e a r c h e r sh a v eb e e nr e s o l v e di n 口 m u l t i e a s tf o ra b o u t2 0y e a r s h o w e v e r , l l l e 口m u l t i e a s ts o l u t i o nh a ss e r i o u ss e a l i n ga n d d e p l o y m e n tl i m i t a t i o n s ，a n dc a n n o tb ee a s i l ye x t e n d e dt op r o v i d em o r ee n h a n c e dd a t a s e r v i c e s t h e r em u s tb eal o n gt i m ef o ri pm u l f i e a s tt ob ed e p l o y e di ni n t e m e tw i d e l y r e c e n t l y , r e s e a r c h e r sh a v e b e e na t t r a c t e dt od e p l o ym u l t i e a s ts e r v i c ea ta p p f i e a t i o nl a y e r , t h e s ek i n do fs o l u t i o n sd on o tn e e dt ou p g r a d et h eu n d e r l a yt o u t e r s , a n dc , a l ls u p p o r t m u l t i e a s ti l l s0 1 1 t ，n e e d c u r r e n t l y , m o s tm u l t i e a s tp r o t o c o l si na p p l i c a t i o nl a y e ro n l yc o n s i d e rh o wt o d e c r e a s et h ed e l a yb e t w e e ns o u l r c eh o s ta n dd e s t i n a t i o nh o s t h o w e v e r , t h e yi g n o r et h e p r o b l e mo fb a n d w i d t hf o ro v e r l a y t w oo v e r l a yp a t h sw h i c hl o o kl i k ed i s c o n n e c tw i t h e a c ho t h e rm a ys h a r et h es 锄eb o t t o ml i n k t h e nt h e yw i l ld e c r e a s et h eb a n d w i d t ho f o v e r l a y , s ot h et o p o l o g i c a ls t r u c t u r eo fb o t t o ml i n kb e c o m e sv e r yi m p o r t a n tw h e n c o n s t r u c t i n g 锄o v e r l a y i nt h i sp a p e r , w er e s e 疵ht h eo v e r l a yi na p p l i c a t i o nl a y e r , a n a l y z et h ec h a r a c t e r i s t i c so fc u r r e n tm u l t i e a s tp r o t o c o li na p p l i c a t i o nl a y e rb a s e do i l o v e r l a y , a n dp r o p o s ean e wm e t h o di nc o n s t r u c t i n go v e r l a y i nt h ep l o c e d u r eo f c o n s t r u c t i n gm u l t i e a s tf r e ei nt h i sn e wm e t h o d , t h et e c h n o l o g yo fd i s t a n c ee s t i l l 3 a t i o ni s a d o p t e dt on l e a s u l et h ep o s i t i o no f d e s t i n a t i o nh o s t i n f o r m a t i o no f b o t t o ml i n ki sd e d u c e d b yu s i n gah e u r i s t i ca l g o r i t h mt oe o n s t n l e tt o p o l o g i c a lg r a p ho f b o t t o m 眦t h e no v e r l a y i sc o l l s l i u c t c d e x p e r i m e n tr e s u l t ss h o wt h a tt h i sn 删m e t h o dc o u l da v o i dl i n k 谢t hh i 曲 l o a da n du t i l i z et h eb a n d w i d t ha d e q u a t e l y i s l a n dm u l d e a s t ( 呻i s 锄i n t e g r a t ei d e ao fi pm u l t i e a s ta n da p p f i e a t i o nl a y e r m u l t i e a s t a p p l i c a t i o nl a y e rm u l t i e a s ti se x e c u t e da m o n gf i e l d s ，w h i l ei pm u l t i e a s ti s e x e c u t e di ne a e hf i e l d i nt h i sp a p e r , w ei m p r o v ei mb yu s i n gt h em e t h o do fo v e r l a y c o n s t l u c t i o no nt h ea p p l i c a t i o nl a y e rm u l t i e a s ta m o n gf i e l d s ，s p e e i f yt h eo p e r a t i n g m c e l a a n i s mo fm e m b e r si nm u l f i e a s tg r o u p ，t h em e c h a n i s mo fj o i n , l e a v e ，e l e e t i o nf o r 重庆邮电大学硕士论文 m e m b e rn o d ea n dt h er e c o v e r ym e c h a n i s mo fo v e r l a y e x p e r i m e n tr e s u l t so ft h i sn e w m e t h o ds h o wt h a tt h ea v e r a g el o a do fl i n kh a sag r e a ti m p r o v e m e n tb y s a c r i f i c i n gt i t t l e e n d - t o - e n dd e l a y 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 , o v e r l a y , i s l a n dm u l f i c a s t 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研 究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人 已经发表或撰写过的研究成果，也不包含为获得重废整电太堂或其他教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均己 在论文中作了明确的说明并表示谢意。 学位论文作者签名：1 嚷讪, 9 -签字日期：) 夕年6 月f 1 日 学位论文版权使用授权书 本学位论文作者完全了解重废监虫太堂有关保留、使用学位论文的规 定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅 和借阅。本人授权重废鲣电太堂可以将学位论文的全部或部分内容编入有关 数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：滚毛导师签名：刍勘根 签字日期：9 7 年莎月l 1 日 签字日期：五卯7 年月厂日 重庆邮电大学硕士论文 第一章绪论 第一章绪论 本章首先介绍传统l p 组播存在问题，及应用层组播所具有的优势和存在的问 题；然后介绍应用层组播技术的研究现状，列举现有的国内外应用层组播协议，并 简要分析了它们各自的特点；接着阐述本文要研究和解决的问题，论文的创新工作； 最后介绍本文的组织结构。 1 1 研究背景 在i n t e r n e t 上，多媒体业务如流媒体、视频会议和视频点播等应用日益广泛。 点对点传输的单播方式已经不再能适应“单点发送、多点接收”的业务，因为服务 器必须为每一个接收者提供一份相同内容的i p 报文拷贝，使得网络上重复传输大量 相同内容的报文，占用了大量资源。在这种情况下组播技术( m u l t i c a s t ) 应运而生， 它的出现解决了网络数据冗余的问题，尤其对于音频、视频数据，可以节省大量网 络资源，解决一个主机向多个接收者发送数据的问题【1 】。图1 1 显示了在单播和组 播两种通信模式下，对于“单点发送、多点接收”应用的实现方式。 1 1 1i p 组播 ( 惮 接收者 ( b 盥播 接收者 图1 1 单播与组播 i p 组播将一个l p 报文向一个“组播组”传送，组播组可以包含零个或多个主机， 由一个单独的i p 地址( d 类地址) 标识。除了目的地址部分，组播报文与普通i p 报文 没有区别。i p 组播提供不可靠的、尽力而为( b e s t e f f o r f ) l 搬务。 传统的i p 组播基于开放的服务模型，对主机和用户创建组播组、发送、接收组 播数据没有限制，不提供任何接入控制。组播组的成员可以动态变化，主机有权选 重庆邮电大学硕士论文 第一章绪论 择加入或者退出某个组播组，主机可以加入多个组播组，也可以向自己没有加入的 组发送数据。希望接收到组播数据的主机通过与运行i g m p ( i n t e r n e tg r o u p m a n a g e m e n tp r o t o c o l 协议的路由器交互加入组播组，加入之后就能接收到组播 源点发送的数据。 i ) i p 组播分发树生成算法 为了向所有接收者传递数据，一般采用组播分发树描述i p 组播在网络里经过的 路径，组播分发树有三种基本类型：泛洪树、源基树、共享树。 泛洪树( r o o d i n g ) 是最简单的组播生成树算法，其基本原理是：路由器收到组 播数据包后，首先判断是否是“首次收到”，如果是，那么将其转发到其它所有接口； 如果不是，则抛弃该数据包。洪泛法不适用于i n t e m e t ，因为它将产生大量重复报 文，而且“首次收到”列表可能很长，占用内存多，并且不能保证对相同数据包只 接收一次。 源基树也称为基于信源的树或最短路径树( s p t ：s h o r t e s tp a t h t r e e j 。它是以组 播源为根构造从根到所有接收者路径都最短的分发树。如果组中有多个组播源，则 必须为每个组播源分别构造组播树。采用s p t 有利于网络中数据流量的均衡，并且 s p t 树中端到端的时延性能较好，有利于流量大、时延性能要求较高的实时媒体应 用。s p t 的缺点是：要为每个组播源构造各自的分发树，构造s p t 的开销相对较大。 共享树也称为r p r e n d e z v o u sp o i n t ) 树，每个组播组有个共用根汇聚 点，并以r p 为根建立分发树。同一组播组的组播源将所要组播发送的数据单播到 r p ，再由r p 向其它成员转发。共享树在路由器所需存储的状态信息的数量和路由 树的总代价两个方面具有较好的性能。当组的规模较大，而每个成员的数据发送率 较低时，使用共享树比较适合，但当通信量大时，由于共享树将导致流量集中，根 节点附近链路将成为系统瓶颈。 2 ) i p 组播路由协议 组播路由协议的任务就是构造组播树，根据对网络中的组播成员的分布和使用 的不同，组播路由协议分为两类：密集模式( d m ，d e n s em o d e l ) 路由协议和稀疏 模式( s m ，s p a r s em o d e l ) 路由协议。 d m 路由协议通常用于组播成员较为集中，数量较多，网络中有少数发送者和 大量的接收者并且有足够带宽的链路环境，比如公司或园区局域网。d m 路由协议 有：距离向量组播路由协议( d v m r p ) 、组播o s p f 协议( m o s p f ) 和协议无关组播协 议密集模式【p i m - d m ) 等。这类协议构造从发送者到接收者的最短路径。 s m 路由协议适用于组成员稀疏分布，接收者比较少，发送者接收者位于分散 地域、大型异构的互联网环境。s m 路由协议有：基于中心的分布树协议( c b t ) 和协 议无关组播协议稀疏模式( p i m - s m ) 等。这类协议构造从r p 到接收者的最短路 2 重庆邮电大学硕士论文 第一章绪论 径。 3 ) i p 组播存在的问题 目前l p 组播的服务模型和协议存在着一些问题，使得i p 组播至今没有能在 i n t e r n e t 上得到广泛部署1 2 l 。一方面，从因特网服务提供者( i s p ) 的角度看，目前的 i p 组播不能很好的适应商业应用的要求： a ) 组播数据包的复制和转发都由路由器来完成，这就需要路由器对组播功能的 支持，如果现有的设备不支持组播，就需要更换设备，增加了商业运营成本。 b ) 一些使用共享树组播路由协议，如p i m s m 和c b t 的i s p 面临跨越组播管理 的问题：如果r p 和其它组播源点不在同一个域内，难以进行流量控制和拥塞控制； i s p 对其它域中的r p 的服务没有控制能力；当需要跨域的组播服务时，i s p 之间必 须进行协调。 c ) 组播代价的问题，组播实施和管理比单播要复杂和困难的多，因此只有使用 它节省的带宽大大超过它的实施代价时才有商业价值。 d ) i p 组播还没有成熟的商业计费模型。 另一方面，i p 组播服务模型本身还存在一些有待解决的技术问题： a ) 要求路由器保存每个组的状态，不仅破坏了最初网络设计的“无状态”原则， 也带来了巨大的复杂性，限制了系统的可扩展性。 b ) l p 组播服务模型没有组播组管理机制，如缺乏组创建的管理，没有对接收者 和数据传输的授权机制，发送者可以随意传输数据而不需要进行任何身份验证和注 册工作，主机可以动态加入或离开组播组，发送者不能阻止其它发送者也选用同样 的地址。缺少访问控制机制会带来很多问题：比如恶意的泛洪攻击，当大量无用的 数据传输到组播组中会导致拥塞和报文丢失；因为没有组创建机制，组播地址可能 发生冲突。 c ) 组播的安全问题。由于很多防火墙不能识别i p 组播使用的d 类i p 地址，目 前的解决办法是使用隧道技术来穿越防火墙，这样在部署组播服务的同时也造成一 些安全漏洞。 d ) 组播服务质量问题。i p 组播基于u d p 协议，遵循传统的在单播的情况下得到 很好执行的“路由与传输分离”的原则，只提供一种尽力而为的服务，要想在它之 上实现更高质量的服务，例如可靠性、拥塞控制和流控制等这些功能，比在l p 单播 上实现要困难很多。 e ) 可扩展性差。要求路由器保持每个组播组的状态信息，而这些d 类地址不能 很好的聚合，组播组的数量一旦大量增加，必然增加路由器存储和处理开销。 o 缺乏灵活、可扩展的地址分配机制。节点不能有效地发现一个立即可用的组 播地址，而只是随机的选取一个来使用，这样随着组数目的增加，组播地址冲突的 3 重庆邮电大学硕士论文 第一章绪论 可能性也随之增加；使用d 类地址作为组播地址，可能面临地址空间用尽的问题。 g ) 域间组播路由协议对组播技术大规模的实施有重要的作用，它使i s p 可以将 它们的网络互连同时隐藏各自网络的拓扑结构，但是i p 组播还没有成熟有效的域问 组播路由协议。 h ) 为了降低复杂性，人们提出了单源点组播应用，e x p r e s s 3 和s s m l 4 1 属于这一 范畴，发送者使用一个本地唯一组地址加上自己的l p 地址来唯一标识一个组，它解 决了组地址的分配问题，但不是所有的应用都是单源点组播，也不能简单地将其转 变成多个单源点的应用，因此人们仍然有必要寻求更加普遍适用的解决方案。 1 1 2 应用层组播 由于一系列技术和非技术方面的原因阻碍了i p 组播在i n t e r n e t 中的配置，因 此近年来一些研究者重新考虑在网络层实现组播服务是否是最为合适的选择，并且 提出了应用层组播( a p p l i c a t i o nl a y e rm u l t i c a s t ) 方案作为i p 组播服务的一个替代 方案。正如名字所说明的，这是一种在应用层提供的组播方案，组播服务在应用层 实现，也就是说组播服务在端节点实现而不是在网络路由器中实现。 图1 2 i p 组播和应用层组播比较 应用层组播的基本概念如图1 2 所示，i p 组播的数据沿着物理链路复制和转发 f 图1 2 ( a ”，而应用层组播的数据则在主机实现复制和转发( 图1 2 ( b ，c ，d ) ) ，数据包 沿着逻辑链路转发，多条逻辑链路可能经过同一物理链路。由于应用层组播协议可 能需要在同一条链路上多次发送相同的数据，因此这种方案相对于i p 组播来说效率 要低一些。从逻辑上说，端节点形成了一个覆盖网络( o v e r l a yn e t w o r k l 。 4 重庆邮电大学硕士论文 第一章绪论 在应用层实现组播服务可以避开在网络层实现组播功能的许多难题： a ) 应用层组播的状态在主机系统中维护，不需要路由器保持组播转发状态，解 决了i p 组播业务的扩展性问题，网络可以支持大量的组播组； b ) 组播应用可以随时部署，不需要网络设备的升级和功能扩展，应用层组播可 以根据所承载的不同业务的需求建立不同的覆盖网络； c ) 简化组播的控制、可靠性以及安全性等功能的实现。建立在网络连接之上的 应用层组播可以使用t c p 、u d p 服务，如可以利用t c p 的可靠性和拥塞控制简化 组播的可靠性和拥塞控制，利用i p s e c 提供安全性保障等。 当然，应用层组播也有许多局限： a ) 端系统对底层i p 网络了解有限，节点参与组网时，只能通过探测获得一些网 络性能参数，如带宽和时延等，以启发式的方式建立覆盖网络，逻辑链路不能较好 地利用质量较好的底层网络资源，覆盖网的多条链路可能经过同一条物理链路。 b ) 相对于路由器而言，端系统稳定性较差，主机性能不高，复制和转发工作由 应用层通过软件实现效率较低。 c ) 为了弥补l p 组播在安全性和可靠性方面的缺陷，应用层组播还要增加提供安 全性和可靠性保证的机制，进一步消耗了主机的资源。 d p e n d a r a k i s 等人在文献【5 】中通过仿真实验比较了应用层组播和l p 组播的效 率，在一个有6 0 0 0 个节点的网络中，覆盖5 0 个随机节点的应用层组播分发树的代 价大约是i p 组播分发树的1 5 倍，其中的代价是指报文传输通过的链路数目。因此， 尽管在i p 层提供组播服务是一种高效得服务，但是在i p 组播服务没有广泛提供的 前提下，应用层组播是值得研究和应用的。 总之，应用层组播的效率要低于i p 组播，但是可以以较少的代价、较好的性能 快速地在i n t e m e t 中配置组播服务。 1 2 研究现状 应用层组播系统的研究目前是学术界的一个研究热点，许多研究机构都提出了 自己的应用层组播协议。 2 0 0 0 年，y c h u 等人提出基于n a r a d a 组网协议的e s m ( e n ds y s t e m m u l t i c a s t ) t 6 ；j j a n n o t t i 等人提出了o v e r c a s t 7 1 ，它通过将新加入成员放到远离 根的位置上，从而最大化发送者到接收者之间链路的带宽，并提供了一种可靠的、 可扩展的组播系统，适合于对带宽要求较高的应用；y a t i nc h a w a t h e 在他的博士 论文中提出了s c a t t e r c a s t p l 系统，提出了基于服务器一客户端两层结构的组播 系统；p f r a n c i s 发表了y o i d 9 组播系统的相关论文。 5 重庆邮电大学硕士论文第一章绪论 2 0 0 1 年，由d p e n d a r a k i s 等人提出一种集中式应用层组播的架构 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 ) 【5 l ，它适用于较小规模的组播 组，建立共享组播树，新成员加入只需获得部分组成员的信息；h b m p o 由v r o c a 等人于同年提出，这也是一种集中控制的协议，但是加入者必须知道全部组成员的 信息；s q z h a n g 发表基于p 2 p 网络的b a y e u x 11 】，它给每个p 2 p 节点分配一个 唯一的节点号，从节点号的最后一位向前，按顺序一位一位的匹配来进行报文路由； lm a t h y 提出t b c p 1 2 ，加入者计算与每个可能父母节点之间的配置方案，取最优 的方案加入，同时考虑到尽量减少汇聚时间：s r a t n a s a m y 提出了基于p 2 p 网络 的c a n p 3 ，它适用哈希函数，将组播组的地址映射到笛卡尔坐标空间中，使每个 组播组都对应一个小的c a n 网络，在小c a n 网络上通过泛洪实现组播转发。 2 0 0 2 年，h m t p 被提出【1 4 】；s u m a nb a n e d e e 发表了基于n i c e ly 5 应用层组 播的论文，提高组成员的可扩展性；m c a s t r o 发表了s c f i b e l l a ，s c d b e 建立在 p 2 p 网络p a s t r y p 7 之上，它通过从第一位往后对节点号和组号按位匹配来确定组播 树的路径，具有较好的扩展性，另外它借助底层p a s t r y 网络可以进行动态的自组织 来适应网络条件的变化。 2 0 0 3 年，m h e f e e d a 提出了p r o m i s e 1 m ，这也是在p a s t r y 网络之上构建的 组播系统，它的实现思想是：一个接收者可以从多个发送者处得到需要的数据，它 不需要构建组播树，当节点需要数据时，由低层p 2 p 系统查找到一系列满足要求的 发送者，接收者再从中挑选一些较好的发送者，并行向接收者发送组播数据；d t r a n 提出了基于p 2 p 的层次型的应用层组播系统z i g z a g 【1 9 j 。 2 0 0 4 年，a h m e ds o b e i h 提出一种基于环而非组播树的应用层组播协议 v r i n g m ，与n l c e 相比，它减少了环的控制代价；s h u j uw u 对组播协议的动态适 应性能进行研究，在i e e e 上发表了文章，与h m t p 相比，它能更好地探测出节点的 失效，并能更有效的进行修复，具有更好的鲁棒性；r o i em e l a m e d 也提出适用于 动态环境下的组播系统a r a n e o l a w 。 目前，应用层组播的研究集中在以下几个方面： 1 2 1 应用层组播体系结构 目前主要有两种系统结构来实现应用层组播： 1 ) 对等型( p e e r - t o - p e e r ) 组成员节点都是平等的，节点之间通过自组织算法组织成控制网格( m e s h ) 和数 据分发树，每个节点仅维护自身参与组的状态信息，组播服务功能以软件形态集成 在参与会话的节点中。 6 重庆邮电大学硕士论文 第一章绪论 2 ) 代理型( p r o x y - b a s e d ) 组播服务功能由增值服务提供商根据一定策略在互联网的特定位置部署可以 提供附加服务的代理节点来完成。端节点与自己拓扑相邻的代理节点相连，并且通 过单播连接收发数据报文，从某种程度上来看，代理节点类似于组播路由器。 1 2 2 应用层组播协议 应用层组播协议不仅要提供有效的数据分发树，还要针对节点的动态性提供可 靠的组管理算法，协议设计强调在动态网络环境下维持网络的稳定性。 根据构建分发树的策略，可以将应用层组播协议分成集中式和分布式两类。集 中式协议假设有一个服务器知道成员之间的关系，即成员之间的拓扑，然后这个服 务器运行最小延迟、最大带宽、最小代价之类的算法来计算分发树，随后将分发树 中节点之间的关系发布给相应的节点。显然这种方法虽然简单，但是扩展性不好， 同时存在服务器这样一个关键节点，容易出现单点故障。 分布式协议中，由每个组成员运行应用层组播协议，分布地构造分发树。为适 应系统的动态性，保证组播传输的有效性，分布式协议还引入了控制和数据两种拓 扑。控制拓- l , ( m e s h ) 中节点对之间存在多条路经，主要负责监视节点变化、维护网 络的连通性；数据拓扑( t r e e ) 就是指分发树。因此分布式协议可以分成m e s h f i r s t 和t r e e - f i r s t 两类。如果先构造m e s h ，然后再在m e s h 的基础上构建树的协议叫做 m e s h - f i r s t 协议；反之，先构建树，再在树的基础上引入额外的边形成m e s h 的协 议是t r e e f i r s t 协议。二者在性能方面表现不同，m e s h f i r s t 方案对于小型组播组来 说是高效的，t r e e - f i r s t 方案对于低时延的应用来说是不适宜的，但是可扩展性好、 对于实现高带宽需求的数据传输而言是非常有效的。 1 2 3 覆盖网络路由算法 网络路由是网络研究中的一个关键问题，路由的目标是为了寻找最优路径以进 行信息传递，提高服务质量，同时提高网络资源利用率【2 2 1 。在应用层覆盖网络中， 应用层组播路由协议设计面临的主要问题除了在广域环境下针对节点的动态性在节 点上建立必要的状态信息，并根据这些信息构建和维护优化的组播路由协议之外， 路由的目标还包括在一组给定可用带宽的m s n 节点集中，进行适当的组播路由以 尽可能充分利用网络资源，也就是以可接受的应用层性能来满足尽可能多的组播会 话数目。 7 重庆邮电大学硕士论文 第一章绪论 1 3 论文内容和相关工作 本文在对现有应用层组播协议进行深入研究的基础上，提出新的应用层组播覆 盖网络算法，并将i p 组播和应用层组播相结合提出了新的组播协议。论文的具体研 究和实际工作包括以下几个方面： 1 ) 分析了i p 组播的工作原理、组播路由协议，结合组播路由的现状深入分析了 l p 组播不能广泛开展的原因。 2 ) 分析了应用层组播覆盖网络特性及具有代表性的应用层组播协议。通过一种 启发式算法构建其底层链路，并提出一种快速应用层算法构建覆盖网络。 3 ) 结合i p 组播和应用层组播提出了岛播的思想，通过仿真证明岛播系统在牺牲 少量延迟下可使链路负载能力获得较大提高。 4 ) 结合中国农业银行数据中心园区网弱电网络需求进行组播测试实验。 1 4 论文结构 本文共分六章，具体内容安排如下： 第一章为绪论，简单介绍了应用层组播的研究背景及研究现状，接着阐述了本 文要研究和解决的问题。 第二章结合覆盖网络对典型的应用层组播协议进行分析。 第三章通过启发式算法构建底层链路拓扑图，提出新的应用层组播覆盖网络算 法，并仿真实现。 第四章将i p 组播与应用层组插相结合提出新的组播协议。 第五章结合实际进行组播测试实验。 第六章对整篇论文进行总结，并对未来工作进行展望。 8 重庆邮电大学硕士论文 第二章基于覆盖网络的应用层组播路由协议 第二章基于覆盖网络的应用层组播路由协议 2 1 覆盖网络概述 2 1 1 覆盖网络的定义 覆盖网络( o v e r l a y ) 的基本含义就是在现有的因特网上构建一个完全位于应用 层的网络系统。覆盖网络服务不是由因特网服务提供商( i n t e m e ts e r v i c e p r o v i d e r ) 提供的，而是由一种新型的服务提供商提供，它存在于因特网基础设施 和应用程序之间，利用i s p 提供的服务来向其用户提供更加优化的服务。可以认为， 覆盖网络是分布在因特网上的一组提供服务的主机的集合，它们为一个或多个应用 程序提供下层的基础设旌，在某种程度上转发和处理应用程序的数据，所采用的方 式与目前因特网上的不同；由第三方运营和管理，不是当前因特网体系结构的一部 分。 2 1 2 覆盖网络的技术优势 覆盖网络的特点决定了它的技术优势，应用层组播基于覆盖网络实现是因为以 下这些原因： a ) 覆盖网的实现无需改变原有的软、硬件，具有较好的可操作性。 b ) 在覆盖网络中部署新的功能，无需在每个节点上实施部署，只要在需要该功 能的节点上部署。 c ) 覆盖网络上的应用无需了解底层网络的拓扑结构。 d ) 覆盖网络中的节点可以根据自己的需求选择最合适的链路，具有较好的适应 性。 e ) 可以在覆盖网节点上部署附加的控制机制，使覆盖网络具有更好的健壮性。 例如在两个覆盖网节点之间完全可能存在两条互相独立的虚拟链路，如果其中之一 发生错误而失效还可以通过备用链路继续节点之间的通信。 o m 于覆盖网节点可以是完成不同任务的计算机，比较容易实现服务定制功能。 g ) 覆盖网报文可以像t c p i p 报文一样处理，而无须其它特殊的处理机制。 9 重庆邮电大学硕士论文第二章基于覆盖网络的应用层组播路由协议 2 1 3 覆盖网络路由的特殊性 由于覆盖网络是构建在底层i n t e m e t 单播基础之上，从网络设计的角度来看， 应用层覆盖网络组播和传统j p 组播在网络代价模型以及路由策略上有所不同。这些 主要的不同之处包括： 1 1 网络可达性 应用层覆盖网络是一个全互连的网络，每个节点都可以通过单播连接到达其它 节点，因此覆盖网络的拓扑结构是一个完全图。而i p 组播中路由器之间通过底层的 实际物理链路连接，网络拓扑结构不是一个完全图。这样，对于一个有n 个节点的 应用层组播覆盖网络而言，将有n n - 2 个不同的支撑树。相对于传统i p 组播来说，覆 盖网络组播路由寻找最优支撑树的问题空间更为庞大，给路由算法的设计带来严峻 的挑战。 2 ) n 络代价 i p 组播中，网络的代价通常由单个链路的代价之和来决定，这对于需要铺设物 理链路或者是从其它i s p 租借物理链路的服务商来说显然是正确的。但是从应用的 角度来看，覆盖网络的代价是由从服务商获得的骨干网络接入带宽所决定的。在设 计和选择路由策略的时候，这种不同的代价尺度有很深的影响。 3 ) 路由限制 i p 组播路由通过最短路径树( s p t ) 最小化从源到每个目标节点的时延，也就是减 少传输组播会话所需的链路，构造应用层覆盖网络路由需要根据不同的应用需求决 定相应的策略。例如对于视频会议、网络游戏以及分布交互仿真等应用来说，任意 两个节点之间的覆盖网络时延满足事先约定的时延约束条件的路由策略是一个高质 量的策略。 覆盖网络路由中需要管理的主要资源是在参与覆盖网络组播服务的m s n 节点 与骨干网络的接入带宽资源。节点的接入带宽资源限制了该节点能够支持的组播会 话数目，所有参与组建覆盖网络的节点的接入带宽总和限制了系统所能支持的组播 会话总数目。因此，应用层组播路由算法需要优化使用这些带宽资源以同时满足尽 可能多的组播会话需求。另外，应用层组播路由算法还要确保在组播会话中不包含 特别长的路径。通常，限制节点对之间的最大时延的目标和优化利用网络带宽资源 的目标是互相矛盾的。 图2 1 描述了采用不同的覆盖网络组播路由策略时，平衡利用节点接入带宽与 端到端时延之间的相互关系。具有最小端到端时延f 直径) 的分发树通常在核心节点 处集中了过高的流量，如图2 1 ( a ) ，而平衡利用接入带宽的分发树又具有过长的路 1 0 重庆邮电大学硕士论文 第二章基于覆盖网络的应用层组插路由协议 径，如图2 1i b ) 。因此，高质量的组播路由策略需要在这两个性能参数之间进行适 当的折衷，如图2 1f c ) 。 一 p ， -、-rj i 、 ia m ， -j-j r1r1 i 曩) 直径优化 ( b ) 负载平衡优化( c ) 直径- 负蓑平衡综合优化 图2 1 直径优化与负载平衡优化策略 2 2 现有的典型的覆盖网络组播协议 2 2 1 s h - fir s t 协议n a r a d a n a r a d a 是最早提出的应用层组播策略之一。n a r a d a 首先在组成员之间建立 一个具有网状连接的网络拓扑并不断优化网状拓扑；随后建立基于网状拓扑的伸展 树，每个伸展树的根都对应着一个数据源，由于最终得到的组播树是建立在网状拓 扑的基础上，因此建立良好的网状拓扑对于组播树是至关重要的。 1 1 网状拓扑的构建 n a r a d a 定义了一个特定的主机，称为汇聚点( r p ，r e n d e z v o u sp o i n t l 。被用 来启动新成员节点的加入过程。当一个新成员节点想要加入组播中，它首先获得网 状拓扑中的成员列表，该列表能够从r p 中获取。因为r p 保存着所有加入组播的成 员节点的状态信息，新成员节点从列表中随机选择一些组成员向它们发送加入消息。 只要有一个组成员节点接受了新成员节点的加入请求，愿意成为新节点的邻居，加 入过程就成功了。新节点加入m e s h 后，与m e s h 上的邻居节点周期性地交换它所 知道的组成员信息，无论是新节点加入还是现有成员节点离开m e s h ，组成员信息 都将被传输到m e s h 中所有其它成员。通过这种方式最终组成员都知道组内其它成 员的信息，这种状态信息的发布导致相对较高的控制负载。n a r a d a 增强了组播策 略的健壮性，但是牺牲了控制开销，因此n a r a d a 扩展性不好，只适合于小规模覆 盖网。 组成员节点会主动或被动离开拓扑。如果是主动离开，该节点在离开前将通知 其邻居节点；如果是被动离开，邻居节点只有通过一段时间内没有收到该节点的交 重庆邮电大学硕士论文 第二章基于覆盖网络的应用层组播路由协议 换信息才能知道节点失效。节点的离开会导致网络拓扑的分裂，n a r a d a 具有自动 修复的能力。以图2 2 来说明网状拓扑的修复。当节点d 失效后，覆盖网被分成两 个部分；经过一段时间，节点a 、b 和c 发现无法从节点e 和f 中收到消息，因此 断定网络已经裂开。每个节点把没有收到更新消息的节点记录下来，并且随机地检 测这些节点建立新的连接并修复分裂。 节点d 失效 _ _ _ 图2 2n a r a d a 中覆盖网的修复 2 ) 数据传输路径 n a r a d a 在网状拓扑上运行距离矢量协议。n a r a d a 采用类似于b g p 的策略 避免无穷跳的问题，每个成员不仅保存着到其它任何成员的路由代价，同时保存着 相应的路由路径。当某个成员节点需要发送数据时，建立一棵以该成员为根节点的 伸展树。建立伸展树的方法就是采用d v m r p 协议反向构建接受数据的成员与根节 点的最短路径，即成员m 通过n 接受根节点s 的数据包仅当n 是从m 到达s 的最 短路径上的下一跳，而且m 将数据发送到使用m 作为到达s 的下一跳的所有邻居 节点。 3 ) 网状拓扑的性能优化 由于成员加入时在选择成员节点时是随机的，又是随意的加入和离开，组成员 关系随时可能改变，底层网络条件、路由和负载状态也是动态变化的，因此网状拓 扑需要动态地进行优化。成员节点互相之间随机地进行检测，通过计算u t i l i h 值来 决定是否增加新的连接，同时成员不断地检测现有连接的u t i l i t y ，丢弃被认为是无 用的连接。 2 2 2t r e e - fir s t 协议o 、，e r c a s t 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 侧重于实现组播数据的可靠分发。 o v e r c a s t 是为那些具有单个业务源且期望具有高带宽的应用而设计的。 o v e r c a s t 的目标就是要最大化从根到所有节点之间的带宽。树的建立过程如下， 在o v e r c a s t 中假定系统中有一个注册点能够知道组成员的信息。当有一个新的成 员希望加入到组内时，首先通过注册点获得树的根节点的信息。随后把根节点作为 当前节点开始循环的寻