（计算机应用技术专业论文）基于隧道技术的组播拥塞控制优选算法.pdf

摘要 对丁单点到多点的通信，组播是一种很有效的数据传输方式。发送端不需要 向接收端发送多份相同的数据复制，而是仅向网络发出一份数据，网络在适当的 节点复制数据并分发到各个接收端。维播的思想非常诱人，然而它在互连网中没 有获得i s p ( i n t e m e ts e r v i c ep r o v i d e r ) 的广泛应用，一个重要的原因就是组播没 有提供合适的拥塞控制机制。 网络中的拥塞来源于网络资源和网络流量分布的不均衡性，拥塞不会随着网 络处理能力的提高而自动消除。搠塞控制算法对保证i n t e m e t 的稳定具有十分重 要的作用。组播的特性使拥塞控制协议的设计变得非常困难。由于组播组成员可 能分布在网络的不同部分，互连网的异构性使组播树各部分的拥塞可能差别很 大，组播拥塞控制在调整速率时应该考虑不同组成员之间拥塞的差异。因此，发 送端可能接收到大量来自组成员的拥塞反馈，湮没发送端的带宽。另外，组播拥 塞控制算法还应该保证组播与单播流量之间公平地竞争带宽。同样由于组播接收 者众多，传统的t c p 拥塞控制机制无法直接扩展到组播环境中。这些特性使得组 播拥塞控制成为互联网研究领域中的一个热点和难点。 组播拥塞控制依据发送端数据的发送方式可以分为单速率组播和多速率组 播两种方案。在单速率组播中，接收端的速率受瓶颈接收端( 所有接收端中拥塞 最严重的接收端) 的限制；而多速率组播的缺点是协议过于复杂，难以实现细粒 度的速率控制。针对这些问题，本文融合了网络层组播与应用层组播以及隧道技 术，在可靠组播差错恢复算法的基础上引入拥塞控制能力，使组播的一些中间接 收者充当虚拟组播源，在拥塞发生处可以进行灵活的速率调节，从而有效地解决 了异构网络中组播的拥塞控制问题。最后根据组播拥塞控制算法的评价指标进行 了仿真试验，证明该算法是一种有效的组播拥塞控制算法，具有一定的实用价值。 关键词：组播；组播拥塞控制；单速率组播：多速率组播；应用层组播；隧 道技术 兰州大学研究生学位论文 a b s t r a c t f o rc o m m u n i c a t i o nc o n c e r n i n go n ep o i n tt om u l t i p o i n t ，n m l t i c a s t i sav e r y e f f e c t i v ew a yo fd a t at r a n s m i s s i o n s e n d e rn e e d n ts e n dm a n yc o p i e so fs a n l ed a t a t o a uo fi t sr e c i v e r s i n s t e a di to n l ys e n do n ep i e c eo fd a t ai n t o t h en e t w o r k ，i ti st h e n e t w o r kt h a tw i l lc o p yt h ed a t aa n ds e n do u tt h e ma tn e e d e dp o r t a l t h o u g ht h et h i n k o fm u l t i c a s ti sv e r ya t t r a c t i v e ， i th a s h tb e e na d o p t e db r o a d l yi nt h ei n t e m e tb yi s p ( i n t e m e ts e r v i c ep r o v i d e r ) t h em a i nr e a s o ni s t h a tm u l t i c a s th a sn o p r o p e r m e c h a n i s m o f c o n g e s t i o nc o n t r 0 1 c o n g e s t i o ni nt h en e t w o r kc o m i n gf r o mt h ed i s t r i b u t i n gi m b a l a n c eo f r e s m j r c e a n dt r a f f i ci nt h e n e t w o r k ，c o n g e s t i o n w o u l dn o t d i s a p p e a r i n p a c e w i t ht h e i m p r o v e m e n to fd i s p o s a la b i l i t yo fn e t w o r k c o n g e s t i o nc o n t r o la l g o r i t h mp l a ya n i m p o r t a n t r o l ei ng u a r a n t e e i n gs t a b i l i z a t i o no fi n t e m e t n l ec h a r a c t e r i s t i co fm u l t i c a s t m a k ei td i f f i c u l tt o d e s i g nc o n g e s t i o nc o n t r o lp r o t o c 0 1 b e c a u s et h em e m b e r so f m u l t i c a s tm a yd i s t r i b u t ei nd i f f e r e n tp a r to fi n t e r a c t ，h e t e r o g e n e i t yo fi n t e m e tm a k e c o n g e s t i o n s t a t u sd i f f e rf r o md i f f e r e n t p a r t o fam u l t i c a s tt r e e m u l t i c a s t c o n g e s t i o n c o n t r o ls h o u l dc o n s i d e rt h ed i f f e r e n c eo f c o n g e s t i o n s t a t u s a m o n g m u l t i c a s tm e m b e r sw h e n a d j u s t i n gr a t e s os e n d e rm a y r e c e i v el o t so ff e e d b a c kf r o m m u l t i c a s tm e m b e r ss oa st ou s eu pt h eb a n d w i t ho fs e n d e ni na d d i t i o nm u l t i c a s t c o n g e s t i 0 1 3 c o n t r o l s h o u l dg u a r a n t e em u l t i c a s tt r a f f i ca n du r d c a s tt r a f f i c c o m p e t e b a n d w i t hf a i r l y a l s od u et ot h el a r g ea m o u n t so fm u l t i c a s tm e m b e r s ，t r a d i t i o n a l t c p c o n g e s t i o nc o n t r o lm e c h a n i s mc a n n o tb ee x p a n d e di n t om u l t i c a s te n v i r o n m e n t t h e s ec h a r a c t e r i s t i c sm a k em u l t i c a s t c o n g e s t i o nc o n t r o lh o t s p o ta n d n o d u si nr e s e a r c h o ni n t e r n e t a c c o r d i n gt ot h em o d e t h a ts e n d e rs e n d si t sd a t a ，m u l t i c a s tc o n g e s t i o nc o n t r o l c a nb ed e v i d e di n t ot w os c h e m e sa ss i n g l e - r a t em u l t i c a s ta n dm u l t i r a t em u l t i c a s t i n s i n g l e r a t em u l t i c a s t ，t h e r a t eo fr e c e i v e r si sr e s t r i c t e db yr e c e i v e r sl o c a t e da f t e r b o t t l e n e c kl i n k ( r e c e i v e r sw h o s ec o n g e s t i o ni st h es e v e r e s ta m o n ga l lo f r e c e i v e r s ) ； w l l i l em u l t i r a t em u l t i c a s ti sd i s a d v a n t a g e db yi t sp r o t o c o l sc o m p l e x i t ya n dd i f f i c u l t t or e a l i z ef i n e g r a n u l a r i t yr a t ec o n t r 0 1 i na l l u s i o nt ot h e s ep r o b l e m s ，t h i sp a p e ru n i f i e s n e t w o r kl a y e r e dm u l t i c a s t 、 r i ma p p l i c a t i o nl a y e r e dm u l t i c a s ta n d t u n n e l i n gt e c h n i q u e b a s e do nr e l i a b l em u l t i c a s te r r o rc o n t r o l ，w el e a dc o n g e s t i o nc o n t r o la b i l i t yi n t o r e s u m p f i v en o d e ，m a k es o m ei n t e r m e d i a t en o d ev i r t u a ls e n d e ro fm u l t i c a s tt r e e ，s o t h e yc a l la d j u s tr a t ef r e e l ya tc o n g e s t i o np o s i t i o n t h u se f f e c t i v e l ys o l v ec o n g e s t i o n c o n t r o lp r o b l e mi nh e t e r o g e n e o u sn e t w o r k f i n a l l yw ed os o m es i m u l a t i o na c c o r d i n g t oe v a l u a t e t a r g e to f m u l t i c a s tc o n g e s t i o nc o n t r o l ，t h er e s u l ts h o w t h a tt h i sa l g o r i t h mi s e f f e c t i v ea n dv a l u a b l e k e y w o r d s ：m u l t i c a s tr o u t i n g ；m u l t i c a s t c o n g e s t i o nc o n t r o l ；s i n g l e r a t e m u l t i c a s t ；m u l t i r a t em u l t i c a s t ：a p p l i c a t i o nl a y e r e dm u l t i c a s t ；t u n n e l i n gt e c h n i q u e 原创性声明 y 7 3 2 1 5 9 本人郑重声明：本人所呈交的学位论文，是在导师的指导下独立进行研究所取得的 成果。学位论文中凡引用他人已经发表或未发表的成果、数据、观点等，均已明确注明 出处。除文中已经注明引用的内容外，不包含任何其他个人或集体已经发表或撰写过的 科研成果。对本文的研究成果做出重要贡献的个人和集体，均已在文中以明确方式标明。 本声明的法律责任由本人承担。 论文作者签名：李未泽日期：越l e ! 直 关于学位论文使用授权的声明 本人在导师指导下所完成的论文及相关的职务作品，知识产权归属兰州 大学。本人完全了解兰州大学有关保存、使用学位论文的规定，同意学校保 存或向国家有关部门或机构送交论文的纸质版和电子版，允许论文被查阅和 借阅：本人授权兰州大学可以将本学位论文的全部或部分内容编入有关数据 库进行检索，可以采用任何复制手段保存和汇编本学位论文。本人离校后发 表、使用学位论文或与该论文直接相关的学术论文或成果时，第一署名单位 仍然为兰州大学。 保密论文在解密后应遵守此规定。 论文作者签名聊签名：翅日导师签名：壹避日强；加l 矗 ! 州1 人学川宄生学位论芷 1 绪论 1 - 1 引言 近年来，随着i n t e r n e t 的迅速普及和爆炸性发展，在i n t e r n e t 上产生了许多新的应 用，譬如网络视频会议、网络音频 见频广播、股市行情发却、多媒体远程教育、协同i l 算、远程会诊等。和早期的单点通f 片不同，它们的通信关系是多点通信，这就带来了带 宽的急剧消耗和网络拥挤问题。为了缓解l x j 络瓶颈，人们提i n 了各种方案，归纳起柬， 主要包括以下四种： 1 增加互连带宽； 2 服务器的分散与集群，以改变网络流量结构，减轻主干网的瓶颈； 3 应用o o s ( q u a i l i t yo f s e r v i c e ) 机制，把带宽分配给一部分应剧； 4 采用i pm u l t i c a s t ( 译为组播、多播或多路广播) 技术。 比较而言，i p 组播技术有其独特的优越性在组播网络中，即使用户数量成倍增 长，主干带宽不需要随之增加。组播传输模式自1 9 8 5 年s d e e r i n g 等人提出以来，就得 到了互连网研究领域的广泛关注。 1 2 组播的基本概念 组播是一种为优化使用网络资源而产生的技术，依托l p 协议完成。在组播中，组播 源把数据包一次发送到特定组播组，而只有属于该组地址的主机才能接收到数据包。并 且在数据传输过程中相同的分组在一条物理链路上最多只经过一次。由此大大地节省了 网络带宽，即使用户数量成倍增长，主干带宽不需要随之增加。单播、组播和广播的区 别如图1 1 所示【1 1 ： 未术泰 r 1r 2r 3 ( a ) r 1r 2r 3r 1r 2r 3 ( b )( c ) 图1 i a ) 单播b ) 组播c ) ，“播 假设我们需要从s 向r l 和r 2 发送分组。在单播中，每个分组将单独向r l 和r 2 分 别发送。在组播中，s 只发送每个分组次，如果需要，则在中间节点进行分组复制， 兰，i 1 入学岍笕生学位沦文 每条链路中最多只出现一次相同的分组。而在广播中，每个中间节点将把收到的分组从 所有接口中( 除了收到分组的接l 1 ) 发送出去。 目前，i n t e r a c t 上已经出现了许多适合组播的应用，如视频会议、w e b 更新、一对多 的文件发布、远程学习、交互式游戏、团体广播、协同丁作等，它们具有与早期网络不 同的特点：通信的关系是多点通信而非单点通信。在这种情况下，如何合理地规划数据 流量，尽量节省网络资源就显得至关重要。组播j 下是应这种需求发展而来，并因其良好 的性能特性和应用前景成为互连网研究领域中的热点课题。 1 3 组播的实现机制 实现组播通信必须解决下列问题【2 】： 1 地址映射：必须有一个网络层的地址用于与一组接收者通信，此外，还要有种机 制将这个网络层地址映射到链路层上对应的主机上去。 i a n a 将整个i p 地址空间分为5 类：为单播地址设计的a 、b 、c 类、为组播地址设 计的d 类以及为今后使用而保留的e 类地址。组播地址用于标识一个组播组，范围从 2 2 4 0 0 0 到2 3 9 2 5 5 ，2 5 5 2 5 5 ，格式为1 1 1 0 + 2 8 位组标识。使用同一个i p 组播地址接收组 播数据包的所有主机构成了个主机组，也称为组播组。 在将网络层的组播地址映射到链路层m a c 地址上时，只要把i p 组播地址中的低2 3 位放入m a c 地址的低2 3 位即可。但i p 组播地址有2 8 位地址空间，其中只有2 3 位被映 射到m a c 地址，这样会有3 2 个t p 组播地址映射到同一m a c 地址上。主机c p u 必须对收 到的每一个组播数据包做出判断。 2 动态注册：必须有一种机制使主机能够告诉网络它是某个组的成员。否则，网络 就无法知道哪些网络需要接收哪些数据流。 i p 组播依靠i n t e r n e t 组管理协议i o j p 在主机与路由器之问通报组成员关系。主机 通过i g m p 向本地的组播路由器发送“主机成员报告”消息，告知欲接收的组播地址。组 播路由器为它的每个端口都维护一张主机组成员表，收到主机请求加入组播组的消息后， 便在对应的端口将陔主机加入组成员列表中。组播路由器还要定期发送“主机成员询问” 消息探询表中的主机组成员，以确定该主机组是否仍然存在。目前 0 b l p 有两个版本： i g m p v l 1 3 1 和i g m p v 2 4 1 。第三版i g m p v 3i f 在制定中。 3 组播路由：网络必须能建立组播树，发送者据此将数据包发给所有的接收者。建 立组搔树的主要目的是保证对任何指定的路径，相同的数据只传递一次。就是说，如果 在某个组播树的分枝上有多个接收者，在这条分枝上组播数据只传输1 次。 2 兰州人学研究生学位论文 这由组播路由阱议来实现。按照组播树的类型，组播路由协议分为有源树协议和共 享树幼、议两类。有源树是以组播源节点作为组播树的根节点的树，有源树的分枝形成通 过网络到达接收主机的分布树。因此有源树协议需要为同一个组播会话中的每个组播源 构建个最短路径组播生成树；而共享树则以组播网络中某些可选择的组播路由器中的 一个作为组播树的公共根，这个根被称为汇聚点。各个组播会话的组播数据均沿着一个 公共的转发树发送。显然，有源树协议的构造、维护代价比较大，但是传输过程中每个 组播源都可以获得自己最佳的传输路径。 按其使用的范围，组播路由协议又可分为域内组播路由协议和域间组播路由协议。 简单归纳如下。 r【d v m r p f d v m r p r 有源删m o s p f r 域内1m o s p fl op i m d m 组播路由协议【p i m - d m s ) 4组播路由协议1 【 c b t irp i l f - s m 域问m b g p 。共享树 c b t l h i p 图1 2 组播路由协议分类 有了上述机制，i p 组播就能够在实际网络中成功地运行。例如最被大家所熟知的组 播网络m b o n e ( i n t e r n e tm u l t i c a s tb a c k b o n e 的组播主干网) ，是一个由i e t f 开发的运行 在i n t e r n e t 上的虚拟重叠网络，其初衷是创建一个半永久的i p 组播测试床而不需要等到 整个i n t e r n e t 都采用支持组播的路由器。1 9 9 2 年，组播技术还处于实验阶段。当时提出 以i p 遂道( t u n n e l i n g ) 联结组播岛，组播岛是支持组播服务的区域，最小的组播岛是一 个支持组播的l a n 。 现在，m b o n e 已跨越几个洲，用户数大约在1 0 0 0 0 3 0 0 0 0 之间。在i e t f 会议期间，大 约有1 0 0 0 个不同的接收主机接入。它成为i n t e m e t 上传送声音和视频信息的一个重要组成 部分。m b o n e 网络成功证明了组播技术在用于多媒体内容发布上的有效性。 1 4 本文的主要研究内容 尽管组播的思想非常诱人，然而要想大规模地推广组播网络技术仍然面临一系列困 难。首先，组播应用难以提供有效的用户认证和计费手段，难以提供安全组播，因而缺 乏成熟的商业化基础；同时，还缺乏有效的手段保证服务质量( q o s ) ，包括延时、丢失 率和对异质链路的支持等。此外，i p 组播数据包典型使用用户数据报协议( u d p ) ，而 u d p 是种“尽力而为”( b e s t - e f f o r t ) 协议，因此，i p 组播应用必定会遇到数据包丢失和 兰州i 大学训究牛学位论文 乱序问题，如何保证可靠组播以及对网络拥塞的合理反应，是组播得以大规模应片j 必须 要解决的问题。 论文的主要思想是针对组播搠塞控制，分析比较各种现有的组播拥塞控制算法，在 此基础上提出了一种基于虚拟组播源的组播速率协调机制，来解决大规模、异构网络上 的组播拥塞控制问题。论文第一章是绪论，简单介绍了组播的概念、特点、实现技术。 第二章是研究的基础部分，叙述了可靠组播错误恢复算法对本文有启发意义的策略。第 三章详细讲述了组播拥塞控制算法的相关内容、研究现状，并具体阐述各种现有的拥塞 控制代表性协议，对它们在实施中的优劣进行评价和总结。第四章介绍了组播领域的新 发展应用层组播，阐述了它在拥塞控制方面的独特优势。第五章简单介绍了隧道技 术及原理。第六章联想前面的知识，提出利用隧道技术构建虚拟组播源的拥塞控制算法， 并针对该算法，给出相应的节点数据结构、参数优化策略，并进一步以算法为基础，论 述了算法的仿真实现。论文最后一章是对本文所做的工作做了一个总结，并提出今后需 要进一步努力的方向。 4 兰! ! 叁兰堕垄竺兰些堡苎一 2 可靠组播差错恢复 当前，支持i p 组播的标准传输层协议只有u d p ( 用户数据报协议) ，因而组播报文 的传输是不可靠的。i p 层的m u i t j c a s t 通信只提供尽力而为型服务，不保证组播数据报文 的可靠传输。然而对于数据组播应用来说，组播的可靠性是十分重要的。如组播报文差 错恢复、所有组播接收者收到的报文数量一致、顺序一致、实时性等。这方面的研究是 一个热点，目前还没有统一的标准，i e t f i e 在努力推出标准，也有很多组织在积极地开 发自己的协议。本章介绍其中对本文具有启发意义的差错恢复策略。 2 1 可靠组播的基本概念 通常意义上的可靠性是指所有组播数据最终都正确传送给每个接收者。 可靠性还可进一步分为半可靠性或准可靠性( q u a s i r e l i a b i l i t i ) 、有一定时间限制的可 靠性和完全可靠性3 种类型。使用半可靠性时，传输层可能重传一个丢失的包或使用错 误校正码来提供一个应用可忍受的丢失率，但不保证所有数据都能无错误地传递给所有 接收者，半可靠性通常用于可容忍一定丢失率的实时组播应用。有时间限制的可靠性适 用于对实时性要求很高的组播应用，如果数据在规定时间内没有收到。那么就认为其丢 失且不再重复传送。有时f 刚限制的可靠性常常意味着是一种半可靠性，但反之不成立口1 。 而完全可靠性则指丢失率为零，通常应用于对正确性要求很高但对实时性要求不高的情 况。 此外，从广义上讲，可靠性还可能包括以下几个方面【6 1 ： ( 1 ) 接收者数目。即保证组播组中的每个成员都能接收到发往该组的组播数据或是 非该组的成员都接收不到该组的数据。 ( 2 ) 有序。即要求接收者接收到的组播包是按一定顺序排列的。除了按发送时问顺 序外，还可能有几种不同的排序定义，如单个源排序，多个源排序，多个组排序。 本文讨论的可靠性侧重于无差错传递，这是目前互连网上大多数组播应用所要求的。 2 2 可靠组播要解决的问题及策略 对可靠组播机制的研究比对t c p 可靠机制的研究要困难得多，其根本的原因是应用 程序对可靠性的要求差异很大，不可能设计出一个可以满足所有应用要求的r m 协议模 型，所以每个协议都要针对一个应用类型进行设计。协议要综合考虑应用的服务要求、 应用的可扩展性能和应用所处的网络环境，并利用通信流的特点提供高性能、低开销的 聪通信服务。r m 的核心问题是如何根据组播通信过程中丢失分组报文的情况柬迅速、 兰型叁堂竺! ! 兰兰竺笙兰 高效地恢复丢失的报文，使得接收者接收到j f 确、有序的报文。评价r m 性能的要素有两 个方面：是数据吞吐率，即发送有片j 数据同冗余数据和控制报文的比例；二是恢复的 时延。最理想的r m 算法应当使吞吐率最大，而恢复的时延最小。可靠组播算法主要包括 r m 错误恢复算法和拥塞控制算法两部分。本章先讲述错误恢复机制，下一章详细介绍组 播拥塞控制算法。 2 3 错误恢复策略 可靠组播的错误恢复一般有自动重传请求a r q 和前向纠错f e c 两种机制。a r q 是一种 “按需重传”的方式，当接收者检测到错误之后，通过错误反馈机制报告错误，然后发 送者或其它节点向出错节点重传所需的组播包进行错误恢复。其优点是简单高效，缺点 是错误恢复的时延较大。f e c 则相反，它是利用编码技术在传送的数据中增加冗余信息， 接收方根据这些冗余信息进行错误检测和恢复。实际运用中通常将这两种机制结合，提 供可靠性保障。 在a r q 中，发送者和接收者通过交互确认信息，以检测数据包是否e 确传递。根据丢 失检测是由发送者还是接收者进行，确认信息分为肯定确认( a c k ) 和否定确认( n a c k ) 两种。a c k 要求保存每个接收者的接收状态信息，并设置相应的定时器，接收者对每个收 到的包进行确认，给发送者返回a c k 消息。只要有一个接收者没有在定时器超时前返回 a c k ，发送者就会假定该数据包丢失，触发重传或拥塞避免机制。n a c k 是由接收者负责丢 失检测的模型，只有检测到丢失后才向发送者返回n a c k 消息请求重传，因此通常反馈信 息带宽较少，并减轻了发送者的负担。 在单播中，差错检测和恢复由传输层t c p 协议来实现：接收端向发送端反馈确认应答， 发送者据此进行数据重发或调整发送速率，从而提供了端到端的可靠数据传输服务。但 这种机制无法直接引入组播中。首先，一个组播会话可能有一个发送者多个接收者 ( 1 - t o n ) 或多个发送者多个接收者( n - t o - m ) ，各接收者的接收能力可能相差很大；其 次，众多接收者向发送者回送接收情况会引起大量的“反馈风暴”，严重时可以“淹没” 发送者。无论是a c k 还是n a c k 模型，当接收者数量较大，较远而链路质量不佳时都有 可能出现反馈风暴。针对这个问题，主要有两种解决方案：分级a c k 和n a c k 抑制。 2 3 1 分级a c k 机制 减少a c k 的一种有效方法b j a c k 聚合。有两种基本的方法来聚合从接收者到发送者 的a c k 。一种是乐观聚合( 也称分级确认) ，即一个中涮节点收到数据包后立即返回确 州人学研究生学位论文 认，然后它负责将这些数据包可靠地发送给其子节点。另一种是悲观聚合，即一个中问 节点只有收：i j n 有子节点m a c k 后4 向其父节点发j , 基a c k ，发送者同时报告其收到的最 高序列号，以确认所有成员都收到了该数据包。乐观聚合方式下，发送者和中间节点的 缓冲区要求较小，因为子节点的立即确认使它们可以较快删除相应的缓存区中的数据包。 而另一方面，悲观聚合的鲁棒性更好，当一个节点的父节点不工作时它还可以从祖父节 点接收数据包。 圈2 1 分级a c k 结构图 图2 1 显示了一个四层结构的a c k 树，其中根节点为发送者，叶节点为接收者。组播 数据仍然由发送者通过i p 组播树发送给接收者，a c k 树仅用于a c k 聚合，接收者的a c k 在d e s i g n a t e dr e c e i v e r 处聚合，然后多个d r 的a c k 在更高一层的节点处聚合，这样就 大大减少了发送者收到的a c k 的数量。 2 3 2 n a c k 抑制机制 由于n a c k 发送的频率更低且只来自相关的接收者，因此基于n a c k 的方法也可减 轻a c k 风暴。不过还需要有相关机制来防止n a c k n , 暴，特别是当丢失率较高、相关丢 失、组播组很大时。减少a c k 的方法是聚合它们，而n a c k 与之不同，n a c k o 司- 以抑制， 也就是说，n a c k 消息通常是多余的，一个n a c k 可代表其它许多携带相似信息的n a c k 。 常用的n a c k 抑制机制是基于定时器的。接收者将为n a c k 设置一个定时器，定时器 超时后发送该n a c k ，如果在定时器超时之前收到包含相同信息( 如报告同一个丢失包) 的n a c k 或是一个重传报文，那么定时器复位，取消该n a c k 。n a c k v j 被组播到该组从 而抑制其它的n a c k ，或者单播给发送者( 或父节点) ，从而促使发送者( 或父节点) 组播一个确认信息( 收到n a c k 或重传请求) 到该组来起到抑制作用。后一种方法用于 接收者无法发送组播消息或代价太大时i ”。 兰卅1 人学 l j f 究生学位论殳 定时器可以被设置为一个随机值或是确定值。s r m ( s c a l a b l e r e l i a b l e m u l t i c a s t ) 使 用平均分布的随机定时器，其中间隔是基于发送者和接收者的单程估计时延来设置的， 这种机制的性能主要取决于估计的精确度。在文献9 i 中提出了一个指数分布的随机定时 器，声称相对于平均分布定时器它有较低的反馈时延和较好的反馈抑制。另一方面，在 有时延保证的网络中，根据d t p d v l ( d e t e r m i n i s t i ct i m e o u t sf o rr e l i a b l em u l t i c a s t ) 算法设置 的优化定时器可确保对每个丢失包都只返回一个n a c k 。 研究表吲l o 】，当接收者数目保持不变时，随着丢失率的增加，n a c k 抑制策略对n a c k 所需带宽只有少量的增加，基本上不随组播规模的增大而变化。与其它方法相比，体现 了良好的可扩展性。因此本文提出的虚拟组播源机制也采用了这种差错恢复策略。 2 3 3 重传策略 可靠组播中采用的a r q 机制主要分为基于发送者的方式、基于接收者的方式以及基于 层次化的方式等3 类。其中基于层次化的方式相对于其它两种方式在可扩展性和效率上都 有明显的优势，是现在可靠组播研究的主要方向【l l 】。 基于层次化的方式一般采用树状结构( 称为a c k 树，发送者作为根节点) ，除了根节 点以外，a c k 树中有多个其它节点都承担了可靠性保证工作，它们之间相互协同工作，共 同保证整个组播组数据传送的可靠性。组播组的成员，即接收者被分为多个本地组，每 个本地组有一个组长，它负责处理组内的错误反馈消息，以及组播包的重传，以确保组 内的接收者能够正确接收到所有组播包。这样从发送者( 根节点) 到接收者在a c k 树上形 成了多级形式，每个组长只负责它所对应的本地组的内部成员数据传送的正确性，同时 它也作为小组成员由上一级的组长对其进行管理。在层次化的方式中，组长可以是指定 的某些特定节点，也可以在本地组内进行动态选择。 层次结构的a r q 中，负责错误恢复的路由器或主机称为r e p l i e r ( 应答者，如本地组的 组长) ，一般从接收者中选取，或者由专门的服务器充当。这种在一个大的组播组中利用 若干中间节点收集反馈信息，进行数据重传的策略，成为本文立论的基础，本文正是在 此基础上改进而成的。 兰型苎兰竺堑兰兰竺丝苎一 _ - j _ _ _ _ - _ _ _ _ _ _ _ _ _ _ _ - - - _ _ _ _ _ _ _ _ _ 一 3 组播拥塞控制 3 1 拥塞和拥塞控制 当网络中存在过多的报文时，网络的性能会下降，这种现象称为拥塞。拥塞是由于 多个用户共同竞争网络资源而引起的。拥塞发生时，网络的吞吐量降低，传输时延增大， 丢包率增加，而大量的错误反馈和重传信息又进一步加剧了掮j 塞的程度，造成上层应用 系统性能下降。因此必须采取措施来避免拥塞的发生或对拥塞的发生做出反应。 文献1 2 1 使用图3 1 描述拥塞。网络负载较小时，吞吐量与网络负载基本保持线性关系， 网络延迟缓慢增加；网络负载超过第1 个关键点k n e e 后，网络吞吐量增长变慢，网络延迟 增长变快；网络负载超过第2 个关键点c 1 i f f 后，网络吞吐量急剧下降，网络延迟迅速增 加。拥塞控制的目标就是使网络在关键点k n e e 附近工作，保证网络中的数据不超过网络 的传送能力。 t h r o u g h p u t l o a d l o a d 圈3 i 尽管组播是一种有效的数据传输方式然而至今组播无法得到i s p ( i n t e m e ts e r v i c e p r o v i d e r ) 的广泛应用，一个重要的原因就在于组播没有提供合适的拥塞控制。组播的特性 使拥塞控制协议的设计变得非常困难。由于组播组成员可能分布在网络的不同部分，互 连网的异构性使组播树各部分的拥塞可能差别很大，组播拥塞控制在调整速率时应该考 虑不同组成员之间拥塞的差异。因此，发送端可能接收到大量来自组成员的拥塞反馈， 湮没发送端的带宽。另外，组播拥塞控制算法还应该保证组播与单播流量之间公平地竞 争带宽。同样由于组播接收者众多，传统的t c p 拥塞控制机制无法直接扩展到组播环境 中。这些特性使得组播拥塞控制成为互联网研究领域中的一个热点和难点。 3 2 组播拥塞控制协议的评价目标 组播拥塞控制协议具有很强的针对性，大部分协议都是针对某些特定问题提出的。在 单播通信中，t c p 协议可以满足很大范围内的应用的需要，但是不同的组播应用对流量有 9 彳1 一 e 一 e。l n 一 k 一盟 h 一 赧 兰卅1 人学研究生学位论文 1 i 同的要求。例如，视频会议不要求保证可靠传输，但希望速率变化尽量平滑；文件分 发要求保证数据的可靠性，所有用户( 或者大多数用户) 都能准确地接收到文件。各式 各样的需求对组播搠塞控制协议的设计选成很大的影响。i e t f 和i r t f 已经取得共识：一 种组播拥塞控制协议不可能满足所有的需求，必须针对不同的应用设计不同的协议【l 3 1 。 需求多样性导致了组播拥塞控制协议的评价目标多样化，其中两个评价目标对组播 的发展龙为重要：可扩展性和t c p f r i e n d l y 。简单地说，可扩展性是指随着组规模的增 大，拥塞控制协议不会造成组播组性能下降。t c p f r i e n d l y 则要求组播和t c p 流量公平 地竞争网络带宽。这两个目标在一定程度上是对立的，组播拥塞控制协议需要根据实际 需求在两者间做出权衡。 3 2 1 组播拥塞控制协议的可扩展性 组播拥塞控制协议的可扩展性通过协议在性能( 包括吞吐率、延时) 下降前可以支持 的用户数量来衡量。它受到4 方面因素的限制： ( 1 ) 任务复杂性：当组成员的数量变得越来越大时，拥塞控制任务的复杂性会急剧上 升，从而限制协议的可扩展性。可以通过在发送端和接收端之间进行合适的分工来解决这 个问题。 ( 2 ) 反馈爆炸问题：拥塞控制需要考虑所有组成员的拥塞状况，随着组的规模增加，大 量的反馈可能湮没发送端。可以通过反馈聚合或反馈抑制机制来解决这个问题。 ( 3 ) l p m 问题( l o s sp a t hm u l t i p l i c i t yp r o b l e m ) ：文献”1 指出，随着组规模的增加， 组播树的数据丢失路径会随之增加，从而导致大多数分组至少会经历一次丢失，如果发送 端对每一次丢失作出响应，组播吞吐量可能下降为0 ( d r o p t o z e r o ) ，这就是组播中的丢 失路径多样性( 1 0 s sp a t hm u l t i p l i c i t y ，简称l p m ) 问题。适当的反馈聚合和反馈抑制可 以减轻l p m 问题对组播组性能的影响。 e 1 ( 4 ) 网络随机延迟的影响：文献”1 指出，即使在非常理想的网络环境中( 网络中无分组 丢失，路由器缓存无限大) ，随着组规模的增加，网络中随机分布的队列延迟( 路由器的服 务延迟) 也会给组播组的性能造成影响。在大的组播组中，多速率组播可能是更好的选择。 上述问题对可扩展性的影响都是因为在组播环境中，组播j i j 塞控制应该考虑所有组 成员的拥塞情况，而随着组规模的扩大，这些问题变得更加严重。 3 2 2 组播拥塞控制协议的t c p - f r i e n d l y 1 0 兰州人学研究牛学位论殳 t c p 在现在的i n t e r n e t 中占据了统治地位，然而随着网络应用的发展，组播流量可 能在未来的网络中占据很重要的地位。如果组播流量过多地占用带宽，会导致f c p 流量 “饿死”( 占用带宽太少) ，对组播应用的推广会产生不利影响。组播捐；i 塞控制协议应该 保证组播流量与t c p 流量之间公平的竞争资源，即t c p 一友好( t c p f r i e n d l y ) 。 1 t c p 流量模型 t c p 是一个面向连接的单播协议，是现在i n t e r n e t 中最主要的传输协议，能提供可靠 的数据传输、流控制和拥塞控制。 t c p 在发送端维护一个拥塞窗口，控制未应答分组的数量。t c p 主要分为“慢启动” ( s l o w s t a r t ) 和“捌塞避免”( c o n g e s t i o na v o i d a n c e ) 两个阶段。启动时首先进入慢启动阶 段，用于探测可用的网络带宽，这期间大约每隔一个r 1 t ( r o u n d t r i pt i m e ) 增加一倍。 进入稳定状态后，也就是拥塞避免阶段，t c p 使用a i m d ( a d d i t i v ei n c r e a s em u l t i p l i c a t i v e d e c r e a s e ) u 6 方式试图避免拥塞。 t c p 的吞吐量与下面的参数有关：往返时间t r _ 丌，重传超时值i r t o ，分组大小s ，丢失 率p 。式( 1 ) 1 7 1 给出一个简化模型，近似模拟t c p 在稳定状态下的吞吐量。该简化模型没 有考虑t c p 超时。 式( 2 ) 1 9 l 给出了一个更复杂的模型：b 是每个a c k 应答的分组数量，w 。是拥塞窗口 的最大值，与式( 1 ) 不同，它考虑了t c p 超时。在高丢失率网络中，式( 2 ) 更精确地模型化 了t c p 的行为。 t ( t r 。，s ，p ) = t 舞 c 是常量，通常取1 5 ( 1 ) r r r 、p ”。 t ( t r t tj ，p ) = m i n j s 7 k 一半+ t 。mm i n ( 1 s 擎删，拽一yjv石 ( 2 ) 2 组播t c p f r i e n d l y 的定义 组播t c p f r i e n d l y 存在多种定义。文献【1 9 1 给出的定义是“非t c p 流量的长期吞吐量不 超过相同情况下t c p 流量的吞吐量”。文献皿。1 对t c p f r i e n d l y 的定义更加严格： ( 1 ) 单播t c p f r i e n d l y ：在相同网络条件下，如果一个单播流量对其他并存t c p 流量 的长期吞吐量的影响( 减少) 不大于另外一个t c p 流量对后者的影响，此单播流量被认 为是t c p - f r i e n d l y 。 兰型查望翌型兰兰竺堡兰 f 2 1 组播t c p f r i e n d l y ：在发送端与每个接收端之侧，如果流量具有单播流量 t c p f r i e n d l v 的特性，此组播流量被认为是t c p f r i e n d l y 。 对组播t c p f r i e n d l y 的定义还存在争论，某些定义提出应该允许组播流量使用比单 播流量稍多的带宽，因为组播流量为多个接收端提供服务。文献1 2 0 还引入下面的公式来 定义组播的t c p f r i e n d l y ： a r t c p r 曼b 。h c p( 3 ) 其中r 表示瓶颈链路上的组播流的速率，r t 。，表示相同情况下t c p 流的速率，a 和b 是流 接收端数目的函数。b a 反映了公平性度量。当a = b = 1 时，两种定义是相同的。 实现t c p 公平的较好方案主要有两个：在组播的每个接收者上使用和t c p 相同的 a i m d 控制算法，自然实现了与t c p 的公平；在组播的每个接收者上使用模仿t c p 稳念 吞吐量的公式( 式