（模式识别与智能系统专业论文）tcpred拥塞控制系统的建模和仿真研究.pdf

- | 文摘要 摘要 i n t e r n e t 之所以能够在短短的二十年内从大学实验室和科研机构走向千家万 户，并迅速膨胀成为全球性的网际网络，存技术上应该归功于其以i p 为中心的 通用互联能力；而t c p i p 协议簇在大型异构网络上强大的伸缩性、稳定性和鲁 棒性，则主要来源于t c p 的具有自适应能力的拥塞控制机制。 近年来，随着i n t e r n e t 上的业务类型的增加，人们发现仅仅依靠t c p 来进 行据塞控制已经远远不够了。首先，越来越多的视频和音频应用采用了其它的 传输协议( 如u d p 等) ，所以如何保证这些大数据量的应用在拥塞出现时和 基于t c p 的应用公平地共事网络带宽成了一个迫切需要解决的问题。其次，当 前i n t e m e t 出现拥塞的一个主要原因是路由器的队列管理算法( 丢尾算法) 并不 处理拥塞问题。由于拥塞总是发生在路由器入口处，所以路由器本身最有资格 判断拥塞的出现与否及其严重程度，并应该采取更积极的措施来避免和控制拥 塞。最后，t c p 的拥塞控制机制也存在着诸多不够完善的地方，比如其基本假 定之一的“网络拥塞是分组丢失的唯一原因”等，在无线和卫星信道中已经失去 意义。本文主要着眼于后两个问题，试图从下面几个方面对i n t e r n e t 的拥塞控制 问题进行深入的探讨： 1 t c p 拥塞控制算法的控制系统模型。当初j a c o b s o n 提出并实现t c p 的 慢启动、拥塞避免、快速重传和快速恢复等拥塞控制算法时，就借用了经典控 制理论的思想，例如把网络负载近似为控制系统中的一阶惯性环节等。但是， 这些算法的设计并没有遵循控制系统设计的思路，而是采用了启发式的思维方 法。由于整个控制系统( i n t e m e t ) 的庞大和复杂，当这些算法运行起来的时候 人们发现很难将它们所执行的步骤跟观测到的t c p 的动态特性肖接对应起来， 这使得当i n t e m e t 的大小和异构性发生变化或者其上的业务类型出现新的特点 而导致t c p 在某个方面出现性能问题时，很难矗接对其进行调整以适应新的情 况。所以，利用系统方法对t c p 进行建模，是优化和改进t c p 的第一步。本文 从经典控制理论的角度建立了t c p 拥塞控制算法的s m i t h d a h l i n 模型。该模型 指出，具有良好控制效果的t c p 拥塞控制算法可以类比为一个带s m i t h 预估的 控制器，它所产生的t c p 输出速率包括三个部分：对偏差的放大，对偏差的积 分，以及对上一个r t t 以来所产生的输出的积分的负数，其中最后一项就是在 j a e o b s o n 算法中已经被考虑到了的f f 9 h t s i z e 而前两项恰好构成了一个p i 控 一i 一 中国科学技术人学博士学位论文 制器。从这个模型出发可以得到t c pv e g a s 的改进算法一t c pv s d 。仿真结 果表明，t c pv s d 在多种场景下都比t c p v e g a s 更能减小路由器的丢包率，更 能避免全局同步现象，并取得更高的端到端有效吞吐量。 2 统计平衡状态下的t c p r e d 模型。和其它经典控制系统一样，网络拥塞 控制也必须具备两个基本的构件：拥塞检测模块和拥塞指示( 反馈) 模块。但 是，t c p 的拥塞指示是“隐式”的，它通过超时和重复确认来判断“分组丢失”， 然后根据这个决定来指示拥塞。这种机制的缺陷是拥塞指示往往来得太慢了， 系统的响应也会相应地被滞后从而引起振荡，所以i e t f 提出必须在路由器上进 行主动队列管理，并推荐采用r e d 算法来实现这一点。由此可见，t c p r e d 的交互在拥塞控制的研究上具有重要意义。本文利用随机过程中的均值分析方 法导出了统计平衡状态下r e d 的e w m a 值的解析方程。当链路参数和r e d 参 数变化时，该方程始终能够准确地预测出利用n s 一2 进行分组级仿真所得到的统 计平衡状态下的e w m a 值。在此基础上，提出了一种新颖的通过解析步骤来 自动设置r e d 的几个重要参数的方法。这种方法不依赖于t c p 对路由器瓶颈 链路的带宽时延乘积的估计，能够适应多种类型的t c p 流量。更重要的是，它 可以实现r e d 参数的动态调整，使r e d 自动适应网络流量状况的变化。 3 t c p r e d 的排队系统模犁及其在大规模网络仿真中的应期。当网络规模 变大时，传统的分组级仿真器( 如n s 2 等) 的仿真耗时会急剧变大，这非常不 剥于仿真参数的快速调整。本文从排队论的基本概念出发推导出了t c p r e d 的 o d e 模型。它用一组常微分方程组来描述t c p 的拥塞窗口、r e d 的瞬时队长 及e w m a 值的动态特性，这样通过求解方程组就可以得到这些量的时间曲线。 和n s 一2 的对比仿真结果表明，该模型不但很好地描述了t c p r e d 拥塞控制系 统各个主要参量的动念特性，而且与n s 2 相比较具有非常短的仿真时间，因此 存大规模网络的长时间仿真中具有重要意义。 关键词：传输控制协议，随机早期丢弃，主动队列管理，拥塞控制，建模，仿 真 i i 英文摘要 a b s t r a c t t h ef a c tt h a tt h ei n t e r a c th a sb e e ne x p a n d e df r o mu n i v e r s i t yl a b sa n dr e s e a r c h i n s t i t u t e st oc o m m o nf a m i l i e s ，a n dt h a ti th a sb e e nm a d ei n t oag l o b a li n t e m e t w o r k w i t h i ns u c has h o r tp e r i o d ，s h o u l db ea t t r i b u t e dt ot h eu n i v e r s a lc o n n e c t i v i t yo fi p o n t h eo t h e rh a n d ，t h es c a l a b i l i t y , s t a b i l i t ya n dr o b u s t n e s so f t c p i po r i g i n a t em a i n l yf r o m t h ea d a p t i v ec o n g e s t i o nc o n t r o lm e c h a n i s mo f c u r r e n tt c p r e c e n t l y ，w i t ht h ee x p l o s i o no fn e ws e r v i c e s ，i th a sb e e ns h o w nt h a tt c p sc o n - g e s t i o nc o n t r o li sn o te n o u g h f i r s t ，m o r ea n dm o r ea p p l i c a t i o n su s et r a n s p o r tp r o t o c o l so t h e rt h a nt c p , s oi t sab i gc h a l l e n g et om a k es u r et c p b a s e da p p l i c a t i o n ss h a r e b a n d w i d t hf a i r l yw i t ht h e s ea p p l i c a t i o n s s e c o n d ，c u r r e n tq u e u em a n a g e m e n ta l g o r i t h m ( d r o p t a i l ) h a sb e e nb l a m e df o rt h el a c ko fc o n g e s t i o nc o n t r 0 1 i t sa g r e e dt h a tr o u t e r s s h o u l di n t r o d u c ea c t i v eq u e u em a n a g e m e n tt oi n d i c a t ec o n g e s t i o nt ot c rt h i r d ，t h e c o n g e s t i o nc o n t r o la l g o r i t h m so ft c pi t s e l fs h o u l db ei m p r o v e dt oa d a p tt oc u r r e n t n e t w o r kc o n d i t i o n s ，t h i sd i s s e r t a t i o nc o n c e r n st h el a s tt w oq u e s t i o n sw i t hi n t e n s i v e d i s c u s s i o n so nt h ef o l l o w i n gt o p i c s ： 1 t h ec o n t r o ls y s t e mm o d e lo ft h et c pc o n g e s t i o nc o n t r o la l g o r i t h m s i nf a c t ， j a c o b s o nh i m s e l f u s e dc l a s s i cc o n t r o lt h e o r ya sr e f e r e n c ew h e nh ed e s i g n e dc u r - r e n tt c pc o n g e s t i o nc o n t r o la l g o r i t h m s ，e g ，a p p r o x i m a t i n gt h en e t w o r kl o a d a saf i r s to r d e rs y s t e m b u ti n s t e a do ff o l l o w i n gt h ea p p r o a c ho fc o n t r o ls y s t e m d e s i g n ，h ea d a p t e ds o m eh e u r i s t i cm e t h o d s w h e nt h e s ea l g o r i t h m sc a m ei n t o o p e r a t i o ni ns u c hah u g ea n dc o m p l i c a t e ds y s t e m ( t h ei n t e r n e t ) ，p e o p l ef o u n d t h a ti tw a sh a r dt om a pt h et c pd y n a m i c sd i r e c t l yi n t ot h ec o r r e s p o n d i n ga l g o r i t h m s ，w h i c hm a d ei tv e r yd i f f i c u l tt ot u n et c pw h e ns o m ep e r f o r l t l a n c ep r o b l e m so c c u r r e dw h e nt h es i z ea n dh e t e r o g e n e i t yo f t h ei n t e m e tc h a n g e ( i th a p p e n s e v e r y d a y ) s oi t sc l e a rt h a tm o d e l i n gt c p w i t hs y s t e ma p p r o a c h e si st h ef i r s t s t e pt oo p t i m i z ei t t h i sp a p e rm o d e l st c p ss e n d i n gr a t e a s as m i t h d a h l i n c o n t r o l l e rw i t ht h r e ei t e m s ：ap r o p o r t i o n a lc o n t r o l l e r , a ni n t e g r a lc o n t r o l l e ra n d as m i t hp r e d i c a t o r w i t ht h i sm o d e la l li m p r o v e dt c pv e g a s ( t c pv s i ) ) i sd e r i v e d s i m u l a t i o nr e s u l t ss h o wt h a tv s ds u f f e r sl e s sp a c k e td r o p p i n ga n dg l o b a l s y n c h r o n i z a t i o n , a n da tt h es a m et i m eo b t a i n sh i g h e re n d t o e n dg o o d p u t i i l 中国科学技术大学博士学位论文 2 t h et c p r e dm o d e lu n d e r s t a t i s t i c a l l ye q u i l i b r i u ms t a t e a sw e l ia so t h e rc o n t r o ls y s t e m s ，an e t w o r kc o n t r o ls c h e m ec o n s i s t so f t w ob a s i cc o m p o n e n t s ：ac o n - g e s t i o nd e t e c t i o nm o d e la n dac o n g e s t i o ni n d i c a t i o nm o d e l t h ec o n g e s t i o ni n d i c a t i o nm o d e lo fc u r r e n tt c pi si n d i r e c t l yc o n s t r u c t e db yt i m e o u t sa n dd u p l i c a t e a c k sa n di so f t e nt o os l o w r e c e n t l yi e t fh a su r g e dt h ed e p l o y m e n to fa c t i v e q u e u em a n a g e m e n ta n dr e c o m m e n d e dr e d a st h er e s o l u t i o n t h i sp a p e ri n t r o d u c e st h ee q u a t i o no ft h ee w m av a l u ei nat c p r e di n t e r a c t i v es y s t e mu n d e r s t a t i s t i c a l l ye q u i l i b r i u ms t a t e t h er e s o l u t i o no ft l a i se q u a t i o np r e c i s e l ym a t c h e s t h ec o r r e s p o n d i n gr e s u l t so fu s 一2s i m u l a t i o n s f u r t h e r m o r e ，a l la n a l y t i cw a yt o a u t o m a t i c a l l yt u n er e dp a r a m e t e r si sd e d u c e d i ti ss h o w nt h a ti nt h i sw a yr e d i sa b l et od y n a r a i c a l l ya d a p tt ot h ee v e rc h a n g i n gt r a f f i cc o n d i d o u s j 3 t h eq u e u i n gs y s t e mm o d e lo ft c p r e dw i t ha na p p l i c a t i o nt ol a r g e s c a l en e t w o r ks i m u l a t i o n s i t sw e l lk n o w nt h a tp a c k e t l e v e ls i m u l a t o r ss u c ha sn s 一2s u f f e r v e r yl o n gs i m u l a t i o no v e r h e a d ( p r o c e s s i n gt i m ea n dm e m o r y ) i nl a r g e s c a l en e t w o r k s i ti ss h o w nt h a tt h i sp r o b l e mc a nb ea d d r e s s e db yi n t r o d u c i n ga no d e m o d e lo ft c p r e ds y s t e m sw i t hs p e c i f i ce q u a t i o n sd e s c r i b i n gt h ed y n a m i c so f t c p sw i n d o ws i z e ，r e d si n s t a n t a n e o u sq u e u el e n g t ha n de w m av a l u e ，r e s p e c t i v e l y s i m u l a t i o nr e s u l t ss h o wt h a tt h eo d em o d e lp r e c i s e l yc a p t u r e st h e m a j o rv a r i a b l e so ft c p r e da n da tt h es a m et i m es c a l e sv e r yw e l l i nl o n g t i m e l a r g e s c a l es i m u l a t i o n si ti so fg r e a ts i g n i f i c a n c e k e yw o r d s ：t c p , r e d ，a q m ，c o n g e s t i o nc o n t r o l ，m o d e l i n g ，s i m u l a t i o n i v 辛要符号对照表 a c k a i m d a q m a t m c ，n d d i f f s e r v e w m a f i f o f t p i e t f i n t s e r v i p i r t f o d e r e d r s d e r 订 s i s o t c p v s d 主要符号对照表 确认( a c k n o w l e d g e m e n t ) 和式递增积式递减( 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 ed e c r e a s e ) 主动队列管理( a c t i v eq u e u em a n a g e m e n t ) 异步传输模式( a s y n c h r o n o u st r a n s f e rm o d e ) 拥塞窗口( c o n g e s t i o nw i n d o w ) 区分服务( d i f f e r e n t i a t e ds e r v i c e s ) 指数加权滑动平均( e x p o n e n t i a l l yw b i 曲t e dm o v i n ga v e r a g e ) 先进先出( f i r s t i n f i r s t c i u t ) 文件传输协议( f i l et r a n s f e rp r o t o c 0 1 ) i n t e r a c t 工程任务组( i n t e m e te n g i n e e r i n gt a s kf o r c e ) 集成服务( i n t e g r a t e ds e r v i c e s ) 网际协议( i n t e m e tp r o t o c 0 1 ) i n t e m e t 研究任务组( i u t e m e tr e s e a r c ht a 呔f o r c e ) 常微分方程( o r d i n a r yd i f f e r e n t i a le q u a t i o n ) 随机早期检测( r a n d o me a r l yd e t e c t i o n ) 反射随机微分方程( r e f l e c t e ds t o c h a s t i cd i f f e r e n t i a le q u a t i o n ) 往返时间( r o u n d t r i pt i m e ) 单输入单输出( s i n g l ei n p u ts i n g l eo u t p u t ) 传输控制协议( t r a n s m i s s i o nc o n t r o lp r o t o c 0 1 ) 带s m i t h - d a h l i n 模型的v e g a s ( v e g a sw i t hs m i t h d a h l i n ) 第章概述 第一章概述 1 1 分组交换网络的拥塞现象及其对策 1 1 1 存储一转发 分组交换网络的中间系统般使用“存储- 转发”( s t o r e a n d f o r w a r d ) 技术来 传送分组：每个中间节点( 如i p 路由器或a t m 交换机) 先从某条输入链路中 接收一个完整的分组，将其放入缓存队列中，然后再通过一定的分组调度策略 将其转发出去。当有多个主机的分组需要通过同一条输出链路时，中间节点采 用“统计多路复用”( s t a t i s t i c a lm u l t i p l e x i n g ) 策略在这些主机之间共享其输出链 路带宽。统计多路复用的基本思想是： 以分组为单位对输出链路进行时分复用。即在当前被调度的分组被完全发 送到输出链路之前任何其它竞争该输出链路的分组都必须等待。 分组调度的对闻分配不是事先预留的，两是按嚣进于于的，印当某个数据 流( 比如一个t c p 连接) 没有分组需要转发时，不为它分配任何调度时 间。 “存储转发”带来了两个基本问题：一是如何决定个输入分组是否可以进 入缓存队列，即队列管理问题；二是如何决定缓存队列中的哪一个分组应该 先被转发出去，即分组调度问题。在传统的i p 路由器中，队列管理是通过“丢 尾”算法来进行的：当个分组到达时，如果缓存队列菲空则克许其进入歇列， 否则就将其丢弃；分组的调度策略则使用“先进先出”的方法，即下一个被转发 的分组总是缓存队列中队头的分组。本文主要研究蔚个问题及其在 n t e r n c t 上 的解决办法。 1 1 2 拥塞和拥塞崩溃 由于路由器往往要把多条输入链路进来的分组复用到同一条输出链路中， 所以它接收这些分组的速度经常会超出共享链路的带宽。如果这种状况持续下 去，路由器的缓存队列里的分组就会越积越多，最终导致这个队列溢出，而路 由器也不得不开始丢弃分组1 。这种状态称为“拥塞”，避免和处理拥塞的策略则 为行文简洁起见，后面的叙述中有时候又把“丢弃分组”简称为“丢包”- 一1 一 中国科学技术人学博士学位论文 称为“拥塞控制”策略。 如果通过路由器的分组携带的是t c p 报文段，那么拥塞会带来更加严重的 问题1 。 t c p 是一个面向数据流的、全双工的、为上层提供可靠的数据交付服务的 传输层协议，它使用一个名为“带重传的肯定确认”( p o s i t i v ea c k n o w l e d g e m e n t w i t hr e t r a n s m i s s i o n ) 的技术来实现可靠性翻。这项技术要求接收方收到数据之 后向发送方回送确认报文( a c k ) 。发送方对发出的每个分组都保存一份记 录，在发送下一个分组之前等待a c k 的到达2 。发送方还在送出分组时估计 a c k 到达的时间( 这个时间称为往返时间，或者r t t ) ，并启动一个定时器。 如果定时器超时前a c k 还没有到达，t c p 就重发相应的分组，同时增大对r t t 的估计，直到这个值达到一个预设的上限。 当拥塞出现时，有的分组被路由器丢弃了，t c p 不得不重发这些分组并增 加r t t 的估计值。有的分组虽然没有被丢弃，但是箕在路由器的排队时间明显 变长了，这同样会引起t c p 发送方的定时器超时，于是t c p “错误”地重发了 这些分组。在最坏的情况下，实际的r t t 超过了t c p 发送方的r t t 估计值的 上限，此时t c p 会在收到每一个分组的a c k 之前把这些分组都重发好几份。 对于已经处于拥塞中的路由器，这无疑于火上浇油：它不得不丢弃更多的分 组，而且也因为这些额外的处理而增加了其它分组的排队时间，从而又增火了 r 1 丌。这种恶性循环的最终结果是网络性能严重恶化，有效吞吐量急剧下降， 甚至于网络完全瘫痪。这种现象称为拥塞崩溃( c o n g e s t i o nc o l l a p s e ) ，在1 9 8 4 年由n a g l e 3 首先观察到。 1 1 3 拥塞的避免和控制 首先需要指出的是，简单的增加共享链路的带宽或者路由器的缓存队列的 大小都无法解决拥塞问题。 正如前面所指出的，引起拥塞的直接原因是来自多条输入链路的大量分组 需要竞争同一条输出链路，而在分组交换网络中一条输出链路同时也是一条 输入链路，所以增加任何一条链路的带宽都无法从原理上解决拥塞问题。另 外，i n t e r n e t 的发展历史表明，任何新增加的链路带宽都会很快地被应用层所产 1 i n t c m e t 上9 0 9 5 的流量是t c p 流量，所以t c p 流量引起的拥塞现象在i n t e r n e t 研究 中具有重要意义。 2 实际上t c p 使用了9 0 - b a c k n 的滑动窗l ：l 算法。在接收到第个a c k 之前可以连续发送 一个窗口人小的数据。为简单起见这里作了很人的简化，但基本原理是一样的。 笫。章概述 生的新流量所填满，所以即使是在带宽达到吉比特大小的高速网络中也同样存 在拥塞问题【”。 在网络负载不是很重时，适当地增加路由器的缓存队列的大小的确可以减 小路由器丢弃分组的概率，并推迟拥塞的发生。但是当拥塞已经发生时，太大 的缓存队列容量不但不会消除拥塞，反而会加重路由器的负担。因为缓存队列 容量越大，分组的排队时间也越长，r t t 也越大，而t c p 也会向网络注入更多 重复的分组。 严格来说，在当前的以主机为中心的i n t e r n e t 体系结构下要完全避免拥塞是 根本不可能的，因为主机需要或多或少地利用网络拥塞的信息来调节自己的发 送速度( 即使是在i n t s e r v 或d i f f s e r v 环境下也是如此) 。但是研究表明，通过 仔细调整主机的拥塞控制策略和路由器的队列管理机制，可以大大地减小拥塞 出现的机会，并且在拥塞发生时使其有效地得到控制，直至将它消除。 1 2 当前i n t e r n e t 的拥塞控制是t c p 拥塞控制 2 0 世纪8 0 年代末，j a c o b s o n 等人首次应用了反馈控制、n y q u i s t 定理等经 典控制理论的思想，将几个著名的拥塞避免和控制算法( a i m d ) 加入到b s d u n i x 的t c p i p 协议栈中 5 ，6 从而极大地改善了i n t e m e t 上端到端连接的性能 和稳定性。随后，这些算法被逐渐加入到其它主流操作系统中，形成了今天 i n t e m e t 拥塞控制策略的基本格局。在这十几年间，虽然接入到i n t e m e t 中的主 机数目从5 万左右剧增到了将近2 亿【7 1 ，i n t e r n e t 的异构程度和流量特性也变 得非常复杂，但是j a c o b s o n 的拥塞控制算法依然表现出了良好的鲁棒性，此后 n t e m e t 再也没有出现过拥塞崩溃现象。 虽然拥塞控制的基本任务是维护网络的鲁棒性和稳定性，但是它的最终目 的还是尽可能把网络资源豹利用率( 端到端的有效吞j 吐量) 提升到最大和最 优，并将时延降到最低。否则没有一台主机会愿意启用拥塞控制，而i n t e m e t 也 会因此陷入到无序和混乱当中，并最终崩溃掉。当今的i n t e m e t 是一个分布式的 协同拥塞控制系统，每台主机都通过不断比较自己获得的实际带宽和链路可 用的带宽来调节数据发送速率的上限，最终达到公平共用链路带宽的目的( 对 于a i m d 的公平性有很多种说法。c h i u 和j a i n 等人最先提出了a i m d ，并宣称 它是公平的嗍，但是近来有很多学者对其提出了质疑【9 1o 】) 。 3 一 。 | 国科学技术人学博- t ：- q ：位论文 和其它经典控制系统一样，网络拥塞控制也必须具备两个基本的构件：拥 塞检测模块和拥塞指示( 反馈) 模块。但是，t c p 的拥塞指示是“隐式”的，它 通过超时和重复确认来判断“分组丢失”，然后根据这个决定来指示拥塞。这种 机制的缺陷是拥塞指示往往来得太慢了，系统的响应也会相应地被滞后从而引 起振荡。 1 3 下一代网络的拥塞控制是t c p r e d 拥塞控制 随着越来越多的传统业务( 如交易平台、视频点播平台等) 转移到i n t e m e t 上来，i n t e m e t 的规模变得越来越庞大，异构性也变得越来越强，其流量特性也 出现了新的特点。当前的t c p 流量主要由两种类型构成，一种是对时延很敏感 的短期流量，如t e l n e t 、 n n ，、d n s 等，另一种是对吞吐量很敏感的长期 流量，如f t p 等。这两种流量对丢包率和时延的要求具有很大的不同，而传统 的丢尾算法却不能区分这一点。比如，当一个f t p 会话正在占用着路由器的大 部分输出带宽时，来了一个携带d n s 报文的分组，则丢尾算法会以同样的概率 丢掉d n s 分组，这种行为对于第一种流量是非常不公平的。 现在一般认为，路由器本身也应该积极地参与拥塞控制。当它检测到潜在 的拥塞危险时( 即在拥塞还没有发生时) ，就应该马上将某些分组加上标记 或者直接将分组丢弃。这些信息被及时反馈到t c p 发送方，使其降低数据发 送速度，从而避免拥塞的发生或者加剧。这种算法被称为主动队列管理算法 ( a q m ) ，而随机早期检测( r e d ) 就是其中最著名的种。仿真和试验的结 果都表明，当参数配置合适时r e d 能够傲到： 1 将平均队列长度保持在一个较小的值附近，以吸收正常的突发流量，减小 总的分组丢弃量，同时降低分组的平均排队时间。 2 避免大数据流长时间抢占小数据流的队列空间。 很显然，在拥塞控制系统中加入r e d 之后，不但可以有效地减小中间系统 发生拥塞的可能性，也给t c p 的a i m d 算法加上了很好的拥塞指示模块。 r e d 作为i e t f 推荐的下一代网络的路由器拥塞控制算法，在学术界得到 了广泛的认同( 也引起了大量的争论) ，但是从实际部署效果来看，r e d 的基 于经验的、手工进行的参数设置方法无法适应大型异构网络中流量大小和流量 特性的变化，这使得它很难在i n t e m e t 核心路由器上进行部署( 它要求维护这些 4 第。章概述 路由器的人员熟悉r e d 的原理，具有调整r e d 参数的经验，而且当流量特性 变化时手工调整r e d 的参数) 。现在已经出现了一些能够根据流量状况自动调 整参数的r e d 变体，但是这些算法基本上都是利用启发式思维季导到的，没有什 么理论上的根据，而且它们所提出的参数设置方法都是以局部仿真结果为基础 的，当网络环境变化时往往会出现问题，甚至使r e d 失去稳定性， 可以想象，当r e d 被大规模地部署到核心路由器上之后，在i n t e r n e t 上流 动的大部分分组都要经过t c p 和r e d 的拥塞控制算法的处理，整个i n t e m e t 将 会变成个t c p r e d 拥塞控制系统。虽然人们对于t c p r e d 的交互已经做了 很多研究，也产生了一些仿真模型，但是仍然缺乏能够准确地描述这种控制系 统的数学模型。 1 4 论文主要贡献和内容安排 本文的主要目的是利用控制论和排队论中的系统分析方法来研究t c p 和 r e d 的基本算法，推导出t c p r e d 拥塞控制系统的严格的数学模型，并以这 些模型为基础解决如下问题： 1 提出并实现一种完全基于控制理论的高性能的t c p 拥塞控制算法。 2 在r e d 的基础上，提出一个能够适应t c p 连接数量、链路状况和流量特 性等情况的变化，自动进行参数设置的主动队列管理算法。 3 提出一种对大规模t c p r e d 网络进行仿真的新方法。 论文接下来的各章的内容安排如下： 第二章介绍论文所涉及到的论题相关的背景知识，以及当今学术界在这些 论题上的研究进展情况，包括：t c p 拥塞控制算法的思想及其出现的原因，当 前在i n t e r n e t 主机上运行的标准t c p 拥塞控制算法及其设计思想，以及路由器 端的拥塞控制策略一主动队列管理算法。 第三章以s m i t h 预估器和d a h l i n 算法为基础，建立了t c p 拥塞控制算法的 反馈控制系统模型，得到了t c p 作为一个s m i t h 预估器的控制输出，并讨论了 该控制输出和t c p 拥毫控制策略的对应关系。这个模型指出，t c pv e g a s 可以 被改造成为一个具有高性能的比例积分控制器：t c pv s d 。 第四章研究了单瓶颈链路环境下t c p 和r e d 两种拥塞控制算法相互作 用所构成的拥塞控制系统，利用均值分析方法导出了统计平衡状态下r e d 的 5 一 中国科学技术人学博士学位论文 e w m a 值所满足的方程。仿真结果表明，通过适当选取r e d 参数之间的制约 关系，可以直接利用解析方法求解出能够达到统计平衡状态，而且在性能和公 平性之间有良好的折中的r e d 参数。 第五章利用排队论的分析方法推导出了r e d 的瞬时队长和e w m a 值的微 分方程，并以文献e 1 1 1 的一个假设为基础推导出了t c p 的a i m d 算法的微分方 程。该模型不但可以正确地描述r e d 的动态特性，还具有非常短的仿真耗时， 其s i m u l i n k 实现可以方便地产生多种仿真场景，这在r e d 参数的快速调整中具 有很重要的意义。 第六章总结全文，讨论本文所提出的模型的优点和局限性，并指出以后的 研究方向。 6 第：章背景及相关工作 第二章背景及个一l b 关工1 l 乍 帚一旱 月京及大上仁 2 1 引言 网络协议设计中要面对的一个重要问题是如何保证在众多用户之间有效和 公平地分配网络资源( 包括链路带宽和路由器的缓存) 。在分组交换网络中， 每个分组在经过路由器时都会先被放到某个队列按一定的规则缓存起来等候发 送。按j a c o b s o n 的说法 1 2 】，缓存队列的主要作用是吸收短期内正常的突发流 量，当有太多的分组竞争同一条输出链路时，缓存队列就会溢出，而路由器也 不得不开始丢弃分组。如果这种状况在某个路由器中持续了足够长的时间，则 称该路由器进入了拥塞状态。在图2 1 中，两个源主机都拥有到达路由器的高速 链路，但是路由器的输出链路只拥有相对来说小得多的带宽，所以这是一个很 容易出现拥塞现象的网络。此时把路由器称为“瓶颈路由器”，输出链路称为j 瓶 颈链路”。 疑 源主机i帕助；r 探主机2 旦旦里圄 - s m b p s 厘盔塾受 图2 1一个容易出现拥塞现象的喇络 目的丰机 处理拥塞的办法一般可以分为两类：拥塞控制( 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 n a v o i d a n c e ) 。前者是在网络已经过载的情况下采取的响应 措施，后者则是为了避免网络出现过载而采取的预防和检测策略。从控制理论 的角度来看，这两个问题是通过控制器的输出统一解决的，所以在本论文中把 这些算法统一称为“拥塞控制算法”。 拥塞控制和资源分配是密切相关的。一方面，如果网络在资源分配上采取 了积极的措施( 比如强制实施指定的准入控制和q o s 策略) ，就可以避免出现 拥塞，从而也就没有必要进行拥塞控制。然而。以任意精度分配网络资源是非 一7 一 匐 霄 中国科学技术人学博士学位论文 常困难的，尤其是在i n t e m e t 这样的以松散方式互联的大型异构网络中，这根本 无法实现。另一方面，如果网络允许主机根据需要想发送多少数据就发送多少 数据，那么不管整个网络的带宽有多大，都有潜在的出现拥塞的危险。一般来 说，为了达到较优的资源共享方案，在主机端和路由器端都必须进行有效的拥 塞控制。主机必须控制自己将数据注入网络的速率，路由器则必须实施积极的 队列管理策略。 本章接下来的内容安排如下：2 2 节首先解释t c p 拥塞控制算法的思想及其 产生的原因，然后介绍在绝大部分i n t e m e t 主机上运行的四个标准的t c p 拥塞 控制算法，并以一个仿真实例阐释这些算法的执行情况，最后给出主要的t c p 拥塞控制实现方法的演化及其各自的设计思想。2 3 节介绍路由器端的拥塞控制 策略一队列管理算法及i e t f 所推荐使用的主动队列管理算法：r e d 。 2 2t c p 拥塞控制机制的出现和演化 2 2 1t c p 的拥塞控制思想 图2 2以土机为斗l 心的i n t e r n e t 体系结构 从i n t e m e t 主机上应用程序的角度来看，i n t e r n e t 的结构大体上可以用 图2 2 来表示：它是一个单一的虚拟网络，具体的物理网络技术( 如以太 网、f d d i 、a t m 等) 被i p 层屏蔽掉”2 。当主机a 上的w w w 浏览器通过协 议软件连接主机b ( 此时在应用层我们称主机b 为服务器) 时，它对分组要经 过的物理网络、路由状况等都不需要做任何假定；相反，它通过不断观测与它 直连的网络的状况来调整自己的行为。这是一种以主机为中心的、“端到端”的 一r 一 第三章背景及相关： 作 系统设计思想1 3 j ，它使t c p h p 变得十分通用和强大，是i n m m e t 日益强大并在 商业上取得巨大成功的主要原因之一。 但是这种体系结构也意味着，i n t e m e t 上的数据流无法在虚拟网络中进行资 源预留，它总是在对网络资源状况一无所知的情况下开始发送数据。这种情况 存在两个隐患。首先，如果一台非常快的s u ns p a r c 工作站通过网络向它的对 端一一台很慢的8 0 3 8 6 微机灌送大量数据，后者的网络软件必然会因接收缓 冲区溢出而崩溃【6 】；其次，如果每一台主机都不加节制地向网络中发送大量的 数据，网络必然会陷入拥塞状态甚至崩溃。 t c p 通过简单的反馈机制解决了这些问题。在前面的例子中，第一个 属于“流量控制”( f l o wc o n t r 0 1 ) 范畴，t c p 通过在滑动窗口算法中让接收方自 己来定义发送方的滑动窗口大小( 图2 3 中的r w n d ) 以限制发送方的发送速 率。r w n d 又称为通告窗口，接收方在t c p 连接的有效期内可以动态地改变其大 小并通知发送方。对于序号落在窗口之外的分组，接收方直接将其丢弃。 接收方通告的窗口大小( 几v n d ) 123 己确认 发蜡方的拥塞窗口人小( c w n d j 已发送但来确认 ( f i i g h l s i 聪) 发送方认为 可以马卜发送 接收方允忤 马上发送 图2 - 3带拥塞控制的滑动窗口算法 窗【j 滑动前不能发送 第二个例子则属于“拥塞控制”范畴，t c p 通过对每条连接增加一个“拥塞 窗口”变量( 图2 3 中的c w n d ) 来进一步限制自己的发送速率，实际有效的滑 动窗口大小则变成了m i n ( c w n d ，r w n d ) 。例如，在图2 3 中，虽然报文段9 落在 r w n d 内，但是由于c w n d 的限制，它不会被发送出去。当前在绝大多数t c p 连 接中，r w n d 都是一个比较大的值，所以除非特别说明，后面所提到的叮c p 窗 口”指的就是c w n d 。 当t c p 运行在工作点偏下的位置时，即使接收方提供的r w n d 非常大， 分组的接收和发送非常及时和准确，它也只是谨慎地以线性方式增大c w n d ： 一q