（计算机应用技术专业论文）基于petri网的aqm算法研究及改进.pdf

摘要计算机网络在过去的十几年中经历了爆炸式的增长，随之而来的是越来越严重的拥塞问题拥塞控制的目标就是要达到链路吞吐量的最大化、分组延时的最小化、各用户之间资源分配的合理化和尽可能少地丢弃数据包。作为t c p 端到端拥塞控制的辅助手段，a q m ( a c t i v eq u e u em a n a g e m e n t ，主动队列管理) 使得中间节点参与到拥塞控制中，是近年来拥塞控制的热点研究领域。本文主要做了如下的工作；介绍拥塞控制研究的背景和意义，总结了主动队列管理( a q m ) 的国内外研究现状和面临的问题：阐述a q m 算法的工作原理，分析主流的主动队列管理算法。详细总结出随机早期检测( 1 也d ) 算法的不足，并在此基础上提出了其可改进方案。提出一种主动队列管理算法n l 礓d 算法。针对n r e d 算法行为建立了基于高级p e t r i 网的模型，对模型进行描述和分析，并抽象出等价的网n 1 ，构造出了网n 1 的可达图，在可达图的基础上对网n l 进行了可达性和活性的论证，利用p e t r i 模型分析证明了n r e d 算法行为的可行性。最后利用网络模拟器n s 2 工具对r e d 算法和n r e d 算法进行了对比仿真实验，分别对不同类型数据流( t c p 流和u d p 流) 、多个t c p 数据流、不同时延下的u d p 流，从吞吐量、延迟、振荡、丢包率等多项性能指标进行分析。验证了n r e d 算法有效性。关键词：拥塞控制：主动队列管理；随机早期检测；p e t ri 网；仿真a bs t r a c ti n t e r n e th a se x p e r i e n c e da l le x p l o s i v e l yg r o w t hi nt h ep a s to f1 0y e a r s ，w h i c hl e a d st os e v e r ec o n g e s t i o np r o b l e m t h ea i mo fc o n g e s t i o nc o n t r o li st om a x i m i z et h el i n ku t i l i z a t i o n ，m i n i m i z et h ep a c k e t sd e l a y , d i s t r i b u t et h en e t w o r kr e s o u r c e sa m o n gu s e r sr e a s o n a b l ya n dd r o pp a c k e t sa sf e wa sp o s s i b l e a st h es u p p l e m e n t a r ym e a n so ft h et c pe n d t o - e n dc o n g e s t i o nc o n t r o l ，a q m ( a c t i v eq u e u em a n a g e m e n t ) m a k e st h ei n t e r m e d i a t en o d ej o i nn e t w o r kc o n g e s t i o nc o n t r o l ，a n db e c o m e sah o tr e s e a r c ha r e ai nc o n g e s t i o nc o n t r o lt h e s ey e a r s t h em a i nw o r ko ft h i sp a p e ri n c l u d e s ：i tf o c u s e so na n a l y z i n gt h er e s e a r c hb a c k g r o u n do fc o n g e s t i o nc o n t r o la n ds i g n i f i c a n c e ，a n di n t r o d u c i n ga q ma l g o r i t h md o m e s t i ca n di n t e r n a t i o n a lr e s e a r c ha c t u a l i t ya n dp r o b l e m s b a s e do i ls y s t e m a t i c a li n t r o d u c t i o no fa q mc o n g e s t i o nc o n t r o l ，s o m et y p i c a la q ma l g o r i t h m sh a v eb e e ns u m m a r i z e da n dc o m p a r e d a f t e rs t u d y i n go fr e d ( t h et y p i c a lr e p r e s e n t a t i v eo fa q ma l g o r i t h m ) ，t h i sp a p e rs u m su pt h ei n a d e q u a c i e sa n di m p r o v e m e n t so fr e da l g o r i t h m t h ei m p r o v e da l g o r i t h m ( n r e d ) i sp r e s e n t e da n dt h ep e t r in e tm o d e lo fn r e da l g o r i t h mi sb u i l t t h ed e s c r i p t i o n a n a l y s i so ft h em o d e la r eg i v e na n dt h ee q u i v a l e n tn e t( n e tn 1 ) i sa b s t r a c t e d ar e a c h a b l em a r k i n gg r a p ho fn 1i sc o n s t r u c t e da n dt h er e a c h a b i l i t y &l i v e n e s so fn1i sd e m o n s t r a t e db a s e do nt h er e a c h a b l em a r k i n gg r a p h t h e n ，t h ef e a s i b i l i t yo fa l g o r i t h m ( n r e d ) i sp r o v e db yt h em o d e la n a l y s i so ft h ep e t r in e t f i n a l l y , s i m u l a t i o n so fn r e d & r e da r ec a r r i e dw i t hn s 2s i m u l a t i o nt 0 0 1 an u m b e ro fp e r f o r m a n c ei n d i c a t o r s ，s u c ha st h r o u g h p u t ，d e l a y , j i t t e ra n dp a c k e tl o s sr a t ea r ea n a l y z e d ，r e s p e c t i v e l yo nt h ed i f f e r e n tt y p e so fd a t af l o w ( t c pa n du d p ) ，m u l t i p l et c pd a t as t r e a m sa n dd e l a yu n d e rd i f f e r e mf l o wu d es i m u l a t i o nr e s u l t ss h o wt h ee f f e c t i v e n e s so ft h ea l g o r i t h m 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 em a n a g e m e n t ：r a n d o me a r l yd e t e c t i o lp e t r in e t ；s i m u l a t i o n长沙理工大学学位论文原创性声明本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律后果由本人承担。作者签名：靼焰日期：办诉堂月劫日学位论文版权使用授权书本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权长沙理工大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。本学位论文属于1 、保密口，在年解密后适用本授权书。2 、不保密函。( 请在以上相应方框内打“4 ”)作者签名：孑受焰导师签名：音放日期：沥萝年夕月。护日日期：伽譬年厂月加日1 1 研究的背景和意义第一章概述过去几年，i n t e r n e t 随着其主干线的升级和技术的改进，其可提供的服务质量得到大幅度提高。但用户的增长速度更快，用户所要传输的数据量也大幅度增加，这就可能产生大量的瞬间突发分组，导致越来越严重的拥塞问题。拥塞产生的根本原因【l 】在于路由器接口的流量超出了出口的带宽，这样大量的数据包先被保存在路由器的缓存中，但当路由器没有多余的空间来保存新的数据包时，它就会丢弃新的数据包。当这个新的数据包被丢弃后，发送端会重发这个数据包，进一步加重拥塞。拥塞控n t 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 na v o i d a n c e ) 和拥塞控制( c o n g e s t i o nc o n t r 0 1 ) 两种不同的机制【3 】。前者是预防策略，维持网络运行在高吞吐量、低延迟状态，避免网络拥塞发生；后者是恢复策略，使网络从拥塞状态中恢复回来，进入正常的运行状态。由于i n t e r n e t 采用无连接的i p 协议，提供尽力而为( b e s t - e f f o r t ) 服务。在一定时期内，虽然可以通过改善网络带宽缓解这种矛盾，但随着对网络资源的要求增加，新的矛盾又将产生，所以，网络资源和对网络资源的需求这对矛盾将会长期存在下去。尽管现有的拥塞控制技术已应用于实际中，但是拥塞控制问题本身尚未得到很好的解决【4 j 。拥塞控制不是一个孤立的问题，解决这一问题涉及到端系统、网络内部传输单元( 例如路由器) 的协同工作；在算法策略上涉及到数据流的调度算法、缓存管理技术等网络资源的分配。对于i n t e m e t 这样一个复杂系统，只有通过通信、控制、数学等多学科相结合的研究，才有望获得突破性的成果。为此，对t c p i p 拥塞控制的研究有着极其重要的意义。1 1 1p e t ri 网及其在网络研究中的应用概况p e t r i 网【5 】是德国c a r ta d a mp e t r i 博士在2 0 世纪6 0 年代初提出的研究信息系统及其相互关系的数学模型，经过四十多年的发展，已成为具有严密数学基础，多种抽象层次的建模工具，并在自动控制和计算机科学中得到广泛应用，如计算机网络性能分析、并行程序的设计与分析、系统可靠性分析、分布式计算机系统的分析和控制、软件工程、知识推理、人工神经元网络和决策模型等领域。近几年，为适应不同规范及验证的需求，从基本p e l r i 网模型衍化出许多扩展模型系统，目前主要有：谓词变迁p e t f i 网、时间p e m 网( t p h 0 、带时态逻辑的p e t a l 网、有色p e t r i 网( c p n ) 、面向对象p e t r i 网( o o e h 0 、随机p e t r i 网( s p n ) 、数字p e t r i 网( n p n ) 等。与传统的系统建模、分析和控制方法相比，p e t r i 网作为一种图形化和数学化的建模工具，能够提供一个集成的建模、分析和控制环境，为系统的设计提供便利。它能较1好地描述离散事件的动态过程，并能精确描述事件的顺序、并发和冲突关系，适合于描述网络协议和拥塞控制行为。目前p e t r i 网在网络中的应用主要集中在对网络协议和网络行为进行研究分析，例如b i l l i n g t o n 使用有色p e t r i 网对通信协议进行建模研究【6 】；t r i v e d i 使用随机p e t r i 网对a t m 网络的早期丢包影响进行了研究r 7 】；h a r tb 使用有色p e t r i 网对t c p 的连接管理进行了研究分析【8 j 。作为本文的一个创新点，将p e t r i 网理论应用到拥塞控制研究中，通过建立基于p e t r i网的拥塞控制算法的行为模型来描述i n t e r n e t 拥塞控制行为。在模型的基础上利用p e t r i的基本性质从理论上论证算法行为的可行性，从p e t r i 网理论分析角度为算法实现提供依据。由于路由器对一个源端操作和n 个源端的操作是一样的，所以本文采用p e t r i 网的高级网系统中的谓词变迁系统，以减少空间节点。谓词变迁系统将代表作用及状态类似的不同类资源用一个谓词表示，只使用少量的节点元素即可描述应用系统，比基本网系统和库所变迁系统更适合计算机自动分析工具的开发。1 1 2 拥塞控制策略的发展进程1 t c p 拥塞控制拥塞控制的主要目标是控制进入网络的数据流量，保证通信子网不会被用户发送的数据流湮没，合理地使用瓶颈资源。拥塞控制的研究开始于8 0 年代中期，1 9 8 4 年，n a g l e 首次提出了复杂的t c p i p 网络中存在的拥塞问题，特别是在由路由器连接的带宽差异较大的网络，容易发生“拥塞崩溃 现象，但在科研界没有引起足够的重视。直到1 9 8 6 年1 0 月，i n t e m e t 首次出现了一系列的拥塞崩溃现象。此后，j a c o b s o n 等人开始对此进行研究，发现这是由于在网络拥塞状态下t c p 的行为失常所致，为此j a c o b s o n在t c p 中增加了拥塞控制算法( 即t c p t a h o e ) ，于1 9 8 8 年提出了著名的“慢启动( s l o w s 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 ) ；1 9 9 0 年的t c pr e n o 版本增加了“快速恢复”( f a s tr e c o v e r y ) 算法，避免了网络拥塞不够严重时采用“慢启动”带来的大幅度减小发送窗口大小的现象。后来又相继产生了几个主要版本的t c p 端系统拥塞控制算法，即t c pn e w r e n o 、t c ps a c k 、t c pv e g a s 。版本虽有不同，但都是遵守a i m d ( a d d i t i v e i n c r e a s em u l t i p l i c a t i o n d e c r e a s e ，加性增加倍乘减小) 的窗口管理算法原理，即网络出现拥塞时，t c p 连接通过丢包发现拥塞，窗口从w 减少至( 1 - b ) w 。t c p 拥塞控制机制在i n t e r n e t 中的执行有效地避免了拥塞崩溃现象的发生。虽然t c p 协议本身具有避免网络拥塞发生的机制【9 】，但这种机制的有效性依赖于两个基本的假设：第一所有( 或者几乎所有) 的流都采用拥塞控制机制；第二这些流采用的机制是同质的( h o m o g e n e o u s ) 或者大体上相同的，即在相似的环境下按可比条件( 丢包率、r 1 盯、m t u ) 不会占用比t c p 流更多的带宽，也即是t c p 友好的( t c p 2f r i e n d l y ) 流。但随着近十年来计算机网络的爆炸式增长，特别是多媒体业务的广泛应用，i n t e r n e t已经不可能再仅仅依靠端节点提供的拥塞控制机制。尽管t c p 拥塞控制机制是必须的而且非常强大，但仍然需要采用基于路由器的拥塞避免机制对端节点的拥塞控制机制进行补充。2 主动队列管理( a q m )在当前的i n t e r n e t 上，解决路由器“满队列”的方法便是在队列充满之前丢包，这样端节点便能在队列溢出前对拥塞做出反应。这种方法便称为“主动式队列管理( a c t i v eq u e u em a n a g e m e n t ，a q m ) ”。主动队列管理( a c t i v eq u e u em a n a g e m e n t ，a q m ) 机制是一种“拥塞避免”控制策略。与拥塞恢复策略相区别的是，主动队列管理机制通过对网络状况进行跟踪，在拥塞发生前对流的分组进行选择性的丢弃或者标记，促使流的发送端做出响应，降低其发送速率，从而减少或避免拥塞的产生。1 2 主动队列管理的国内外研究的现状和面临的问题1 2 1 国内外研究现状对于有线网络而言，拥塞控制主要集中在源算法( s o u r c ea l g o r i t h m ) 和链路算法( 1 i n ka l g o r i t h m ) 两个方面【l o 】。链路算法和源算法是以拥塞控制算法的实现位置为划分依据的。源算法在主机和网络边缘设备中执行，作用是根据反馈信息调整发送速率。基于源端的拥塞控制策略中，使用最为广泛的是t c p 协议中的拥塞控制策略，所以研究主要集中在对t c p 协议方面提出改进。而链路算法在网络设备( 如路由器和交换机) 中执行，作用是检测网络拥塞的发生，产生拥塞反馈信息。目前i n t e r n e t 拥塞控制研究的热点逐渐由端系统向网络中的路由器等中间节点设备转移，期望通过加强它们的功能来实现端系统无法达到的技术目标，从而更好地避免“拥塞崩溃现象的发生。链路算法的研究热点主要集中在主动队列管理( a c t i v e q u e u e m a n a g e m e n t , a q m ) 算法方面。作为研究的热点，到目前为止己经出现了数十种主动队列管理( a q m ) 算法。根据拥塞检测方法的不同，可以将主动队列管理算法分为3 种：基于队列长度的算法，如r e d t l l l 及其改进s r e d 1 2 1 ，a r e d 1 3 】；基于通信流量速率的算法，如a v q t l 4 1 ，c s f q t l 5 】等；以及基于流量速率和队列长度组合的算法，如r e m t l 6 1 ，p i t l 刀，f r e d t l 明等。根据算法能否提供带宽分配的公平性，可以将主动队列管理算法分为2 种：公平带宽分配算法，如f r e d ，w f 2 q 【1 9 1 ，d r r t 2 0 ，c s f q ，c h o k e 2 1 1 ，r f q t 2 2 1 和非公平带宽分配算法，如r e d ，s r e d ，a r e d ，b l u e t 矧。1 9 9 8 年，b r d a n e 等人在e i t f 提出在路由器中使用主动队列管理技术( a c t i v eq u e u em a n a g e m e n t ，a q m ) ，采用排队算法和数据包丢弃策略监控路由器缓冲区队列，提前检测拥塞的到来并通知数据发送方。这样发送方可以在路由器缓冲区溢出之前调整数据的发送速率，避免更严重的拥塞发生，并降低丢包率和提高链路利用率。s f l o y d 等人提出的r e d ( r a n d o me a r l yd e t e c t i o n ，随机早期检测) 算法作为最早提出的主动队列管理算法，已被广泛用来提高系统的综合性能。但是r e d 算法的性能对算法参数设置相当敏感，随后又有很多改进r e d 算法和新算法相继被提出，比较有代表性的有s r ed 、f r e d 、d r e d 、b l u e 、r e m 等等，不过这些算法的提出都是基于启发式思维和仿真，缺乏系统的方法，因此算法的稳定性和鲁棒性较差，一般只适用于特定的网络环境。不仅这样，不管是r e d 还是其改进s r e d ，a r e d ，及b l u e 等主动队列管理算法对于公平性的考虑不足，也就是说，当检测到拥塞时，算法对于所有分组的丢弃概率的计算是一样的，这样不同的流的分组以同样的比率被丢弃，而没有考虑每个流当前占用带宽的多少。这样占用带宽多的流经过丢弃后仍然占用较多带宽。这对于t c p 流和t c p 友好的流( t c p - f r i e n d ) 是不公平的，一些u d p 流或不响应拥塞的流可以通过维持或加大发送速率来获取较多的带宽，从而侵占正常的t c p 流的带宽。上述算法所存在的问题，后来的研究者对最初的主动队列算法进行了一些改进，使得主动队列算法能对公平性予以一定的支持。在这些算法中，具有代表性的有如下几种，f r e d ，c h o k e ，c s f q ，d r r 等。它们实现公平性的方法各有不同，实现公平的程度也不一样。c h o l l o t 等人在2 0 0 1 年将经典控制理论引入到了a q m 算法的设计中，并利用频域校正法设计了p i 控制器阱l 。由于p i 控制器的调节时间太长，于是有人将带有反映队列变化速率的微分环节的p i d 、p d 控制器应用于a q m ，以期获得更佳的性能，后来又出现了采用非线性控制理论的变结构控制器。随着智能控制理论的发展，智能控制的应用领域也得到不断扩大，将智能控制理论应用于a q m 的设计也得到了不断尝试，象文献瞪j 就结合单神经元自适应p i d 控制器，为p i d 算法建立了自适应的模型，提出一种参数自适应的p d 算法。控制理论的发展和应用，为主动队列管理算法的设计开辟了一条崭新的道路，使得a q m 算法的设计可以转化成一种控制器的设计。通过给出一个包含t c p 源端和路由器动态特性的网络受控模型，可以方便地进行算法性能分析和控制器设计，并且可以根据控制目标进行参数设定，从而有效地提高拥塞控制效果。国内方面，近年来，清华大学、国防科技大学以及其他一些国内科研机构对a q m机制进行了深入的研究。清华大学在该领域的研究成果主要有任丰原提出的模糊控制器【硐、滑模变结构控制器 2 6 1 等多种a q m 新算法以及章渺提出的p 2 i 算法 2 7 1 。该领域的成果还包括简贵胄提出的基于测量的主动队列管理算法团j ，樊燕飞提出的e c n 与模糊智能丢弃算法的结合应用1 2 9 ，李锁刚提出的基于主动队列管理的区分服务节点机制等【刈。任丰原等人在文献1 3 1 中提出利用模糊逻辑设计智能分组丢弃机制，定义了拥塞指数作为测度来量化描述网络的拥塞状态，离线的合成推理使得分组丢弃的判定通过查表4操作和比较运算完成。该文提出的模糊控制器需要经过初始的调节过程，以便建立控制规则集和变量集合。从仿真结果可以看出，这种调节过程表现为队列在初始阶段的大幅振荡。章渺等人在文献 2 7 q h 提出p 2 i 的主动队列管理算法，研究了在主动队歹i j 管理算法中使用的p i 控制器和比例控制器之间的优劣。p 2 z 结合了比例控制器和p i 控制器的优点。当网络流量比较平稳的时候采用p i 控制器，当网络流量动荡比较大的时候采用比例控制器。这样既可以消除稳态误差，又可以提高系统的响应速度。但是从仿真结果可以发现当流量变化时，p 2 i 控制器难以控制队列振荡。国防科技大学在该领域的研究成果主要有张鹤颖博士提出的基于报文平均到达速率和平均队列长度的r q 算法【3 2 1 、基于反馈校正的p p 算法【3 3 】、近似公平带宽分配机制f p d 算法、采用自校正调节技术设计的主动队列管理算法1 3 4 1 等多种a q m 新算法以及张明杰博士提出的a p i 算法1 3 5 1 。其他大学和研究机构研究主要集中于r e d 算法的研究及其改进算法、应用控制理论设计新算法、应用于区分服务的a q m 机制以及a q m 机制的稳定性和公平性。1 2 2a o m 技术所面临的问题主动式队列管理a q m 技术是i e t f 推荐的基于路由器拥塞控制的关键技术，它和t c p 端到端的拥塞控制相结合，是解决目前i n t e r n e t 拥塞控制问题的一个主要途径。公平性是a q m 需要解决的一个重要问题。如何使路由器不增加过多的额外负担，又能够提高公平性，一直是困绕广大研究人员的一个难题。参数设置问题是a q m 需要解决的另一主要阊题。虽然目前也提出了一些解决方法和很多改进的算法，但并没有完全解决这类问题。另外，目前的a q m 机制仍然没有一套系统的理论体系来指导主动队列管理技术的研究。1 3 本文所做的主要工作和组织结构1 3 1 本文的主要内容本论文是基于有线网络的拥塞控制研究，介绍了主动队列管理( a q m ) 的国内外研究现状和面临的问题；分析研究了拥塞控制算法，并对链路算法中的a 铆算法进行深入的探讨，主要总结出a q m 算法中随机早期检测( r e d ) 算法在参数设置、对小数据包丢弃问题上的不公平待遇、对不同业务流不能区分对待等方面的不足，并在此基础上提出了其可改进方案。提出_ 种改进了的主动队列管理算法一n r e d 算法，并针对n r e d 算法建立了基于高级p e t r i 网的模型，对模型进行描述和分析，并抽象出等价的网n 1 ，构造出了网n 1 的可达图，在可达图的基础上对网n 1 进行了可达性和活性的论证，利用p e t r i 模型5分析证明了n r e d 算法行为的可行性。最后利用网络模拟器n s 2 工具对r e d 算法和n r e d 算法进行了三个对比仿真实验，分别对不同类型数据流( t c p 流和u d p 流) 、多个t c p 数据流、不同时延下的u d p流，从吞吐量、延迟、振荡、丢包率等多项性能指标进行分析。仿真实验结果表明了改进得到的n r e d 算法在解决拥塞响应的t c p 流和非拥塞响应的u d p 流之间资源享用不公平问题以及对待小数据包丢弃不公平待遇问题取得了较好的成效，进一步验证了n r e d 算法有效性。1 3 2 本文的组织结构本文主要章节内容安排如下：第一章，阐述研究的背景和意义、拥塞避免机制和主动队列管理( a q m ) ，总结a q m 的国内外研究现状和面临的问题，最后介绍本文所做的工作。第二章，归纳网络拥塞的基本概念，分析研究拥塞控制算法。对感兴趣的链路算法中的a q m 算法进行深入的比较分析，总结其中r e d 算法的不足( 如参数设置敏感、对小数据包丢弃问题上的不公平待遇、对不同业务流不能区分对待等方面) 和可完善之处，为以后章节的研究奠定基础。第三章，提出一种改进的主动队列算法n r e d 算法，并建立基于高级p e t r i 网的模型，对模型进行描述和分析，抽象出等价的网n 1 ，构造网n 1 的可达图，在可达图的基础上对网n 1 进行可达性和活性的论证，利用p e t d 模型分析证明n r e d 算法行为的可行性，为第四章n r e d 算法的仿真实验提供理论的依据。第四章，在n s 2 仿真平台下，对第三章提出的n r e d 算法和原r e d 算法进行对比性仿真实验，对结果进行分析，论证算法的有效性和可行性。第五章，总结本文所做工作并提出进一步的工作。6第二章主动队列管理算法分析弟一早土驯队列昌1 琏畀法，刀俐i2 1 拥塞的基本概念当网络中存在过多的数据包时，网络的性能就会下降，这种现象称为拥塞。在网络发生拥塞时，会导致吞吐量下降，严重时会发生“拥塞崩溃”( c o n g e s t i o nc o l l a p s e ) 现象。一般来说，拥塞崩溃发生在网络负载的增加导致网络效率降低的时候。最初观察到这种现象是在1 9 8 6 年1 0 月，在这个过程中，l b l 与u cb e r k e l e y 之间的吞吐量从3 2 k b p s下降到4 0 b p s 。f l o y d 总结出拥塞崩溃主要包括以下几种：传统的崩溃、未传送数据包导致的崩溃、由于数据包分段造成的崩溃、日益增长的控制信息流造成的崩溃等。墓茎蘸翰e域右负糊数据包负射数据笆图2 1网络负载与吞吐量及响应时间的关系对于拥塞现象，可以用图2 1 来描述。当网络负载较小时，吞吐量基本上随着负载的增长而增长，呈线性关系，响应时间增长缓慢。当负载达到网络容量时，吞吐量呈现出缓慢增长，而响应时间急剧增加，这一点称为崖点( k n e e ) 。如果负载继续增加，路由器开始丢包，当负载超过一定量时，吞吐量开始急剧下降，这一点称为膝点( c l i f f ) 。拥塞控制机制实际上包含拥塞避免( c o n g e s t i o na v o i d a n c e ) 和拥塞控制( c o n g e s t i o nc o n t r 0 1 ) 两种策略。前者的目的是使网络运行在k n e e 附近，避免拥塞的发生；而后者则是使得网络运行在c l i f f 的左侧区域。前者是一种“预防”措施，维持网络的高吞吐量、低延迟状态，避免进入拥塞；后者是一种“恢复”措施，使网络从拥塞中恢复过来，进入正常的运行状态。拥塞现象的发生和互联网的设计机制有着密切关系，这种设计机制简单归纳如下：1 数据包交换( p a c k e ts w i t c h e d ) 网络：与电路交换( c i r c m ts w i t c h e d ) 网络相比，由于包交换网络对资源的利用是基于统计复用( s t a d s t i c a lm u l t i p l e x i n g ) 的，因此提高了资源的利用效率。但在基于统计复用的情况下，很难保证用户的服务质量( q u a l i t y o f7s e r v i c e ，q o s ) ，并且很容易出现数据包“乱序 的现象，对乱序数据包的处理会大大增加拥塞控制的复杂性。2 无连接( c o n n e c t i o n l e s s ) 网络：互联网的节点之间在发送数据之前不需要建立连接，从而简化了网络的设计，网络的中间节点上无需保留和连接有关的状态信息。但无连接模型很难引入接纳控制( a d m i s s i o nc o n t r 0 1 ) ，在用户需求大于网络资源时难以保证服务质量；此外，由于对数据发送源的追踪能力很差，给网络安全带来了隐患；无连接也是网络中出现乱序数据包的主要原因。3 “尽力而为”的服务模型：不对网络中传输的数据提供服务质量保证。在这种服务模型下，所有的业务流被“一视同仁”地公平地竞争网络资源，路由器对所有的数据包都采用先来先处理( f i r s tc o m ef i r s ts e r v i c e ，f c f s ) 的工作方式，它尽最大努力将数据包送达目的地。但对数据包传递的可靠性、延迟等不能提供任何保证。这很适合e m a i l 、f t p 、w w w 等业务。但随着互联网的飞速发展，i p 业务也得到了快速增长和多样化。特别是随着多媒体业务的兴起，计算机已经不是单纯的处理数据的工具。这对互联网提出了更高的要求。对那些有带宽、延迟、延迟抖动等特殊要求的应用来说，现有的“尽力而为”服务显然是不够的。2 2 拥塞产生的原因导致拥塞的直接原因有：( 1 ) 路由器缓存不足导致拥塞。当多个分组突然从不同输入线路涌入路由器时，这些分组就要在路由器进行排队。如果路由器没有足够的缓存存储分组，就会使一些分组被丢弃。虽然增加缓存对这一问题会有所帮助，但n a g l e 在文献【3 6 】中指出，过大的缓存反而会导致拥塞的恶化。因为当分组最终排到队列头部时，源端早已超时重发。实际上，太多的缓存远比较少的缓存危害更大；( 2 ) 链路带宽不足导致拥塞。高速链路和低速链路的不匹配，或者多条输入带宽总和大于输出带宽容量，都会使路由器中数据到达率远远大于离去率，从而导致长队列缓冲区用完进而导致拥塞；( 3 ) 处理器速度慢导致拥塞。如果路由器的c p u 在执行排队缓存，更新路由表等功能时处理速度跟不上高速链路，也会产生拥塞。同样低速链路对高速c p u 也会产生拥塞。总结而言，拥塞发生的主要原因在于网络能够提供的资源不足以满足用户的需求，这些资源包括缓存空间、链路带宽容量和中间节点的处理能力。由于互联网的设计机制导致其缺乏“接纳控制能力，因此在网络资源不足时不能限制用户数量，而只能靠降低服务质量来继续为用户服务，也就是“尽力而为 的服务。拥塞虽然是由于网络资源的稀缺引起的，但单纯增加资源并不能避免拥塞的发生。例如增加缓存空间到一定程度时，只会加重拥塞，而不是减轻拥塞，这是因为当数据包8经过长时间排队完成转发时，它们很可能早已超时，从而引起源端超时重发，而这些数据包还会继续传输到下一路由器，从而浪费网络资源，加重网络拥塞。事实上，缓存空间不足导致的丢包更多的是拥塞的“症状 而非原因。另外，增加链路带宽及提高处理能力也不能解决拥塞问题。单纯地增加网络资源之所以不能解决拥塞问题，是因为拥塞本身是一个动态问题，它不可能只靠静态的方案来解决，而需要协议能够在网络出现拥塞时保护网络的正常运行。2 3 链路算法中队列管理算法链路算法，就是路由器的队列管理策略，包括队列管理算法和队列分组调度算法两部分。前者主要是在必要时通过丢包来管理队列长度。后者决定下一个要发送哪个包，主要用来管理各流之间带宽的分配。由于i n t e r n e t 数据本质上是突发的，因此允许传输突发的数据包非常必要，而路由器中队列的重要作用就是吸收( a b s o r b ) 突发的数据包。较大的队列能够吸收更多的突发数据，提高吞吐量，但t c p 机制往往会保持较高的队列占用，从而增加了数据包的排队延迟。因此需路由器对队列进行管理，维持较小的队列长度。因为维持较小的队列长度除了降低排队延迟，提高吞吐量外，还能保持较大的队列空间来吸收突发数据包。拥塞控制机制就是要维持网络处于低延迟高吞吐量的状态。就i n t e r n e t 中的路由器而言，当网络负载很大的时候，在瓶颈链路上，就会有部分包被存到路由器的缓存队列中，然而缓存的大小是有限的。当队列长度达到缓存上限时，路由器就不得不丢弃所有后续到达的包。当前的队列管理算法可以分为两大类：被动式队列管理( p a s s i v eq u e u em a n a g e m e n t ，p q m ) 和主动式队列管理( a c t i v eq u e u em a n a g e m e n t ，a q m ) 。2 3 1 被动式队列管理及缺陷管理路由器队列长度的传统技术是对每个队列设置一个最大值( 以包为单位) ，然后接受包进入队列直到队长达到最大值，接下来到达的包就要被拒绝进入队列直到队长下降。这种技术也就是所谓的“去尾 ( d r o p - t a i l ) 算法。虽然这个方法在当前i n t e r n e t上得到了广泛的使用，但其存在几个重大缺陷：独占资源( e x c l u s i v e r e s o u r c e s ) 问题：在某些情况下，“去尾 算法会让某个流或者少数几个流独占队列空间，阻止其他流的包进入队列。这种现象通常是由于同步( s y n c h r o n i z a t i o n ) 或其他定时作用的结果。满队列( f u l lq u e u e s ) 问题：由于“去尾”算法只有在队列满时才会发出拥塞信号，因此会使得队列在相当长时间内处于充满( 或几乎充满) 的状态。而队列管理最重要的目标之一就是降低稳定状态下队列的长度，因为端到端的延迟主要就是由于在队列中排队等待造成的。全局同步( g l o b a ls y n c h r o n i z a t i o n ) 问题：由于i n t e r n e t 上数据的突发本质，到达路9由器的包也往往是突发的。如果队列是满的或者几乎是满的，就会导致在短时间内连续大量地丢包。而t c p 流具有自适应特性，源端发现包丢失就急剧地减小发送窗口，包到达速率就迅速下降，于是网络拥塞得以解除，但源端得知网络不再拥塞后又开始增加发送速度，最终又造成网络拥塞，而且这种现象常常会周而复始地进行下去，从而在一段时间内网络处于链路利用率很低的状态，降低了整体吞吐量，这就是所谓地”t c p 全局同步”现象。除了“去尾 机制，另外两种在队列满时进行队列管理的机制是“随机丢弃 ( r a n d o md r o p ) 和“从前丢弃”( d r o pf i ：o n t ) 机制。当队列满时，前者从队列中随机找出一个包丢弃以让新来的包进入队列；后者从队列头部丢包，以便让新包进入队列。这两种方法虽然都解决了“独占”问题，但仍然没有解决“满队列”问题。由于这几种方法都是在队列满了被迫丢包，因此称为被动式队列管理。2 3 2 主动式队列管理及优点为了避免上述被动队列管理情况的出现，路由器应该在缓存被占满之前主动而有选择的丢弃部分到达包，这样端节点能够在缓存溢出之前及时调整窗口的大小，减低数据包发送速率，从而有效地降低路由器中缓存队列的平均大小和网络拥塞时路由器所丢失的数据包数目，降低端到端的传输延迟，这就是主动队列管理( a q m ) 的主要思想。a q m 是一种基于f i f o 调度策略的队列管理机制，使得路由器能够控制在什么时候丢多少包，以支持端到端的拥塞控制。a q m 有以下优势：1 ) 减少了路由器中丢弃的包的数量：i n t e r n e t 中数据包的突发本质是不可避免的，a q m 通过保持较小的平均队列长度( a v e r a g eq u e u es i z e ) ，能提供更大的容量吸收突发数据包，从而大大减少了丢包数。进一步说，如果没有a q m ，会有更多的包被丢弃。这主要是因为以下三个原因：由于使用共享的队列，会不可避免地产生全局同步，导致很低的平均带宽利用率，也即吞吐量很低。t c p 从突发包的丢弃中恢复要比从单个包丢弃中恢复更加复杂。如果一个数据包在到达目的端之前被丢弃，则其在传输过程中所消耗的资源都被浪费，降低了网络带宽的利用率。因此，不必要的包丢弃也就意味着带宽的浪费。2 ) 对交互式服务提供了更低的延迟：a q m 通过保持较小的平均队列长度，队列管理能够减少包的排队延迟( q u e u i n gd e l a y ) ，而排队延迟是造成端到端延迟( e n dt oe n dd e l a y ) 的主要原因。这对交互式应用比如w e b 浏览、t e l n e t 业务和视频会议等非常重要。3 ) 避免了“独占”现象：a q m 能够通过确保到来的包几乎总是有可用的队列空间，从而阻止”独占”行为的发生。也因为这个原因，a q m 能防止路由器对低带宽高突发的流的偏见。1 02 4 主流a q m 算法简述1 a q m 的典型代表是r e d ( r a n d o me a r l yd e t e c t i o n ，随机早期检测) 算法r e d 是由s a l l yf l o y d 和v a nj a c o b s o n 提出来的，它通过监控路由器输出端口队列的平均长度来探测拥塞，一旦发现拥塞逼近，通过以一定概率丢失或标记报文通知端系统网络的拥塞情况。r e d 使用平均队列长度度量网络的拥塞程度，然后将拥塞信息反馈给端系统，使他们在队列溢出导致丢包之前减小拥塞窗口，降低发送数据速度，从而缓解网络拥塞。研究表明r e d 比d r o pt a i l 具有更好的性能。i n t e r n e t 工程任务组( i n t e r n e te n g i n e e r i n gt a s kf o r c e ，i e t f ) 推荐r e d 作为下一代网络路由器默认的算法。r e d 算法包括两部分：计算平均队列长度和计算丢包率。计算平均队列长度，采用的是低通滤波器带权值的方法。a v g ( t i ) = ( 1 一w q ) 宰a v g ( t , 一1 ) + w 口q ( t i )( 2 1 )上述公式( 2 1 ) 中各参数的含义是：a v g ( t j ) ：i 时刻的平均队列长度a v g ( t , 一1 ) ：i - 1 时刻的平均队列长度g ( 办) ：i 时刻的瞬时队列长度：是在( 0 ，1 ) 之间的个权值然后，根据平均队列长度计算报文丢弃概率p ：p h2p =。：-max，maxt hm in _ t h0a v g m j n _ t hp：女m a nt h a v g m a xt h1 一c o u n t 幸一一一a v g m a x _ t h( 2 2 )( 2 3 )上述公式( 2 3 ) 中各参数的含义是：m a x _ t h ：队列的最大阀值m i n _ t h ：队列的最小阀值n l a x p ：分组最大丢弃概率c o u n t ：两次丢包间隔内收到包的数量，即队列位于最大和最小阀值之间时，没有被丢弃的分组个数。所以，r e d 算法可以简单描述为：f o r 每个到达的分组计算i 时刻平均队列长度a v gi fm i n _ _ t h a v g t a r g e ta n dm a x 。0 5 )增加m a x p ：m a x p4 - - - m a x p + 口；e l s ei f ( a v g t a r g e ta n dm a x 。0 0 1 )减小m a x p ：m a xp4 - m a xp i 队其中，a v g 是平均队列长度：i n t e r v a l 是设定的时间间隔，一般设置为0 5 秒；t a r g e t是a v g的目标值，一般设置为 m i n _ t h + 0 4 * ( m a x _ t h m i n _ t h ) ，m i n _ t h + 0 6 奉( m a x _ t h r a i n