（计算机应用技术专业论文）网络多播拥塞控制技术研究.pdf

硕上论文网络多播拥塞控制技术研究 摘要 近年来，随着网络技术的飞速发展，网络带宽的不断增加，许多新的多媒体应用开 始涌现，例如视频广播、视频点播、会议电话等。对于这些应用的飞速发展，如果仅仅 使用传统的单播技术，将会带来大量的带宽浪费。多播技术能够在不改变当前网络结构， 不增加过多的额外投资的前提下，在一定范围内，有效的缓解带宽消耗过大的压力。在 多播拥塞控制技术领域里，多播拥塞控制器的设计得到极大关注。 本文利用了单点到多点的多播系统模型，并根据校园网实际的数据流量，设计了一 种发送端驱动的单速率多播拥塞控制器。运用现代控制理论，s c h u r - c o h n 判据和 r o u t h - h u r w i t z 稳定性判断方法，为控制器选取较优的参数。通过理论计算证实，发送 端设置此多播控制器，多播信源端节点的发送速率趋于稳定，并且分支节点缓冲占有量 也趋于稳定。 本文在n s 2 的仿真环境下，搭建了多播仿真平台，建立自相似流量模型和指数分 布流量模型，并以多播拥塞控制器理论计算得到的值为基础，在数据源加上不同的负载， 研究在不同模型下，分支节点缓冲占有量的均值，峰值以及瞬态响应情况。通过仿真数 据的分析，我们可以得到以下结论：在自相似流量模型下，当网络负载不超过5 4 1 时， 网络不会发生拥塞，并且缓冲占有量较小；在指数分布流量模型下，当网络负载不超过 9 2 7 时，网络不会发生拥塞，并且缓冲占有量较大。自相似流量比指数分布流量具有 更大的突发性，本文通过仿真证明：网络传输指数流量负载的能力更强；多播拥塞控制 器的理论设计是合理的。这对我们在校园网中，设定分支节点的缓冲占有量和控制源端 的负载具有现实的指导意义。 关键词：多播，拥塞控制，缓冲占有量，自相似，指数分布 a b s t r a c t 硕上论文 a b s t r a c t w i t ht h es p e e d yn e t w o r kt e c h n o l o g ya n db a n d w i d t hi m p r o v e m e n tan u m b e ro fn e w m u l t i m e d i aa p p l i c a t i o n si m m e r g e s ，s u c ha s ：v i d e ob r o a d c a s t ，v i d e oo nd e m a n d ，c o n f e r e n c e c a l la n de t c f o rt h e s en e wa p p l i c a t i o n s ，t r a d i t i o n a lu n i c a s ta n db r o a d c a s tt e c h n o l o g yw i l l r e s u l ti nb i gb a n d w i d t hw a s t e m u l t i c a s tt e c h n o l o g yc a ns i g n i f i c a n t l yr e l i e v et h eb a n d w i d t h c o n s u m p t i o nw i t h o u tc h a n g i n gc u r r e n tn e t w o r ks t r u c t u r ea n dp u t t i n gm u c hi n v e s t m e n t i nt h e m u l t i c a s tc o n g e s t i o nc o n t r o lf i e l d ，m u l t i c a s tc o n g e s t i o nc o n t r 0 1d e v i c eh a sb e e ng i v e nm u c h a t t e n t i o n i nt 1 1 i sp a p e r , w eu t i l i z eao n e n o d et om a n y n o d em u l t i c a s tm o d e la n dt h ed a t af l o wo f c a m p u sn e t w o r kt od e s i g nac o n g e s t i o nc o n t r o ld e v i c ew h i c hi sa taf i x e ds e n d i n gr a t ea n d e n dd r i v e n w i t ht h em o d e mc o n t r o lt h e o f i e s s c h u r - c o h nc r i t e r i o na n dr o u t h 。h u r w i t z s t a b i l i t yj u d g m e n tm e t h o d ，w ef i n dt h eb e t t e rp a r a m e t e r s t h ec a l c u l a t e dr e s u l t sp r o v e st h e d e v i c ec a nm a k et h es o u r c e st r a n s m i t t i n gr a t es t e a d ya n db r a n c h e sb u f f e ro c c u p a n c ya ta s t a b l ev o l u m e t h e nie s t a b l i s h e dam u l t i c a s tm o d e l i nn s 2 a n da d ds e l f - s i m i l a rf l o wa n de x p o n e n t i a l d i s t r i b u t i o nf l o w i nt h eb a s i so fc a l c u l a t e dr e s u l t sb yt h ed e v i c e ，w eg i v ed i f f e r e n tl o a d sa t s o u r c ea n d s t u d yt h e b r a n c h e s a v e r a g eo c c u p a n c y , m a xo c c u p a n c ya n dr e a l t i m e o c c u p a n c y w i t ht h es i m u l a t i o nd a t a , w ec o u l dg e tt h ef o l i o w i n gc o n c l u s i o n ：i ns e l f - s i m i l a r f l o wm o d e l ，w h e nt h el o a dd o e s n ts u r p a s s5 4 1 ，t h e r ei sn oc o n g e s t i o ni nn e t w o r k a n dt h e o c c u p a n c ya tal o w e rv o l u m e ；i ne x p o n e n t i a ld i s t r i b u t i o nf l o wm o d e l w h e nt h el o a dd o e s n t s u r p a s s9 2 。7 ，t h e r ei sn oc o n g e s t i o ni nn e t w o r k ，a n dt h eo c c u p a n c ya tah i g h e rv o l u m e s e l f - s i m i l a rf l o wi ss h a r p e rt h a ne x p o n e n t i a ld i s t r i b u t i o nf l o w t h i sp a p e rp r o v e s ：n e t w o r k h a sas t r o n g e rc a p a b i l i t yt ot r a n s p o r te x p o n e n t i a ld i s t r i b u t i o nf l o wa n dt h ed e s i g no ft h e d e v i c ei sr e a s o n a b l e t h er e s u l t sc a ng i v es o m ea d v i c ew h e nw es e tt h eo c c u p a n c yv o l u m e a n dn e t w o r kl o a di nc a m p u sn e t w o r k k e yw o r d s ：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 ，b u f f e ro c c u p a n c y , s e l f - s i m i l a r , e x p o n e n t i a l d i s t r i b u t i o n 声明 本学位论文是我在导师的指导下取得的研究成果，尽我所知，在 本学位论文中，除了加以标注和致谢的部分外，不包含其他人已经发 表或公布过的研究成果，也不包含我为获得任何教育机构的学位或学 历而使用过的材料。与我一同工作的同事对本学位论文做出的贡献均 已在论文中作了明确的说明。 细7 年6 月万日 学位论文使用授权声明 南京理工大学有权保存本学位论文的电子和纸质文档，可以借阅 或上网公布本学位论文的部分或全部内容，可以向有关部门或机构送 交并授权其保存、借阅或上网公布本学位论文的部分或全部内容。对 于保密论文，按保密的有关规定和程序处理。 硕十论文网络多播拥塞控制技术研究 1 综述 1 1 概述 近年来，计算机技术和通信技术的飞速发展带来i n t e m e t 也以惊人的速度发展。 i n t e m e t 已经走进了干家万户，它全方位地影响着我们的各项生活。信息爆炸已不是一 个陌生的名词，每个人的生活都受到信息所带来的冲击。新的网络应用，例如，视频点 播、网络购物、远程教育、视频电话等等，人们尽情享受着i n t e m e t 所带来的便捷。但 是，随着这些应用相继产生，网络需要传输的数据量也呈现指数级的增长。这就对网络 的负荷能力提出了更高的要求，也就导致了问题的产生。当网络中需要传输的分组数量 超过了网络的总负载能力时，就可能导致网络发生拥塞，即使没有拥塞，也会在一些网 络节点处出现大量的传输分组堆积，使得网络性能大幅下降。网络拥塞问题已经成为人 们关注的热点。 网络拥塞会导致很多不良的后果。一旦发生拥塞，整个网络的性能就会下降，整个 系统的吞吐量也会下降、严重时甚至有可能导致整个系统瘫痪。下面从三个方面对拥塞 产生的危害i l3 l 进行具体描述： ( 1 ) 网络的性能下降 网络的性能下降主要表现在分组从发送端到达目的节点的延迟增大以及丢包率增 大【2 】。因为拥塞产生后，路由器的缓冲队列中等待排队输出的分组就会增多，但路由器 对分组的处理能力是有限的。这就会使得每个分组等待处理的时间增长。如果这个等待 的时间超过了发送端对这个分组设置的重传时间，发送端就会认为该分组丢失了。发送 端就会重传该分组，这样导致更多的分组而且是重复的分组进入网络，使有效传输率下 降，还进一步加剧了拥塞，延迟增大。这样的状态一持续，慢慢地当路由器的缓冲队列 已满，到来的分组就会被丢弃，丢包率增大。 ( 2 ) 系统的吞吐量下降 上面已经提到了，网络发生拥塞时，网络中发送的分组，一部分因为超时被重传了， 一部分因为路由器的缓冲队列已满被丢弃了，链路中实际传输的有效分组其实就很少 了，系统的吞吐量自然就会下降。在这个过程中，链路得不到充分地利用，降低了资源 的有效利用率。 ( 3 ) 系统瘫痪 网络发生拥塞时，网络就可能进入死锁状态。此时的网络，工作效率几乎为零，网 络上几乎没有什么有效的数据传输。此时，如果网络负载增加，即使是极小的网络负载， 也有可能导致网络瘫痪。 i n t e m e t 历史上第一次关于网络拥塞的记载是发生在1 9 8 6 年1 0 月。这次拥塞发生 1 l 综述硕士论文 在连接l b l ( l a w r e n c eb e r k e l e yl a b o r a t o r y ) 至ou cb e r k e l e y 之间的网络上。虽然当时它 们的距离只有4 0 0 码，而且二者之间的网络连接情况也非常简单。当拥塞发生时，它们 之间的数据吞吐量从原本的3 2 k b p s 急剧地下降到了4 0 b p s 们】，降幅惊人，由此拥塞 的危害性也可见一斑。自此以后，人们花费越来越多的时间和精力来研究网络拥塞问题。 所以也就使得现在网络拥塞问题成为网络研究领域的热点，人们对它们的关注度一直居 高不下。 文献【2 2 】中使用图1 1 来描述拥塞发生时，网络的负载和吞吐量以及网络的负载和响 应时间三者之间的关系，其实这个图在其他的很多文献中也被引用了。图形中所表达的 意思，我们这里简单地描述如下：当负载( l o a d ) 较小时( 没有超过k n e e 时) ，吞吐 量( t h r o u g h p u t ) 和负载( 1 0 a d ) 之间呈线性的增长关系，而且增长率较大，同时，响应时间 ( r e s p o n s et i m e ) 和负载( 1 0 a d ) 之间也呈线性的增长关系，但是增长率较小。慢慢地，当负 载超过k n e e 之后，吞吐量和负载仍然呈线性的增长关系，但是增长速度明显放慢，于 此同时，响应时间的增长速度明显加快。当负载超过c l i f f 之后，吞吐量和负载之间的 线性关系急剧下降，响应时间急剧上升。文献中给图1 1 中横坐标的三段区间给出了定 义：【0 ，k n e e 一拥塞避免区间；【k n e e ，c l i f f 一拥塞恢复区间；【c l i f f , + 】拥塞崩溃区 间。根据图1 1 可以看出，当加入的负载的值在k n e e 左右时，网络的工作效率最高，系 统的整体性能最好。我们之前提到的拥塞控制的含义是指采取一定的措施，使负载尽量 保持在k n e e 值左右，因为这个时候网络能够传输更大的有效吞吐量，网络性能状态也 是最佳的。 在研究拥塞控制时，我们很容易把它和流控制这个概念发生混淆。流控制主要考虑 的对象是接收端，目的是使发送端的发送速率不超过接收端的接收能力。具体的实现过 程是这样的：当接收端的缓冲区已满时，发送端继续发送来的数据就会发生丢失。当接 收端对接收到的数据处理不过来时，就会发出“不再接收 的信号告知发送端。这时， 发送端就会停止发送数据，一直到接收到接收端发出的“可以再发送 的信号为止，它 再发送数据。在这个过程当中，我们只关注发送端和接收端，实现起来相对简单。相比 之下，捌塞控制就要复杂的多，它要考虑节点之间的网络环境，目的是使负载不超过网 络的传送能力。 2 硕上论文 网络多播拥寨控制技术研究 1 2 拥塞产生的原因 图1 1 拥塞的示意图 拥塞，在本质上是一种持续过载的网络状态。当拥塞发生时，也就是此时用户对网 络资源( 包括链路带宽、存储空间和处理器的处理能力等) 的需求超过了网络固有的容 量。就i n t e r n e t 的体系结构而言，拥塞的发生是其固有的属性。我们把拥塞产生的原 因简单概括为以下四点【1 6 】： ( 1 ) 存储空间不足 在共享网络中，对共享资源的使用是在事先没有任何协商和请求许可机制下进行 的。在这种环境下，几个i p 分组同时到达路由器，并期望经同一个输出端口转发的可 能性是存在的。显然，不是所有分组可以同时接受处理，必须有一个服务顺序，中间节 点上的缓存为等候服务的分组提供一定的保护。然而，如果此状况具有一定的持续性， 当缓存空间被耗尽，路由器只有丢弃分组。在这种持续过载的状态下，网络性能会急剧 下降。 ( 2 ) 处理器处理能力弱 处理器的速度和链路速度不匹配。不论是处理器的处理速度跟不上高速链路还是低 速链路跟不上处理器的处理速度都会发生拥塞。 ( 3 ) 带宽容量不足 根据香农公式：任何信道带宽的最大值为： 信道容量c = b l o g ：( i + s n ) 其中： n 一信道白噪声的平均功率，s 为信源的平均功率，b 为信道带宽。 所有发送端的发送速率r 不能大于信道容量c 。如果r 大于c ，在理论上就不可能 实现无差错传输。所以网络中的低速链路就成为数据传输的瓶颈。当某条链路不能满足 所有经过它的发送端的带宽要求时，网络就会发生拥塞。 ( 4 ) t c p i p 协议中拥塞控制机制的缺陷 l 综述 硕，f ：论文 t c p 是目前互联网上使用最广泛的传输协议，它已经成为保证互联网稳定性、健壮 性的重要因素。它的实现原理是基于端到端的拥塞控制。而这种拥塞控制机制最致命的 弱点是延迟问题。这与机制的实现原理有关。端到端拥塞控制是发送端根据接收到的接 收端的反馈信息来对发送速率进行调节的，反馈信息的传输会造成发送端速率调节的滞 后性，发送端不能及时地调整发送速率，从而造成网络出现拥塞。 上面列举出的只是产生拥塞的四个比较常见的因素，在实际的网络环境中还有其它 的一些因素也是需要考虑的。由此可见，网络的拥塞问题是一个相当复杂的问题，我们 需要综合考虑各种因素，如果我们只针对其中的一个因素加以解决，只会将问题转移， 不能从根本上解决拥塞问题。例如：如果为了缓解存储空间不足的问题，我们一味的增 加路由器的存储量，这样不仅不能解决存储空间不足的问题，还会使拥塞变得更坏。因 为数据包在网络里经过长时间排队等待继而完成转发时早己超时，发送端就会默认为它 们已经被丢弃，而这些数据包却还在继续向下一个路由器转发，这样一来既浪费了网络 的资源，同时也加重了网络拥塞。 1 3 拥塞控制机制 如果从控制理论的角度上来划分，拥塞控制算法可以分为两类：开环控制和闭环控 制【3 2 】【1 6 】。它们分别适用于不同的环境。前者适用于网络环境的流量事先可以准确的加 以确定，系统的性能事先也可以准确的确定；后者适用于网络环境的流量事先不可以准 确的加以确定，系统的性能事先也不可以准确的确定。 因为网络环境是动态实时变化的，在进行拥塞控制时，事先不可能对网络流量和系 统性能这些量进行确定，所以我们主要采用的是闭环控制方式。这种方式的设计关键是 如何产生反馈信息和如何对反馈信息做出相应地响应。 闭环的拥塞控制的过程可以分为三个阶段【2 0 j ： ( 1 ) 首先，需要检测网络中是否发生了拥塞，在哪儿发生了拥塞； ( 2 ) 然后，在发生拥塞的地方将拥塞信息以反馈分组的形式报告给拥塞控制点； ( 3 ) 最后，拥塞控制点再依据接收到的反馈分组中包含的拥塞信息进行调整从而 消除拥塞。 闭环的拥塞控制算法可以根据所在的闭环环境的变化动态实时地变化，但是算法的 性能会受到反馈延迟的影响。如果检测到的拥塞发生点和拥塞控制点之间的延迟很大， 算法的性能就会严重地下降。 1 4 拥塞控制算法 拥塞控制对确保互联网的健壮性起着至关重要的作用。在上一节中，列举了网 络产生拥塞的几个主要原因。其实，拥塞是一个非常复杂的问题，产生的原因也很多， 4 硕上论文网络多播拥塞控制技术研究 针对不同的原因，我们会有不同的解决方法。所以对拥塞控制算法的分类也是多种多样 的。例如：根据网络层次和拥塞控制算法实现的位置，拥塞控制算法可分为两类，t c p 拥塞控制和i p 拥塞控制【3 l 】。根据控制参数选择的不同，拥塞控制算法也可分为两类， 基于窗口的拥塞控制【1 2 1 和基于速率的拥塞控制【1 3 1 。在实际应用时，我们应该针对不同 的应用需求选择不同的拥塞控制算法。近来，为了解决网络中的抖动问题，也有不少文 献提出了控制理论的相关思想，但这些方法通常都要求依据不同的网络环境来变换反馈 控制参数用以确保系统的稳定性。 1 4 1 拥塞控制算法分类 在众多的拥塞控制算法中，根据算法的实现位置可以将拥塞控制算法分为链路算 法【7 4 1 3 3 1 和源算法两类。源算法中，t c p 协议【7 2 1 的使用最广泛。根据m c i 的统计，总字 节数的9 5 和总报文数的9 0 都是使用t c p 传输的。t c p 协议中采用了很多算法确保网 络的传输性能，我们知道的有，慢启动( s l o ws t a r t ) 、拥塞避免( c o n g e s t i o na v o i d a n c e ) 、 快速重传( f a s tr e t r a n s m i t ) 、快速恢复( f a s tr e c o v e r y ) 、选择性应答( s a c k ) 等。链路 算法【l6 j 的研究目前则主要集中在“主动队列管理 ( a c t i v eq u e u em a n a g e m e n t ，a q m ) 1 6 1 这一块。主动队列管理机制的实现原理是在网络设备的缓冲溢出之前丢弃或标记报文 【3 3 l ，使得缓冲区中维持一个较小的队列长度以降低排队延迟，提高吞吐量。 根据算法不同的控制参数，拥塞控制算法还可分成基于窗口和基于速率两类【l 引。 基于窗口的拥塞控制算法，需要在网络的端系统设置拥塞控制窗口。通过对拥塞控制窗 口的调整，控制还没有应答的分组数量。它的具体实现机制是这样的：当发送端发送一 个分组，拥塞窗口相应地增一。当它收到一个分组的应答反馈信息后，就会释放一个拥 塞窗口。如果拥塞窗口不满，发送端就可以继续发送分组。没有发生拥塞时，增加拥塞窗 口数目；发送拥塞时，减小拥塞窗口数目。基于速率的拥塞控制算法，还可进一步细分 为基于探测和基于模型。前者是指发送端通过调整自身的发送速率来探测网络的可用带 宽，通常采用的方法是a i m d 。而后者是利用t c p 连接的吞吐量模型，再根据测量得到的 一些参数，调整发送端的发送速率。 1 4 2 拥塞控制算法的评价标准 拥塞控制算法设计时要综合考虑整个网络系统的各个方面的因素，所以我们在对拥 塞控制算法做出评价时，应该从整个系统的角度。下面我们将要讨论在对拥塞控制算法 做出评价时，需要考虑的两个重要指标一资源分配的公平性和资源的利用率。 首先是公平性，这里我们明确地提出是资源分配的公平性【5 9 1 。网络中的资源，不仅 包括一些硬件，例如：链路的带宽、路由器的缓冲区、c p u 等等；还包括一些软件，最 主要的就是网络中传输的信息。资源分配的公平性，我们可以理解为在网络发生拥塞时， 各个连接都能公平地共享网络上的资源，包括硬件的和软件的。现在网络上传输数据流 5 1 综述 硕上论文 量比例最大的是t c p 流和u d p 流。所以在讨论公平性问题，我们主要是从下面两个方面 来考虑： ( 1 ) t c p 流和u d p 流之间的资源享用公平 ( 2 ) t c p 流之间的资源享用公平 前者主要是由于在发生拥塞时，t c p 流和u d p 流所做出的不同反应造成的。简单地 说，t c p 流具有拥塞控制机制，而u d p 流没有拥塞控制机制。在网络发生拥塞时，t c p 流会降低它的发送速率，相应的得到的资源就会减少，但是u d p 流不会降低发送速率， 得到的资源就相对较多，导致不公平的产生。后者主要跟一些参数的设置有关，例如， 拥塞控制窗口的大小、r t t 的值和设定的分组大小。研究表明，拥塞控制窗口值较大， r t t 值较小，分组设定的长度较大的流往往能占用更多的带宽。 其次是资源的利用率。拥塞控制的目的是更加有效地管理网络资源，使有限的网络 资源能够被合理地利用，最大程度地提高网络资源的利用率。在网络系统中，对于资源 的利用率，我们可以使用下面这样一个函数来衡量： e f f i c i e n c y = t h r o u g h p u t 术a r e s p o n s et i m e 参数说明：t h r o u g h p u t - - 吞吐量 r e s p o n s et i m e 一响应时间 fa = l ，一般情况 a 1 ，侧重吞吐量 la l ，侧重响应时间 在有些文献中，也将这个函数称为资源分配效率性。 1 5 论文主要研究工作与结构 1 5 1 论文的主要研究工作 首先，本文利用单点到多点的多播系统模型，设计了一种发送端驱动的单速率多播 拥塞控制器。根据校园网实际的数据流量，运用现代控制理论，s c h u r - c o h n 判据和 r o u t h h u r w i t z 稳定性判断方法对多播拥塞控制器的参数选取进行了讨论，并利用c + + 程序对所设计的控制方案进行理论数据的计算，为控制器选取较优的参数。通过理论计 算证实，发送端设置此多播拥塞控制器后，多播系统的性能良好，不会发生拥塞。发送 端的发送速率随着时间的推移慢慢趋于稳定，同时各个分支节点缓冲占有量也趋于稳 ，上， 疋。 然后，本文在n s 2 的仿真环境下，首先搭建了一个多播仿真平台，在发送端建立自 相似流量模型和指数分布流量模型，并以多播拥塞控制器理论计算得到的值为基础，在 6 硕上论文网络多播拥塞控制技术研究 两种数据源加上不同的负载，研究在不同的流量模型下，分支节点缓冲占有量的均值， 峰值以及瞬态响应的情况。通过仿真得到数据的分析，我们可以得到以下的结论：在自 相似流量模型下，当网络负载不超过5 4 1 时，网络不会发生拥塞，并且缓冲占有量较 小；在指数分布流量模型下，当网络负载不超过9 2 7 时，网络不会发生拥塞，并且缓 冲占有量较大。自相似流量比指数分布流量具有更大的突发性。通过本文的仿真结果证 明：网络传输指数模型负载能力更强；多播拥塞控制器的理论设计是合理的。这个结果 对我们在校园网中，设定分支节点的缓冲占有量和控制源端的负载具有现实的指导意 义。 1 5 2 论文的结构 论文具体内容安排如下： 第一章：主要介绍网络拥塞控制的基本概念、产生原因、机制、算法及其分类和评 价标准。 第二章：主要介绍多播拥塞控制的几个关键性问题和算法，以及多播拥塞控制的发 展趋势。 第三章：根据文献例建立了一个单点到多点的多播系统模型，并在发送端设计了具 有反馈形式的控制器，还对控制器参数的选择进行了讨论。接着，根据校园网的实际网 络情况，在多播系统模型上加载数据流量。然后选取了六个的值，通过计算得到六组 值，对这六组值用c + + 程序对它们进行理论计算。最后，六组值进行比较分析，得出一 组较优的参数。 第四章：在n s 2 的仿真环境下，搭建了多播仿真平台，建立自相似流量模型和指数 分布流量模型，并以多播拥塞控制器理论计算得到的值为基础，在数据源加上不同的负 载，研究在不同模型下，分支节点缓冲占有量均值，峰值以及瞬念响应情况。通过仿真 数据的分析，我们可以得到以下结论：在自相似流量模型下，当网络负载不超过5 4 1 时，网络不会发生拥塞，并且缓冲占有量较小：在指数分布流量模型下，当网络负载不 超过9 2 7 时，网络不会发生拥塞，并且缓冲占有量较大。自相似流量比指数分布流量 具有更大的突发性。通过本文的仿真结果证明：网络传输指数模型负载能力更强；多播 拥塞控制器的理论设计是合理的。这个结果对我们在校园网中，设定分支节点的缓冲占 有量和控制源端的负载具有现实的指导意义。 第五章：对文中的单速率多播拥塞控制器的设计方法进行总结，并且对今后的研究 工作进行展望。 1 6 本章小结 本章首先阐述了网络拥塞的一些相关概念，然后说明它的产生原因和控制机制，接 7 1 综述 硕上论文 下来对拥塞控制算法进行了分类并给出对算法进行评价的标准，最后说明了论文的主要 工作和结构。 8 硕士论文网络多播拥寒控制技术研究 2 多播拥塞控制概述 当前网络中有三种最基本的通信模式：单播( u n i c a s t ) 、广播( b r o a d c a s t ) 和多播 ( m u l t i c a s t ) 。其中，虽然多播出现的时间最晚，但是因为它同时具有单播和广播的优点， 所以最具有发展前景。 单播就是传统的点到点的数据传输，也叫“一对一”的通讯模式。单播中，网络 中的交换机和路由器对数据只进行转发不进行复制。它的优点是服务器能及时响应客户 的请求，并且根据不同客户的不同请求发送不同的数据，从而实现个性化服务。但是如 果有l o 个客户需要相同的数据，则服务器需要逐一传送，重复1 0 次相同的工作，这样 导致传输了大量的数据冗余，加重了网络的负担。 广播是点到多点的数据传输，也叫“一对多”的通讯模式。网络对其中每一台主机 发出的信号都进行无条件复制并转发，所有主机都可以接收到所有信息( 不管你是否需 要) 。接收到之后，需要的主机对其进行处理，不需要的就将其丢弃。这种模式不用路 径选择，所以网络成本很低廉，实现起来也很简单。但是，它无法提供个性化服务，而 且广播是禁止在i n t e m e t 宽带网上传输的。 最后，我们要说的多播【5 5 】传输，也叫“一对一组的通讯模式。多播中，只有加入 了同一个多播组的主机才能接收到发送给该组的分组。主机如果想接收或不再接收组的 数据就可以向路由器发出请求，加入或退出这个组。网络中的路由器和交换机有选择地 复制并传输数据，即只将组内数据传输给那些加入组的主机。这样既能一次将数据传输 给多个有需要( 加入组) 的主机，又能保证不影响其他不需要( 未加入组) 的主机的其 他通讯。多播同时具有单播和广播的优点，但它也存在很多其他的问题。多播拥塞控制 问题是所有问题中非常重要而且还难以解决的，因此它获得了更多的关注。 2 1 多播拥塞控制中的几个关键性问题 多播的出现提高了网络带宽的利用率和网络效率，优化了网络性能。它缓解了随着 新业务的出现给网络带来的压力。 可靠多播( r e l i a b l em u l t i c a s t ) ，顾名思义，提供的是可靠的多播技术。为了实现传 输的可靠性，数据恢复和拥塞控制【4 3 1 是可靠多播协议里必须提供的两个机制。i r t f 和 i e t f 取得了共识：好的拥塞控制是多播的能够发展的关键性因素。因此，多播拥塞控 制成为很多人研究的一个热点领域。 但我们在设计多播拥塞控制方案时，需要注意几个关键性问题，分别是：可扩展性、 异构性以及公平性【17 1 。 ( 1 ) 可扩展性。 9 2 多播拥采控制概述 硕i 二论文 多播技术是一对多或者多对多的通信模式( 多对多可以通过多组一对多来实现) 。 因为多播流会沿着多播树广泛地分布在整个因特网中，所以多播的接收者一般情况下数 量都比较大，并且具有异构性。这样的情况就要求我们设计的多播拥塞控制方案不但能 扩展到大规模的多播组中，还需要能够适应具有不同链路能力和延迟的异质网络环境。 为了实现可靠传输，多播源根据它接收到的反馈信息调整它的发送速度，避免产生拥塞。 多播源处理的反馈信息有好多种，常见的如确认报文、否定报文、状态报文。这些报文 如果处理的不正确，就可能会导致两种经典的问题：反馈内陷( f e e d b a c ki m p l o s i o n ) 与归 零( d r o p t o z e r o ) 。如图2 1 所示【2 引，图中s 表示发送方，r e v 表示接受者，r 表示路由 器。 图2 1 反馈内陷与归零 1 ) 共享链路1 5 】上发生数据丢失，如图2 1 所示，l l 链路即为共享链路。如果l 1 链 路上发生了数据丢失，多个接收者( 图2 1 中所示的有四个) 会同时给发送方发出反馈 信息告知发送方。大量的反馈信息可能会造成通往发送方的链路或在发送方发生严重的 堵塞。这就是反馈内陷( f e e d b a c ki m p l o s i o n ) 问题【4 5 1 。 2 ) 多播树中存在多条端到端的路径( 如图2 1 ，在l 1 ，l 2 l i 链路上) ，传输的一 个分组有可能在多播树的多条路径上独立的发生丢失。假设一个多播组中，共有n 个 接收者，每条连接多播源和多播组成员的路径上分组独立丢失的概率设为p 。那么每一 个分组收到至少一个丢失反馈的概率为： p = 1 - ( 1 一p ) “，n - - 0 0 ，p 一1 上面的式子中，假如多播发送方一旦收到丢失反馈就降低它的发送速率，那么当n 趋近无穷大时，分组收到至少一个丢失反馈的概率就趋近1 。最终这个多播会话的平均 带宽会趋近零，这就是归零( d r o p t o z e r o ) i h - j 题。 为了避免上述两种问题的出现，我们一般采取反馈聚集与反馈抑制两种方法。高小 山副教授在他发表的多播协议中拥塞控制的可靠性研究中 3 7 1 中，为了完善多播协议 拥塞控制的可靠性，利用基于反馈抑制的随机定时器，设计了一个调度单速率多播拥塞 控制协议。 l o 硕十论文 网络多播拥塞控制技术研究 ( 2 ) 异构性 异构性是数主要体现在数量较大的多播接收者具有不同的处理能力以及不同的接 收者与多播源连接的链路的特性不同。再加上多播的接收者可以自由的加入或者退出多 播组，所以异构性是会常常改变的。基于上述两个原因，为了便于多播源了解网络的整 体情况，多播组的每个接收者都应该及时地给它发送反馈，告知自身情况。多播源( 发 送方) 将接收到的反馈信息进行整合之后，对自己的发送速率进行调整，从而防止分组 发生丢失，实现可靠传输。文献f 9 】中，作者设计了s i m 协议，它集中了三种不同的机制： 选择加入、多播组内发送速率调整和菜单适应。它为具有异构性的网络提供了一种高效、 可扩展的拥塞控制算法。 ( 3 ) 公平性1 4 6 j 多播拥塞控制的公平性可以归纳为以下三个方面：协议问的公平性、协议内的公平 性和会话内的公平性。 1 ) 协议间的公平性】。这主要是指当多播流与t c p 流共享一段链路时，能够公平 的占用网络的带宽，这就是我们经常说的多播流是t c p 友好( t c p f r i e n d l y ) 【2 4 】的。在制 定多播拥塞控制标准时，i e t f ( i m e m e te n g i n e e r i n gt a s kf o r c e ) 要求多播拥塞控制算法必 须要做到t c p 友好。 2 ) 协议内公平。上面提到过，现有的拥塞控制算法中，为实现可靠传输，多播拥 塞控制算法通常是以接收能力最差的一个接收者的接收速率为自身的发送速率。这样虽 然不会发生拥塞，但浪费网络资源。而且不同的数据流之间有一定的公平性，但在同一 个多播组中的各个接收者之间将会导致不公平。 3 ) 会话内的公平。会话内的公平性指的是同一个多播会话内的不同的接收者之间 的公平性。当同一个多播会话内的不同的接收者处于同一个瓶颈带宽之下，它们应该能 够公平地利用带宽。 针对上述三种不同的公平问题，人们也用不同的解决方法。例如，多播拥塞控制一 般采用类似t c p 的响应机制来提供协议问的公平，具体的，主要可以分为下面两种： 基于速率与基于窗口。同时采用基于代理与前向纠错等方式来提供协议内公平。分层多 播和编码变换多播可以提供会话内公平性。 2 2 多播拥塞控制算法分类 多播拥塞控制算法存在多种分类方法【6 9 1 。本节将讨论几种可能的分类方法，同时简 单介绍在不同分类方法下，一些常用的多播拥塞控制算法。 2 2 1 发送端驱动和接收端驱动的拥塞控制 发送端驱动方案，顾名思义，就是发送方负责调节发送速率，以及对所有的接收者 1 1 2 多播拥寒控制概述硕士论文 的状态信息进行维护。而接收方驱动方案就将调节的任务放在接收者。 随着接收者数量的增多，发送方驱动方案的性能就会下降。这很容易理解，因为发 送方需要维护接收者的状态信息和接收者的反馈信息，而多播组中接收者的数量又往往 很大。例如发送方可能要给每一个接收者维护一个窗口，并对接收者的反馈做出响应。 相反，接收方驱动方案是将控制的任务分发到了每个接收者，发送方只要以稳定的发送 速率发送分组，直到接收到某个接收者反馈回来的信息通知发送方有分组丢失。这时， 发送方要重传丢失的分组。所以，其实接收者是要负责检测是否有分组丢失。如果将 这两种方案结合在一起就能综合两者的优点。比较而言，接收方驱动的方案具有更好的 可扩展性，所以现在的多播拥塞控制一般会选用接收方驱动。 接收方驱动的多播拥塞控制需要解决的一个核心问题是接收者对网络的可用带宽 和网络的拥塞状况的探测。因为接收者要根据探测到的情况来调节它的接收速率。目前， 常用的探测技术有：加入实验技术和发送数据包对。前者是通过分组的丢失情况，对网 络的状态做出判断。它的缺点是可能会使得接收端的接收速率不稳定，不能很好地预防 拥塞。后者是接收方探测一个周期里发送的n 个分组到达接收方的时间间隔，然后估 计出网络的可用带宽，再根据可用带宽决定接收者的接收速率。例如b d p t 3 4 j ( b a s e do n d e l a yp a r a m e t e r s ) 协议，就是一种适用于多媒体传输的接收端驱动的分层多播拥塞控制 机制。该协议依据时延参数的动态变化来估测路径可用带宽，保证了网络资源的有效利 用，实现了自适应的加层判断，预测网络的拥塞状况，实现了对捐j 塞的快速响应。还有 p t m c c t 2 9 l ( p a c k e t b u n c hp r o b ea n dt c p f o r m u l ab a s e dm u l t i c a s tc o n g e s t i o nc o n t r 0 1 ) - - 中新 的基于数据包束探测和t c p 吞吐量公式的多速率多播拥塞控制方案。 接收者驱动方案中最典型的代表是接收方驱动多层次多播( r e c e i v e r d r i v e nl a y e r e d m u l t i c a s t r l m ) 算法。这个算法的实现原理是发送方将视频流编码成为一个基础层( b a s e l a y e r ) $ 1 j 多个增强层( e n h a n c e m e n tl a y e r s ) 。基础层包含的信息是视频流中最基本的信息， 接收者只接收这层，就可以得到一些基本的信息；而增强层则逐层递进地包含了更细信 息，接收者接收的越高层次的增强层，接收到的信息就更完善。接收端可以根据自身的 情况，有选择性地加入适合自己的层次。根据网络状态的变化，接收端还可以自由地加 入或者退出。 很多人对r l m 算法提出了改进。文献1 3 8 1 中就提出了一种改进的接收到驱动的分层 多播拥塞控制算法i r l m c c ( i m p r o v e dr e c e i v e d d r i v e nl a y e r e dm u l t i c a s tc o n g e s t i o n c o n t r 0 1 ) 。该算法采用新的r t t 计算方法，不是像t c p 协议那样采用接收端每包反馈确 认a c k 的方式来确定r t t ，同时采用计算接收端的丢包个数来确定系统的拥塞情况， 而不是根据源端发送反馈信息而获得，解决了反馈爆炸问题。同时拥塞响应策略机制采 用了g a i m d 算法，提高了多播会话的有效吞吐量。 1 2 硕上论文网络多播拥塞控制技术研究 2 2 2 单速率和多速率的拥塞控制 一 单速率1 2 5 】【1 1 多播拥塞控制是指多播源以相同的速率向所有接收者发送数据，即使针 对不同的接收者，多播源( 发送方) 的都是单一的。为了防止发生分组的丢失，多播源 单一的发送速率受到接收者中接收能力最差的节点( 瓶颈节点) 的限制。一般情况下， 多播源的发送速率跟瓶颈节点的发送速率保持一致。这样会造成网络资源的浪费，对于 高性能的接收者不公平。基于上述原因，单速率多播拥塞控制不适合推广到大规模的异 构网络中，特别是因特网。 文献【8 j 指出，目前常用的单速率多播拥塞控制有t f m c c ( t c pf r i e n d l ym u l t i c a s t c o n g e s t i o nc o n t r 0 1 ) 和p g m c c ( p r a g m a t i cg e n e r a lm u l t i c a s tc o n g e s t i o nc o n t r 0 1 ) ，同时作 者还提出了一种具有自适应性的a s m p 协议。文献【7 j 中，k a m m o u n ，w 和y o u s s e f , h 提 出了一种端到端的单速率拥塞控制算法。它是在提出的t f m c c 协议的基础上提出了2 点改进。第一，利用a i d m 方法，在多播源具有稳定吞吐量的前提下建模方程估计出 每个接受节点的吞吐量；第二，通过在源端监测i 玎t 的变化值，调整数据源的发送速 率。文献最后的仿真结果表明，加入这两个改进后网络的性能，包括吞吐量、响应时间 等有明显的提高。 多速率【2 6 】多播拥塞控制机制能够很好地解决上面提到的问题。前面已经提到过接收 方驱动多层次多播( r e c e i v e r - d r i v e nl a y e r e dm u l t i c a s t ，r l m ) 算法是典型的多速率多播拥 塞控制。这个算法的实现原理上面已经做了介绍，下面我们具体地介绍下它的实现过程： 发送者将信息通过编码放在不同的层次上发送，每层都通过具有不同传输速率的多播组 进行发送。接收者就根据自身的情况选择适合自己的层次对数据进行接收。一段时间以 后，如果接收者发现一直没有发生拥塞，它就会选择加入更高一层。但是，如果在这段 时间里，接收者发现发生了拥塞，它就会选择退到低一层。这样使得接收方接收数据非 常的灵活，它只受到连接发送方到接收者的链路上的可用带宽的影响，其他接收者( 特 别是瓶颈接收者) 影响，这就解决了上面提到的单速率多播拥塞控制中的不公平性问题。 在现今的异构网络环境下，多速率多播已经成为一种非常有效的多播通信手段，应用也 非常广泛。但它也并不是完全成熟的一种通信方式，其中还有许多亟待解决的问题。在 分层多播中，还有人提出了依靠边缘