（控制科学与工程专业论文）网络拥塞控制的若干问题研究.pdf

博k 学付论丈网络拥寨拧制中的若干问题研究 摘要 随着i n t e r n e t 本身规模的迅速扩大、i n t e r n e t 用户数的剧增、以及网络应用类 型的快速增加，网络正经历越来越多的包丢失和其他的性能恶化问题，其中一个 比较严重的现象就是网络拥塞。 网络拥塞导致的直接后果是整个网络的性能下降：包括分组丢失率增加、端 到端延迟增大、网络吞吐量下降、甚至有可能使整个系统发生拥塞崩溃当网络 处于拥塞崩溃状态时，微小的负载增量都将使网络的有效吞吐量急剧下降。 造成网络拥塞的原因很多，主要有：存储空间不足、带宽容量不足、处理器 处理能力弱、t c p 1 p 协议拥塞控制机制中的缺陷、用户的恶意攻击造成的网络拥 塞，以及网络系统的混沌、分叉等现象都会导致网络通讯的崩溃。 在目前的i n t e r n e t 中，既然网络拥塞是无法避免的，就必须采取积极主动的策 略控制和避免拥塞，把拥塞发生的可能性降到最低，即使在发生拥塞后也能及时 地恢复到正常运行状态；同时拥塞控制也必须保证网络效率。因此，网络拥塞控 制是网络系统改善性能、提高服务质量的主要手段，网络拥塞控制问题的研究具 有重要的理论意义和应用价值。 近年来，国内外关于网络拥塞控制研究方面的成果很多，从已经发表的相关 文献来看，网络拥塞控制的研究主要集中在网络拥塞控制系统建模、网络拥塞控 制系统的非线性动力学分析、t c p 拥塞控制算法的改进、主动队列管理算法等几 个方面。 本文主要从t c p 拥塞控制和主动队列管理两方面对网络拥塞控制进行研究， 主要研究成果如下：， ( 1 )研究了t c p 拥塞控制的四种经典算法：t c p t a h o e 、t c p r e n o 、t c p s a c k 和t c p v e g a s 算法，分析比较了这些算法的特点和优缺点。文中构造了不 同的网络拓扑结构，利用n s 仿真器比较了这些算法的性能。总结了研究 。出一种理想t c p 拥塞控制算法存在一定的困难。 ( 2 )基于网络拥塞控制的内在反馈控制思想，提出将一些控制器应用于a q m 算法。分析比较了内模控制与p i 控制在克服滞后方面原理的不同，体现 了内模控制在克服滞后方面的优越性；在此基础上，提出将p p i ( p r e d i c t i v e p i ) 这种更易调节参数的特殊i m c 控制算法应用于a q m ，并从开环增益 和相位裕度证明了系统的稳定性。分析了基于p l 控制的两种不同模式， 博 学位论史 嘲络拥襄拧制中的若干问题研究 即字节模式和包模式对网络通信产生的不同影响，提出一种根据网络状态 调整p l 控制参数的方法，证明参数的选择从开环增益和相位裕度方面保 证了系统的稳定性，并对p i 控制做了丢失概率计算的改进。在分析p d 和 p i d 控制器模型的基础上，提出了基于a p i d ( a d a p t i v ep i d ) 和a p d ( a d a p t i v ep d ) 控制的a o m 算法。 ( 3 ) 分析和研究了两个拥塞路由器同时采用r e d 控制时，改变其中一个r e d 的若干参数对整个网络性能造成的影响。 ( 4 ) 提出一种结合速率和队列长度信息的r o c ( r a t e o u e u ec o n t r o i l e r ) 算法， 分析了此算法的实现机理，并分别仿真含t c p 流、t c p 流和u d p 流、t c p 流和h r i p 流、混合流时算法的控制情况并综合比较了本论文中所涉及 的一些算法的性能特点。 最后论文分析了在当前网络拥塞控制中存在的一些问题，并指出了进一步的 研究方向 ”一一+ ” 以上内容均经过了仿真研究，验证了所研究方法的有效性和可行性。 关键词：网络拥塞，t c p 拥塞控制，主动队列管理，队列长度 i i 博l 学位论史 刖络拥襄拧制中的荐f 问题研究 a b s t r a c t w i t ht h ee x p l o s i v ei n c r a s eo fi n t e r n e ts i z e ，t h en u m b e ro fu s e r sa n dt h en e t w o r k a p p l i c a t i o n s ，i n t e r n e ti ss u f f e r i n gm o r ea n dm o r el o s sp a c k e t sa n ds o m ep e r f o r m a n c e d e p r a v a t i o np r o b l e m s ，a n dn e t w o r kc o n g e s t i o ni so n e o ft h es e v e r ep r o b l e m s t h ed i r e c t r e s u l to ft h en e t w o r kc o n g e s t i o ni st h ep e r f o r m a n c ed e c l i n eo ft h e w h o l en e t w o r kw h i c hi n c l u d e s ：t h ep a c k e tl o s sr a t ei n c r e a s e s ，t h ee n d t o - e n dd e l a y i n c r e a s e s ，t h en e t w o r kt h r o u g l 】p u td e c r e a s e s ，a n dt h en e t w o r ks y s t e mm a yg ot h r o u g h c o n g e s t i o nc o l l a p s e w h e nt h en e t w o r ki s i nt h es t a t eo fc o n g e s t i o nc o l l a p s e ，t h e n e t w o r kt h r o u g l l p u tw i l ld e c r e a s e ss h a r p l yw i t ht i n yl o a di n c r e m e n t t h e r ea r em a n yr e a s o n st h a tc a u s en e t w o r kc o n g e s t i o n ，a n dt h em a i no fw h i c ha r e l i s t e da sf o l l o w s ：t h el a c ko fb u f f e rc a p a c i t y , t h el a c ko fb a n d w i d t h ，t h el o wa b i l i t yo f p r o c e s s o r , t h ew e a k n e s so ft h et c p i pp r o t o c o lc o n g e s t i o nc o n t r o l ，t h ei n t e n d e da t t a c k o fs o m eu s e r , t h ec h a o sa n db i f u r c a t i o no ft h en e t w o r ks y s t e m i nt h ep r e s e n ti n t e r n e t ，s i n c et h en e t w o r kc o n g e s t i o ni si n e v i t a b l e ，w em u s tt a k e e f f e c t i v ea n da c t i v em e t h o d st oa v o i da n dc o n t r o lt h ec o n g e s t i o n ，t r yt or e d u c et h e p o s s i b i l i t yo fn e t w o r kc o n g e s t i o nt ot h el o w e s tl e v e l ，a t t e m p tt om a k et h en e t w o r k r e s u m ei t sn o r m a lw o r ke v e na f t e rt h ec o n g e s t i o n ，a n dt h ec o n g e s t i o nc o n t r o ls h o u l d e n s u r et h en e t w o r ke f f i c i e n c y s o ，t h en e t w o r kc o n g e s t i o nc o n t r o li st h em a i nw a yt o i m p r o v et h en e t w o r kp e r f o r m a n c ea n dr e f o r mt h es e r v i c eq u a l i t y t h ei n v e s t i g a t i o no f t h en e t w o r kc o n g e s t i o nc o n t r o li si m p o r t a n tn o to n l yi nt h et h e o r yb u ta l s oi nt h e a p p l i c a t i o n i nr e c e n ty e a r s ，t h e r ea r em a n yp a p e r st h a tr e l a t et ot h en e t w o r kc o n g e s t i o n c o n t r o l ，a n dt h er e l a t e ds t u d i e sm a i n l yf o c u so nt h ef o l l o w i n gf i e l d s ：t h em o d e l i n go f t h en e t w o r kc o n g e s t i o nc o n t r o ls y s t e m ，t h en o n l i n e a rd y n a m i cb e h a v i o r so ft h e n e t w o r kc o n g e s t i o nc o n t r o l ，t h ei m p r o v e m e n to ft 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 ， t h ei n v e s t i g a t i o no fa c t i v eq u e u em a n a g e m e n t ，e ta 1 i nt h i sd i s s e r t a t i o n ，s o m ei s s u e si nt c pc o n g e s t i o nc o n t r o la n da c t i v eq u e u e m a n a g e m e n ta r es t u d i e d ，w h i c ha r ed e t a i l e da sf o l l o w s ： ( 1 ) f o u rm a i nt 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 sa r es t u d i e d t h ef o u ra l g o r i t h m sa r e t c p t a h o e ，t c p - r e n o ，t c p s a c k ，t c p v e g a s ，a n dt h e i rc h a r a c t e r i s t i c ，m e r i t a n dd e f e c ta r ea n a l y z e d s o m ed i f f e r e n tn e t w o r kt o p o l o g i e sa r ep r o v i d e d ，a n dt h e i l l 1 绪论博p 学位论文 相关文献来看，关于网络拥摩控制的研究主要集中在网络拥塞控制系统建模、网 络拥塞控制系统的非线性行为分析、t c p 拥塞控制算法的改进、主动队列管理算 法等几个方面。 网络拥塞控制系统建模： 拥塞控制研究由于其复杂性，已不满足于以往的基于主观的分析方法。国内 外在拥塞控制研究方面基本上已转向严格的数学上的动力学分析，对网络拥摩控 制系统的建模研究是一项基础工作，在此研究基础上可结合l 线性动力学、控制 与优化理论等分析现有拥塞控制的稳态与动奁性能，以便丁二设计新的拥塞控制算 法。 因此，不少研究人员致力于网络拥塞控制系统的建模：最早是1 9 9 1 年f l o y d 等【l ”1 提出了t c p 吞吐量的一个简单稳态模型，分析了稳态分组丢失率、往返时 间、拥塞网关数肇以及窗口增长、减小算法之问的关系；随后，1 9 9 7 年m a h d a v i 等1 1 9 9 i 根据三失生成的方式( 周期性丢失还足随机丢失) 对h o y d 模型进行了进一 步扩展，这个简单模型没有考虑t c p 慢启动以后的超时蕾传的影响，因厨只是实 际环境中t c p 性能的上限；1 9 9 6 年m a t h i s 和o t t l 2 0 0 1 给出了t c p 拥摩避免性能的 简甲模型的详细推导过程，并对其进行了详细研究，从他们的研究成果中可以获 得建立基本t c p 分析模型的原理；1 9 9 7 年i a l s h m a n l 2 0 1 l 等在考虑了象a d s l 这 样的异步连接上逆向通道拥塞的条件下，推导了吞吐星的一个近似公式，但没有 考虑丢失所引起的超时对t c p 性能的影响；1 9 9 8 年k u m a r 等1 2 0 2 l 基ft c p 的演 变周期对t c p 的稳态吞吐量性能进行了建模，该模型也未考虑超时的影响；2 0 0 0 年p a d h y e 等l ”5 l 提出一个作为丢失率和往返时日j 函数的t c p 稳态吞吐量模型，但 该模型末考虑超时结束后的慢启动过程对t c p 数据流性能的影响：2 0 0 0 年a l t m a n 等1 1 5 6 j 给出了一个多个t c p 连接带不同回路响应时间的拥塞控制系统的数学模 型，但也没有考虑排队时延。 以上这蝗人员在研究t c p 稳态流性能时，均使用随机过程或随机点过程理论 作为分析的工具，以下的研究人员则采用不同的数学工具对t c p 进行建模研究： 如m i s r a 等人【1 2 2 1 提出了t c p a q m ( a o m ：a c t i v eq u e u em a n a g e m e n t ，主动队列 管理) 的微分方程h u i d h o w 模型，从而可以从理论上分析网络参数如窗口大小、 丢失率、时延和排队长度、链路容鼍之间的关系，很多学者在此模型基础上，利 用控制理论提出了很多新的拥塞控制算法l 摊5 9 ，1 2 2 , 1 2 3 l ；b a c c e l l i 2 0 3 1 使用线性动态系 统对t c p 进行了分析；c i g n o l 2 0 q 手【lg a r e t t o l 2 叫则使用t a p 队论作为建模和分析工 具；r o y 等1 6 j 基于时滞微分方程建立了一个t c p 瓜e n o 的流星模型，但没有考虑排 2 博p 学位论文网络拥雍拧制的苫f 问题研究 法，指出网络中信息流的延时和自相似程度以及采样速；鍪之间的定性关系。 这方面的研究还有很多，其目的是试图更深入地理解网络拥塞控制系统的本 质以便进一步改善拥塞控制系统的性能。 t c p 拥塞控制算法的改进： t c p 拥塞控制算法方面的工作主要集中在协议参数的修改上以及考虑加入一 些与网络层配合的新机制。在这个阶段提出了大最新的修改算法以及新的机制， 并且也开始利用中日j 节点反馈的一些信息进行发送速率的调节。算法的改进方面 主要有如下几个方面：慢启动方面的改进、无线网络算法的改进【1 6 5 l 、提出t c p w ( t c pw e s t w o o d ) 算法1 1 6 l 、针对高速链路的h s t c p ( h i g h s p e e dt c p ) 算法f 1 7 1 、 针对高速网络的f a s tt c p 算法【19 ”、适应区分服务要求及无线网络环境的综合 x c p ( e x p l i c i tc o n t r o lp r o t o c 0 1 ) 协议1 2 2 , 2 3 1 、提出s t c p ( s c a l a b l e t c p ) 算法【2 6 1 、 双窗口a i m d 算法瞄憎。另外，有仿真表明，接收端的接收波动足与网络抖动一 致的，能否应用这种一致性让接收端具有反馈功能是值得考虑的。 关于t c p 拥塞控制的e 要方法和研究现状洋见1 2 。 主动队列管理算法： 为持续有效地控制i n t e r n e t 拥塞，一方面要继续改进已有的t c p 拥塞控制算 法，并要求所有用户采用兼容的端到端拥塞控制：另一方面，网络路由器也应采 用适当的调度算法与队列管理策略，与t c p 拥塞控制算法协作以便有效地避免和 控制网络拥塞。目前路由器中使用最广泛的足简单的先进先出( f i f o ) 包调度算 法结合“丢尾”( d r o p t a i l ) 队列管理策略，即当路由器缓存已存满时，丢弃后续 到达的数据包。对h f o 算法的改进包括公平排队算法( f q ) 、加权排队算法( w f q ) 和基于类的排队算法( c b q ) 等。 “丢尾”队列管理策略的主要缺点是会产生闭塞和满队列现象，造成大晕的 数据包丢失而导致网络的效率和性能降低，这促使i e t f ( i n t e m e te n g i n e e r i n g t a s k f o r c e ) 建议在路由器中采用主动队列管理( a o m ) 策略，即在队列满之静即按 一定概率丢弃或杯记少最数据包，从而使得缓存溢出之前端点就能对拥塞作出响 应1 2 8 1 。a q m 的目标是控制平均排队长度，减少数据包丢弃数，提高网络吞吐量， 避免网络拥塞等【1 眠1 0 5 】。 近年来，关于主动队列管理算法的研究很多l 昝1 5 0 l 。随机早期检测( r e d ： r a n d o me a r l yd e t e c t i o n ) 是最早提出的主动队列管理算法1 3 0 l 。r e d 的主要问题在 于参数配置的困难，而配置不当会引起网络不稳定和性能下降。因此，尽管新的 5 1 2t c p 拥塞控制的主要方法和研究现状 基于窗口的端到端t c p 拥塞控制对i n t e m e t 的稳定性起到了关键作用【1 1 。t c p 拥摩控制的基础足加性增乘性减( a i m d ：a d d i t i v e - i n c r e a s cm u l t i p l i c a t i v e d e c r e a s e ) 策略，主要包括慢启动、拥摩避免、快速重传和快速恢复这四个相关联的算法： ( 1 ) 慢启动( s l o ws t a r t l 慢启动的原理是：使要发送到网络的新数据包的发送速窜等于从接收方返回 的确认消息的速率。 该算法通常用了：连接的丌始阶段和超时引起的。蓖传丢失包阶段，随往返时间 ( r t t ：r o u n d t r i pt i m e ) 按指数增长拥塞窗口c w n d ，作用是探测当前网络可提供 的容量，避免由于发送大量突发数据导致网络拥塞。 6 博 学付论文网络拥雍拧制的若 问题研究 ( 2 ) 拥塞避免( c o n g e s t i o na v o i d a n c e ) 当c w n d 大于慢启动阀值s s t h r e s h 时，即执行拥塞避免算法，在此阶段，每个 r t t 时间内，若发送方收到对当前c w n d 对应数据的应答后，c w n d 就比原来增加 一个最大t c p 数据包所对应的字节数，即c w n d 线性增长。 拥塞避免的作用是通过减缓c w n d 值的增加速率推迟网络拥塞的发生，这样 使发送端能在较长一段时f h j 内保持较高的数据传输率。 ( 3 ) 快速重传( f a s tr e 士r 觚f 珂淞协 通常假定，如果发送方连续收到几个( 通常为三个) 重复a c k ( a c k n o w l e d g e m e n t ：确认) 时，即认为肓一个数据包丢失。此时，发送方不必等 到蘑传定时器超时即莺新传送丢失的数据包。同时t c p 将s s t h r e s h 值设为当前 c w n d 值的一半。t c p 发送方就是利用快速重传算法检测和恢复数据包丢失的。 ( 4 ) 快速恢复( f a s tr e c o v e r y ) 在快速藿传可能丢失的数据包之后，t c p 就执行拥塞避免算法( 而不足慢启 动算法) ，这就是快速恢复算法。此后，快速恢复算法将控制新数据的传送，直到 收到一个非重复的a c k 为止。快速恢复算法可使大窗口下发生中度拥摩时网络 仍具有较高的吞吐量，此算法也可减少快速重发造成的c w n d 急剧振荡。 t c p 拥塞控制中比较有代表性的方法有：t c pt a h o e l 7 1 ，t c pr e n 0 1 7 1 ，t c p n e w r e n o 8 i ，t c pv e g a s 9 1 ：f lt c ps a c k l l 0 ”l ，这些控制算法一般部包含以上四个 过程。 目前，t c p 拥摩控制协议方面的改进依然集中在协议参数的修改上以及考虑加 入一些与网络层配合的新机制，并且也开始利用中间节点反馈的一些信息进行发 送速；蕾的调节，如e c n 机制和链路影子价格机制的研究与应用，这个思想基本可 描述如下：首先发送端和接收端协商是否使用这些机制，然后由路由器根据当时 的网络情况作标记或修改“p r i c e ”值，再由接收端将拥塞信息反馈给发送端，发 送端相应地调整拥塞窗口和慢启动阀值。 、 在算法的改进方面主要有如下内容：慢启动方面的改进1 1 7 4 1 ，无线网络算法改 进【1 3 ，t 4 , 1 5 1 ，m a s c o l o 等提出的t c pw e s t w o o d ( t c p w ) 1 6 1 ，p a g a n i n i 等提出的 h i 曲s p e e dt c p ( h s t c p ) 1 17 嘲，c j i n a n d 等提出的f a s tt c p 19 2 0 , 2 1 1 ，麻省理工大学 和柏克利等提出的x c p ( e x p l i c i tc o n t r o lp r o t o c 0 1 ) l z 2 1 ，另外，有仿真表明接收端 、 7 博p 学位论史嘲络拥寒柠制的苷十彻题研 除r e d ，其余比较有代表性的a q m 算法包括： f e n g 等于1 9 9 9 年提出的b l u e 算法1 3 5 l ：此算法的主要思想足利用丢包事件 和链路宅闲时阳j 动态调整标记丢弃概率。b l u e 的最大贡献在于使用较小的缓存 区即可实现拥塞控制。但一旦发生丢包事件后b l u e 会相对大地增加丢包概率， 从而产生连续丢包，导致t c p 陷入超时，严重时降低链路利用率；也存在参数设 置问题。 h o i l o t 等于2 0 0 1 年提出的p l ( p m p o r t i o n a l i n t e g r a l ) 算法【3 6 l ：此算法应用控制 理论 线性模型在链路中设霞比例积分控制器以增加系统的稳定性与适应能力。 k u n n i y u r 等于2 0 0 1 年提出的a v o ( a d a p t i v ev i r t u a lq u e u e ) 算法1 3 7 嘲j ：此算 法利用简单微分方程调节虚拟队列容量，借助调整利用率因子和阻尼因子在高利 用率和小队列长度之日j 实现适当的平衡，本质上也是一种早期分组丕弃技术【瑚。 a t h u r a l i y a 等于2 0 0 1 年提出的r e m ( r a n d o me x p o n e n t i a lm a r k i n g ) 算法【3 9 1 ： 此算法利用网络流星优化理论中链路影子价格1 3 9 】的概念探测和控制网络的拥塞 状态。 w y d r o w s k i 等于2 0 0 2 提出的g r e e n 算法 4 0 1 ：此算法足一个反馈控制机制， 根据测量的数据到达速率调整拥塞通知的速率。 a ot a n g 等于2 0 0 3 年提出的c h o k e ( c h o o s ea n dk e e pf o rr e s p o n s i v ef l o w s ， c h o o s ea n dk i l lf o ru n r e s p o n s i v ef 1 0 w s ) 算法1 4 1 】：此算法的主要目的足保护适应 流，惩罚i # 适应流。基本思想足当一个分组到达路由器时，从缓存区随机抽取一 个分组与之比较，若这两个分组属于同一流则两个分组均被抛弃，若两个分组不 属f 同一流，则所到分组按一定概率丢弃，此概率由当前队列长度( 类似r e d ) 决 定。c h o k e 基本上继承了r e d 的优点，只是少量增加了一些额外开销。 尽管近年来国内外研究人员提出很多主动队列管理算法，但很多算法本身存 在缺陷，设计和实现部面临众多的折衷，不可能肓一种算法在所有环境中都性能 最佳。冈此，国内外对a q m 的研究工作包括对现有算法的改进、提出新的算法、 分析a o m 算法等。 1 3 2 国外研究现状与分析 a q m 算法根据其拉制原理可以分为如下三大类：基于队列控制、基于速率 控制、基于队列和速率控制。以下分别从这三方面分析近年来国外提出的a o m 算法。 9 博 学位论定 网络拥采拧制的若十问题研究 法、p i d 算澍5 9 1 ：y a s s i n e 等利用模糊控制理论设计的f a f c ( f a s ta d a p t i v ef u z z y a o mc o n t r o l l e r ) 机制 6 0 l 、l i c h a n g 等提出的f a f d ( f u z z ya p p r o x i m a t ef a i r d r o p p i n g ) 1 6 q 机制、s u b a s r e c 等提出的f d s r e d ( f u z z yd o u b l es l o p er e d ) 和 f e r e m ( f u z z ye n h a n c e dr e m ) 6 2 1 ；p i e r r e f r a n c o i s 等利用鲁捧h o o 控制技术设计算 法【6 3 删；a n d r e a s 等利用非线性控制理论设计的i d c c ( i n t e g r a t e dd y n a m i c c o n g e s t i o nc o n t r 0 1 ) 机制【鲫。 此外，还有基于虚拟队列进行控制的a o m 算法，典型代表即a v q 算法，此 算法利用简单微分方程调节虚拟队列容量，本质上也是一种早期分组丢弃技术 p s i 。 另外，近年来，很多研究人员利用控制理论对a q m 机制进行分析：如d i r c e u 等利用控制理论分析s m i t h 预估器的暂态和稳态性能1 1 4 8 1 、s r i s a n k a r 等提出设置 a v q 参数的简单规则( 1 4 9 1 、o r h a n 等分析r e m 算法的收敛性质【1 s o l 、m a t t h e w 等分 析t c p a q m 拥塞控制的全局渐近稳定问趔1 5 1 i 、t a n g 等提出t c p c h o k e 的平衡 模型1 1 5 2 1 、h i r o y u k i 等提出复杂闭环网络模型1 5 3 1 等。 基于速率控制的a q m 算法： g r e e n 算法根据数据包到达速率调整包的丢弃概率，是一种典型的基于速率 控制的a q m 算法。近年柬提出的此类算法还有：e u n c h a n 等提出的v r c ( v i r t u a l r a t ec o n t r 0 1 ) 1 6 6 1 、c h o n g g a n g 等提出的r a q m ( r a t e b a s e d a q m ) 5 5 1 、a b h i n a v 等提 出的f a b a ( f a i r a d a p t i v eb a n d w i d t h a l l o c a t i o n ) 1 6 7 1 等。 基于队列和速率控制的a q m 算法： 一些研究人员提出结合队列信息和速率信息决定丢弃概率的算法，如：j a e s u n g 等提出一种基于平均队列长度和数据包到达速率的a o m 算法【6 8 】、l jz l l u 等基于 虚拟队列长度和总数据速率提出一种新的a d a p t i v eq u e u em a n a g e m e n t 机制1 6 9 】等。 其他a q m 算法： 包括：m a n o j 等提出的基于链路利用率的l u b a ( l i n k u t i l i z a t i o n b a s e d a o m ) 7 0 1 算法、n o r i o 等提出基于数据流的d m f 0 ( d u a lm e t r i c sf a i ro u e u e i n g ) 1 7 1 1 算法、 o m g a n t i 等提出基于逻辑函数控制的p a o m ( p r e d i c t i v ea q m ) 1 7 2 1 算法等。 1 绪论 博卜学位论史 1 3 3 国内研究现状与分析 国内对a o m 的研究较图外晚，但近年来，很多研究人员投入这一新的研究热 点领域，设计了很多新的a o m 机制： 基于队列控制的a q m 算法： 国内提出的改进r e d 算法有：西安交通大学的张德运教授、李增智教授分别 提出自适应阀值r e d ( s a t r e d ) 算法【7 3 1 和基f 优先级的p r e d l 7 4 i 算法；浙江大学 的张顺亮提出根据_ 平均队列长度的变化速率调整丢弃概率1 7 5 l 。 基f 虚拟队列控制的算法有：西安交通大学的张德运教授等提出基于虚拟队 列控制的机制【”1 。 利用控制理论提出基于队列控制的a o m 算法包括： 上海交通大学的邵惠鹤教授等应用s m i t h 原理结合r e d ，提出 p - r e d ( p r e d i c t i v er e d ) y l $ 1 1 7 7 1 、k a i y u n0 i n 等利用控制系统技术设计一个基于呵 变结构的控制a q m 机制f 7 研、孙鹏等提出基于延时反馈的机$ 0 t , n 。 清华大学的任丰原教授，林闯教授，山秀明教授等在这方面做了很多工作【1 2 9 1 ： 提出p i d 控制器i 舯 9 9 】、提出基于内模补偿原理的延时补偿d c a o m ( d e l a y c o m p e n s a t i o n a o m ) i s l s 2 , s 3 1 、吴建平教授等结合了p 控制器和p i 控制器的优点， 提出一种p 2 i 算法【鲫。 华南理工大学的胥布工教授等设计基于微分先行p i 算法1 8 5 1 。 南京理工大学的孙金生教授等提出p d ( p r o p o r t i o n a l d i f f e r e n t i a l ) 控制器f “、 p d r e d ( p r o p o r t i o n a ld e r i v a t i v er e d ) 算法i s 7 1 、智能p 1 d 算法i 嬲1 。 大连理工大学的朱瑞军教授等基于预估控制提出顾估p i d ( p r e d i c t i v ep i d ) 控制 器四l 。 中翻科学院的王晓曦等设计了p i d 和类p i d 的a o m 控制器【q o l 。 东南大学的o i a ny a n p i n g 等结合s m i t h 预估器和d a h l i n 算法提出一种预测性 的p i 控制算法：p p l ( p r e d i c t i v ep i 妒。 另外，也有不少研究人员利用控制理论分析a o m 的控制性能和稳定性等1 1 删： 东南大学的杨洪勇教授等利用广义n y q u i s t 判据研究了具有通信时延的a o m 策略的稳定性【叼、上海交通大学的蒋凯，汪小帆教授等基于 e 线性动态比较分折 r e d 和a d a p t i v er e d 的性能f 叫、清华大学的任丰原教授等构造一个新的分析框 架，结合现有结果和非线性控制理论中的一些描述函数方法提出判断t c p r e d 系统是否稳定的标准唧i 等。 博 学位论文 嗣铬拥雍拧制的荐f 问题研究 基于速率控制的a q m ： 浙江大学的张顺亮，叶澄清教授等0 4 年提出改进b l u e 算法：根据数掘包的 到达速率自适应地调整标记概率【7 5 1 。 基于队列和速率控制的a q m ： 华南理工大学的汤德佑，张大方教授等结合平均队列和负载衡量拥塞，提出 早期选择性丢包算法：e s d ( e a r l ys e l e c t i v ed r o p ) 1 9 6 i 。 其他类别的算法： 清华大学的任丰原教授等利用f i s h e 线性判别方法设计了一个a q m 分类器【9 7 粥1 、设计基于s m v s ( s l i d i n gm o d e v a r i a b l es t n l c i u 化) 控制的鲁捧a q m 控制器【1 0 0 l ； 吴建乎教授采用模糊逻辑控制提高p l 控制器性能，提出f p i ( f u z z y p 1 1 控制器【埘j 。 以上内容基本归纳了国内外的学者在网络拥摩控制方面所作的研究，可知大 多数a o m 算法均基于队列控制，自从2 ( x ) 1 年h o l i o t 提出t c p a q mi 线性模型 后，很多基f 队列的控制算法包括r e d 等部可利用控制理论进行参数设簧、算法 分析和设计等，这也成为当前a q m 研究的一个热点。且因为很多算法的设计和 实现面临众多方面( 如吞吐量、响应时间、丢弃率等) 的折衷，所以对现有算法 的分析、改进，及提出新的有效算法方面还有很多工作需要完成。 1 4 本文的主要内容及安排 本文主要从t c p 拥塞控制和主动队列管理两方面对网络拥震控制进行研究， 着重研究的是主动队列管理，在分析和研究现有的a q m 算法及不同控制器的控 制原理基础上，改进了现存的一些算法，并提出了一些新的a q m 算法。本文不 仅从控制理论上分析了这些算法，证明了一些算法的稳定性，刚时进行了较详细 的仿真研究。全文的内容安排如下： 第l 章简要介绍了网络拥塞控制的研究目的和意义。简要介绍了t c p 拥塞控 制的主要方法和研究现状，重点介绍了近年来国内外在a q m 机制方面的研究现 状，总结了控制理论在a q m 中的应用情况。 第2 章分析并比较了t c p 拥塞控制的网种算法：t c p t a h o e 、t c p r e n o 、 t c p s a c k 和t c p - v e g a s 的特点和优缺点，并在不同的网络环境下仿真比较了这 些算法的不同性能。总结了研究出一种理想t c p 拥塞控制耸法的困难性。 1 3 博卜学位论史嘲络拥皋拧制的苜十蜘题研究 通常假定，若发送方连续收到三个以上的a c k ，则表明很可能一个数据包丢 失了。此时，发送方不必等重传定时器超时就重新传送那个可能丢失的数据包。 t c p 发送方利用快速薹传算法检测和恢复数据包丢失。 ( 4 ) 快速恢复( f a s tr e c o v e r y ) 在快速藿传可能丢失的数据包之后，t c p 就执行拥塞避免算法( 而不是慢启 动算法) ，这就是快速恢复算法。此后，快速恢复算法将控制新数据的传送，直到 收到一个 重复的a c k 为止。快速恢复其实是基于“管道”模犁的“数据包守 恒”的原则，即同一时刻在网络中传输的数据包数量足恒定的，只有当“旧”数 据包离丌网络后，才能发送“新”数据包进入网络。 快速恢复可使大窗口下发生中度拥塞时网络仍具有较高的吞吐鼍。此外，快 速恢复算法也可减少快速重发造成的c w n d 急剧振荡。 2 2t c p 拥塞控制算法简介 2 2 1t c p 1 陷h o e t a h o e 算法由v a nj a c o b s o n 和k a r e i s 与1 9 8 8 年提出f 1 i 。此算法极大地提高了 网络控制拥塞的能力，并成为i n t e r n e t 标准之一。t c p t a h o e 算法在之前的算法中 加入了一些新的算法和改进。加入的新算法包括慢启动、拥塞避免和快速重传。 快速重传在后来的t c p 版本中又得到了改进。 目前，t a h o e 在i n t e r n e t 上的应用己不多。 2 2 2t c p r e n o 在t a h o e 算法实现的两年后，其作者将之修改为r e n o 算法。r e n o 保留了t a h o e 的算法，修改了快速霞传算法，加入了快速恢复算法【1 0 6 1 ，这样t c p 发送端能更 准确地计算链路中的包数目。r e n o 避免了网络拥塞不够严重时采用慢启动造成的 过度减小发送窗口的现象。 和t a h o e 相比，r e n o 可用的带宽增加了，重传率也降低了。但r e n o 还存在 很多问题：采用r e n o 算法时，连接的延迟越长，所能获得的吞吐量就越少；r e n o 不能公平分配带宽；窗口大小的不断更新导致窗口大小的周期性振荡，产生大的 延迟波动，结果足不能有效利用带宽。 另外，当一个窗口仅丢失一个包时，r e n o 的快速恢复算法可以发挥最优的性 能，优于t a h o e 。但相对其他算法，当一个数据窗丢失多个数据包时，r e n o 出现 1 7 博t 学位论艾蜘铬拥塞榨制的营f m 题研究 2 3 仿真和主要的结果 文中所示的仿真结果均为接收端接收的数据。仿真采用的是单向通信。所以， 由接收端发送给源端的确认包在其传输途径中不会被压缩或丢弃。 对t a h o e 来说，不管源端窗口丢失了多少个包，t a h o e 源端总是从快速重传中 恢复，紧接着进入慢启动过程。对于带有更大拥塞窗口的连接，t a h o e 在执行慢 启动过程中窗口逐渐增加到原拥塞窗口一半大小的过程中引起了传输延迟，这对 网络的整体性能有很大的影响。 文献【1 0 8 】中说明，不带s a c k 选项的r e n o 算法在窗口仅丢失一个包时性能最 优，而当窗口丢失了两个包时，源端连续两次启动了快速重传和快速恢复机制， 并两次降低了拥塞窗口，这是完全没有必要的。而当窗口丢失三个或四个数据包 时，r e n o 源端必须等待萤传定时器超时恢复数据的传输。 文献【1 0 8 】中也提到，t c p s a c k 不需要等待毫传超时从丢包中恢复。但是， 当拥摩窗口变大，且窗口中有更多包丢失时，每个往返时间之内只能霞传至多一 个丢包的限制导致了传送下个丢包的延迟变得很大。而且，如果在恢复阶段，源 端发送数据的量被接收端的声明窗口大小所限制，则源端就无法有效利用可用的 带宽。而总体来说，s a c k 在吞吐量等方面的性能表现部比较不错。 对v e g a s 算法，因为它有着不同于其他算法的网络带宽预测方法，故它在单独 运行时在吞吐黾、丢失率等方面部取得了较好的结果，但是当它与其他算法竞争 时就不能获得公平的带宽，这是v e g a s 本身算法所致。 综合来说，这几种算法在不同的网络情况下有着各异的表现，丽没有一种算法 可以在不同的环境下均获得最优的性能。目前来说，研究人员也没有能够提出一 种性能椎常完善的算法可以适应不同的网络环境，并能取得令人满意的结果，这 也是未来的一个挑战。 2 3 1 单个算法的比较 以下内容描述各个算法的仿真及结果，所有的仿真在网络仿真器n s 上执行。 图2 3 1 是比较单个算法的网络拓扑仿真图。图中的节点如n o 、1 1 2 为客户端 ( 即发送端或接收端) ，带方框的节点n 1 为缓存有限的丢尾网关。发送端与网关、 以及网关与接收端都由链路所连接，链路上均显示有带宽容量和延迟。程序共运 行1 0 秒，n 0 的最大声明窗口设为2 0 个包。接下来仿真n l 与1 1 2 之间的最大缓存 变化的情况。每次只改变n l 与n 2 之问的缓存量( 见表2 3 1 ) 。 1 9 2 t c p 拥雍件制博卜学位论艾 ，1