（检测技术与自动化装置专业论文）网络拥塞控制中智能aqm算法的研究.pdf

硕士论文网络拥塞控制中智能a q m 算法的研究 摘要 网络拥塞控制已经成为网络系统改善性能、提高服务质量的主要手段，网络拥塞控 制问题的研究具有重要的理论意义和应用价值。主动队列管理( a q m ) 是网络拥塞控制中 效果较好而广泛使用的一种方法，成为i n t e m e t 拥塞控制领域的热点问题。 本文在已有的a q m 算法的基础上，将智能控制理论的思想引入到a q m 算法的设 计中，提出了两种新的a q m 算法，明显地改进了队列的稳定性和鲁棒性，并且在公平 性方面也有所改善。本文所做的主要工作如下： ( 1 ) 提出了基于队列长度和链路速率相对变化率的模糊a q m 算法。该算法通过引入队 列长度与期望队列长度以及链路速率与链路容量的相对误差量作为网络拥塞指示， 并采用模糊推理来决策出中间节点( 路由器) 的丢包概率。仿真实验表明，该算法不 仅具有良好的队列稳定性和较小的队列延时，同时对实际网络中的非线性和负载波 动等不确定性具有鲁棒性。 ( 2 ) 给出了一种基于n l m s 的a q m 算法( n a q m ) 。通过引入加权队列长度作为拥塞指 示，采用归一化最小均方m o 锄a l i z e dl e 嬲tm e ms q u a r e ，n l m s ) 的方法对权值自适 应调整，结合负载因子对分组进行更为合理的丢弃，将队列长度的变化稳定在一个 理想的水平。仿真表明该算法具有较好的动静态性能，且能提高队列稳定性，降低 丢包率。尤其在多瓶颈链路中，算法的队列稳定性最好。 ( 3 ) 研究了主动队列管理的公平性问题，并引入流的鉴别机制，分别对以上算法进行了 公平性研究。仿真表明，改进后的算法队列稳定，具有良好的公平性。 关键词：网络拥塞控制，主动队列管理，模糊，n l m s ，公平性 a b s t r a c t 硕士论文 a b s 仃a c t 砀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 oi m p r o v et h en e t w o r kp e r f o r m a n c e a n dr e f o r mt h eq u a l i t yo fs e r v i c e t h ei n v e s t i g a t i o no ft h en e t w o r kc o n g e s t i o nc o n t r o li s i 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 ea p p l i c a t i o n a c t i v eq u e u em a n a g e m e n t ( a q m ) f o rt h er o u t e r sh a sb e e nd i s c u s s e dw i d e l y t h i st h e s i sr e v i e w st h es t a t eo fa r ti na c t i v eq u e u em a n a g e m e n t ( a q m ) ，a n dt w on e w a q ma l g o r i t h m sa l ep r o p o s e db a s e do nc o n t r o lt h e o r y s i m u l a t i o nr e s u l t sa l eg i v e nt op r o v e t h ep e r f o r m a n c eo f t h en e w a q ma l g o r i t h m s t h ee o n t r i b u t i o mo f t h i st h e s i sa l ea sf o l l o w s ： ( 1 ) an o v e lf u z z ya q m c o n t r o l l e rb a s e do nt h er e l a t i v ec h a n g e so f q u e u el e n g t ha n d l i n k r a t ei sp r e s e n t e d ，w h i c hi n t r o d u c e st w or e l a t i v ee r r o r sa sc o n g e s t i o nn o t i f i c a t i o n sa n da l s oa s t h ei n p u t so ff u z z yi n f e r e n c es y s t e m ，t h ef i r s ti st h ee r r o rb e t w e e nc u r r e n tq u e u el e n g t ha n d t h ed e s i r e dv a l u e s ，t h es e c o n di st h ee r r o rb e t w e e nt h el i n kr a t ea n dl i n kc a p a c i t y , a n dt h e na n a p p r o p r i a t ed r o p p i n gp r o b a b i l i t ya tr o u t e ri sd e t e r m i n e db ya s e to ff u z z yr u l e s s i m u l a t i o n r e s u l t ss h o wt h a tt h i sp r o p o s e da l g o r i t h mh a sb e t t e rp e r f o r m a n c eo nq u e u es t a b i l i t ya n dl e s s d e l a y , a tt h es a m et i m ei th a sg o o dr o b u s t n e s sf o rn o n l i n e a r i t ya n dl o a dv a r i a t i o n ( 2 ) a na c t i v eq u e u em a n a g e m e n ts c h e m eb a s e do nt h en o r m a l i z e dl e a s tm e a ns q u a r e f 卜m m s ) f l g o f i t h mi sp r o p o s e d w ea d o p tt h ew e i g h t e dq u e u el e n sa sc o n g e s t i o nn o t i f i c a t i o n a n du s et h en l m sa l g o r i t h mt oa d j u s tt h ew e i g h tf a c t o r t h el o a df a c t o ri sc o n s i d e r e dt og i v e am o r er e a s o n a b l ed r o pp r o b a b i l i t ys ot h a tt h ed e v i a t i o no fq u e u el e n g t hi sr e l a t i v e l ys m a l l s i m u l a t i o nr e s u l t ss h o wt h a tt h ea l g o r i t h mh a sb e t t e rp e r f o r m a n c ei nb o t hd y n a m i c sa n ds t a t i c c o n d i t i o n s ，e s p e c i m l yi nm u l t i p l eb o t t l e n e c kl i n k s ( 3 ) t h ef a i m e s sa b o u ta c t i v eq u e u em a n a g e m e n ti sd i s c u s s e da n dt h ef l o wd i s t i n g u i s h m e c h a n i s mi sa d d e di nt h ep r o p o s e da q ma l g o r i t h m s i m u l a t i o nr e s u l t ss h o wt h a tt h e i m p r o v e da l g o r i t h mh a sb e t t e rp e r f o r m a n c eo nq u e u es t a b i l i t ya n d t h ef a i m e s sf a c t o r k e y w o r d s ：n e t w o r kc o n g e s t i o nc o n t r o l ，a c t i v eq u e u em a n a g e m e n t ，f u z z y , n l m s ，f a i r n e s s 声明 本学位论文是我在导师的指导下取得的研究成果，尽我所知，在本 学位论文中，除了加以标注和致谢的部分外，不包含其他人已经发表或 公布过的研究成果，也不包含我为获得任何教育机构的学位或学历而使 用过的材料。与我一同工作的同事对本学位论文做出的贡献均已在论文 中作了明确的说明。 研究生签名：l 随 。7 年参月8 日 学位论文使用授权声明 南京理工大学有权保存本学位论文的电子和纸质文档，可以借阅或 上网公布本学位论文的部分或全部内容，可以向有关部门或机构送交并 授权其保存、借阅或上网公布本学位论文的部分或全部内容。对于保密 论文，按保密的有关规定和程序处理。 研究生签名：窒室堕少罗年占月8 日 硕士论文 网络拥塞控制中智能a q m 算法的研究 1 绪论 1 1 网络拥塞控制的研究现状 i n t e m e t 在过去二十年中取得了巨大的成功和发展，近年来全球i n t e r n e t 的发展速度以 指数增长，随着i n t e m e t 网络规模的迅速扩大，网络上开放的业务种类不断增加，网络应 用的不断深入，导致网络吞吐量急剧降低。严重时甚至发生网络崩溃，这就是网络拥塞 现象。 网络发生拥塞的直接原因有以下三点： ( 1 ) 存储空间不足。几个输入数据流需要同一个输出端口，在这个端口就会排队。如 果没有足够的存储空间，则会被丢弃。增加存储空间在一定程度上可以缓解这一矛盾。 但仅靠增加存储容量并不能有效缓解拥塞，因为数据包在网络中经过长时间排队等待， 它们早已超时，源端则认为它们已经被丢弃，而这些数据包还会继续向下一路由器或交 换机转发从而加重网络拥塞。 ( 2 ) 带宽容量不足。根据香农信息理论，所有信源发送的速率必须小于或等于信道容 量。如果信源的发送速率大于信道容量，则理论无差错传输就不可能，在网络低速链路 处就会形成带宽瓶颈，当瓶颈带宽无法满足通过它的所有源端带宽需求时，就会发生拥 塞。 ( 3 ) 处理器处理能力弱。如果路由器或者交换机的c p u 在执行排队缓存、更新路由表 等功能时，处理速度跟不上链路速度，也会导致拥塞。 由上分析可见，网络拥塞产生的根本原因在于用户提供给网络的负载大于网络资源 容量和处理能力【l 】，表现为数据包延时增加，丢弃概率增大，上层应用系统性能下降等。 网络拥塞已经成为制约网络发展和应用的瓶颈。为了满足人们对网络传输容量和服 务质量越来越高的要求，网络拥塞控制的研究已经成为当前网络和控制界研究的一个热 点问题。 1 1 1 基于源端的t c p 拥塞控制研究进展 基于源端的t c p 拥塞控制中，使用最广泛的是t c p 协议中的拥塞控制算法。根据 统计，目前网络流量中大部分使用的是t c p 协议传输【2 】【3 1 。早期的t c p 协议只有基于窗 口的流量控制机制而没有拥塞控制，因而容易导致网络拥塞。 t c p 拥塞控制机制通过使用窗口流量控制机制，根据网络的拥塞程度来有效地调节 每个连接的传输速率。t c p 拥塞控制策略包括慢启动( s l o ws t a r t ) 、拥塞避免( c o n g e s t i o n a v o i d a n c e ) 、快速重传( f a s tr e c o v e r y ) 和快速恢复( f a s tr e t r a n s m i t ) 个核心算法。 ( 1 ) 慢启动 1 绪论硕士论文 慢启动算法设置了两个参数：拥塞窗( c w n d ) 和慢启动阈值( s s t h r e s h ) 。当建立新的 t c p 连接时，拥塞窗口( c w n d ) 被初始化为一个数据包大小，而实际发送窗口 w i n - - m i n ( c w n d ，a w n d ) ，即拥塞窗m ( c w n d ) 和通告窗m ( a w n d ) 的较小值。源端按w i n 大小发送数据，每收到一个a c k ，拥塞窗n ( c w n d ) 就加1 ，这样就使得c w n d 随往返时 间呈指数增长。因此，源端向网络中发送的数据量将急剧增加。 ( 2 ) 拥塞避免 当拥塞窗口达到慢启动阂值的时候，就进入拥塞避免阶段。在该阶段，源端每收到 一个a c k 确认，拥塞窗口就增加1 c w n d 个数据包，所以在拥塞避免算法中c w n d 是呈 线性增长的。 ( 3 ) 快速重传 如果一个t c p 连接由于拥塞而丢弃了一个数据包，接收端对收到的每个错序数据 包发送相应的重复确认，直到丢失的数据包收到为止。源端在接收到重复的a c k 时并 不能确定是由于分组丢失还是分组乱序造成的，如果假定是分组乱序，在目的端处理之 前源端只可能收到一个或两个重复a c k ；如果收到三个或更多的重复a c k ，表明网络 已经发生拥塞。源端不等到重传定时器超时就重发这个可能丢失的分组，这就是快速重 传。 ( 4 ) 快速恢复 当快速重传算法重传了可能丢失的分组之后，如果t c p 重新进入慢启动阶段，则 拥塞窗口c w n d 置为1 ，重新开始探测网络带宽，从而严重影响网络吞吐量，因此快速 恢复算法在快速重传之后转去执行拥塞避免算法，避免了过大地减小发送窗口而导致的 网络性能下降。 针对t c pr e n o 快速重传及丢失恢复算法中存在的问题，n e w r e n o ，s a c k 等算法 提出了相应的解决方案。n e w r e n o 算法【4 】【5 】不依赖于重传定时器，利用一个a c k 确认 部分发送窗口，立即重传剩下的数据包，尽量避免在快速恢复阶段的许多重传超时。 s a c k 算法对数据包进行选择性的确认和重传，避免了不必要的重传，减少了延时，但 是s a c k 需要修改t c p 协议。 不同于t c p 基于包丢失率的拥塞控制机制，t c p v e g a s 算法 6 】【7 1 通过在源端监测r t t 的变化来调节拥塞窗口c w n d ，如果r t t 显著增加，便认为网络发生拥塞，此时相应的 减小c w n d ；如果i 唧变小，则认为拥塞己经解除，再次增加c w n d 。v e g a s 的不足之处 是在竞争带宽时会导致不公平性问题。 1 1 2 基于中间节点的a q m 拥塞控制算法 随着网络规模的增大，仅仅依靠t c p 拥塞控制机制来提高网络的服务质量是远远不 够的，因此路由器作为网络的中间节点也必须参与到网络拥塞控制中来。基于中间节点 2 硕士论文 网络拥塞控制中智能a q m 算法的研究 的拥塞控制机制通常称为主动队列管理，其主要思想是通过排队算法决定哪些包可以传 输，以此来分配带宽，通过丢弃标记策略决定包丢弃标记概率，以此来分配缓存。队 列管理机制可分为被动式队列管理和主动式队列管理。 被动式队列管理就是在路由器的缓存中，所有到达的包都进入缓存队列直到缓存溢 出，接下来到达的包则被直接丢弃，这种算法称为“去尾 ( d r o pt a i l ) 算法。由于该算 法实现简单，在i n t e r n e t 上得到了广泛的应用，但是该算法存在死锁现象( l o c k - o u t ) 和满 队j i u ( f u l l - q u e u e s ) i 口- j 题。 传统的“去尾”( d r o p t a i l ) 算法不能有效的解决网络的拥塞，i e t f ( i n t e m e t e n g i n e e r i n gt a s kf o r c e ) l l p _ 互联网工程任务组，提出使用主动队列管理算法( a c t i v eq u e u e m a n a g e m e n t ，a q m ) t 8 】进行分组缓存管理。和“去尾 算法相比，主动队列管理算法 ( a q m ) 在缓存溢出之前就主动丢弃或标记一部分报文，使得源端提前对拥塞作出反应。 最早的a q m 算法是由f 1 0 v d 和j a c o b s o n 【9 】提出的随机早期检测( r a n d o me a r l y d e t e c t i o n ，r e d ) 算法。r e d 算法采用平均队列长度作为拥塞度量，一旦发现拥塞逼近， 就采用随机选择的策略对分组进行丢弃或标记，以达到拥塞避免的目的。但r e d 算法存 在参数难以设置和不必要的丢包等问题。这样就导致了网络性能的下降，使得网络延迟 增大，吞吐率下降。为了克服i 也d 算法的这些缺陷，近年来很多研究者陆续提出了各种 新的a q m 算法。 由于r e d 采用线性丢包策略，在轻负载时r e d 的参数设置使得丢包概率过大，而 重负载时参数设置使得丢包又过于柔和，导致当采用r e d 算法时的吞吐量较低，因此 k a i y uz h o u 等人提出了非线性r e d ( n l r e d ) 算法【l o 】。此算法认为r e d 算法的不稳定性 是由于其采用的线性丢包函数，故提出了用二次函数来代替线性函数的a q m 策略。 f e n g 等人【1 1 】针对r e d 算法参数难以设置的问题，提出了一种参数自适应配置的 r e d 算法( s e l f - c o n f i g u r i n gr e d ) ，其主要思想是根据网络中负载的变化对参数m a x 。( 最 大丢弃标记概率) 进行动态调整，从而获得更好的性能。该算法能够有效地降低丢包率， 且在重负载的情况下，能维持较高的链路利用率。该算法虽然解决了r e d 中参数设置 的敏感性问题，但同时给最大丢包概率带来的波动较大，使得队列波动也较大。 f l o y d 在f e n g 等人的算法基础上提出了自适应r e d 算法【1 2 ( a d p t i v e - r e d 算法) 。该 算法对平均队列长度的变化范围和丢弃标记概率参数的调整范围进行了限定，从而保证 了队列的稳定。改进后的算法将r e d 算法的控制参数动态化，提高了r e d 算法的鲁棒 性，但同时也增加了处理的复杂度，参数取值不当会导致系统振荡，不利于网络的稳定。 f e n g 等人于2 0 0 0 年提出- b l u e 1 3 】算法，它通过记录过去时刻的丢包率和链路利用 状态，根据网络中负载的情况对标记丢失概率进行动态调整，以此来对拥塞进行管理。 该算法减小了数据延迟，增强了传输实时数据的能力，但该算法缺乏r e d 早期告警机制， 对拥塞的变化的反应比较慢，从而使队列长度发生较大的波动，且公平性较差。 3 i 绪论硕士论文 由于r e d 算法的丢包策略没有对响应流( 如t c p 流) 和非响应流( 如u d p 流) 加以区分， 使得算法在混合流的情况下几乎没有公平性。因此文献【h 】提出一种基于数据流的 r e d ( f l o wr e d ) 算法，该算法通过记录每个数据流的信息来区别对待不同数据流，对于 非响应流，给予较高的分组丢弃概率，对于响应流，则以低分组丢弃概率保护其带宽占 有率。采用该算法能够对非响应流进行有效的鉴别和管理，同时能够有效保护脆弱流， 增强r e d 算法的公平性，但是该算法需要维护每流信息，计算量较大。 l a k s h m a n 等人于1 9 9 9 年提出s r e d t l 5 1 ( s t a b i l i z e dr e d ) 算法，该算法的丢弃概率取决 于队列的占用情况和活跃流的估计值。它根据瞬时缓存占用率和活跃流的数量来计算丢 包率的。这种算法在某种程度上稳定了缓存占用率，链路利用率比较高，丢包概率波动 小，使得吞吐量达到很高而且队列比较稳定。但该算法需要额外的计算，加大了路由器 的负担。 l i n 和m o r r i s 1 6 1 提出了自适应虚拟队列a v q ( a d a p t i v ev i r t u a lq u e u e ) 算法，其利用简 单微分方程调节虚拟队列容量，本质上也是一种早期分组丢弃技术。该算法将输出链路 的带宽利用率作为首要目标，它在路由器上维护了一个虚拟逻辑队列，该队列的虚拟服 务速率低于实际服务速率，而队列缓存大小和实际一样。当有新分组到达实际队列时， 也设定有一个相同大小的虚拟分组到达虚拟队列，如果该虚拟分组引起虚拟队列溢出， 则对应的真实分组将被丢弃或者标记。这样既能保证系统的高吞吐量，队列长度也较稳 定，队列延迟也较低，但是算法的稳定性受控制参数的影响比较大。 l o w 等人提出了随机指数标记算法r e m 【f 7 1 ，该算法采用价格机制来激励用户对拥 塞作出正确的决策，合理利用网络资源，以减轻网络拥塞，该机制把链路价格的总和作 为拥塞度量，根据拥塞度量来随机标记用户发送的数据包，并将网络的拥塞信息反映到 标记概率上，从而使用户调整其发送速率。该算法提高了链路的利用率，降低了网络延 迟。 r e d 算法采用队列长度作为其标记或丢弃策略的依据，这种策略虽然简单，但在动 态网络中常常是不稳定的，而采用自适应参数调整，则可以解决这种问题。在此c w a n g 等人提出- j l r e d 1 8 】算法，通过测量最新的丢包比率，用它作为队列长度的补充来自适 应调整丢包概率。实验表明，该算法可以取得较快的响应速度和较好的鲁棒性，能够及 时捕获网络的动态变化，从而达到快速响应，在吞吐量、平均队列长度上有更好的性能。 n x i o n g 等人在l r e d 算法的基础上提出tl r c r e d 1 9 算法，该算法使用总的输入 速率，丢包率以及队列长度这三者结合来自适应调节丢包概率，仿真实验证明该算法比 l r e d 算法具有更好的响应速度和稳定性。 1 2 拥塞控制算法的分类 目前a q m 已经成为i n t 锄c t 用塞控制研究领域的一个技术热点，相继也产生了很多 4 硕士论文 网络拥塞控制中智能a q m 算法的研究 有影响力的算法，例如r e d 、p 1 1 2 0 、s r e d 、b l u e 、r e m 、a v q 笔j ；等。根据采用的方 法，这些算法可以大致分为三类：( 1 ) 4 发式，( 2 ) 优化类，( 3 ) 控制理论类。具体分类如 表1 1 所示。 表1 1a q m 机制的分类 a q m 机制 方法拥塞度量目标 r e d 9 t 2 1 j 、a r e d 1 2 1启发式 队列长度( q u e u el e n g t h ) 整体性能 b l u e t l 3 】 丢包事件( l o s se v e n t ) a v q 1 6 】 输入速率( i n p u tr a t e ) r e m 1 7 】 优化 队列长度输入速率( q u e u el e n g t h i n p u tr a t e ) 整体性能 p i l 2 0 、p d 2 2 1 、p i d t 2 3 】【2 4 】控制理论队列长度( q u e u el e n g t h )队列稳定 l r e d t i 8 】 队列长度丢包率( q u e u el e n g t h l o s sr a t e l f a f c t 4 9 1 队列长度( q u e u el e n g t h ) 1 2 1 基于启发式的拥塞控制 基于启发式的拥塞算法，最典型的如f l o y d 等提出的随机早期检澳j j ( r e d 算法) ，它依 赖于启发式的直觉思维，因此原理简单，更容易实现。然而由于算法的设计依赖于直觉， 使得最终形成的算法在稳定性和鲁棒性方面存在不少问题。例如r e d 的参数选择问题， 参数选择不当会导致r e d 算法不稳定等。随着r e d 带来的问题，改进的r e d 算法也随之 产生，例如自适应r e d 算法( a r e d ) 、s r e d 等派生算法。除此之外新的启发式a q m 算法 也不断涌现，例如b l u e 、a v q 等。 b l u e 的思想是结合过去的丢包率和链路利用状态，根据网络中负载的情况对标记 丢弃概率进行动态调整，以此来对拥塞进行管理。b l u e 设定概率尸胁用来标记( 或丢弃) 队列中的包。如果由于缓存溢出而造成队列连续丢包，b l u e 将增大标记概率，使返回 源端的拥塞通知的速率增加。相反，如果队列变空了或链路处于空闲状态，则减小标记 概率，从而降低丢包率，提高链路利用率。 而自适应虚拟队列( a v q ) 算法则是一种典型的基于流量速率的a q m 算法。在路由器 上维护了一个虚拟逻辑队列，该队列的虚拟服务速率低于实际服务速率，而队列缓冲大 小和实际一样，当有新分组到达实际队列时，也设定有一个相同大小的虚拟分组到达虚 拟队列，如果该虚拟分组引起虚拟队列溢出，则对应的真实分组将被丢弃或者标记。 1 2 2 基于优化理论的拥塞控制 基于优化理论的拥塞控制主要是利用价格等经济因素限制用户对网络资源的需求， 从而减少拥塞的发生【2 5 】【2 6 】，所采用的方法主要是将用户所占的带宽和效用值联系起来的 函数，这种函数称为效用函数。效用函数可定义为某种度量，例如音频视频的服务质量、 5 1 绪论 硕士论文 满意度、或用户为所分配带宽支付的费用等。 基于效用最优的拥塞控制算法采用控制理论【2 7 】、优化方法【2 8 】等技术根据一定的网络 模型来设计具有稳定性、公平性和相应服务质量保证的拥塞控制算法。效用函数方法的 设计思想如下：假设l 为网络中所有链路的集合，对某条特定的链路，l ，其传输能力 或带宽为c ，s 为网络中信源或用户的集合，对某一特定的用户s ，定义效用函数玑( t ) 为递增函数，则拥塞控制问题转化为在带宽限制条件下使相应的性能指标最优的优化问 题。 效用函数通常是带宽、时延或分组丢失率的函数，它反应了用户在一定条件下所获 得的效用。对于不同类型的通信量，如弹性通信量( e l a s t i ct r a f f i c ) 和实时通信量( r e a l - t i m e t r a f f i c ) ，其效用函数通常具有不同的形式【2 9 1 。弹性通信量在目前i n t e r n e t 中应用较为普 遍，其代表性的应用包括文件传输、电子邮件以及远程终端等。这些应用对延时的要求 相对较低，其性能随着传输速率的增加而增加。因此其效用函数通常是传输速率的严格 递增函数，比较常用的形式为l n x 和一 2 8 】等。而对于实时通信量，通常不能简单地,1 x ；t 用带宽来表示其效用。这是因为实时应用( 如音频和视频) 要求数据必须在一定的时间内 到达接收端，因此实时通信量的效用函数通常用传输延时来表示。 在口网络中，源端获取链路拥塞信息的方式十分简单，因此要想实现该算法必须 将源端算法和链路算法进行有机地结合。具体而言，路由器根据链路的拥塞信息对进入 的分组进行标记，源端则依据被标记分组的比例来更新数据传输速率。因此基于效用最 优的拥塞控制算法也可以看作是端到端拥塞控制与主动队列管理算法的结合。文献 3 0 1 对该问题做了比较详细的描述。 1 2 3 基于控制理论的拥塞控制 目前，从控制理论的角度出发，拥塞控制算法可分为开环控制和闭环控制【3 1 1 。一般 当流量的特征可以准确描述，性能要求可以事先获得时，适用于开环控制。而当流量的 特征不能准确描述或者系统不提供资源预留时，适用于闭环控制。由于网络流量具有突 发性，因此在i n t e m e t 中拥塞控制主要采用闭环方式。具体运行方式可以分为3 个阶段：( 1 ) 监视网络，检测拥塞的发生。( 2 ) 将拥塞的信息反馈到拥塞的控制点。( 3 ) 拥塞的控制点 根据得到的拥塞信息进行调整以消除拥塞。 在该类方法的研究中，主要是从控制系统稳定性的角度，并结合网络性能来设计柑 应的速率控制器，对系统稳定性的分析与设计。 这方面的研究的突破是m i s r a 等【2 0 1 提出的t c p a q m 的微分方程模型，在此模型的 基础上，可将i n t e m e t 源端、队列长度和延时回路视为控制对象，a q m 作为控制器。可 以运用反馈控制理论设计a q m 控制器，并对闭环系统进行性能分析。 不同的a q m 策略对应不同的控制器，在m i s r a 等提出的t c p a q m 的微分方程模 6 硕士论文网络拥塞控制中智能a q m 算法的研究 型的基础上，h o l l o t 掣3 2 】研究了在a q m 中采用经典的p i 控制器的设计方法。p i 控制器 是在控制对象的线性化模型的基础上进行设计的，p i 控制器与r e d 的不同之处在于采 用了瞬时队列值作为拥塞标识，引入期望队列作为控制目标，为了消除稳态误差，在设 计中引入了积分环节。 还有一些基于反馈控制理论的a q m 控制器，如比例微分控制器( p d ) 【2 2 1 ，p i d 控制 器【2 3 】【2 4 】等。这些静态的p i d 控制器虽然在某些情况下都可以达到较满意的暂态响应以 及较小的稳态误差，但当网络条件( 如负载、时延等) 变化时，鲁棒性欠佳。 文献【3 3 】提出了种自适应预测p i 主动队列管理算法，该算法将s m i t h 预估和达林 算法相结合，既克服了大时滞带来的不利影响，又减小了控制参数的整定数量，通过对 网络参数的在线估计，实时调整控制参数，使得控制器能够适应网络参数的变化。 针对长时滞对a q m 算法性能的影响，文献【3 4 】提出了基于内模补偿的网络拥塞控制 新算法( i c a q i v 0 ，该算法利用频率域模型降价拟合方式建立t t c p 流量控制中a q m 系 统的等效模型，应用控制理论中的内模补偿原理设计具有鲁棒性的时滞补偿a q m 算法， 克服了长时滞对队列稳定造成的不利影响。 由于传统控制理论方法的应用在很大程度上依赖于结构已知的系统数学模型，而且 这些数学模型往往受到许多严格的限制，因此未能从根本上解决拥塞控制问题，网络的 性能仍未得到充分的提高或明显的改善。鉴于智能控制应用于a q m q h 具有参数配置容 易、算法性能对网络条件的敏感性降低、实现简单等优点，尝试把智能控制理论引入到 a q m q b 也成为一个研究的方向。 针对传统p i d 控制器在网络环境变化时鲁棒性欠佳的缺陷，文献【3 5 】在非线性动态模 型的基础上，将神经网络与a q m 控制器相结合，设计了单神经元自适应神经网络p i d 控 制器( s a n n ) 和后向传播神经网络p i d 控带0 器( b p n n ) ，来自适应调节p i d 的参数。 文献【3 6 】中，基于自适应模糊逻辑的控制器( a f l c ) 被运用到t c p a q m 网络中参与队 列管理和拥塞避免。文中采用队列长度的误差及其误差的变化率作为模糊控制器的输 入，并引入了李亚普诺夫函数来保证收敛。该算法对时变、复杂系统具有鲁棒性，总体 性能优于p i 算法。 文献【3 j 7 】中改变r e d 算法传统的做法，采用模糊规则和优先级策略来决定不同队列的 丢包率。采用了分段r e d 的方法( p i e c e w i s er e d ) ，将丢包概率划分为多个小区间，使得 丢包函数更加平滑，从而使丢包率有所降低。 针对b l u e 算法的队列长度增减过大、吞吐量波动大的缺陷，文献【3 s j 提出了一种改 进算法f b l u e 。该算法根据模糊理论使用平均队列长度来动态地调整丢包率的变化步 长，在队列长度、带宽利用率上明显优于b l u e 算法。 文献【3 9 】将模糊控制技术与比例微分控制方法相互结合，采用模糊控制器在线调整比 例微分控制器参数的方法实现r e d 算法控制，改善了r e d 算法网络性能对参数敏感的问 7 l 绪论 硕士论文 题。 针对动态网络的拥塞问题，有学者提出了基于模糊滑模控制的主动队列管理算法 ，该算法基于模糊滑模控锘n 器( f s m c ) 设计，适合于动态网络流量的变化。模糊控制 的加入，缩短了到达时间，改善了滑模控制的抖振现象。对于t c p i p 网络模型的不确定 性、网络参数的时变性以及非响应流所引起的网络抖动，该算法具有较强的鲁棒性。 基于模糊控制的a o m 方法适合于复杂系统且在吞吐量、网络利用率等方面有所改 进，但是也有许多问题需要进一步地研究，如系统的稳定性、公平性和异构网络环境下 的强健性等。 1 3 本文的主要内容及安排 本文对i n t e m e t 的t c p i p 拥塞控制机制进行了探讨，通过对基于网络的流体模型进行 分析，在现有的a q m 算法基础上，提出了两种a q m 算法，并通过网络仿真软件进行验 证分析。仿真研究表明，本文所提出i 约a q m 算法能能将队列长度有效地稳定在期望的 目标值附近，具有较强的稳定性和鲁棒性，并且在其他网络性能指标方面，特别是丢包 率，延迟等方面都有所提高。全文的内容安排如下： 第一章简要阐述了网络拥塞的研究意义，介绍了拥塞的基本概念及其拥塞控制算法 的研究现状，并重点介绍了近年来国内外在a q m 机制方面的代表性方法，总结了各种 理论在a q m 机制中的应用情况。 第二章主要对t c p a q m 流体非线性模型进行线性化，得到网络被控对象的动态特 性。然后分析了几种典型的a q m 算法，比较了各种算法的优缺点。最后通过n s 2 网络仿 真软件，对各算法在队列长度变化，延迟以及丢包率方面的性能进行了比较和分析。 第三章提出了基于链路速率和队列长度相对变化率的模糊a q m 算法。它将链路速 率和队列长度的变化二者相结合作为模糊控制的输入来调节丢包概率，实验仿真结果表 明该算法既能够较快的使分组稳定在期望队列附近，同时又保持较小的队列延时。然后 在其基础上做了进一步改进，提出了自适应模糊a q m 算法，该算法同样利用了中间节 点信息即队列长度的变化和t c p 源端信息即链路速率的变化这两个信息作为网络拥塞 指示的特征量，并将这两个信息综合作为模糊控制器的输入，并根据相应的自适应模糊 推理来决策丢弃标记概率。仿真表明，该算法不仅具有良好的队列稳定性和较小的队列 延时，而且动态响应快，同时对实际网络中的非线性和负载波动等不确定性具有鲁棒性。 第四章给出了一种基于n l m s 的a q m 算法( n a q m ) 。通过引入加权队列长度作为 拥塞指示，采用归一化最小均方( n o r m a l i z e dl e a s tm e a ns q u a r e ，n l m s ) 的方法对权值自 适应调整，结合负载因子对分组进行更为合理的丢弃，将队列长度的变化稳定在一个理 想的水平。仿真表明该算法具有较好的动静态性能，且能提高队列稳定性，降低丢包率。 尤其在多瓶颈链路中，算法的队列稳定性最好。 g 硕士论文 网络拥塞控制中智能a q m 算法的研究 第五章对主动队列管理在保证网络的公平性方面进行了讨论。并在t c p 流和u d p 流同时存在的情况下对第三、四章的算法进行公平性的结合。通过仿真实验，对第三、 四章的a q m 算法以及改进后的算法进行比较，来验证主动队列管理算法在保证公平性 方面的性能。结果表明经过改进的主动队列管理算法比单纯的依靠t c p 拥塞控制在实 现公平性方面要好。 第六章对本文研究内容进行了总结，并提出了进一步的研究方向。 9 2 主动队列管理算法及其仿真研究硕士论文 2 主动队列管理算法及其仿真研究 本章首先通过对t c p a q m 动态非线性模型进行线性化，得到网络被控对象的动态特性。然后 分析了几种典型的a q m 算法，并比较了各种算法的优缺点。最后通过n s 2 网络仿真软件对各算法 在队列长度变化、延迟以及丢包率方面的性能进行了比较和分析。 2 1 引言 t c p 的端到端拥塞控制对于i n t e m e t 的鲁棒性起到了关键作用，然而随着网络规模 的增大，仅仅依靠t c p 拥塞控制机制来提高网络的服务质量是远远不够的，因此网络 中间节点也必须要参与到网络拥塞的控制中来。 主动式队列管理( a q m ) t 8 】是i e t f 为了解决t c p 端到端拥塞控制机制存在的问题而 提出的一种队列管理技术。a q m 方法指根据队列长度的变化对队列进行提前丢包，即 在队列满之前丢包，对网络拥塞进行早期通告，使发送端能在队列溢出之前对拥塞作出 反应，从而达到避免网络拥塞的发生。a q m 的本质是对拥塞进行早期的检测并向端系 统发出拥塞指示，端系统通过相应的机制在路由器缓冲区溢出和丢包产生之前降低数据 的发送速度，从而达到降低丢包率和提高链路利用率的目的。 2 2t c p a q m 系统模型 m i s r a 等人【2 0 】提出了一个采用流体流和随机微分方程进行分析而获得的t c p 动态模 型。如果忽略t c p 的超时机制，则得到简化的非线性微分方程： 掣二磊1 一掣微p ( ( f ) ) 破e 。，：。) 2 j 2 2 ( t - r ( 。) ) 2 、 。 ( 2 1 ) a q ：型mc 、7 d t r ( n 式( 2 1 ) 中的各参数定义如下： 胍t c p 窗口大小( 单位：包) g ：瞬时队列长度( 单位：包) r ：往返延时( 单位：秒) c ：链路容量( 单位：包秒) - 连接数，即网络负载 p ：丢弃标记概率 式( 2 1 ) 的微分方程所表示的t c p 动态模型的框图如图2 1 所示。 1 0 硕士论文网络拥塞控制中智能a q m 算法的研究 图2 - 1t c p 流体模型的方框图 假设t c p 流的连接数和往返时间尺为常量，定义式( 2 1 ) 方程组如下： 懒，寺警删 n 。 g ) 2 i 形( ) 一c 其中哌( f ) = w ( t - r ) h o l l o t 等人【3 2 】采用线性化方法，使用小信号分析法在- v 作点( ，q o ，p o ) 处对该模型 线性化，记( 形，q ) 为系统的状态，p 为时延反馈输入，系统的平衡点为( w o ，q o ，p o ) ，使 得矿= o 和口= o ，从而得到 矿= oj 孵p o = 2 0 = oj ：望 ( 2 3 ) 对于式( 2 2 ) ，对厂( 形，q ，p ) 和g ( 形，g ) 在系统平衡点( 甄，q o ，p o ) 处求偏导，由全微分方 程可以得到 j 肺 一丽n 形( t ) + s w ( t _ r o ) ) r w o c 2 8 p p 喝) ( 2 4 ) 卜) _ n - - - s w ( t ) _ i - - - 幻 其中，8 w = w w o ，两= g g 。，万p = p - p o 。将式( 2 4 ) 所表示的线性方程进行拉普拉斯变换， 可以得到下式 由式( 2 5 ) 和( 2 6 ) ，令 一r 。c 2e - 喁 挪( j ) = 等艿p ( s ) 抖雨 n 却( s ) = 册( s ) s 十 r ( 2 5 ) ( 2 6 ) 形 矿 何 缈 ， g ， 2 主动队列管理算法及其仿真研究硕士论文 鱼竺 ，( j ) = j 嗡，则o ) 表示t c p 的动态特性的传递函数。 抖币 n 暑一( s ) = 耳，则。一( j ) 表示队列的动态特性的传递函数。 s + 二 民 利用上述的t c p 线性化模型，把a q m 机制加入到t c p 窗口与队列组成的系统中， 可以构造出如图2 - 2 所示的a q m 闭环反馈控制系统。根据控制理论知识，a q m 控制模 块可以是一个控制器或者补偿器，控制器的设计目标就是保证一个稳定的闭环系统。 被控对象 h 然hp 咄卜h 讪，h 铀) j 图2 - 2t c p a