（控制理论与控制工程专业论文）自适应主动队列管理算法研究.pdf

硕上论文 自适应主动队列管理算法研究 摘要 经过几十年的高速发展之后，计算机网络已经得到极其广泛的应用。高速发展造就 了如今这个规模巨大的系统，但是也给目前的计算机网络带来了很多无法避免的问题。 快速增长的网络处理能力赶不上更快速增长的用户需求，多种瓶颈问题因此而出现，其 中之一就是网络拥塞。表现出来的现象通常是：实际有效的吞吐量降低，网络延时增长 等等，严重的时候还会导致网络发生崩溃。 为了解决这一问题，历史上出现了很多的网络拥塞控制算法，目前的研究热点是主 动队列管理( a q m ) 算法。 本文首先介绍了网络拥塞产生的原因以及该研究领域的历史与现状，接着介绍了一 些经典的拥塞控制算法。针对网络的强时变性和强非线性，给出了两种具有一定自适应 能力的a q m 算法。 1 ) 模糊算法具有比较好的动态特性，超调量低，系统响应时间短，但是稳态误差 比较大。p i 算法有比较好地稳态特性，稳态误差小，但是超调量大，响应时间长。第一 个算法依据实时队列长度与期望队列长度之间的误差来实现模糊算法和p i 算法之间的 渐进式的切换，以充分利用这两个算法的特点。由n s 一2 的仿真结果可以发现，相比于 传统的p i 算法，这一新算法的动态性能和稳态性能均得到一定程度的改进。 2 ) r e m 算法利用队列长度的偏差和输入输出速率的偏差计算出一个链路价格，依 据这个链路价格来计算丢弃率。从控制理论的角度来说，速率是队列长度的微分，因此 相比于仅仅利用队列长度进行拥塞控制的算法，r e m 算法对拥塞的发生有更好的早期 判断能力。但是仿真发现r e m 算法的稳态误差较大，队列长度大幅波动。为了减小r e m 算法的稳态误差，我在r e m 算法中加入了比例算法。当系统进入稳态之后，比例算法 起主要作用。由n s 2 的仿真结果可以发现，相比于r e m 算法，这一新算法的动态性能 和稳态性能得到一定程度的改进。 关键词：拥塞控制主动队列管理算法自适应性 a b s t r a c t 翌圭笙茎 - ，_ 。一 a b s t r a c t a f t e rd e c a d e so f r a p i dd e v e l o p m e n t ，t h ec o m p u t e r n e t w o r kh a sb e e nu s e dw i d e l y t o d a y , t h ef a s td e v e l o p m e n th a sc r e a t e das y s t e mo fs u c ham a g n i t u d e ，a l s ot ot h ec u r r e n tc o m p u t e r n e t w o r kh a sb r o u g h tal o to fd e f e c t sw h i c hc a nn o tb ea v o i d e d r a p i dg r o w t ho fn e t w o r k c a p a c i t yc a nn o tm e e te v e nm o r er a p i dg r o w t ho fu s e rd e m a n d ，m a n yb o t t l e n e c k sa r i s e ， t h e r e f o r e o n eo fw h i c hi st h en e t w o r kc o n g e s t i o n p h e n o m e n o nu s u a l l y i s ：t h ea c t u a le f f e c t i v e t h r o u g h p u td e c r e a s e s ，t h en e t w o r kd e l a yg r o w s ，e t c ，e v e nn e t w o r k c r a s hw h e ns e r i o u s t os o l v et h i sp r o b l e m ，t h e r eh a v eb e e nm a n yh i s t o r i c a ln e t w o r kc o n g e s t i o nc o n t r o l a l g o r i t h m s t h ef o c u so fc u r r e n tr e s e a r c hi st h e a c t i v eq u e u em a n a g e m e n t ( a q m ) a l g o r i t t n n t h i sd a p e rd e s c r i b e st h ec a u s e so fn e t w o r kc o n g e s t i o na n dt h er e s e a r c hh i s t o r ya n d p r e s e n ts i t u a t i o n ，t h e nd e s c r i b e ss o m eo ft h ec l a s s i c a lc o n g e s t i o nc o n t r o la l g o r i t h m s s e e i n g t h eg r e a tv a f f a b i l i t ya n ds t r o n gn o n 1 i n e a ro fn e t w o r k ，id e s i g nt w oa l g o r i t h m sw i t hc e r t a i n a d a p t i v ea b i l i t y 1 ) t h ef u z z ya l g o r i t h mh a sg o o dd y n a m i cc h a r a c t e r i s t i c s ，t h eo v e r s h o o ti sl o w , s y s t e m r e s p o n s et i m ei ss h o r t ，b u tt h es t e a d y - s t a t ee r r o r i sr e l a t i v e l yl a r g e p ia l g o r i t h mw o r kb e t t e ri n s t e a d y - s t a t e s t e a d y s t a t ee r r o r i ss m a l l ，b u to v e r s h o o ti sl a r g e ，r e s p o n s et i m ei sl o n g t h ef i r s t a l g o r i t h mi sb a s e do nt h ee r r o ro fr e a l t i m eq u e u el e n g t h a n de x p e c t e dq u e u el e n g t h ，t o a c h i e v eag e n t l es w i t c hb e t w e e nt h ef u z z ya l g o r i t h ma n d t h ep ia l g o r i t h m ，i no r d e rt ot a k ef u l l a d v a n t a g e so ft h ec h a r a c t e r i s t i c so ft h i st w oa l g o r i t h m s f r o mt h es i m u l a t i o nr e s u l t sc r e a t e d b vn s 2 。c o m p a r e dw i t h t h et r a d i t i o n a lp ia l g o r i t h m ，t h ed y n a m i cp e r f o r m a n c ea n d s t e a d y s t a t ep e r f o r m a n c eo f t h i sn e wa l g o r i t h ma r ei m p r o v e dt os o m ee x t e n t 2 ) r e ma l g o r i t h mu s e st h eq u e u el e n 垂h d e v i a t i o na n dt h ed e v i a t i o no fi n p u ta n d o u t d u tr a t et oc a l c u l a t eap r i c eo fl i n k ，a c c o r d i n gt ot h i sp r i c et oc a l c u l a t et h ep r o b a b i l i t yf o r d r o p i n gp a c k e t f r o mt h ev i e wi nc o n t r o lt h e o r y , t h er a t ei st h e d i f f e r e n t i a lo ft h eq u e u el e n g t h s oc o m p a r e dt ot h ec o n g e s t i o nc o n t r o la l g o r i t h m sj u s tu s i n gt h eq u e u el e n g t h ，r e m a l g o t h mh a sab e t t e ra b i l i t yt of o r e c a s ta n e t w o r kc o n g e s t i o n b u tt h es i m u l a t i o ns h o w st h a t r e ma l g o r i t h mg e n e r a t e sal a r g e rs t e a d y - s t a t ee r r o ra n dg r e a tf l u c t u a t i o n so fq u e u el e n g t h t br e d u c et h es t e a d y s t a t ee r r o ro fr e ma l g o r i t h m ，ia d d e dt h ep r o p o r t i o na l g o r i t h m i n t o r e ma l g o r i t h m w h e nt h es y s t e me n t e r ss t e a d ys t a t e ，t h ep r o p o r t i o na l g o r i t h mp l a y s am a j o r r o l e b yt h en s 一2s i m u l a t i o nr e s u l t s ，c o m p a r e d t or e ma l g o r i t h m ，t h ei l e wa l g o r i t h m p e r f o r m sb e t t e ri ns t e a d y - s t a t ea n dd y n a m i c - s t a t e 硕士论文 自适应主动队列管理算法研究 k e yw o r d s ：c o n g e s t i o nc o n t r o l a c t i v eq u e u e m a n a g e m e n ta d a p t i v e 声明 本学位论文是我在导师的指导下取得的研究成果，尽我所知，在本 学位论文中，除了加以标注和致谢的部分外，不包含其他人已经发表或 公布过的研究成果，也不包含我为获得任何教育机构的学位或学历而使 用过的材料。与我一同工作的同事对本学位论文做出的贡献均已在论文 中作了明确的说明。 研究生签名： 三二函 研究生签名：! 二! f 习 。c 0 年6 目蜘 学位论文使用授权声明 南京理工大学有权保存本学位论文的电子和纸质文档，可以借阅或 上网公布本学位论文的部分或全部内容，可以向有关部门或机构送交并 授权其保存、借阅或上网公布本学位论文的部分或全部内容。对于保密 论文，按保密的有关规定和程序处理。 研究生签名：一 研究生签名：一 璺 0 支1年6 月巧日 硕士论文自适应主动队列管理算法研究 1 绪论 1 1 网络拥塞控制的研究意义 上世纪6 0 年代计算机网络的雏形在美国出现，在这之后的几十年内计算机网络的 规模飞速发展，互联网已经将其触角延伸至世界的每一个角落，它在各个领域内都得到 了广泛的应用，同时与计算机网络相关的技术也得到了迅速的发展。 但是在这个飞速发展的过程中，也遇到了很多的瓶颈。其中之一就是网络拥塞 ( c o n g e s t i o n ) 。例如：在1 9 8 6 年，因为网络的拥塞崩溃，美国l b l 到u cb e r k e l e y 的数据吞吐量从3 2 k b p s 跌落到4 0 b p s ，致使网络完全不能使用【2 】。 网络拥塞( c o n g e s t i o n ) 将会导致各项服务性能急剧下降，用户的请求不能得到及时有 效地响应。大量的数据包被中间接点丢弃( p a c k e t l o s s ) ，网络端到端的延时( r t t ) 增长并 且越发不稳定，实际有效的吞吐量( t h r o u g h p u t ) 严重降低，在极端的情况下，甚至会发生 网络崩溃( c o l l a p s e ) 【川。 在网络负载刚开始增加的阶段，因为网络处理能力可以满足用户的需求，所以各项 服务性能指标均随着负载的增加而增加。而当负载增加到一定程度之后，由于网络的处 理能力不能完全满足用户的要求，轻度拥塞开始显现，各项服务性厶匕e , 七匕3 h 标增长速度放缓， 有效的吞吐量开始降低，网络延时逐渐增长，出现数据包被迫丢弃的现象等等。此时若 不采取拥塞避免的措施，网络的拥塞程度将会逐渐加深，最终各项性能指标急剧下降， 网络发生瘫痪。 就目前而言，网络上绝大部分的数据流是遵循t c p i p 协议的，因此针对t c p i p 协 议数据流的拥塞控制机制在整个网络的拥塞控制机制中占有主要地位。拥塞控制机制能 够保证网络在各种强烈的内部和外部干扰下依然可以达到各项用户层服务性能指标，主 要包括：实际有效吞吐量高、网络延时低、丢包率低等等。但是由于网络具有很强的分 布性、不均衡性、非线性、大延时等特性，网络拥塞控制方面的研究依然是当今的一个 热点方向。 1 2 网络拥塞控制研究的历史与现状 网络中的一个数据包，在源端产生，经过中间节点的传输，最终被终端接收，终端 发出确认包给源端。在这一个过程中，源端、中间节点、终端的工作状态都会对这个数 据包能否顺利地传输产生影响。 面对网络拥塞问题，人们最初想到的是在源端寻求解决问题的方法。vj a c o b s o n 在 1 9 8 8 年发表了文献【4 j ，提出了基于发送端滑动窗口的t c p 端到端拥塞控制算法，这是 种基于流的拥塞控制机制，采用和式增加积式减少( a d d i t i v e si n c r e a s em u l t i p l i c a t i v e l 绪论硕士论文 d e c r e a s e ，a i m d ) 的方法。之后端节点上的拥塞控制算法得到了大量学者的极大关注， 出现了很多不同版本的t c p 拥塞控制算法。例如：t a h o e 、r e n o 、n e w r e n o 、v e g a s 等 等。这些机制对避免发生网络拥塞起到了重要的作用。并且其中的一些设计思想也对后 来的研究者提供了很多的启发。但是在端节点上进行拥塞控制也有许多的局限和不足。 例如：不能保证公平性，加重端节点的负担，不能适应网络自身状态的变化，被动地进 行拥塞控制等等。另外，随着互联网业务的发展，为了满足实时多媒体流的传输，出现 了很多新的网络协议，这些非t c p 协议数据流在传输过程中会最大限度地索取带宽， 不对自己的数据发送速率进行控制，这些数据流不受t c p 端节点的拥塞控制的约束， 相对于t c p 数据流，这些流占有不公平的优势。 当人们在端节点上做出了很多的尝试与努力之后，发现仍然无法很好的解决网络拥 塞问题【5 】，于是开始重新考虑自己的出发点是否正确，既仅仅在端节点上进行拥塞控制 是否就可以很好的解决网络拥塞问题。渐渐地，人们将目光转向了中间节点。在数据包 传输过程中，中间节点也是起着很重要的作用。除了可以在端节点上进行拥塞控制，也 可以在中间节点上进行拥塞控制。 起初人们以为是中间节点的硬件资源不足，致使中间节点的处理能力不足，无法及 时的处理大量的数据包。于是人们增加各种硬件资源，包括增加路由器缓冲区的大小、 提高出口带宽、提高处理器的速度等等。在采取这些措施之后，网络拥塞得到了一定程 度的缓解，但是依然存在，甚至在有些情况下更严重。于是人们又开始重新审视自己的 思路。最终人们发现，不是端节点或者中间节点单独产生了网络拥塞，而是二者共同产 生了网络拥塞。源端提供的负载超过了中间节点的处理能力时，暂时无法被转发的数据 包就会积累在路由器的缓冲区当中，队列增长，由此而导致网络延时增加。当缓冲区满 了之后，路由器就会被迫丢弃数据包，而源端根据t c p 协议，重传被丢弃的数据包。 这进一步增加了网络中间节点的负担。并且队列过长导致网络的延时过长，致使一部分 数据包在缓冲区中排队等候的时间太长，t c p 源端误认为该数据包已经被中间节点丢 弃，对这些数据包进行重新发送，由此而导致网络负载进一步加重。所以一味地增加中 间节点的各项硬件资源，是不能根本解决网络拥塞的，甚至可能会加剧网络拥塞的程度。 b r a d e n 等人在1 9 9 8 年提出了主动队列管理技术( a c t i v eq u e u em a n a g e m e n t a q m ) 6 】，这里的“主动”二字是相对于之前路由器“被动”地丢弃数据包而言的。在此之前， 路由器一直使用一种很简单的队尾丢弃原则：当缓冲区满了之后才开始丢弃数据包，而 这时拥塞已经发生了。a q m 的思想就是：在路由器缓冲区尚未满之前，主动地进行数 据包的丢弃，并通知源端降低发送速率，以此来避免拥塞的发生，从而降低丢包率，提 高链路的实际吞吐量，改善网络的综合性能。其中，最著名的a q m 算法当属sf l y o d 等人提出的随机早期检测r e d ( r a n d o me a r l yd e t e c t i o n ) 算法【n 】。然而r e d 算法作为 种早期的a q m 算法也存在很多问题。例如：算法对参数设置十分敏感，如果参数设 2 硕_ = l 论文自适应主动队列管理算法研究 置与网络环境之间匹配程度很低，该算法并不能起到很好的拥塞控制效果。因为是使用 平均队列长度来表示拥塞程度，因此不能有效地估计实际拥塞程度。存在公平性问题等 等。很多学者在此之后提出了一些r e d 算法的改进版本以及一些其他的a o m 算法。 r e d 算法的改进版本有g e n t l e r e d 算法、s e l f - c o n f i g u r a t i o nr e d 算法、a d a p t i v e r e d 算法等等，其他的a q m 算法包括：b l u e 算法、r e m 算法等等。不过这些算法缺乏系 统的理论分析，因此自适应性和稳定性较差，当网络状态大幅波动的情况下，性能依然 不够理想。 在网络拥塞机制研究的发展历史上，人们关注的焦点从源端走向中问节点是第一次 重要变革。第二次重要变革就是将整个网络系统视作一个被控系统，把成熟的控制理论 引入到拥塞控制算法的没计之中，为网络拥塞算法的设计提供了大量的素材。2 0 0 1 年 c h o l l o t 等人将经典控制理论引入到a q m 算法的设计之中，提出了用于网络拥塞控制 的p i 算法j 。由于p i 算法本身的特性，使得该算法的响应时间比较长，于是人们又引 入了微分环节，相继出现了p i d 算法【9 】和p d 算法【1 0 】，微分环节的引入使得系统的响应 时间缩短，超调量降低。但是面对具有强时变性、强非线性的计算机网络，微分环节会 放大这些特性对算法性能的影响。模糊算法也被引入到网络拥塞控制算法的设计之中， 文献j 提出了一种基于模糊控制的主动队列管理算法，该算法使用一个二入一出的模糊 控制器，两个输入量分别为输入速率和队列长度的变化，输出量为丢弃率的增量。为了 能够容纳突发数据流，对输入速率采取加权滑动平均的办法，两个输入量的模糊化均采 取非均匀分割。文献【1 2 j 提出了一种将模糊算法和p i 算法相结合的新算法，该算法使用 一个模糊控制器对p i 算法的两个参数进行实时的自适应调整。模糊控制器以队列误差 和队列误差的变化作为输入量，根据两套模糊控制规则，对p i 算法的比例系数与积分 系数进行调整。文献【l3 提出了一种基于模糊调节滑膜面的t c p 拥塞控制算法，该算法 通过模糊调节滑膜表面，使得队列的跟踪性能得到改善。选择切换函数为： s ( t ) - a x + x 2 + 万，依据两个状态量五和而，对参数兄和万进行调节。文献4 】提出了一种 基于模糊理论的拥塞控制算法。该算法充分利用了模糊理论在处理不确定问题上的优 势，依据路由器负载的模糊化，将拥塞程度划分为四个状态：正常、轻度、中度、严重， 结合整体与局部的拥塞状态，取得了较好的效果。模糊算法本身具有一些良好的特性， 例如：不需要精确地被控系统模型，可以适应变化的被控系统，响应速度快，可以引入 专家经验等等。但是模糊算法不能保证较小的稳态误差，通常只适用于一个或者两个输 入量，当输入量超过两个之后，模糊规则表的设计就会变得十分困难。同时得益于人工 神经网络理论的发展，神经网络理论也被应用在网络拥塞控制算法的设计之中。神经元 是神经网络的基本单位，具有比较简单的结构和一定的自适应能力、自学习能力。一个 神经元具有多个输入，每一个输入均会有一个对应的加权系数，单个神经元使用线性的 传递函数和l m s 学习规则算法，通过改变各个输入的加权系数来获得一定的自学习能 3 1 绪论硕士论文 力。文献 1 5 】提出了一种基于独立神经元的自适应主动队列管理算法，该算法针对传统 p i 算法自适应性不足的缺点，利用两个独立的神经元控制器来动态调整p i 算法参数， 两个神经元根据系统实时的状态采用最速下降法。文献【l6 】提出了一种基于神经网络的自 适应p i d 算法。根据t c p 流模型，利用r b f 辨识器进行在线地辨识，将辨识结果提供 给单神经元控制器，单神经元控制器对p i d 的三个参数进行在线整定。文献 17 j 设计了一 种单神经元自适应p i d 控制器。该算法依据队列长度的变化信息动态地调整神经元的三 个输入加权系数和一个输出比例系数。文献【l8 j 提出了一种基于模糊神经网络的捐j 塞控制 算法。该算法使用神经网络对模糊控制器的隶属度函数的参数和加权系数进行实时地修 正，避免了依据经验确定算法参数的弊端。实时队列长度的误差以及输入输出速率之间 的误差作为神经网络的两个输入，通过神经网络的输出对模糊控制器的相关参数进行动 态地调整。 自1 9 9 8 年b r a d e n 等人提出主动队列管理技术以来，很多学者对此进行了大量的深 入研究，设计出了很多种拥塞控制算法。但是在当前的网络环境下，已有的拥塞控制算 法依然无法很好的解决网络拥塞这一问题。原因就是计算机网络本身具有很强的时变性 和非线性，致使单一的算法和单一的参数设置不可能在不同的网络环境下取得良好的拥 塞控制效果。因此，设计一个对网络状态的变化具有一定自适应能力的拥塞控制算法就 显得极为重要了。可以提高算法自适应能力的方法有很多，常用的有模糊算法、神经网 络、遗传算法等等。文献【l9 提出了一种新的自适应p i 拥塞控制算法。该算法将p i 控制 器视作一个二入出的神经元，依据网络的实时状态信息，让p i 控制器的两个参数按 照l m s 算法进行在线调整。文献 2 0 提出了一种参数自适应的随机早期检测算法，该算 法将当前队列长度与上一次计算出的平均队列长度相比较来实时调整r e d 算法的加权 系数缈，依据当前队列长度来实时调整r e d 算法的最大丢弃率。文献【2 l j 提出了一种基 于模糊参考模型机制的网络自适应拥塞控制算法，该算法以模糊参考模型机制的核心来 提高a q m 算法的自适应能力，用两条通道分别实现a q m 的控制能力与学习能力，并 结合参考模型机制实现模糊反向推理。文献【2 2 在灰色预测、自适应控制、虚速率三者的 基础之上，提出了一种基于自适应灰色预测的虚速率算法。该算法将二次型性能指标引 入到v r c 算法中的p i d 控制器参数整定之中，按照性能指标的负梯度方向修改加权系 数。 控制理论自身的发展与成熟为a q m 主动队列管理算法的设计提供了大量的素材， 并且也提供了很多的理论分析依据，使得算法的设计转换为控制器的设计。可以将整个 t c p 网络视作一个强非线性、强时滞性的被控系统，对其进行数学建模，在此基础上运 用各种成熟的控制理论在路由器上设计各种拥塞控制算法，以达到提高网络性能的目 的。但是也要记住t c p 网络系统与传统意义上的被控系统是有着本质区别的，一些在 传统的被控系统中适用的方法在t c p 网络环境下可能无法取得预期的效果。目前应用 4 硕士论文自适应主动队列管理算法研究 控制理论设计a q m 算法依然面临着一些问题，首先就是如何让这些传统的控制理论算 法在这样一个恶劣的网络环境中依然有足够的鲁棒性，让网络系统稳定工作。其次就是 如何获得比较准确的网络系统模型，以便更好的为控制器的设计服务。以及如何成功的 引入新发展的高级控制理论，例如：神经网络、遗传算法等等。 1 3 本论文工作和章节安排 在江苏省自然科学基金项目下一代高速互联网智能自适应主动队列管理算法 研究的支持下，我进行了本论文课题的相关研究。主要介绍：与本论文研究内容相关的 t c p i p 拥塞控制原理，网络拥塞产生的原因，该研究领域的历史与现状，一些经典拥塞 控制算法的原理，以及自己在此基础之上给出的新算法的原理。通过n s 一2 仿真结果的 对比可以看出新算法在一些性能指标上有了一定程度的改进。 本文各章节的内容组织如下： 第l 章：介绍网络拥塞产生的原因与危害，以及这一研究领域的历史与现状。 第2 章：介绍了t c p 源端拥塞控制策略以及口层的拥塞控制策略，同时介绍了一 些经典的a q m 主动队列管理算法。 第3 章：在模糊算法与p i 算法的基础之上，给出了一种具有一定白适应能力的复 合a q m 算法，并进行n s 2 仿真。由仿真结果可以看出，新算法的性能有了一定程度 的改进。 第4 章：结合比例算法和r e m 算法，提出一种新的算法，并进行n s 一2 仿真。由仿 真结果可以看出，新算法的性能有了一定程度的改进。 第5 章：总结自己所做的工作，并提出一些该领域中可以进一步研究的方向。 5 硕- 上论文 自适应主动队列管理算法研究 2t c p i p 拥塞控制策略 2 1t c p 层的拥塞控制机制 2 1 1t c p 拥塞控制简介 t c p 层拥塞控制协议采用基于滑动窗口的和式增加积式减少( a i m d ) 的拥塞控制机 制【2 3 | ，当源端未检测到拥塞发生时，拥塞窗口进行加性的增加。而当源端检测到拥塞发 生时，拥塞窗口进行乘性的降低。这样的一种机制使得网络未发生拥塞时，源端可以不 断地加大发送速率，网络资源被充分利用。而当拥塞发生时，源端迅速地降低发送速率， 避免拥塞的加剧。t c p 协议是通过重传机制保证数据传输的高可靠性。源端维持一个已 经发送但是尚未得到确认的数据包的队列，当在重传时间内没有收到某个数据包的应答 包时，则认定该数据包已经丢失，重发这个数据包。根据返回信息，t c p 源端维持一个 动态的发送窗口，依据这个窗口来调节发送速率。这个协议虽然通过滑动窗口对发送速 率进行控制，但是过于强调端节点的作用，忽略了中间节点在网络运行中的作用。因为 在发生超时重传时，数据包已经丢失或者因为长时间的排队而留存在某个中间节点的缓 冲区之中。此时拥塞已经发生，而t c p 源端要在经过一段的时间之后才开始调整发送 速率，具有很大的滞后性。因此该协议并没有从根本上解决网络拥塞的问题，其不足之 处也逐渐被人们所发现。因此出现了一些对t c p 协议的改进版本。1 9 8 8 年v a nj a c o b s o n 提出了“慢启动”( 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 ) 算法【2 4 】，1 9 9 0 年 出现的t c pr e n o 版本增加了“快速重传( f a s tr e c o v e r y ) 算法”和“快速恢复( f a s tr e c o v e r y ) ” 算法，这四个算法组成t c p 拥塞控制的核心成分，新出现的改进版本有n e w r e n o 2 5 】， s a c k 2 6 等。 在整个t c p 层拥塞控制过程中，有七个参数起着决定性的作用【27 1 ，它们分别是： 1 ) 发送端拥塞窗口( c w n d ) ：限制了源端一次最多可以发送的数据包的个数，在t c p 拥塞控制中，这个参数起着关键性的作用。 2 ) 通告窗口：接收端在t c p 建立初期为发送端设立的发送窗口大小，该参数只是 在链接建立初期起作用。 3 ) 源端的发送窗口( w i n ) ：决定源端每次实际上可以发送多少个数据包。 4 ) 慢启动阀值( s s t h r e s h ) ：慢启动阶段和拥塞避免阶段的分界点，初始值通常设为 ( 2 1 6 ) 字节。 5 ) 回路响应时间( r 盯) ：一个数据包从源端发出，被接收端接收，接收端发出的 应答包被源端接受，这一过程所需要的时间被称作回路响应时间。这一参数对网络性能 有比较大的影响，这是网络具有时滞性的主要原因。 7 2t c p i p 拥塞控制控制策略硕士论文 6 ) 超时重传计时器( i 玎o ) ：每当一个数据包从源端发出，即启动一个计时器，当 计时器到达规定时间时，源端仍然没有接收到该数据包的应答包，则认定该数据包丢失， 源端重传该数据包，r t o 通常设置为r 1 盯的数倍。 7 ) 快速重传阀值( t c p r e x m t t h r e s h ) ：决定源端是否进入快速重传阶段。当源端收到 的重复确认包的个数超过该阀值的时候，触发源端的快速重传机制。 2 1 2t c p 拥塞控制的四个组成阶段 1 ) 慢启动阶段弘副 在早期开发的t c p 协议当中，在源端建立一个新的t c p 链接时，会立刻发送大量 的数据包进入网络，网络的负载迅速增加，在很短的时问内各项网络资源就被耗尽，网 络拥塞发生，各项性能急剧下降，实际有效的吞吐量迅速下降，最终导致此链接以及很 多其他的链接无法获得很好的网络服务。产生这一问题的原因是源端对网络的运行状态 毫不知情，因此过于贪婪地发送数据包。为了解决这一问题，t c p 中增加了慢启动机制。 顾名思义，就是缓慢地增加t c p 源端的发送速率。当t c p 源端新建立一个链接时，拥 塞窗口被限制为一个数据包的大小，强制源端无法立即大量的发送数据包，而每当源端 收到一个a c k 应答包时，拥塞窗口就增加l ，不断地持续下去。这样源端的拥塞窗口 就会呈指数增长。这一机制使得源端可以在链接建立初期一定程度上限制自己的发送速 率，以此来避免拥塞的发生。 2 ) 拥塞避免阶段 当源端收到三个相同的a c k 应答包时，判定网络拥塞发生。为避免拥塞加剧，源 端进入拥塞避免阶段。此时慢启动阀值s s t h r e s h 将会被设置为当前c w n d 值的一半，如 果发生数据包超时，c w n d 还会被设置为1 。如果c w n d = s s t h r e s h ，则进入拥塞避免阶段。与慢启动阶段不同的是，在j 爿j 塞避 免阶段，源端每接收到一个a c k 应答包时，拥塞窗口c w n d 的大小只增加1 c w n d 。这 样的线性增长就避免了在慢启动阶段拥塞窗口的指数增长，防止在网络拥塞已经发生的 情况下，源端继续发送大量的数据包进入网络，加剧拥塞程度。 3 ) 快速重传阶段 当一个数据包从源端发出，在两种情况下接收端将无法及时接收到该数据包。第一 种情况是该数据包在某一个中间节点处被丢弃，第二种情况是该数据包没有被丢弃，但 是因为中间节点的缓冲区队列太长，该数据包依然在排队，而当后续的数据包被接收端 接受之后，接收端收到的就是乱序的数据包。为此，接收端会向源端发出相应的重复确 认。源端在收到一个重复确认之后，并不能判定该数据包是真的被丢弃了，还是数据流 发生了失序。为此做出一个假定：即当源端收到三个以下的重复确认请求时，源端判定 数据流发生失序。而当收到三个或者三个以上的重复确认请求时，源端判定发生数据包 8 硕士论文自适应主动队列管理算法研究 丢失，此时源端不需要等待超时重传立即重新发送该数据包，也即快速重传。 4 ) 快速恢复阶段 在快速重传之后，如果源端依据三个连续的重复确认请求信号，而判定网络发生严 重拥塞，进入慢启动阶段，就会大大降低链路利用率。实际上通常在这个时候尚未发生 严重的拥塞，因此快速恢复算法就是在源端经历快速重传之后，进入拥塞避免阶段，这 样可以保证网络资源被有效地利用。 快速恢复之后接着就是快速重传，其算法描述如下： 1 ) 当源端收到三个连续的重复确认请求信号之后，进入到快速重传阶段，设置 s s t h r e s h = m a x ( 2 ，c m w d 2 ) ，c w n d = s s t h r e s h + 3 ，重传丢失的分组。 2 ) 每当源端收到一个重复的a c k ，设置c w n d = c w n d + l 。 3 ) 当源端再一次收到确认新数据的a c k 时，设置c w n d = s s t h r e s h 。分组丢失之后， 第一个重复a c k 之前源端发送的数据包，都会因为这个新数据包的确认a c k 而得到确 认。 2 1 3t c p 拥塞控制的不足之处 由上述四个t c p 拥塞控制步骤，可以看出i p 层不对t c p 层的拥塞控制提供任何支 持，t c p 层必须使用超时重传和确认请求一类的信息来判断网络拥塞状况，这是一种端 到端的拥塞控制机制，与a q m 主动拥塞控制机制有着本质的区别，因此这种拥塞控制 机制必然存在一些无法避免的问题： 1 ) 滞后性：无论是通过超时重传计时器( r t o ) 的超时来判断拥塞，还是通过多 次重复确认请求信息来判断拥塞，这都是在已经发生拥塞之后源端才开始采取措施，为 时已晚。源端对中间传输节点的情况一无所知，是一种被动地拥塞控制机制。而当源端 发现拥塞之后，急剧降低拥塞窗口，大幅降低发送速率，又有可能导致链路为空，网络 资源不能得到充分的利用。 2 ) 公平性问题：公平性是指在网络拥塞发生时，各个源端之间以及同一源端建立 的不同t c p 链接之间或者u d p 链接之间可以公平的使用网络资源，例如：带宽，缓存 等等。处于相同级别的源端应该享有同等数量的网络资源。不公平现象产生的原因就是 网络拥塞，因为一旦拥塞发生，就会发生丢包，导致各个链接之间为了获得更多的网络 资源而发生竞争。公平性主要表现在两个方面，第一，u d p 数据流对t c p 数据流的不 公平，源端的t c p 拥塞控制机制只能对遵循t c p 协议的数据流进行约束，对非t c p 数 据流是没有约束作用的。当拥塞发生时，t c p 源端会按照拥塞控制步骤进入拥塞避免阶 段，主动降低数据包的发送量，避免拥塞的发生。而u d p 源端仍然继续大量发送数据， 并且由于t c p 流让出了一部分的资源，u d p 流就会抢占这些资源，最终导致t c p 链接 所占有的资源越来越少，而u d p 链接占有的资源越来越多，进一步加剧二者之间的不 9 2t c p f p 拥塞控制控制策略硕士论文 公平，甚至会最终导致网络崩溃。第二个不公平表现在t c p 链接之间的不公平，这是 因为在拥塞产生之前，各个t c p 链接就存在参数设置上的不一样，例如：一些链接使 用了更大的拥塞窗口，或者它们的r t t 较小。这些链接在网络资源的争夺之中将会占 据优势。 3 ) 恢复时间长：依据t c p 拥塞控制机制，在拥塞发生之前，各个源端的拥塞窗口 大小会呈指数增长，源端的发送速率急剧增长，而一旦源端判断网络发生拥塞，就会乘 性减少拥塞窗口大小，使得源端发送速率急剧下降，需要经历一段较长的时间，源端才 能从低发送速率的状态中恢复过来。 总之，在目前的网络中，t c p 拥塞控制机制对网络的正常运行依然起着重要的作用。 但是随着网络的快速发展，各种非t c p 流进入网络，所占比例也在逐渐增加，用户层 服务质量的要求也越来越高，这使得仅仅依靠源端的t c p 拥塞控制机制难以应付这些 问题，中间节点在网络拥塞控制中可以发挥的作用逐渐受到人们的重视，也相继出现了 很多基于路由器的拥塞控制策略。 2 2i p 层的拥塞控制机制 由上述分析可以看出，t c p 端节点的拥塞控制机制对网络的正常运行，避免拥塞的 发生起到了巨大的作用。但是这种拥塞控制机制的发挥需要两个基本前提：首先就是网 络中几乎所有的数据流都采用拥塞控制机制。第二，网络中的数据流只能是t c p 数据 流或者t c p 友好的数据流。从这几十年的网络发展来看，这两个基本前提已经越来越 不能满足。例如：没有针对u d p 数据流的源端拥塞控制机制，为了满足更多的网络业 务，非t c p 友好的数据流也越来越多。 2 2 1 i p 层拥塞控制的意义 随着网络在更广泛的领域内得到使用，更多的业务得到发展，同时用户对网络服务 质量的要求也越来越高，使得现在的网络变得空前的复杂，数据流遵循的协议种类越来 越多，进入网络的数据量也越来越多，很多实时性的多媒体业务无法忍受源端急剧降低 数据发送速率。由于技术和经费的原因，网络中依然会存在大量的瓶颈链路，网络拥塞 依然会继续大量存在，并且有加剧的趋势。因此，除了在t c p 端节点建立拥塞控制机 制之外，中间节点也应该参与到拥塞控制机制当中。 路由器工作在i p 层，连接多个子网。在网络工作过程中起着很重要的作用。它除 了负责数据包的转发之外，还需要维护一个缓冲队列，以便存储暂时无法立即转发的数 据包。如何有效科学地管理该缓冲队列，对提高网络传输性能就显得尤为重要了。路由 器对缓冲队列的管理分为两大类：一类是被动式的管理，另一类是主动式的管理。 最先出现的，也是最简单的路由器队列管理算法就是d r o p t a 订队尾丢弃算法【2 9 1 ，属 1 0 硕士论文自适应主动队列管理算法研究 于被动式的队列管理算法。虽然该算法已经在路由器中被广泛地使用，但是它也存在一 些无法避免的问题。第一，因为路由器每次都是在缓冲区满了之后才开始丢包，这是一 种很被动的方式，使得大量的数据包在路由器中等待的时间太长，大大增长了网络延时， 不仅使得源端的拥塞控制机制无法得到及时的拥塞信息，采取措施，并且有的数据包可 能因为在路由器缓冲区中等待的时间太长，触发了源端的超时重传，这会更迸一步加重 网络的负载。第二，容易导致死锁现象的发生，一个流或者几个流在某些时候排斥其他 流，独占了路由器的缓冲区。第三，当路由器的缓冲区满了之后，如果依然有大量的数 据包进入，那么缓冲区会长时间处于充满的状态。第四，全局同步问题。第五，相当大 的丢包率。 针对队尾丢弃算法只能在路由器物理缓冲区满了之后才丢弃包的缺陷。人们想到了 在缓冲区满之前就主动地进行丢包，这就是主动队列管理算法。这个算法在一定程度上 较好地避免了队尾丢弃的一些缺陷i 使得算法性能有了很大的改进。同时将大量成熟的 控制理论思想引入到算法的设计之中，大大扩展了算法的设计思路。 2 2 2 主动队列管理( a q m ) 算法 用户端发送数据流的突发性和中间节点处理能力的有限性，这二者之间不可调和的 矛盾决定了路由器中必须有缓冲区来存储无法立即转发的数据包。因此，就带来了一个 如何管理路由器缓冲队列的问题。队列太长，虽然可以提高吞吐量，但是数据包在路由 器中等待时间太长，会加重网络的时滞性，使得源端不能及时地获得拥塞信息。如果队 列太短，那必然要求路由器大量丢包，网络实际有效的吞吐量无法得到保证。如何在高 吞吐量与低网络延时之间取得平衡，对网络运行的各项性能指标有着至关重要的作用。 相对于早期的队尾丢弃算法，a q m 算法在这方面有了很大的改进。 主动队列管理算法主要分为两个步骤。第一步，路由器获得一些网络实时状态信息， 例如：实时队列长度、输入输出速率等等，a q m 算法依据这些信息计算拥塞程度。第 二步，依据拥塞程度来计算丢弃率。以此来维持一个较小的队列长度，在低网络延时和 大吞吐量之间寻求一个平衡。这一算法的引入对拥塞控制具有重大的意义。它改变了以 往路由器被动地进行队列管理的情况，使得中间节点可以更加积极主动地参与到拥塞控 制之中。 传统的队尾丢弃算法存在一些无法避免的严重缺陷。人们对此也作出了一些改进， 相继出现了“首丢弃”和“随机丢弃”，这两个新算法很好的避免了死锁【3o 引j 和全局同 步 3 2 】，但是这些算法都没有让中间节点积极主动地参与到拥塞控制当中，只是一味地让 路由器充当了一个中转站与缓冲区。解决问题的根本途径在于让路由器可以对即将可能 发生的拥塞具有一定的预测能力，避免在缓冲区已满，拥塞已经发生的时候，被迫地丢 弃数据包。 2t c p 1 p 拥塞控制控制策略硕士论文 b r a d e n 等人于1 9 9 8 年提出主动队列管理机制之后，由于该机制在网络拥塞方面有 着广大的应用前景，很多学者对此进行了大量的研究，也相继出现了很多算法