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

山东师范大学硕士擘位论文 摘要 网络及其应用需求的发展推动着新的通讯方式不断产生，组播就是其中的一个产物。 组播是指从一点到多点或者从多点到多点的一种组通信机制它是一种有效的数据传输方 式，发送的同一数据包在相同链路中只传输一次，与单播相比，大大减少了数据包在网络 传输中的冗余。组播功能作为一种基本的通讯方式最开始被建议在网络层实现，但由于一 些技术和非技术因素的影响，i p 组播在i n t e r n e t 范围内一直没有得到大规模的配置和应 用。近年来，研究学者们开始分析在网络层实现组播功能的局限性，并提出了应用层组播 ( a l m ) 作为i p 组播的替代方案。a l m 最大的优势在于组播协议可以运行在覆盖网络 ( o r e r l a y ) 上，不需要改变基础的网络设施便可以为用户提供组播功能。 随着对应用层组播研究的不断深入和细化，我们发现a l m 在技术和应用方面还存在各 种各样的问题，如中间节点负载过重问题、网络瓶颈问题和异步移动用户问题等。针对这 些问题，本文分析了当前几种典型的应用层组播协议及其分类，并对其性能进行了详细的 分析，针对o v e r l a y 上应用层组播所存在的几个问题，提出了相应的网络优化机制，论文主 要工作有以下几点： 针对应用层组播中的中间节点负载过重的问题，论文分析了影响节点负载的两个重要 因素：组播组的个数和组中接收者的数量，并把显式组播( x c a s t ：e x p l i c i tm u l t i c a s t ) 的思想，分别与动态规划策略和贪婪算法结合运用，提出两种低负载的基于o v e r l a y 的优化 应用层组播树的策略，即l l d p v 也盯和l l g p a l m t 实验分析表明，我们所提出的节点减负 策略能使网络资源达到更有效的利用。 针对应用层组播网络瓶颈问题，论文从普通和异构网络两个角度分别进行了研究，提 出两种应用层组播网络瓶颈消除策略，即b n f p a l m 和b n f p h a l m 通过分析和评估发现，我 们所提出的网络瓶颈消除策略有效地消除了网络瓶颈，减少了网络资源的浪费，提高了网 络的可靠性和数据传输效率 针对o v e r l a y 上异步移动用户问题，本文从用户请求的时间相关性和o v e r l a y 节点自身 的缓存能力入手，提出了一种基于异步移动用户的自适应覆盖网络应用层组播算法来解决 应用层组播用户的移动问题，即从l m p 删。此算法不仅考虑到了应用层组播接收者的移动 问题，而且考虑到了其中数据源的移动问题，并在组播成员节点间创建了一棵逻辑组播树 来转发数据，适应节点的移动性，尽力避免数据重传，节省了网络资源。此策略具有很强的 可行性和有效性。 此外，为了评估策略的性能，我们运用算法复杂度分析和网络模拟器n s 一2 从不同的角 度对本文所提出的策略进行了详细的分析和实验，仿真结果表明，我们的策略有效地改善 t o v e r l a y 上应用层组播的性能，尤其是低负载的基于o v e r l a y 的优化应用层组播树的 山东师范走荦硕士擘住论文 l l d p a l m t 策略，以及基于异步移动用户的自适应o v e r l a y 应用层组播算法a a l m p a m u ， 在网络的传输效率和可扩展性等方面都表现出了令人满意的效果。 希望本文所做的工作能够对覆盖网络上应用层组播的研究和发展起到一定推动作用。 关键词：覆盖网络。应用层组播。节点负载，瓶颈，移动用户 分类号：t p 3 9 3 山东师范大学项士擘位论文 r e s e a r c h e so na p p f i c a f i o nl a y e rm u l t i c a s ts t r a t e g yb a s e do i lo v e r l a y a b s t r a c t a st h ei n t e r n e t g r o w su p ，t h ed e v e l o p m e n to fa p p l i c a t i o nr e q u i r e m e n t si m p e l st h e p r o d u c t i o no fn g wc o m m u n i c a t i o nm e a n s ，o fw h i c hm u l t i c a s t i n gi so n e a tf i r s t , t h em u l t i c a s t f u n c t i o n a l i t yw h i c hw a sab a s i cc o m m u n i c a t i o nm e a n sw a sp r o p o s e dt ob ea d d e dt ot h en e t w o r k l a y e r d u et oav a r i e t yo ft e c h n i c a la n dn o n - t e c h n i c a lr e a s o n s ，t h ed e p l o y m e n to fi pm u l t i c a s ti n i u t e r n e th a sb e e nl i m i t e da n ds p a r s e t h e r e f o r es o m er e s e a r c h e r si nt h er e c e n tp a s th a v er e v i s i t e d t h ei s s u ew h e t h e rt h en e t w o r kl a y e ri st h eb e s tl a y e rf o ri m p l e m e n t i n gm u l t i c a s tf u n c t i o n a l i t ya n d h a v ep r o p o s e da p p l i c a t i o nl a y e rm u l t i c a s t ( 札m ) a san e wa p p r o a c h t h eb a s i ca d v a n t a g eo f a l mi st h a ti tr e q u i r e sn oi n f l a s l l u c t l es u p p o r ta n dc 孤b ee a s i l yd e p l o y e di nt h ei n t e r n c t w i t ht h ed e t a i l e da n di n - d e p t hr e s e a r c hf o ra p p l i c a t i o nl a y e rm u l t i c a s t ，w cf o u n dt h a tt h e r e a r eav a r i e t yo fp r o b l e m sa b o u ta l mi nt e c h n o l o g ya n da p p l i c a t i o n s , s u c ha st h ei n t e r m e d i a t e n o d e so v e r l o a d i n g ，n e t w o r kb o t t l e n e c k sa n da s y n c h r o n o u sa n dm o b i l eu s e r se t e t h e r e f o r e , t h i s p a p e ra n a l y z e st h ec u r r e n ts e v e r a lr e l a t i v e l yp o p u l a ra l mp r o t o c o l sa n dt h e i rc l a s s i f i c a f i o mw e a l s od oad e t a i l e de v a l u a t i o nf o rt h e i rp e r f o r m a n c e , e s p e c i a l l yf o rt h e i rr e s p e c t i v el i m i t a t i o n s m e a n w h i l ef o rs e v e r a le x i s t i n gp r o b l e m so f t h ea l mo nt h eo v e r l a yn e t w o r k s ，w es u p p o s es o m e c o r r e s p o n d i n gn e t w o r ko p t i m i z a t i o nm e c h a n i s m s ： f o rt h eo v e r l o a d i n gp r o b l e mo fi n t e r m e d i a t en o d e si na l mn e t w o r k s ，t h i sp a p e ra n a l y z e s t h et w oi m p o r t a n tf a c t o r st h a ti m p a c tt h ea l mn o d el o a di nc h a p t e rt l l 托e ：t h en u m b e ro f m u r i c a s tg r o u p sa n dt h en u m b e ro fr e c i p i e n t so ft h eg r o u p a n dt h a t c o m b i n i n gt h ei d e ao f e x p l i c i tm u l t i c a s t ( x c a s t ) r e s p e c t i v e l yw i 也t h ed y n a m i cs t r a t e g ya n dt h eg r e e d ya l g o r i t h m , w e p r o p o s et w ok i n d so fl o wl o a do v e r l a y - b a s e da l mt r e eo p t i m i z a t i o ns t r a t e g y , n a m e l y l l d p k a l m tl l g p b l m t t h ea n a l y s i sr e v e a l st h a to u rm e c h a n i s m sf o re a s i n gn o d e sw o u l d e n a b l en e t w o r kr e s o u r c e st ob eu s e dm o r ee f f i c i e n t l y i nv i e wo f t h eb o t t l e n e c kp r o b l e mo f a p p l i c a t i o nl a y e rm u l t i c a s t ，w er e s e a r c hi tf r o mt w o a s p e c t sr e s p e c t i v e l yo fag e n e r a ln e t w o r ka n dah e t e r o g e n e o u so n ei nc h a p t e rf o u ra n dp r o p o s e t w ok i n d so f m e c h a n i s m st oe l i m i n a t eb o t t l e n e c k si nt h ea l m n e t w o r k s n a m e l yb n f p u 山m a n db nf p 、h a i ，m t h r o u g h a n a l y s i sa n de v a l u a t i o nw ef o u n dt h a to u rm e c h a n i s m se l i m i n a t e b o t t l e n e c k si nt h ea l mn e t w o r k se f f e c t i v e l y ，a n dt h a tt h e yr e d u c et h ew a s t o f n e t w o r kr e s o u r c e s a n di m p r o v et h en e t w o r k sr e l i a b i l i t ya n de f f i c i e n c yo f d a t at r a n s m i s s i o n f o rt h ep r o b l e mo f a s y n c h r o n o u sa n dm o b i l eu s 懿o nt h eo v e r l a y , w er e s e a r c hi tf r o mt w o a s p e j 2 t sr e s p e c t i v e l yo f t h e t i m e - r e l a t e do f r e q u e s t i o nf r o mt h eu s e r sa n dt h ec a c h e a b i l i t yo f o v e r l a y n o d e si nc h a p t e rf i v ea n dp r o p o s ea na d a p t i v ea l m a l g o r i t h mb a s e do na s y n c h r o n o u s a n dm o b i l eu 鞭：r so no v e r l a yt os o l v et h ep r o b l e m , n a m e l ya a l m p k a m u t h i sa l g o r i t h mt a k e s m 山东师范大学硕士学位论文 i n t oa c c o r n tn o to n l yt h ea l mm o b i l er e c e i v e r , w h i c ha l s ot a k e si n t oa c c o u n tt h em o v e m e n to f d a ms o u r c e s ，a n dt h a tm e m b e r so f t h em u l t i c a s tt r e en o d e sc o u l dc r e a t eal o g i c a lm u l t i c a s tt r e et o t r a n s m i td a t at om e e tt h em o b i l en o d e s ，w h i c ht r yt oa v o i dd u p l i c a t ed a t aa n ds a v en e t w o r k r e s o r r c e s t h es t r a t e g yh a ss t r o n gf e a s i b i l i t ya n de f f e c t i v e n e s s f u r t h e r m o r e ，i no r d e rt oe v a l u et h ep e r f o r m a n c eo fo u rm e c h a n i s m s , w eu s ea l g o r i t h m c o m p l e x i t ya n a l y s i sa n dn e t w o r ks i m u l a t o rn s - 2t o c o n d u c ts o m ed e t a i l e de x p e r i m e n ta n d a n a l y s i sf r o m d i f f e r e n tp e r s p e c t i v e so ft h ep r o p o s e ds t r a t e g i e s t h es i m u l a t i o nr e s u l t si n d i c a t e t h a to u rm e c h a n i s m sa r ce f f e c t i v et oi m p r o v et h ep e r f o r m a n c eo fa p p f i c a t i o nl a y e rm u l t i c a s t , e s p e c i a l l yt h el o wl o a dd y n a m i cp r o g r a m m i n gf o ra l mt r e e ( l l d p 、_ a l i v i t ) a n dt h ea d a p t i v e a l mp r o g r a m m i n gf o ra s y n c h r o n i s ma n dm o b i l eu s e r s ( a a l m p a m u ) w h i c hh a v es h o w n s a t i s f a c t i o n a lr e s u l t si nt h ed a t aw a n s m i s s i o ne f f i c i e n c ya n de x p a n s i b i l i t yo f n e t w o r k se t o w eh o p et h a tt h i sp a p e rw i l lb ea b l et op l a yac e r t a i nr o l ei np r o m o t i n gt h er e s e a r c ha n d d e v e l o p m e n tf o ra p p l i c a t i o nl a y e rm u l t i c a s tb a s e do no v e r l a y k e y w o r d s ：o vc r l a 孔a p p l i c a t i o nl a y e rm n l f i c a s t , no d el o a d , b o t t l e n e c k , m o b i l e u s e r c l a s s i t c a t i o n ：t p 3 9 3 独创声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。据 我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过 的研究成果，也不包含为获得( 注：如没有其他需要特别声明的，本栏 可空) 或其他教育机构的学位或证书使用过的材料。与我一同工作的同志对本研究所做的 任何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名：麦淋导师签字：莉镧和 j 学位论文版权使用授权书 本学位论文作者完全了解堂撞有关保留、使用学位论文的规定，有权保留并向国家 有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权堂撞可以 将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复 制手段保存、汇编学位论文。( 保密的学位论文在解密后适用本授权书) 一躲壕妙脊 山东师范大学硕士学位论文 1 1 研究背景 第一章绪论 无论是t c p i p 的发展，还是万维网( w w w ) 的诞生都印证了这样一个道理网络 应用的需求是推动网络技术发展的主要动力。随着i n t e r n c t 和计算机技术的发展，网络用 户和i n t e r n e t 技术应用表现出了新的特点：端用户计算机能力不断增强；与之对应的网络应 用需求也进一步变化。应用需求的发展推动了新的通讯方式的产生，组播就是其中的一个 产物。 如今全球个人计算机的数量在飞速的增长曾有调查显示，截至到2 0 0 6 年5 月，全球 互联网用户的数量己超过l o 亿同时，个人计算机的计算能力、存储能力、接入带宽都有 了飞速的提高。而随着计算机能力的不断增强，用户已经不再满足于仅仅在i n t e r n c t 上浏 览网页，收发邮件等基本的功能。各种新型的应用需求不断涌现，计算机的各种功能得到 了淋漓尽致的发挥。从9 0 年代中期开始，以流媒体形式出现的音频、视频经历了快速的发 展，逐渐由窄带向宽带转移，提供音频、视频内容服务的网站和访问人数急剧增加，视听质 量有了明显的改进。音频、视频的多媒体服务内容也趋于多样：如多媒体数据库、环球超 媒体信息系统、视频点播、电视会议、远程教育系统、多媒体信息检索等等 但是，各种新型应用的网络规模的不断扩大及网络信息资源的迅速增加，使网络传输 负担逐渐加重，尤其是现在比较流行的视频会议和多媒体数据传输问题，它们都要求将网 络资源传送给网络中所有对此信息感兴趣的主机，采用传统的单播技术己无法解决此类传 输问题，若采用广播技术又会造成巨大的网络报文，增加网络的传输负担，严重地影响网 络的效率，对网络资源造成了极大的浪费而组播( m u l t i c a s t ) 正是针对此类问题提出的 一种新的、高效的网络传输方案，它是面向“组”的介于单播和广播通信之间的数据传送 方式。组播的特点是能够在网络上提供单点到多点通信以及多点到多点通信。相对于单播 来说，组播可以有效的利用网络带宽，减少网络流量，提高数据传输的效率。 目前存在的组播技术主要有i p 组播和应用层组播( a l m ：a p p l i c a t i o nl a y e rm u k i c a s t ) 。 但是，i p 组播由于其自身的缺陷i l l ，如地址分配机制复杂，缺少合理的域间路由协议以及 网络支持的问题，至今没能在i n t e m c t 上进行有效的大规模的部署。针对i p 组播存在的这 些问题，近年来研究者提出了以底层网络为基础的基于覆盖网络( o v e r l a yn e t w o r k s ，简称 o v e r l a y ) 的应用层组播协议覆盖网是位于一个或多个己知网络之上的一个独立的虚拟网 络。它的主要优点在于它的架构：它不需要改变底层网络的结构，可以快速部署所需的网 络功能。在覆盖网的基础上实现组播，我们就可以把组播的实现提到应用层。于是，应用 层组播便应运而生，并得到了迅速的发展和广泛的应用。群组通信业务也随之蓬勃发展起 来，越来越多的a l m 应用和服务己经在i n t c r n e t 上兴起，并很快成为网络研究的热点。 1 2 组播技术概述 组播是从一点到多点或者从多点到多点的一种组通信机制。它是一种有效的数据传输 方式，发送的同一数据包在相同链路中只传输一次，减少了数据包在网络传输中的冗余，节约 了带宽，提高了传输效率。组播可以在网络的各个层次上实现：物理层( 例如：卫星、以太 山东师范走学硕士擘住论文 网) 、网络层( i p 组播) 、应用层( 即a l m ) 。本节主要叙述i p 组播和应用层组播这两种 传输机制。 1 2 1lp 组播技术 在i p 网络中，主机的通信可采用三种模型：单播、广播和组播。单播和广播是两种传 统的通信方式。单播( u n i e a s t ) 传输方式只允许单个网络节点一次向同一网络上的另一个节 点发送报文。单播过程如图1 1 所示，在发送者和每一接收者之间都需要单独的数据信道。 如果一台主机同时给很少量的接收者传输数据，一般没有什么问题。但如果有大量主机希 望获得数据包的同一份拷贝时却很难实现。这将导致发送者负担沉重、延迟长、网络拥塞， 因此，需要增加硬件和带宽来保证一定的服务质量。广播( b r o a d c a s t ) 通信方式则允许某个网 络节点将一个报文一次发给网上所有节点，广播过程如图1 2 所示，在m 予网内部的所有 主机都将收到源点所发的数据包，不论这些主机是否乐于接收该数据包。因为广播会给网 络带来很多脏数据甚至一些难以解决的拥塞问题，所以路由器会封锁广播通信，致使广播的 使用范围非常小，只在本地子网内有效。并且广播传输还会增加非接收者的开销。 图1 1 单播方式实现组播功能 图1 2 广播方式实现组播功能 鉴于以上两种传输机制的不足，研究者提出了i p 组播通信方式。组播过程如图1 3 所 示，不论组成员数量有多少，数据源只发送一次数据包，并且组播只向那些需要数据包的 主机和两络发送包( 以组播地址寻址) ，在共享的链路上，相同的信息只需要一个组播流，从 而能够很好地控制流量，减少了主机和网络的负担，提高了网络应用服务的效率和能力 组播组中的主机可以是在同一个物理网络，也可以来自不同的物理网络( 如果有组播路由器 的支持) 。 2 山东师范太学项士学位论文 图1 3 组播方式 1 i p 组播的服务模型 i p 组播是一种开放的服务模型，模型中具有发送者和接收者两个概念。主机通过 i g m p 2 1 报文与本地路由器交互，成为接收者。发送者只需将报文的目的地址指定为组播组 地址就可实现发送。口组播使用d 类m 地址作为组播组地址。i p 组播没有提供技术用 来限制用户创建一个组播组，接收组播组的数据，和向组播组发送数据。组成员身份只是 实现了接收者可以收到数据，不提供任何访问控制的功能。为了收到一个组播组的数据， 用户只需用i g m p 协议与本地路由器联系。当一个主机变成组播组的接收者之后，它可以 收到组播组的所有数据报文，而不管数据报文的发送者是谁，是否是恶意的发送者发送 者不需要成为组的接收者，只需将报文的目的地址指定成组播组地址，就可以实现向组播 组发送报文。发送者不能对自己使用的组地址进行保留，限制别的用户使用与自己相同的 组地址。 总之，i p 组播的服务模型没有提供组的管理。碑组播数据报文与所有的口数据报一 样，提供尽力而为服务，没有可靠性保证。坤组播传送功能是通过在i p 网络设备上运行 相应的组播路由协议来实现的 2 1 p 组播基本协议 在i p 组播通讯中需要完成两个方面的基本工作：组播成员如何加入组播，如何将组播 信息路由到每个接收者那里去。这样就产生了两类基本的协议：组管理协议和组播路由协 议。耳前组播研究领域有关i p 组播的各种协议已经有很多种，其分类方式如图1 4 所示 i g m p 用于主机与边缘组播路由器之间主机使用i g m p 消息通知本地的边缘组播路由 器它想加入的组，即通知相应组的组播地址。组播路由器通过i g m p 协议来维护一个组播 成员列表，并且定期发送“成员询问”消息来探寻表中的各个成员是否仍然存在。i g m p v 2 中，增加了退出通知功能。一旦组播路由器知道了所在域是否存在组播成员，就可以通过 组播路由协议来决定是否加入到相应组通讯中，即是否进入组播的转发树中。此时需要组 播路由协议。它运行于组播路由器之间，负责构建转发树和路由组播包。按照组播路由协 议使用的范围可以分为域内组播路由协议和域问组播路由协议。其中域内组播路由协议包 括d v m r p ( 距离向量组播路由协议) 、m o s p f ( 最短路径优先组播) 、p i m - s m ，p i m d m t 3 1 ( 密集模式协议无关组播) 和c b t ( 核心树协议) 等；域间组播路由协议包括m b g p t 4 1 ( 组 播边缘网关协议) 等。 山东师范大学硕士擘住论文 茎嚣e 堂d v m i 撞s m f 组撂路 由协谡 i 图1 4i p 组播路由协议分类 潦篓 厂眦s m 摹树 c b t ll 皿( h i m m r e h i e a l m u l t i c a s tp r o t o c 0 1 ) 为了将组播数据传送到所有的组成员，组播路由器之间需要建立和维护组播转发树。 因此，按照构建转发树方法的不同可以分成有源树和共享树协议。有源树协议需要为同一个 组播会话中的每个组播源构建一个最短路经组播生成树；而共享树协议需要在网络中选取 某一点作为公共的根节点，然后再构建一棵生成树，各个组播会话的组播数据均沿着一个 公共的转发树发送。显然，有源树协议的构造、维护代价比较大，但是传输过程中每个组 播源都可以获得自己最佳的传输路径 d v m r p 是第一个在m b o n e 嘲( 组播试验床) 上得到普遍使用的组播路由协议，它是 一个洪泛剪枝协议d v m r p 在r i p t 6 1 协议的基础上扩展了组播功能。与r i p 协议不同的是， r i p 计算路由器到目的地的最佳下一跳，而d v m r p 根据路由器到源方向的上一跳的信息来 构建转发树。d v m r p 协议首先通过发送探测消息来发现邻居，然后通过路由交换来进行 路由选择和确定上下游依赖关系。 p i md m 使用“扩散与剪枝”机制来建立和维护转发树。路由器周期性地发送h e l l o 消 息，以发现相邻的p i m 路由器，且负责在多路访问网络中选举指定路由器，然后根据单播 路由表的信息来确定上下游依赖关系。p i m 与 十分类似，当组播源第次发_ d m d v m r p 送组播报文时，使用t r p b 2 4 算法沿着源的组播转发树向下转发组播数据包。 m o s p f 是o s p f t 0 协议的一个扩展，它通过o s p f 路由表来获得网络拓扑。m o s p f 路 由器除了进行组播路由选择外，还要进行正常的o s p f 单播路由选择。像o s p f 一样， m o s p f 也是使用层次路由，包括区内组播路由、区间组播路由、自治系统问组播路由。 i p 组播路由协议的组播树算法更侧重于控制开销，因为i p 组播的状态维护全由路由器完成 为了保证核心路由器的高效，应尽可能减少路由器状态数目和处理器开销。至于其他几种 协议，这里就不作叙述了。 3 i p 组播遇到的问题 尽管i p 组播很早就被提出，但时至今日并没有得到广泛的应用。i p 组播还有一大堆问 题需要解决，这限制了i p 组播服务的广泛使用。这些问题既有技术上的缺陷又有商业原因， 文献”1 对其进行了详细的讨论。 i p 组播配置方面的一个问题是它不符合现在i n t e r n e t 上i s p ( i n m m e ts e r v i c ep r o v i d e r ： 互联网服务提供商) 采用路由器的升级模型。在现有的i n t e r n e t 中，路由器首先被配置在骨 干网，然后逐渐地推向用户接入点。在网络层提供组播功能，要求网络中基本的硬件设备( 如 路由器) 进行升级以支持组播功能，组播颠覆路由器升级模式，因为硬件不会随着时间的推 4 山东师范大擘硕士擘位论文 移逐渐的实现支持组播功能。i p 组播服务在i n t e r n e t 上的配置速率受限于多种因素，但最主 要的还是商业上的原因。对于整个i n t e r n e t 上的路由器进行升级是不太可能的，i s p 不可能 丢弃已存的网络基础设施。 i p 组播要求网络必须维持必要的状态信息，路由器需要维护组成员关系、组播路由等 信息。这不仅违背了i n t e r n e t 基本的设计初衷( i n t e r n e t 是一个无状态的网络) ，而且成为 i p 组播一个主要的问题：可扩展性。随着组播组和组成员数量的增加，路由器需要维护和 分发的状态信息越来越多，与单播明显不同的地方是组播路由记录很难进行聚合，路由器 需要使用很大的内存空间来保存路由信息。这不仅对路由器的硬件水平提出挑战而且大大 增加查找路由记录的延迟，增加分组的等待延迟。这使得i p 组播很难从容地处理组播组不 断增加的情况，严重地限制了应用的可扩展性。 在i p 组播上面提供高层次的特征，如可靠性、拥塞控制、q o s 、组成员控制和安全问题， 变得十分困难。虽然t c p i p 在i p 层提供的尽力传输的服务之上提供了可靠性和流控制，但 是同样的技术很难应用到i p 组播中。 现在的组播地址是d 类i p 地址，这本身就存在许多问题：d 类地址不是分层的，没法提 供路由信息，而且其数量有限，这使得在i n t e r n e t 范围内配置大量的组播组交得很困难。 i p v 6 被用来解决这个问题，但是只要i p v 4 还是i n t e r n e t 的标准，问题就仍然存在。 在商业因素中一个主要的问题是缺乏标准方法来对组播服务进行收费应该依靠哪个 参数来进行收费呢? 多个参数都有可能，例如组成员数量、发送的分组数量、消耗的带宽 但是没有一个统一的标准。i s p 在引入组播功能上面犹豫不决的一个重要原因是要求路由器 转发的报文并不是他们自身域内需要的i s p 不愿提供组播服务的另外一个原因是目前对 i n t e r n e t 范围内的组播需求并不那么急切，实际上也缺乏组播应用软件。 但是，组播以其节约带宽、传输快捷的传输特性一直被人们推崇，于是人们又研究了 应用层组播，希望可以在现行的网络基础设施上来实现组播通讯。 1 2 2 应用层组播技术的提出 面对i p 组播业务在因特网中的困境，一些研究者开始反思i p 组播体系结构本身的问题。 针对i p 组播存在的这些问题，提出将复杂的组播功能放在端系统实现的新思想。于是出现 了一种以底层网络为基础的基于覆盖网( o v e r l a y ) 的应用层组播协议。o v e r l a y 是一个位 于一个或多个己知网络上的独立的虚拟网络。这种网络由主机基于自组织算法建立和维护， 不需要改变底层网络的结构，可以快速部署所需的网络功能。如果在覆盖网的基础上实现 组播，我们可以把组播实现提高到应用层。端系统实现组播业务的思想就是将组播作为一 种o v e r l a y 业务，实现应用层的服务，因此，端系统组播即是应用层组播( a l m ) 1 应用层组播的基本思想 应用层组播的基本思想是屏蔽底层物理网络的拓扑细节，将组成员节点直接自组织成 一个逻辑o v e r l a y ，并在应用层提供组播路由协议来构建和维护该网络，为数据传输提供高 效、可靠的服务。它将转发树构建在应用层上。两个主机实际的链路是底层的单播i p 路径具体来讲： 组播源准备数据，查询组播路由表，获得予节点的单播i p 地址，再分别打包、转发数据包通过相应 5 山东师范大擘硕士擘位论吏 的单播路径传输给子节点，子节点接收数据包后查询路由表，再分别打包、转发。这一过程重复进行， 直到所有节点都收到数据包查询、打包、接收和转发工作都在网络终端主机的应用层上完成通过在 主机上安装相应的应用层组播软件就可以实现广域网范围内的组播服务。图1 5 显示了应用层组播在 口体系结构中所处的位置。图1 6 示意了应用层组播的基本思想及其与i p 组播的差别，如图 1 6 a ，i p 组播的数据沿着物理链路复制和转发，分组由网络中的路由器进行复制，如果主机a 需 要向主机b ，c ，d 发送分组，则分组在路由器1 处进行复制。而应用层组播的数据则在主机实现复制 和转发，数据报沿着逻辑链路转发，多跳逻辑链路可能经过同一条物理链路( 如图1 6b d ) 。 在应用层组播机制中，主机基于自组织算法建立和维护覆盖网。因此，自组织算法是 端系统组网的核心功能和机制，自组织算法的主要功能包括：周期性地交换节点状态信息， 通报组成员状态；周期性地收集网络逻辑连接的带宽、时延等动态参数；动态地调整覆盖 网拓扑。 u d p t c pl - 一一一一一。 窭一固婴堑固一 釜釜= = = 釜 ， = = _ 4 。专一一一一，。2 2 2 2 一 数据链路层i【敷据髓路尉【数据链路层j 气面氐再司科 应用层l o 啊i l 。z s t c k r7 ，o r i a 娌 - o 譬= = = = = 号 u d p t c pi 塑 i 。口；+ ) ；= = = = ；i = = 2 数据链路层1 韵理层1 应甩层组插端系统 母网络系统。 应甩层组撬端系统 图1 5 应用层组播网络协议 2 应用层组播性能评价指标 应用层组播使用传统单播提供的服务，在终端主机的应用层上实现组播功能，例如组 关系、寻址、组播路由和报文复制，网络只需要提供尽力传输的单播功能。端系统构成逻 辑上的覆盖网络，应用层组播的目标就是便于进行数据传输，构造并维护高效的覆盖网络。 评价应用层组播协议的性能通常采用下面的指标。 ( 1 ) 数据路径的质量 数据路径的质量一般采用两个参数来衡量：强度( s t r e s s ) ，伸展度( s t r e t c h ) 。强度 定义为每条链路或者每个路由器在传输组播分组时发送相同分组的次数。对于i p 组播来说 链路上没有多余的数据报文复制，因此对于网络中的每条链路或节点来说，s t r e s s 值均为1 。 伸展度定义为数据分组从源沿着覆盖网络中路径到达组成员的路径长度和直接的从源到组 成员的单播路径长度的比值，这是为每个组成员定义的尺度。显然，采用1 6 b 中的应用层 组播方案，由于每条路径就是单播路径，每个成员的伸展度均为l 。在图1 6 c 中，a b 之间的 伸展度为1 ；a d 之间的伸展度为1 5 ；a c 之间的伸展度为3 ：平均伸展度等于( 1 十1 5 + 3 ) 3 = 1 8 3 。 ( 2 ) 控制信息负担 在覆盖网络中，每一个成员都要和它们的对等体周期性地交换刷新信息。这些信息在 组中不同的路由器、链路和组成员中构成控制信息负担。控制信息负担是衡量应用层组播 6 山东师范大学硕士学位论之 可扩展性一个非常重要的度量尺度。 除了这些指标，还有其它一些衡量应用层组播的性能指标，包括数据生成树中成员的 度的分布，数据传输延迟等等。 o 主杌一路由嚣 图1 6 网络层组播和应用层组播 不同的应用层组播协议对这些性能指标有不同的考虑，因此不同的协议将使用不同的 方法构造覆盖网络。图1 6 ( b d ) 给出了在相同的网络拓扑结构下，用不同的应用层组播协 议构造不同覆盖网络的例子。假定图中每条链路都具有单位长度。图1 6 b 直接采用源节点h 到其它节点的单播路径进行组播分组转发，其伸展度为1 ，a 和路由器之间的链路强度为3 ， 其它链路强度均为l 。一般来说，在n 个节点的组中如果全部采用单播路径进行组播转发， 那么可能出现的最大强度为0 优) ，出现在源节点的某条链路上，而组成员的伸展度为1 。另 外由于数据源节点和组播组中所有其它节点交换更新消息，因此最坏情况下负载为d 口i f ) 。 图1 6 c 采用环形组播方案，其链路最大强度为2 ，平均伸展度为p f 7 桫。图1 6 d 是上述两种方 案的折衷，最大强度和平均伸展度都位于两者之间，链路 的s t r e s s 是2 ，其余为1 ； s t r e t c h 为：b = 3 3 = 1 ，c = 6 4 = i 5 ，d = 3 3 = 1 。 3 应用层组播的体系结构 目前主要有3 种系统结构来实现应用层组播： ( 1 ) 对等型每个组成员节点都是平等的，动态变化且完全分布节点之间通过一定 的算法、协议自组织成控制网络和数据转发树。每个节点仅维护自身参与组的状态信息， 所有相关功能以软件实体形态集成于参与组播会话的节点中，每个节点完成相同的工作 ( 2 ) 代理型这是一种基于固定节点配置的覆盖式组播技术，一般由增值服务提供商 根据一定策略在i n t e v n c t 的某些位置部署应用层代理节点。代理节点之间的数据传输路径和 传输方式也由增值服务商预先确定终端主机通过接入距自身最近的代理节点获取数据。 7 山东师范大擘硕士学位论文 从某种程度上来看，代理节点类似于组播路由器。 ( 3 ) 服务器型介于对等型和代理型之间。转发树的主干由一些负载较大的服务器构 成，不同于代理类型，这些服务器不一定来源于i s p ，可能是作为普通用户加入的、性能较 高的网络终端主机。 在服务器型和代理型应用层组播中存在一些节点，其性能相对较高，所以基于这些节 点构建的转发树也比较稳定，可支持规模相对较大的应用层组播服务。 4 应用层组播的优势和局限 直观上，端系统实现组播功能可以避开网络层实现组播功能的许多难题： 1 ) 单播方案能够被运用到组播应用中；没有i p 组播中复杂的地址结构、复杂的协议， 对路由器没有多余的要求。 2 ) 应用层组播的状态在主机系统中维护，不需要路由器保持组的状态，解决了业务的 扩展性问题，网络可以支持大量的组播组，可以灵活地定制组播业务。 3 ) 组播应用可以随时部署，无须购买昂贵的组播路由器、不需要网络设备的升级和功 能扩展。组播不再需要d 类i p 地址，因为a l m 方案可以指定自己的寻址方案。 4 ) 可以简化组播的控制、可靠等功能的实现，建立在网络连接之上的应用层组播可以 使用t c p ，u d p 服务，如可以利用t c p 的可靠和拥塞控制简化组播的可靠和拥塞控制。在网络 层实施组播易产生拥塞的限制，因此应用层组播解决i p 组播的不可靠性及拥塞问题。 当然，应用层组播也有许多局限： 1 ) 端系统对i p 网络的了解有限，节点参与组网时，只能通过探测获得一些网络性能参 数，选取的逻辑链路难以优化。 2 ) 主机不了解i p 网络的拓扑结构，只能通过带宽和时延等外在的特性参数，以启发式 的方式建立覆盖网，逻辑链路不能较好地利用质量较好的底层网络资源，覆盖网的多条链 路可能经过同一条物理链路。 3 ) 相对i p 组播效率较低。对于网络层组播，由于没有冗余数据包复制，因此网络中的 每条链路或每个节点上的强度为1 。与由路由复制数据包的网络层组播不同，应用层组播 是由端节点复制数据包，如图1 6 。理论上，在端节点构造一个虚拟层，其目的是在端节 点间构造和维护一个有效的数据传输中间件。由于应用层组播协议必须在同一链路上传输 多个相同数据包，因此，相对i p 组播效率较低。 1 3 问题的提