（计算机应用技术专业论文）基于组播的拥塞控制研究(1).pdf

硕士学位论文 似s j r s f l i e s i s 摘要 随着i n t e m e t 在全球范围的迅速发展，网络应用尤其是多媒体应用的增长， 原有的拥塞控制中某些假设和算法已经不再适用。同时，特殊网络环境和应用 也需要特殊的流量控制技术的支持。拥塞控制的目的是希望通过对输入交通流 的控制以达到拥塞避免即避免丢包和较高网络吞吐率之间的一种平衡。但目前 在拥塞控制方面的研究对于网络节点的缓冲占有量的抖动性即系统稳定性考 虑不多。当系统稳定时可以防止因为抖动而造成数据包的丢失，而且在网络可 用带宽增加时可以迅速加以利用，提高网络系统的吞吐率。 本文针对计算机高速互联网中组播流的速率调节问题，在单点对多点的组 播流量模型基础上，提出了一类由发送方驱动的单速率组播拥塞控制器的设计 方法。并且运用现代控制理论和方法，特别是s c h u r c o h n 判据和r o u t h h u r w i t z 稳定性分析方法，讨论如何利用基于组播的单速率拥塞控制方法来对组播信源 端节点的发送速率进行调节，从而使得1 ) 信源端节点的发送速率趋于稳定：2 ) 分支节点缓冲占有量趋于稳定，没有出现动态抖动，可以防止丢失数据包：3 ) 拥塞控制器可以保证组播的公平性。 为了深入研究控制器性能，本文运用m a t l a b 对所提出的拥塞控制方案进 行了个例仿真。仿真结果显示，这些拥塞控制方案使网络性能表现良好。 关键词：计算机通信网络，组播，拥塞控制，稳定性，缓冲占有量 本论文的研究工作受到国家自然科学基金( 批准号：6 0 1 7 4 0 4 3 ) 和湖北省自然 科学基金重点项目( 批准号：2 0 0 2 a b 0 2 5 ) 的资助。 硕士学位论文 m a s lf r st i i e s i s a b s tr a c t w i t ht h ei n t e r n e t s p r e a d i n gf a s t i nt h e w o r l d ，t h ei n c r e a s i n go fn e t w o r k a p p l i c a t i o n s ，e s p e c i a l l ym u l t i m e d i aa p p l i c a t i o n s ，m a k e st h eu s u a la p p r o a c h e sa n d m e t h o d so fc o n g e s t i o nc o n t r o ln o l o n g e r s u i t a b l ef o rt h en e we n v i r o n m e n t m o r e o v e r , s p e c i a l n e t w o r ke n v i r o n m e n ta n d a p p l i c a t i o n a l s on e e d p a r t i c u l a r c o n g e s t i o n c o n t r o l t e c h n i q u e ss u p p o r t t h ep u r p o s eo fc o n g e s t i o nc o n t r o l i s c o n g e s t i o na v o i d i n gb yc o n t r o l l i n go fi n p u tt r a f f i ct or e a c hak i n do f t r a d e o f f t h i s s t a t ei sd e s c r i b e da sab a l a n c i n gs i t u a t i o nb e t w e e n a v o i d i n gl o s so fp a c k e t sa n dh i g h t h r o u g h p u t o fn e t w o r k b u tu pt o n o w , t h es t a b i l i t yo fs y s t e m ，e s p e c i a l l yt h e o s c i l l a t i o no fb u f f e ro c c u p a n c yh a s n tb e e nt h ef o c u si nr e s e a r c ho fc o n g e s t i o n c o n t r 0 1 i ft h es y s t e mi sn o ts t a b l e ，t h ep a c k e t s l o s sc a n tb ea v o i d e db e c a u s eo f o s c i l l a t i o n m o r e o v e rt h es y s t e mc a nq u i c k l yu s et h ei n c r e a s i n ga v a i l a b l eb a n d w i d t h a n dt h et h r o u g h p u to fn e t w o r ki si n c r e a s e d w i t hr e g a r dt ot h ef l o wr e g u l a t i o no fm u l t i c a s tf l o wi nh i g h s p e e dc o m p u t e r c o m m u n i c a t i o nn e t w o r k s ，t h et h e s i sp r o p o s e sac l a s so fs e n d e r - d r i v e ns i n g l er a t e c o n g e s t i o nc o n t r o l l e r sb a s e do ns i n g l e t o m a n y m u l t i c a s tm o d e l b a s e do ns y s t e m s t a b i l i t y , e s p e c i a l l y s c h u r - c o h na n dr o u t h - h u r w i t z c r i t e r i a ，i t i ss h o w nt h e c o n t r o l l e rc a nr e g u l a t et h es o u r c er a t eo nt h eb a s i so ft h ek n o w l e d g eo fb u f f e r o c c u p a n c y o f t h ed e s t i n a t i o nn o d ei ns u c ham a n n e rt h a t ( 1 ) t h er a t eo fs o u r c en o d e i s s t a b l e ；( 2 ) t h ec o n g e s t i o nc o n t r o l l e dn e t w o r ki sa s y m p t o t i c a l l y s t a b l ew i t h o u t o s c i l l a t i o ni nt e r m so ft h eb u f f e ro c c u p a n c yo ft h ed e s t i n a t i o nn o d e ；( 3 ) i ts a t i s f i e s t h ec o n d i t i o no ff a i m e s si nm u l t i c a s t w eh a v ef u l f i l l e da v a r i e t yo f s i m u l a t i o n su n d e rv a r i o u st r a f f i cc o n d i t i o n sa n d n e t w o r ke n v i r o n m e n t t h e ys h o wg o o dp e r f o r m a n c eo ft h ep r o p o s e dc o n g e s t i o n c o n t r o ls c h e m e s k e y w o r d ：c o m p u t e rc o m m u n i c a t i o nn e t w o r k s ，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 l ， s t a b i l i t y , b u f f e ro c c u p a n c y 甜m a s i l 矩i r s 舣t i i e s 。 1 1 概述 第一章概论 随着信息社会的来临，计算机网络变得越来越庞大，网络容纳的节点也 越来越多，路由策略必须能够应付不断增多的分组数量。不断增长的需求会 对网络的拓扑结构、网络的负荷能力提出挑战。当一个或多个网络连接失效 时或者当必须传输的分组数超过网络的负荷能力时，潜在的后果是网络产生 拥塞( c o n g e s t i o n ) ，或在一个甚至多个网络节点上大量分组堆积。网络产生猢 塞的严重后果则是网络的性能降低，甚至导致网络瘫痪。 简单地讲，所谓拥塞是指在某一时刻当网络中某一资源的到达量超过了该 资源在相关网络节点的承载量时，则称该资源在该节点在该时阳j 内产生了拥 塞。随着网络的日益普及，网络用户的急剧增加，网上业务尤其是多媒体业 务的同益增多，不断增长的需求会对网络的拓扑结构和负荷能力提出挑战。 i n t e m e t 上最早的拥塞发生于1 9 8 6 年l o 月，当时网络的吞吐率由3 2 k b p s 下降 至l j 4 0 b p s 峨 t h m - 曲l k i 脚 a 肝 l l e s 姐娆 l k 眦 c l i f f 图1 1 拥塞发生时系统的情况 k 喊 c l i f f 硕士学位论文 l 5j e r s1 lj i ! s i s 一般使用图1 1b 1 柬描述拥塞的发生。当负载较小时，吞吐量和功率的增 跃与负载基本呈线性关系，而延迟增长缓慢：在负载超过k n e e 点之后，吞吐 量和功率的增长趋于缓慢，但延迟增长较快；当负载超过c l i f f 点之后，吞吐 量和功率急剧下降，延迟急剧上升。可以看出，负载在k n e e 点附近时网络的 使用效率最高。 塞控制实际上就是网络节点采取措施来避免拥塞的发生或 者对拥塞的发生做出反应，也就是使负载保持在k n e e 点附近。拥塞控制主要 考虑端节点之间的网络环境，目的是使负载不超过网络的传送能力；而流量 控制主要考虑发送端与接收端之间的点对点通信量，目的是使发送端的发送 速率不超过接收端的接收能力。 1 2 拥塞产生的原因 拥塞产生的根本原因在于用户( 或称为端系统) 提供给网络的负载( l o a d ) 犬于网络资源容量和处理能力。 封j 塞的具体表现为：数据包时延增加、数据 包丢失概率增大、服务质量( q u a l i t yo f s e r v i c e ，q o s ) 降低等。拥塞一旦发生， 如果不采取正确的方法来加以控制，会继续加重网络的负担，最终将导致整 个网络的崩溃。 拥塞产生的直接原因3 1 主要表现在： 】) 存储空间不足。当几个输入数据向同一个输出端口发送数据包的时候，数 据包会在这个端口排队等待被处理。如果没有足够的存储空问来存储，输 出端口就会将排列在队尾的数据包丢弃。当有突发数据流时更是如此。增 加存储空问在某种程度上可以缓解这一矛盾，但是如果路由器有无限大的 存储量时，拥塞的情况只会变得更坏，而不是免好。因为随着路由器的存 储容量的增加，数据包在队列中等待的时问也会随之而变长，等到这些数 据包经过长时问排队完成转发时，它们早己超时，此时发送方会认为它们 已经被丢弃因而重新发送这些数据包，从而浪费网络资源，加重网络捅塞 的情况。 2 ) 带宽容量相对不足。在低速链路中进行高速数据流的传输时也会产生拥 2 耻m a s t e 牝r s 敞 i i i e s i 。 塞a 根据香农信息理论，任何信道带宽最大值即信道容量i 。 c = b l o g ：( 1 十s n ) ( 其中，n 为信道白噪声的平均功率，s 为信源的平 均功率，b 为信道带宽) 。所有信源发送的速率r 必须小于或等于信道容 量c 。如果r c ，则在理论上1 4 - 6 无差错传输就是不可能的，所以在网络 的低速链路处就会形成带宽瓶颈。当瓶颈满足不了通过它的所有源端带宽 要求时，网络就会发生拥塞。 3 ) 处理器处理能力弱，速度慢。如果路由器的c p u 在处理排队缓存，更新 路由表等功能时，处理速度跟不上高速链路的要求，同样也会产生拥塞。 此外，低速链路对高速c p u 也会产生拥塞。 要避免拥塞的发生，对以上三点原因需要综合考虑。例如，提高链路速 率而不改变处理器，只会转移网络瓶颈，而不能从真正意义上避免拥塞，所 以拥塞往往也是系统各部分不匹配的结果。 拥塞一旦发生，往往会形成一个恶性循环，而且不断加重的过程。如果 路由器没有空余的缓存，它就必须丢弃新到的数据包。当数据包丢弃时，发 送方会因超时而重传被丢弃的数据包。 认之前，发送方只能保留这些数据包， 会不断的加重。 1 3 拥塞控制 而且在没有得到已发送的数据包的确 结果缓存会进一步消耗，拥塞的情况 对于a t m 和t c p i p 高速网来说，网络交通管理的地位显得尤其重要。 随着多媒体业务的发展，网上业务变得日益繁忙。通信流量的迅猛增长会使 主干网产生拥塞，为此主干网路由器或交换机必须采取一定的策略来避免和 控制网络拥塞，以保证网络的通畅和保证所需的服务质量。由图1 1 可以看 出，k n e e 点是系统最理想的工作点。拥塞控制就是采用某种策略或机制，保 持网络工作在正常状态下，也就是使网络始终工作在c l i f f 点左侧的区域内， 尽可能使其工作在k n e e 点附近。 硕士学位论文 m a sf e r si l i e s i $ 通常拥塞控制算法包括捌塞避免( c o n g e s t i o na v o i d a n c e ) 和拥塞恢复 ( c o n g e s t i o nr e c o v e r y ) 这两种不同的机制。拥塞避免机制的目的就是使网络工 作在k n e e 点附近：拥塞恢复机制的目的就是当网络工作在c l i f f 点或c l i f f 点 以后时，使网络回复至k n e e 点前后。拥塞避免策略是预防性的，其目标是避 免网络进入拥塞状态，使网络能够在高吞吐量、低延迟的状态下运行：而拥 塞恢复策略是救治性的，其目标是当拥塞发生后，使得网络复原至j 下常的工 作状态，它用于把网络从搠塞状态中恢复出来。若没有拥塞恢复机制，当拥 塞发生时网络有可能崩溃。因此，即使使用了拥塞避免策略，仍需要拥塞恢 复策略来保持吞吐率。此外网络中源节点发送数据的起始时间、发送速率及 数据量具有不可预测性和突发性，这些也有可能会导致网络的拥塞。 网络的拥塞控制一般有开环控制( o p e n 1 0 0 pc o n t r 0 1 ) 和闭环控制 ( c l o s e d 1 0 0 pc o n t r 0 1 ) 两种。对于i n t e m e t 这种网络业务不断变化的复杂系统， 通常倾向于二采用闭环的拥塞控制方法。根据控制论的观点，发送方接收来自 接收方的反馈信息，利用反馈信息来了解当前网络的情况( 如交换节点：| 爿j 塞 的情况、数据包是否到达、数据是否正确等等信息) ，并确定控制参数，然后 依据预先设定的控制算法来调整发送速率，完成对网络拥塞的响应。正确的 控制算法和准确及时的控制参数是网络拥塞控制的关键。因此，网络拥塞控 制的研究重点就变成研究控制算法和控制参数。 1 4 拥塞控制算法 由于拥塞产生的原因众多，因而解决方案也随之而异，但目前在a t m 和 t c p i p 网络中较常用的方案为基于速率的拥塞控制方案和基于窗口的拥塞控 制方案，而前者目前正成为国际上的研究热点。典型的基于速率的拥塞控制 技术包括前向显式通知拥塞方案( f o r w a r de x p l i c i tc o n g e s t i o n n o t i f i c a t i o n ， f e c n ) 和后向显式通知拥塞方案( b a c k w a r de x p l i c i tc o n g e s t i o nn o t i f i c a t i o n ， b e c n ) 。这两种方案在低速网络中使用效果良好，但在高速网络中却不能彻 底解决系统不稳定即抖动( o s c i l l a t i o n ) 的问题。一般网络交换节点处缓冲占 射m a s h 牝! r s 敞f l l e s l 。 有量的动态抖动如果过大，则容易丢失数据包，因而系统的稳定性对拥塞控 制方案十分重要| 1 1 。 为了解决t c p i p 网络中的抖动问题，文【3 】提出了使用控制理论的思想， 文【7 8 】对此做了进一步地阐述。但这些方法通常都要求依据不同的网络环境 变换反馈控制参数以确保系统的稳定性，这对于网络的软、硬件实现势必带 来一定的不便。文【9 j 提出了一种基于速率的跳式流控制方案( h o p b y - h o d r a t e - b a s e df l o wc o n t r o ls c h e m e ) 来控制虚拟连接( v i r t u a lc o n n e c t i o n ，v c ) 交 换节点到虚拟链路带宽( b a n d w i d t h ) 的分配。在文【1 0 仲s m i t h 预测控制定理 被运用到a t m 网络中用来设计可获字节速率( a v a i l a b l e b i t r a t e ，a b r ) 的输 入速率。文 1 1 - 1 2 针对常字节速率( c o n s t a n t b i t r a t e ，c b r ) 单个节点的情况 提出了两种线性反馈拥塞控制算法。文献 1 3 提出了单控制交通源与其他信源 共享瓶颈节点的情况下，运用h “控制的理论来设计拥塞控制器的思路和方 法。 目前在基于速率的网络拥塞控制中多采用比例加微分( p r o p o r t i o n a lp l u s d e r i v a t i v e ，p d ) 控制方案。文p 1 最早针对单个拥塞节点的情况提出了一种 p d 控制方案。文【8 则在文 3 】的基础上，针对网络的流量变化对于p d 控制方 案设计做了进一步地阐述，并利用其所提出的仿真测试模型，同时针对局域 网与广域网的情况进行仿真。此后设计p d 控制的论文女n 1 4 】和 1 5 】均是在文 f 8 】的控制方案基础上进行深入研究，最近文【1 6 也在文【8 的基础上提出了一 种新的简化了的p d 控制方案。文献 1 7 1 在单个信源单个信终端节点模型的基 础上，在以上研究的基础上也提出了一种采用p d 控制的设计方案。同时文 献1 8 2 0 卿j 在单个信源单个信终端节点模型的基础上，提出了利用比例加微 分( p r o p o r t i o n a lp l u si n t e g r a t i v e ，p i ) 、比例( p r o p o r t i o n a lp l u sp r o p o r t i o n a l ，p p ) 和比例微分加积分( p r o p o r t i o n a li n t e g r a t i v ep l u sd e r i v a t i v e ，p i d ) 的拥塞控制 器方案。通过对以上各种仿真器的仿真结果进行比较，发现p i d 控制方案比 其他控制方案使得系统稳定的响应时间更短。响应时间短的控制方案有如下 优势：在信终端节点缓冲占有量l 临近门限值时，可以尽快通知信源端减少发 送速率，防止数据包丢失；另一方面，当系统的可用带宽增加时，可以很快 地通知信源端提高发送速率，尽快地利用可用带宽，提高带宽利用率。文献 硕士学位论文 n k a s i e r sr l i i e s i s 【2 1 2 4 则针对单个信源多个信终端节点( 即端对端系统) 模型的基础上，运 用控制理论中系统稳定的方法进行拥塞控制器的设计。 1 5 小结 拥塞控制的目的是希望通过对输入交通流( i n p u tt r a f f i cf l o w s ) 的控制以 达到拥塞避免即避免丢包和高的网络吞吐率之间的一种平衡。在a t m 中，使 用a b r 服务的用户可动态地公平地共享可用带宽，但却得不到必要的服务质 量( q o s ) ，只有在发生延迟时，丢失的数据包数达到最小。a t m 论坛中定义 了一种端对端的基于速率反馈流控方法来控制信源端的速率 2 s 1 。该方法中所 涉及的反馈信息包括依据网络控制策略所确定的瓶颈节点的状念和可用带宽 的内容。信源端所产生资源管理( r e s o u r c em a n a g e m e n t ，r m ) 信元的速率 是一般数据信元的若干倍。接收端接收r m 信元后，将该信元反馈回信源节 点。在游程中交换节点检验和修正r a m 信元的信息，r m 将链路中拥塞程度 和可用带宽的公平分配情况反馈回源端。要实现此目的交换节点应至少能实 现以下控制方法中的一种方法：1 ) 单位显式前向拥塞标记方法( s i n g l e b i t e x p l i c i tf o r w a r dc o n g e s t i o ni n d i c a t i o nm a r k i n gs c h e m e ) 。此方法中，若交换节点 发生拥塞，交换节点对数据信元头部的e f c i 置位；2 ) 多位显式速率标记方 法( m u l t i 七i te x p l i c i tr a t em a r k i n gs c h e m e ) 。该方法利用前向后向r m 信元中的 e r 域，来告知信源其可支持的速率。 尽管拥塞控制已有了相当的发展，由于网络的规模扩大的速度很快，网 络拥塞仍然是一个十分严峻的问题。特殊的网络应用也需要不同的拥塞控制 技术支持，因而拥塞控制技术对于未来网络的设计、协议工程及网络应用均 有着十分重要的意义。 1 6 本文的工作及结构 本文将考虑在多点流量控制模型的基础上，运用现代控制理论和稳定性 6 。l 。s f e r 雠 s i 1 i 文e s i 。 原则，设计由发送方驱动的单速率组播拥塞控制方案，并利用m a t l a b l 2 6 i 对所 设计的控制方案进行仿真。仿真结果显示组播系统具有较好的性能，组播源 端节点的发送速率和终端节点的缓冲占有量可逐渐趋于稳定。本文具体内容 安排如下： 第二章：介绍有关组播的基本情况。主要介绍组播的基本问题和解决的 办法，以及组播的常用分类方法。 第三章：详细讨论本文所设计的组播拥塞控制器的设计。这一章从单点 到多点的组播系统模型入手，提出了一类由发送方驱动的单速率的组播拥塞 控制器的设计方法，并利用现代控制理论中的s c h u r c o h n 判据和 r o u t h h u r w i t z 稳定性分析方法来进行系统的稳定性分析，并且讨论了在网络 中实现的具体细节。 第四章：利用m m l a b 对所设计的控制方案进行仿真。通过对于控制参数 的不同选择和网络情况的变化来进行仿真，仿真结果显示如果控制参数选择 合适，控制器可以使得组播系统的速率逐渐稳定，信终端节点的缓冲占有量 也能够趋于稳定。 第五章：对文中的单速率组播拥塞控制器的设计方法进行总结，并且对 今后的研究工作进行展望。 硕士学位论文 m a s i e r sj i l e s i s 第二章组播概述 随着计算机网络技术地不断发展，越来越多的网络应用需要使用组播 ( m u l t i c a s t ) 的支持，以便节省网络带宽，提高应用的可伸展性，可以说组 播是一种为优化使用网络资源而产生的技术。i e t f 将组播划分为两类1 2 7 1 ： 单点对多点模式和多点对多点模式。对于多点对多点模式，由于其在组播树 的生成和组管理等方面存在较大的难度，现阶段在i n t e r n e t 上推广的希望不 大，而且它可以通过多组单点对多点的通信来实现f 2 。因此本文也只考虑单 点到多点的工作模式。 组播的引入虽然节约了网络资源，减少了网络管理费用，但同时也给 i n t e r n e t 带来了许多潜在的问题【2 9 1 ，例如：组播安全问题、拥塞控制问题、组 播路由问题和错误恢复问题等，而其中组播 | i 塞控制是所有问题中重要但又 难解决的一个问题，同时也是最令人关注的问题之一。如果组播应用不能对 网络搠塞做出正确响应，将会给i n t e r n e t 带来比单播( u n i c a s t ) 投递应用产生 的 j 塞更为严重的影响。这主要因为1 2 8 - 2 r 4 3 】：( i ) 组播数据流可能沿着其多 点投递树广泛分布于整个i n t e r n e t ：( 2 ) 组播数据流的接收方具有异构性，每 个接受方的处理能力不同，其分组投递路径也可能有不同的带宽和差错特性： ( 3 ) 组播发送方需要处理比单点投递多得多的反馈报文，对这些报文如果不加 以处理，不仅可能淹没发送方，而且它们本身也是对网络资源的一种极大的 开销。 2 1 端对端系统中拥塞控制任务的概述 图2 1 1 3 0 1 中描述了端对端组播拥塞控制的主要任务和设计方法。尽管图中 有些任务在单播系统中也有描述，但在组播系统中我们采取了一些不同的术 语加以区别。图中流量控制模块是搠塞控制的核心，它是指会话到网络中迸 船m a s h i r s1li羔es 行流量调节的方法或算法，这部分由调节参数和调节算法组成。 图2 】端对端系统中组播拥塞控制的土要任务和设计方法 通常流量控制的任务可由网络访问点或进行会话的端系统自身来执行， 而后者在当前i n l e r n e t 中较常用。从拥塞控制的角度而吉，在组播的会话过程 中接收方的关系有永久型和可变型两种。在永久型会话中，每个接收方无论 网络的状况如何变化，在整个通信过程中始终都存在。在这种情况下，拥塞 控制的关键就在于采用一定的方法对发送方的流量进行调节，而这个调节的 过程一般会受到最差接收方的影响。 但是在可变型会话中，为了在网络发生拥塞时进行缓解，在通信过程中 接收方可能会从整个组播系统中被删除或由源端对其进行一些改变。为此， 可通过流量调节和组成员的关系两者之间进行平衡来达到拥塞控制的目的。 在进行两者之间平衡时，一般依靠两个方面来确定：一是特殊应用的数据速 率要求，二是满足为尽可能多的接收方服务的需要。最简单的一种平衡方法 9 硕士学位论文 m a s i e r s t i l i s i s 是将组播中最慢的接收方从组播组中删除。这种方法实现起来虽然简单，但 是在实际网络中却并不可行。目前有一种改进的方法是将组播中接收方按不 同的速率划分为不同的分组，对于最慢的分组，在实时通信中他们的延迟最 长，而且服务质量最低。但是在这种方式下，数据必须按定的编码和分层 技术来进行组织，以便于对不同的分组提供数据。在图2 1 中，这些任务由组 管理和数据组织模块来完成。 从图21 中可以看出，在差错控制和拥塞控制两者之间也存在紧密的联 系。首先，发现和报告数据丢失对实现差错和拥塞控制都十分有帮助；其次， 数掘重传会加重整个网络的负担；最后差错恢复方法的实现也会影响编码和 数据组织，甚至对组的管理也有一定的影响 3 1 - 3 3 i 。 捌塞控制任务的实旌一般都由大量的小任务组成。这些小任务可交出发 送方或接收方来完成，也可以由双方共同来完成。在单播通信中，这些任务 的划分远不及组播中那么重要和复杂。但值得一提的是，在t c p 网络中，接 收方要反馈下一个希望接收的数据包的编号等信息给发送方，发送方则需要 根据这些反馈信息调节发送窗口的大小，确立下一个被发送的数据等。因此 如果在组播环境中对任务进行划分后，接收方可能会有更多的任务( 如自行 调节窗口大小及反馈必要的信息等等) 要完成。 在组播通信中，会话内任务的组织即不同任务在发送方和接收方之阳j 的 分派与组织，对整个端对端协议是一个关键的特性。协议的鲁棒性、会话内 控制信息的交换等原因所导致的系统丌销以及协议的扩展性等都依靠此特性 来确定。会话内任务的组织会受到诸如组内接收方的关系与接收方是否了解 每个接收方是否存在等因素的影响；反之，组织内接收方的组织方式对差错 控制和流量控制算法亦有一定的约束力。 酣m a s i e 牡r s 敞t i i e s i 。 2 2 组播的基本问题和解决办法 2 2 1 可扩展性 在任何组播拥塞控制算法中一个关键的设计原则就是其可扩展性 ( s c a l a b i l i t y ) 。所谓可扩展性【3 4 】是指算法在性能丌始下降前可以支持多少用 户。在拥塞控制中，可扩展性会直接受到以下两个方面的限制m3 4 i ： i 当组成员的数量越来越大时，拥塞控制任务也会越来越复杂。 可以通过在发送方和接收方之间进行协作分工的方式来解决此 间题： i i 流量调节算法的限制。从图2 1 中可以看出调节算法的公平性 和搠塞预防的能力，该算法需要依靠组中所有成员来确定。 组播拥塞最核心的问题是可扩展性。在个组播组中接收方数量往往很 大，而且还可能遍布于整个i n t e r n e t ，因此在发送方需要处理大量的反馈报文 ( 如确认报文、否定报文或状态报文等) ，若不及时对这些报文进行正确处理， 将会导致两类经典问题：速率归零( r a t ed r o p t o z e r o ) 和反馈风暴( f e e d b a c k i m p l o s i o n ) 。 一般在组播拥塞控制时需要考虑所有组成员的拥塞状况，随着组规模地 扩大，来自接收方的大量反馈报文可能会湮没发送方，从而导致反馈风暴。 对于反馈风暴的问题，可以采用反馈抑制机制【3 5 - 3 8 j ( f e e d b a c ks u p p r e s s i o n m e c h a n i s m ) 来解决。 在当前网络中，通常将数据包的丢失作为网络拥塞的唯一信号。当网络 拥塞时，若发送方对每一个接收方的数据丢失做出响应的话，那么其发送速 率可能下降为零。对于速率归零的问题，可以采用反馈聚集机制 3 5 - 3 8 1 ( f e e d b a c ka g g r e g a t i o nm e c h a n i s m ) 来解决。 在实际网络中，组播般表现为三种情况( 39 j ：独立型拥塞( i n d e p e n d e n t c o n g e s t i o n ) 、共享型拥塞( s h a r e dc o n g e s t i o n ) 和混合型拥塞( c o m b i n a t i o n o f i n d e p e n d e n t a n ds h a r e dc o n g e s t i o n h y b r i dc o n g e s t i o n ) ，如图2 2 所示。图中s 表 示发送方，r 表示接收方，虚线表示发生拥塞的链路。 硕士学位论文 独立型 共享型混合型 图2 2 组橘拥塞的类j 弘 在独立型搠塞中，每个因拥塞而丢失报文的接收方将向发送方反馈不同 的拥塞信息，发送方会对每个拥塞信息做出响应，降低发送速率。当独立型 捌塞较多时，最终将导致发送速率归零。在共享型拥塞中，拥塞链路下游的 每个接收方都将向发送方反馈丢失信息，如果下游接受方数目较多时，此时 将发反馈风暴。而在混合型拥塞中，以上两种现象均会发生。 2 2 2 公平性 在组播拥塞控制中，公平性例( f a i m e s s ) 是每个组播拥塞控制算法所追求 的设计目标之，也是其可否得到广泛应用的基础之一。组播拥塞控制中的 公平性主要表现在两个方面： 协议内的公平性( i n t r a p r o t o c o lf a i r n e s s ) 协议内的公平性是指发送方在通信过程中对每一一个接收方都按照同 样的标准发送数据包。在组播中，发送方的发送速率一般受到组中所有 接收方的制约，而且通常是由最差的接收方的发送速率来决定。 t c p 友好( t c p - f r i e n d l y ) t c p 在当前i n t e r n e t 中占据了统治地位，其成功归因于它的拥塞控制 和差错控制机制【1 1 。然而随着网络应用地不断发展，组播可能在未来的 网络中变得越来越重要。组播拥塞控制协议应该保证当组播流与t c p 流 融m a s i e 张r s 敞t i i e s i ； 共享瓶颈链路时，双方可以公平地占用网络带宽，即组播的t c p 友好， 这也称为协议间的公平性( i n t e r p r o t o c o lf a i r n e s s ) 。 目前网络中数据流多使用t c p 作为可靠传输协议，若组播拥塞控制 与t c p 不同，可能会导致两者无法公平地共享网络带宽，甚至可能因抑 制t c p 流而导致整个i n t e r n e t 的崩溃。 当前对于组播t c p 友好存在多种定义。文献【4 0 】给出的一科t 定义是 “非t c p 流量的长期吞吐量不超过相同情况下t c p 流量的吞吐量”，而 文献f 4 1 1 对t c p 友好给出了更加严格的定义： 夺所谓单播t c p 友好，是指在相同网络条件下，如果一个单播流 量对其他并存t c p 流量的长期吞吐量的影响( 减少) 不大于另 外一个t c p 流量对后者的影响，此单播流量被认为是t c p 友好； 夺所谓组播t c p 友好，是指在发送端与每个接收端之间，如果流 量具有单播流量t c p 友好的特性，此组播流量被认为是t c p 友 好。 值得一提的是，目前对于组播t c p 友好的定义还存在很多争论。有些定 义指出，由于组播流量为多个接收方服务，因此应该允许组播流量使用比单 播流量稍多的带宽。但文献 4 2 】采用下面的公式来定义组播t c p 友好： a 。r ，r b r l u i ， 这里r 表示瓶颈链路上的组播流的速率，k ，表示相同情况下t c p 流的速率 口和b 是流接收端数目的函数。当b = 1 时，以上两种定义是相同的。 2 2 3 异构性 异构性4 3 1 是指组播的接收方处理能力不同，而且报文到达不同接收方经 历的链路的网络特性( 如带宽、延迟等) 不同。更为重要的是，链路的异构 性在组播会话期阳j 常常是动态变化的，这就更增加了拥塞控制的难度a 为保 证报文的可靠投递，发送方需要及时地获取由每个接收者或其它网络设备的 m a s t e r 雠 $ t i i e 文s i 。 反馈信息，调整发送速率、重传丢失报文。因此，组播拥塞控制往往选择最 差接收方的发送速率来发送报文，这在很大程度上浪费了网络资源，降低了 组播通信的效率。 2 3 分类 对于组播的分类根据不同的分类条件可以有多种分类结果，下面将介绍 目前几种比较常见分类方法和分类结果。 2 3 1 发送方驱动的组播拥塞控制和接收方驱动的组播拥塞控制 如果按照控制算法的驱动方式可以划分为以下两类： 发送方驱动的组播拥塞控制 3 9 , 4 4 , 4 8 - 5 1 1 ( s e n d e r d r i v e nm u l t i c a s t c o n g e s t i o nc o n t r 0 1 ) 这种方式与t c p 中类似。拥塞算法放置在发送方，每个接收方按照一定 的时间周期向发送方发送反馈报文，发送方则从反馈报文中获取有关的信息， 并以此来调整发送速率。在这种方式中，发送方需接收并处理大量的反馈报 文，极易发生反馈风暴。为解决此问题，需采用反馈抑制和反馈聚合的机制 来解决。文献 3 9 还提出采用基于代表的方案来减少反馈报文的数目，但却需 增加附加网络设备或向现有网络设备中添加复杂的归并算法，因此并不能从 根本上解决可扩展性问题。 利用发送方驱动的组播拥塞算法，发送方能及时地了解整个组播组的状 况，并做出响应。但是在发送方需要处理大量的反馈报文，并且要进行大量 的计算，开销过大，容易造成网络瓶颈，可扩展性较差。 接收方驱动的组播拥塞控制3 0 , 4 9 - 5 0 , 5 2 - 5 4 ( r e c e i v e r d r i v e nm u l t i c a s t c o n g e s t i o nc o n t r 0 1 ) 在接收方驱动的组播拥塞控制中，数据被组织成不同的层次，发送到不 同的组播组。接收方根据当前网络情况订阅适当的层次。在这种方式中大量 靴m a s i e 牝r s 敞t i i e s 。 的计算任务交由接收方完成，减轻了发送方的计算开销。 但是接收方驱动的组播方式中也存在不少缺陷2 “3 4 ，”1 ：1 ) 在进行大数据 传输时，对数据不易自然分层，而且分层难以实现数据的一致性和有序性；2 ) 由于编码和译码的复杂性，可用层次数较少，因此会限制拥塞的自适应范围； 3 ) 当接收方加入和离丌组播组时，会增加系统的丌销，而且会过分依赖组播 路由协议；4 ) 大多数接收方驱动的协议中主要通过n a k s 来确定网络拥塞程 度，如果发送方没有收到反馈n a k s ，则有可能错误地推断网络无拥塞或拥 塞已清除；4 ) 接收方驱动的协议中采用的随机n a k 抑制技术要求每个接收 者执行复杂度为o ( n2 ) 的链路往返时间计算丌销，这在一定程度上限制了协议 的可扩展性。 2 3 2 基于速率的组播拥塞控制和基于窗口的组播拥塞控制 如果按照j j 塞控制参数束划分，组播可以划分为两类： 基于速率的组播拥塞控制 3 9 , 4 4 - 4 5 , 4 9 - 5 0 , 5 5 - 5 6 1 ( r a t e b a s e d m u l t i c a s t c o n g e s t i o n c o n t r 0 1 ) 在这种方式下所调整的拥塞控制参数是发送速率( t r a n s m i s s i o nr a t e ) 。拥 塞控制算法根据网络的状态调整发送速率，使其不超过某个期望值。一般在 组播中这种拥塞控制的实现方法与单播通信中类似。为了实现协议间的公平 性，通常有以下几种常用的方法： i a i m d 拥塞控制1 3 9 ：这种方法与t c p 协议中a i m d ( a d d i t i v e i n c r e a s e a n d m u l t i p l i c a t i v ed e c r e a s e l 行为类似。这种方法实现起来虽然十分简单，但速 率在短期内易出现与t c p 相似的锯齿形： i i 基于稳态下t c p 响应函数的拥塞控制5 0 , 5 5 6 j ：为了保持速率变化 的平衡性，实现与t c p 公平共享网络带宽，并且不失对拥塞进行响应，可采用 稳定状态下t c p 速率响应函数作为其响应函数。式( 2 1 ) 、( 2 2 ) 为两种常 用的t c p 速率晌应函数1 4 4 】： 删浮m a s t e r 雠 s t i i 文e s i ； t = 7 ! - i 型! ! ! 些 r t t x q p m r 玎j 币+ ，。m i n ( 1 ，3 厕) p ( 1 + 3 2 p 2 ) ( 21 ) ( 2 2 ) 在( 2 1 ) 、( 2 2 ) 式中，m 表示分组大小( p a c k e ts i z e ) ，p 表示丢包率， r 玎表示游程延迟( r o u n dt r i pd e l a y ) ，k 。表示超时重传值。( 2 1 ) 式中所 给出的是在未考虑t c p 超时情况下，t c p 稳念时的吞吐量，( 2 2 ) 式中所给 出的是在考虑了超时和高丢包率的前提下t c p 的稳态行为。利用这两式进行 调整可以产生适合于多媒体应用的平滑速率，但却需要在拥塞反应速度和速 率振荡之间作出权衡，而且尺7 t 与p 的测量精确性决定着响应函数的准确度。 i i i 优化的一二阶速率控制1 4 3j ( o p t i m a ls e c o n d o r d e rr a t ec o n t r 0 1 ) ：这种方 法与a i m d 类似，在增加时仍然按照速率的变化线性增加，但是在减少时则按 照指数规律减少。 利用基于速率的组播拥塞控制，可以不需要像基于窗 1 的组播拥塞控制那 样维护窗口，而且在单播或组播中的实现方法类似，可扩展性好。但是这种方 式必须测定r t t ，在组播中测量r t t 比在单播中复杂的多；发送方也需从接收 方收集控制参数，若不采取适当的反馈抑制机制，发送方也会遇到反馈风暴问 题。 基于窗口的组播拥塞控制4 2 , 5 1 1 ( w i n d o w b a s e dc o n g e s t i o nc o n t r 0 1 ) 这种方式与t c p 中窗口机制类似。在组播窗口拥塞机制中，在端系统设 立窗口，通过窗口来控制未应答的分组数目，窗口的维护由端系统来完成。 每发送一个数据分组，窗口的一部分会被占用，知道此分组的a c k 信号收到 后j 会释放。当窗口有空闲时，发送方可继续发送数据。没有拥塞时增加窗 口数；发生拥塞时则减少窗口数目。发送方始终要保证被所有接收方确认的 报文个数小于窗口的大小。 在基于窗口的组播拥塞