（计算机应用技术专业论文）基于主动队列管理的拥塞控制算法的研究.pdf

摘要 主动队列管理( a c t i v eq u e u em a n a g e m e n t ，a q m ) 技术是i e t f ( i n t e r n e te n g i n e e r i n g t a s kf o r c e ) 推荐的基于路由器拥塞控制的关键技术。到目前为止已经出现了数十种主 动队列管理算法。作为a q m 算法的代表，随机早期检测( r a n d o me a r l yd e t e c t i o n ，r e d ) 算法被广泛地关注和研究。但是近期的大量研究表明r e d 算法存在公平性问题，它无法 有效处理不响应拥塞通知的连接，而这样的连接经常会挤占大量的网络带宽，导致各种 连接不公平地共享带宽；此外，它对网络的参数设置和运行状况比较敏感，会出现节点 队列大幅振荡、吞吐量降低、时延增加等网络不稳定现象。本文针对a q m 算法在公平性 方面存在的问题进行了改进。 本文首先介绍了拥塞控制算法的国内外研究现状，及现今的拥塞控制算法中存在的 问题。阐述了拥塞、拥塞崩溃及拥塞控制的定义，分析拥塞形成的原因。重点针对拥塞 控制算法中主动队列管理算法的公平性问题进行研究。具体分析以下五种算法：r e d 、 f r e d ( f l o wr a n d o me a r l yd e t e c t i o n ) 、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 l o w s ) 、c s f q ( c o r e s t a t e l e s sf a i rq u e u e ) 、 a f d ( a p p r o x i m a t ef a i rd r o p p i n g ) 。后四种算法实现公平性的方法各不相同，实现公平 的程度也不一样。由于r e d 算法本身不具有公平性，本文使用它作为没有公平性保证的 参照。本文从理论上对上述算法进行了分析，结合仿真实验，在不同的网络环境下对这 些算法的公平性能进行了比较。 本文重点研究主动队列管理算法中的c h o k e 算法，针对c h o k e 算法对非适应流的惩罚 力度不够，不能够很好地实现带宽的公平分配这一问题进行了深入研究。在此基础上本 文提出了一种改进的基于丢弃优先级的w - c h o k e 算法，并对w c h o k e 算法的实现进行了仿 真实验。通过l i n u x 下的网络仿真软件n s - 2 网络模拟器在同样拓扑结构的网络和链 路、带宽、信息源等环境下对现有的三种c h o k e 算法和w c h o k e 算法进行了仿真实验，来 检测新算法的实现并对比四种算法性能。结果给出了w c h o k e 算法有效地控制了非适应 流大量的挤占带宽，改进了c h o k e 算法的性能。 本文由六部分组成，第一章介绍了研究背景和意义；第二章介绍了拥塞控制的基本 概念、队列管理算法的分类及主动队列管理算法的公平性问题：第三章介绍了五种典型 的主动队列管理算法，并结合n s - 2 上实验比较上述算法的公平性能；第四章针对c h o k e 算法的缺陷作了分析并提出改进的w - c h o k e 算法，并对算法进行仿真实验。最后，第五 章对本文的研究内容作了总结，并提出了进一步的研究方向。 关键词：主动队列管理公平性带宽t c p 流u d p 流 a b s t r a c t a c t i v eq u e u em a n a g e m e n ti sak e yt e c h n i co fc o n g e s t i o nc o n t r o lb a s e do nr o u t e r s r e c o m m e n d e db yi n t e r a c te n g i n e e r i n gt a s kf o r c e u pt on o w , t h e r ea r ea l r e a d yaf e wn u m b e r o fa c t i v eq u e u em a n a g e m e n ta r i t h m e t i c s r a n d o me a r l yd e t e c t i o na r i t h m e t i ci st h e r e p r e s e n t a t i o no fa c t i v eq u e u em a n a g e m e n ta l g o r i t h m s ，i ti sw i d e l ya t t e n t e da n ds t u d i e db y p e o p l e b u tt h en e w l yl a r g en u m b e ro fr e s e a r c h e si n d i c a t e st h a tt h e r ei s s o m ef a i r n e s s p r o b l e mw i t ht h er a n d o me a r l yd e t e c t i o na l g o r i t h m i tc a n td e a lw i t ht h ef l o w sw h i c h d o n t a n s w e rt oc o n g e s t i o ni n f o r m se f f e c t i v e l y i na d d i t i o n ，i ti sc o m p a r a t i v e l ys e n s i t i v et ot h e p a r a m e t e r s a n dr u n n i n gs t a t u so ft h en e t w o r k t h e r ew i l lb e n o d e q u e u es u r g i n g ， t h r o u g h p u t r e d u c i n ga n dd e l a y i n c r e a s i n gi n t h en e t w o r k i nt h i sp a p e r , w em a k es o m e i m p r o v e m e n t so nt h ef a i r n e s sp r o b l e mi na c t i v eq u e u em a n a g e m e n ta l g o r i t h m s i nt h i sp a p e r , w ef i r s t l yg i v ei n t r o d u c et h er e s e a r c h i n gs t a t u sq u oo ft h ec o n g e s t i o n c o n t r o la l g o r i t h m s ，a n dt h ep r o b l e m e so ft 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 sn o w a d a y s w e e x p a t i a t et h ed e f i n i t i o no fc o n g e s t i o n ，c o n g e s t i o nc o l l a p s ea n dc o n g e s t i o nc o n t r o l ，w ea l s o a n a l y s et h ec a u s a t i o n so fc o n g e s t i o n w em a k ead e e pr e s e a r c hi na c t i v eq u e u em a n a g e m e n t a l g o r i t h m sw h i c hb e l o n g t oc o n g e s t i o nc o n t r o la l g o r i t h m s w ea n a l y s ef i v ek i n d so f a l g o r i t h m sc o n c r e t e l y t h e ya r er e d ，f r e d ，c h o k e ，c s f qa n da f d t h em e t h o da n dt h e d e g r e eo ft h el a t t e rf o u ra l g o r i t h m s t oi m p l e m e n tt h ef a i r n e s sa r ea l ld i f f e r e n t b e c a u s er e di s l a c ko ff a i r n e s s ，s ow eu s ei tf o rc o n t r a s t i n gw i t ho t h e rf o u ra l g o r i t h m s i nt h i sp a p e r ，w e a n a l y s et h ea l g o r i t h m sa b o v ei nt h e o r y ，t h e nw ec o m p a r et h ef a i r n e s sc a p a b i l i t yo ft h e s e a l g o r i t h m sc o m b i n i n gw i t ht h es i m u l a t ee x p e r i m e n t s i nd i f f e r e n tn e t w o r ke n v i r o n m e n t s t h ep a p e rg i v e sad e t a i l e d d e s c r i p t i o n o fc h o k ea l g o r i t h mo fa c t i v eq u e u e m a n a g e m e n ta l g o r i t h m s ，w em a k ead e e pr e s e a r c hi nt h ep r o b l e m t h a tc h o k e a l g o r i t h m c a n n o tp u n i s ht h eu n r e s p o n s i v ef l o w se n o u g ha n di to a nn o td i s t r i b u t eb a n d w i d t hf a i r l y b e c a u s e o ft h i sp r o b l e m ，w ep r o p o s ea ni m p r o v e da l g o r i t h mw - c h o k eb a s e do nd r o p _ p r i o r i t y t h e n w es i m u l a t et h ew - c h o k ea l g o r i t h m u s i n gt h en s 一2u n d e rl i n u xo p e r a t i o ns y s t e m ，w e s i m u l a t et h ew - c h o k ea l g o r i t h mw i t ht h et h r e ek i n d so fp r i m a r yc h o k ea l g o r i t h m su n d e r n e t w o r ks i m u l a t o rb a s e do nt h es a m en e t w o r kt o p o l o g y , l i n k ，b a n d w i d t h ，a n ds o u r c et o c o m p a r et h e s ef o u ra l g o r i t h m si nt h ep e r f o r m a n c e a n dt h es i m u l a t i o nr e s u l t ss h o wt h a tt h e w - c h o k ea l g o r i t h mp u n i s ht h eu n r e s p o n s i v ef l o w se f f i c i e n t l ya n di m p r o v et h ec h o k e p e r f o r m a n c e t h i sa r t i c l ei sm a d eu po f6p a r t s s e c t i o n1i n t r o d u c e st h eb a c k g r o u n da n ds i g n i f i c a n c e o ft h ei n v e s t i g a t i o n s e c t i o n2i n t r o d u c e ss o m eb a s ec o n c e p t i o n so fc o n g e s t i o nc o n t r o l ，t h e s o r t so fq u e u em a n a g e m e n t a l g o r i t h m s a n dt h ef a r i n e s s p r o b l e m o fa c t i v eq u e u e m a n a g e m e n ta l g o r i t h m s i ns e c t i o n3 ，w ei n t r o d u c ef v et y p i c a la c t i v eq u e u em a n a g e m e n t a l g o r i t h m s ，a n dw ec o m p a r et h ef a i r n e s sc a p a b i l i t yo ft h e s ea l g o r i t h m sc o m b i n i n gw i t ht h e s i m u l a t ee x p e r i m e n t si nn s - 2 s e c t i o n4a n a l y s e st h es h o r t c o m i n go ft h ec h o k ea l g o r i t h m a n d p r o p o s e sa ni m p r o v e da l g o r i t h mw - c h o k e ，t h e ng i v e s t h es i m u l a t i o no ft h ew - c h o k e a l g o r i t h m i nt h ef i n a lp a r t ，s e c t i o n5 ，w eg i v eas u m m a r i z a t i o no ft h i sp a p e ra n dp r e s e n tt h e n e x tw o r kw ew i l ld o k e yw o r d s ：a c t i v eq u e u em a n a g e m e n t ，f a i r n e s s ，b a n d w i d t h ，t c pf l o w s ，u d pr o w s 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取 得的研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得天津理工大学或 其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研 究所做的任何贡献均己在论文中作了明确的说明并表示了谢意。 学位论文作者签名：羡孑贺签字日期：伽8 年月，罗日 学位论文版权使用授权书 本学位论文作者完全了解 墨盗堡兰盘堂有关保留、使用学位论文 的规定。特授权墨盗墨兰盘堂一可以将学位论文的全部或部分内容编入 有关数据库进行检索，并采用影印、缩印或扫描等复制手段保存、汇编， 以供查阅和借阅。同意学校向国家有关部门或机构送交论文的复本和电子 文件。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：裘弓首 签字日期：伽8 年，月，7 日 拍弛：加弼 签字日期：嘞，月z , l o 日 第一章绪论 1 1 研究背景和意义 第一章绪论 网络是现代化信息时代人们进行数据和信息传输不可缺少的重要工具。通过网络人 们可以通信、娱乐、接受教育、购物等，可以说人们的日常工作和生活越来越依赖于网 络带来的各种信息。 近年来，随着i n t e r n e t 的快速发展，各个领域的网络应用大量增加。这些应用的出 现使得网络的数据流类型发生了很大变化，除了传统的e m a i l 、f t p 、t e l n e t 流量外， 出现了大量的多媒体数据流( 实时或非实时的视频、音频等) 。同时，网络的流量具有 突发性、自相似性，这些不同的数据流在网络的路由节点处交汇，因此给网络的路由节 点造成了很大的负担。而网络硬件资源的增长速度无法满足如此快速增长的网络传输需 求，于是网络拥塞就产生了。 拥塞的产生会对整个网络的性能造成极大的损害。一旦发生拥塞，网络的吞吐量无 法维持在网络固有的传输能力水平，它会急剧下降；情况严重时会产生拥塞崩溃，致使 网络完全瘫痪i l j 。i n t e r n e t 采用“尽力而为 ( b e s t - e f f o r t ) 的服务机制，当有拥塞发 生时，它不能限制用户数量，而只能依靠降低服务质量来继续为用户服务。基于i n t e r n e t 这个特点，我们必须对拥塞加以控制，否则常会导致恶性循环。这时如果路由器没有空 余的缓存空问，它就必须丢掉新到的分组，当数据分组丢弃时，发送端可能会因为超时 而重传分组。由于发送端在未收到确认之前不能丢弃分组，相应的缓存不能释放，使缓 存进一步消耗，导致捌塞加剧1 2 3 。 那么如何控制拥塞? 很自然地，解决长期拥塞的最好方法是为瓶颈链路增加带宽， 直至拥塞不再出现为止。但无论是从理论上还是从实践上，这都不能实际解决问题1 4 1 。 因为带宽是有限的，并且它的成本不低。有限的带宽供应量和不断增长的带宽需求之间 存在着不可解决的矛盾。 在传统的拥塞控制机制中，对于拥塞都是采用一种称之为“拥塞恢复 的机制，在 拥塞发生后，传输控制功能对于流的发送端产生抑制作用，促使数据流的发送端降低其 发送速率，使得拥塞的程度得以减轻以至于消失【4 1 。但是，单凭“拥塞恢复”策略也不 能解决根本问题，因为它必须在拥塞产生以后才起作用。如果单用“拥塞恢复 策略， 网络性能会不太稳定。 因此现在研究的更多的是一种称为“主动队列管理”a q m 机制的网络拥塞控制算法， 它属于“拥塞避免”策略范畴。与“拥塞恢复”策略相区别的是，主动队列管理机制通 过对网络状态进行跟踪，在拥塞发生之前对流的分组进行选择性的丢弃或者标记，促使 流的发送端作出响应，降低其发送速率，减少拥塞的产生，从而提高网络的服务质量。 网络拥塞已经成为制约网络发展和应用的一个瓶颈，如何更好的预防和控制拥塞一直是 第一章绪论 近年来网络研究的热点问题。 1 2 拥塞控制算法的研究现状 目前国内外的拥塞控制算法研究主要分为： 一、从控制论的角度出发，拥塞控制算法大致可分成开环控制和闭环控制两大类。 1 开环控制算法是通过良好的网络系统设计来避免拥塞问题的发生，在网络运行 过程中，何时接受新分组，何时丢弃分组以及丢弃哪些分组都是事先规划好的， 并不考虑当前的网络流量状况； 2 闭环控制算法是通过反馈机制来调整当前网络流量，使网络流量与网络可用资 源相协调，从而使网络拥塞问题得到解决。 当流量特征可以准确规定、性能要求可以事先获得时，适于使用开环控制；当流量 特征不能准确描述或者当系统不提供资源预留时，适于使用闭环控制。i n t e r n e t 中主要 采用闭环控制方式1 5 j 。闭环的拥塞控制分为以下三个阶段：检测网络中拥塞的发生；将 拥塞信息报告到拥塞控制点；拥塞控制点根据拥塞信息进行调整以消除拥塞。闭环的拥 塞控制可以动态地适应网络的变化，但它的一个缺陷是算法性能受到反馈延迟的严重影 响。当拥塞发生点和控制点之间的延迟很大时，算法性能会严重下降。 二、根据拥塞控制的实施位置，也可将拥塞控制算法分为两大类：源算法( s o u r c e a l g o r i t h m ) 和链路算法( l i n ka l g o r it h m ) i 酬。 1 源算法是指在端系统( 主机和网络边缘设备) 上运行的算法，作用是主机在收 到路由器或交换机的拥塞信息后，根据反馈信息调整发送速率。目前国内外对 源算法的研究，主要集中在对t c p ( t r a n s p o r tc o n t r o lp r o t o c o l ，传输控制协 议) 协议的研究上，因为t c p 协议中的拥塞控制算法是在源算法中使用最广泛 的。目前t c p 中采用的拥塞控制算法有：慢启动( s l o ws t a r t ) 、拥塞避免、快 速重传( f a s tr e t r a n s m i t ) 、快速恢复( f a s tr e c o v e r y ) 、选择性应答( s a c k ) 等，大大提高了网络传输的性能。t c p 中使用的拥塞控制算法已经成为保证 i n t e r n e t 稳定性的重要因素。t c p 算法已经过了t a h o e 、r e n o 、n e wr e n o 、s a c k 和v e g a s 等多个版本的增强与改进，目前在网络仿真工具n s 2 中提供的发送代理 有：t c p ，t c p r e n o ，t c p n e w r e n o ，t c p v e g a s ，t c p s a c k l ，t c p f a c k ，t c p f u l l t c p 等，接收代理有t c p s i n k ，t c p s i n k d e l a c k ，t c p s i n k s a c k l ，t c p s i n k s a c k l d e l a c k 等。 2 链路算法是指在网络中间设备( 如路由器或交换机) 上实施的算法，作用是检 测网络拥塞的发生，采取一定的措施缓减拥塞状况，产生拥塞反馈信息，以使 发送端采取适当的措施避免拥塞恶化。目前国内外对链路算法的研究主要集中 在主动队列管理算法和显式拥塞通知( e x p l i c i tc o n g e s t i o nn o t i f i c a t i o n ， e c n ) 两个方面。到目前为止已经出现了数十种主动队列管理算法。随机早期检 测r e d 算法是最早出现的a q m 算法，它作为a q m 算法的代表受到广泛地关注和 第一章绪论 研究。其它几种较主要的主动队列管理方案包括：f r e d ，s r e d ( s t a b i l i z e dr e d ) ， b l u e ，p i ( p r o p o r t i o n a li n t e g r a l ) 和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 ) 等。国内的a q m 算法研究相对少一些，都是对已有算法的改进，并且大多数的 改进是在r e d 的基础上完成的。 三、从实施控制的类型上，拥塞控制可以分为基于窗口和基于速率两种类型 7 1 。t c p 采用的是典型的基于窗口的控制方式，而多媒体数据流的传输控制则用基于速率的控制 方式。 四、从推断网络状态的反馈信息的类型上，可以分为显式拥塞控制和隐式拥塞控制。 在显示控制方式中，网络使用显式信号，向执行控制的端点通告其状态( 可用带宽、缓 存容量等) ；在隐式控制方式中，控制端使用流量标记或者通过超时、重复a c k 等隐式 信号来推断网络状态1 5 j 。 1 3 拥塞控制算法目前存在的问题 目前国内外的拥塞控制算法所存在的问题大致分为以下几个方面： 一、开环控制算法有良好的网络系统设计，但它在实施过程中并不考虑当前的网络 流量状况，因此灵活性不好。并且在设计时要确定精确的业务特征几乎是不可能的，因 此为保证服务质量、减少拥塞，往往需要预留多余的网络资源，很容易造成网络资源利 用率下降。 二、闭环算法可以动态地适应网络的变化，但是算法性能受反馈延迟的影响。当反 馈延迟很大时，算法的性能会严重下降。 三、算法中参数的设置问题。一些算法需要设置参数，其中有的算法对参数设置很 敏感，如果我们改变了对参数的设置，将对算法的性能带来很大影响。 四、算法的公平性问题，这是目前拥塞控制算法研究中最突出、最重要的问题之一。 公平性是指在网络发生拥塞时各连接能公平地共享网络资源。产生公平性问题的根本原 因在于拥塞的发生必然导致数据包( 分组) 丢失，而数据包丢失会导致各数据流之间为 争抢有限的网络资源发生竞争，竞争能力强的数据流将得到更多的网络资源，从而损害 了其它流的利益。公平性问题表现主要在两方面：一是拥塞响应的t c p 流和非拥塞响应 的u d p 流之间资源享用的不公平；二是t c p 流之间资源享用的不公平性。前者是我们研 究的重点，主要是由于发生拥塞时，不同的数据流对拥塞指示做出的不同反应造成的。 由于t c p 流具有拥塞控制机制，因此发送端在收到拥塞指示后会主动降低数据发送速率。 结果在网络拥塞时，拥塞响应的t c p 流得到的资源越来越少，非拥塞响应的u d p 流得到 的资源越来越多，从而导致了网络资源分配的不公平。对于后者，研究表明，不同的窗 口大小、r t t 值及数据包的尺寸都会影响t c p 流对带宽的占用。窗口较大，或者r t t 较 小，或者数据包较大的流往往能占用更多的带刻8 。 第一章绪论 1 4 本文的主要工作 目前i n t e r n e t 网络中多媒体数据流明显呈逐年增长的趋势。并且现有的大部分多 媒体数据流大多都是u d p 流，它们属于非适应i j ；c i 引，不支持传统的端到端的拥塞控制， 而又要保证传输的连续性，因而在常规的端到端t c p 拥塞控制下可能出现在一定时期内 这些数据流始终占有带宽，而响应拥塞控制的t c p 数据流( t c p 友好流) 则被抑制而始 终无法成功的发送数据。因此，在路由节点处会出现网络拥塞现象，严重时可导致全局 同步和拥塞崩溃。这就要求必须采取有效地控制机制来确保这些服务与t c p 流共存， 同时要与传统的t c p 机制相融合。 本文的研究工作是针对目前网络服务质量( q u a l i t yo fs e r v i c e ，q o s ) 中存在的公 平性问题展开的。具体是针对现有拥塞控制算法中的主动队列管理中存在的带宽分配的 公平性问题而展开的。主要目的是提出一种改进的、性能更优化的主动队列管理算法， 来抑制非适应流( 如u d p 数据流) 长时间占用带宽，从而使响应拥塞控制的t c p 流可以 与u d p 流公平地共同使用带宽。 本文首先从理论上分析具有代表性的五种a q m 算法：r e d 、f r e d 、c h o k e 、c s f q 、a f d 。 并通过使用l i n u x 下的网络仿真工具n s 第2 版( n e t w o r ks i m u l a t o r ，v e r s i o n2 ) 1 1 0 j 来进 行大量的仿真实验，在多种不同的网络环境下对这些算法的公平性能进行比较。我们没 有找至i j a f d 算法的源代码，只做了f r e d 、c h o k e 、c s f q 算法的公平性实验。但是由于a f d 算法是近期提出的一种较新的实现带宽公平分配的算法，本文也对a f d 算法的理论部分 作了详细介绍。 本文重点针对c h o k e 算法对非适应流的惩罚力度不够，不能够很好地实现带宽的公平 分配这一问题进行了深入研究。在此基础上本文提出了一种改进的基于丢弃优先级的 w - c h o k e ( w e i g h tc h o k e ) 算法，并对w c h o k e 算法的实现进行了仿真实验，检验算法性 能的优劣。 1 5 本文的组织结构 本文分为六章，重点是第三章、第四章。具体结构如下： 第一章介绍本文的研究背景和意义，阐述了拥塞控制算法的国内外研究现状，接下来 介绍了现今的拥塞控制算法中存在的问题。并指出了本文的主要研究内容及论文安排。 第二章介绍拥塞、拥塞崩溃及拥塞控制的定义，分析拥塞形成的原因。接下来介绍 了拥塞控制算法的评价标准。通过介绍拥塞控制算法的分类，引出了被动式队列管理算 法和主动队列管理算法。分析两种队列管理算法的定义、实现思想及优缺点，重点指出 了主动队列管理算法的公平性问题。 第三章介绍比较典型的五种主动队列管理算法。采用l i n u x 下的网络仿真软件n s 一2 网络模拟器在网络的拓扑结构和链路、带宽、信息源等相同的环境下对上述算法进行仿 真实验，进行公平性能比较。 第一章绪论 第四章重点研究c h o k e 算法，介绍c h o k e 算法的概念、目前所存在的版本，及c h o k e 算法的优缺点。针对c h o k e 算法的不足提出了改进的基于丢弃优先级的w - c h o k e 算法。 然后对算法进行理论分析，给出算法流程图及伪代码。最后对算法进行仿真实验。采用 n s 一2 网络模拟器在同样拓扑结构的网络环境中对现有的三种版本的c h o k e 算法和 w - c h o k e 算法进行仿真实验，来检查新算法的实现，并对比这四种算法的性能。 第五章总结了本文所做的工作并对下一步的研究工作进行了展望。 最后在附录中介绍了n s 2 下w - c h o k e 算法模拟实验的部分脚本代码。 第二章i n t e r n e t 拥塞控制基础及主动队列管理算法的公平性问题 第二章i n t e r n e t 拥塞控制基础及主动队列管理算法的公平性问题 2 1 基本概念 2 1 1 拥塞和拥塞崩溃 当网络中存在过多的报文时，网络的性能会下降，这种现象称为拥塞。拥塞是一种 持续过载的网络状态，此时用户对网络资源( 包括链路带宽、存储空间和处理器能力等) 的需求超过了网络可提供的容量【1 1 j 。就i n t e r n e t 的体系结构而言，拥塞的发生是其固有 的属性。因为在事先没有任何协商和请求许可机制的资源共享网络中，几个i p 分组同时 到达路由器，并期望经过同一个输出端口转发的可能性是存在的，显然，不是所有的分 组都可以同时接受处理，必须有一个服务顺序，中间节点上的缓存为等候服务所有的分 组提供一定保护。然而，如果此状况具有一定的持续性，当缓存空间被耗尽时，路由器 只有丢弃分组。表面上，增大缓存可以防止由于拥塞引起的分组丢失，但随着缓存的增 加，端到端的时延也相应增大，因为分组的持续时间是有限的，超时的分组同样需要重 传。因此，过大的缓存空间反而可能会妨碍拥塞的恢复，因为有些分组自白浪费了网络 的可用带宽。 拥塞导致的直接结果是分组丢失率提高，端到端时延加大，甚至有可能使整个系统 发生崩溃。严格来说，拥塞崩溃现象是网络的占用率很高但分组不能到达信宿。当网络 处于拥塞崩溃状态时，微小的负载增量都将使网络的有效吞吐量急剧下降。目前主要的 拥塞崩溃可以分为两种1 1 2 j 1 传统的拥塞崩溃1 1 3 】：拥塞崩溃的产生大多是由于t c p 连接中不必要的重传一些分 组所诱发的，而这些分组或是正在传输过程中，或是已经到达接收方。通常将不必要的 分组重传所造成的拥塞崩溃称为传统的拥塞崩溃。这种崩溃可以通过j a c o b s o n 提出的拥 塞避免机制来解决。 2 未投递分组造成的拥塞崩溃1 1 4 j ：这是由于网络带宽浪费在传递那些在到达最终 信宿前就被丢弃的分组所造成的。这种崩溃可能是今天的i n t e r n e t 所未能解决的最危险 的拥塞崩溃。未投递的分组所造成的拥塞崩溃危害是相当大的，将导致链路的有效利用 率急剧下降。消除未投递分组造成的拥塞崩溃只有两种方法。第一种是在网络端节点使 用有效的端到端的拥塞控制机制。第二种方法是网络保证将已经被拥塞链路接收的分组 送至信宿，即网络的端到端的带宽保证。两种方法可以相互结合。 2 1 - 2 拥塞形成的原因 拥塞是网络中的一种中间状态。当用户所期望占有的网络资源与对应的网络资源接 第二章i n t e r n e t 拥塞控制基础及主动队列管理算法的公平性问题 近，甚至超过网络所能提供的资源时，则出现网络拥塞，导致拥塞的直接原副1 5 】有： 1 路由器缓存不足导致拥塞。当多个分组突然从不同输入线路涌入路由器时，这些 分组就要在路由器进行排队。如果路由器没有足够的缓存存储分组，就会使一些分组被 丢弃。虽然增加缓存对这一问题会有所帮助，但有研究表明：过大的缓存反而会导致拥 塞的恶化。因为当分组最终排到队列头部时，发送端早已超时重发。实际上，太多的缓 存远比较少的缓存危害更大； 2 链路带宽不足导致拥塞。高速链路和低速链路的不匹配，或者多条输入带宽总和 大于输出带宽容量，都会使路由器中数据到达率远远大于离去率，从而导致长队列缓冲 区用完，进而导致拥塞； 3 处理器速度慢导致拥塞。如果路由器的c p u 在执行排队缓存，更新路由表等功能 时处理速度跟不上高速链路，也会产生拥塞。同样低速链路对高速c p u 也会产生拥塞。 拥塞是由网络资源短缺引起，但仅依靠增加资源却无法从根本上解决拥塞问题，它 只能转移网络瓶颈网络资源分布的不均衡及网络流量分布的不均衡，使拥塞总是发生在 网络资源相对短缺的地方。因此，怎样有效和公平的分配好现有资源对拥塞控制就显得 极其重要。实质上，拥塞控制和网络资源分配是对立统一的：一方面，如果网络在资源 分配方面采取了积极的措施，比如严格的资源预定，就可以避免拥塞，从而也就没有必 要进行拥塞控制。但由于资源分布在整个网络，要想准确的分配资源十分困难；另一方 面，可以对资源分配不加以限制，发送方想发多少就发多少，然后当拥塞发生时再恢复。 后一种方式实现容易，但对网络具有一定的破坏性。比较可行的办法是采取一些资源分 配措施，又允许适当的拥塞情况发生。结合资源分配和拥塞控制，进行拥塞检测和拥塞 恢复两者良好的结合对网络的运行起着重要的作用。 2 1 3 拥塞控制 拥塞控制就是网络节点采取措施来避免拥塞的发生或者对已经发生的拥塞做出的 反应。拥塞控制包括拥塞避免和拥塞恢复两种不同的机制。拥塞恢复机制用于将网络从 拥塞状态中恢复出来。而拥塞避免为预防机制，它的目标是避免网络拥塞的发生，使网 络运行在高吞吐量、低延迟的状态下【l 酬。 图2 - i 刻画了负载与吞吐量之间的关系。当负载较小时，吞吐量与负载之间呈线性 关系，随着负载的增加，吞吐量线性增加，此区间为拥塞避免区间；负载到达膝点之后， 吞吐量随着负载的增加量逐渐变小，通常将膝点和崖点之问的区间称为拥塞恢复区间。 负载超过崖点之后，吞吐量急剧下降，此区间称为拥塞崩溃区间。 第二章i n t e r n e t 拥塞控制基础及主动队列管理算法的公平性问题 存叶鲢 图2 1 负载与吞吐量之间的的关系曲线图 负载 拥塞控制的目标就是使网络工作在膝点附近一一这样既可以充分利用网络，使网络 的吞吐量发挥到极致，又没有形成拥塞。 2 1 4 拥塞控制算法的评价标准 在研究拥塞控制算法的过程中，需要一定的评价方法和评价标准来分析一个算法的 可行性、可靠性以及效率等。其中端系统的吞吐率、连接的丢失率和延迟等指标，都是 拥塞控制算法的重要的评价指标，而且这些正是端系统所关注的。但是拥塞控制算法主 要是针对整个网络系统的，因此在评价算法时也应该从整个系统的角度出发进行考虑。 1 吞吐量( t h o u g h o u t ) ：指单位时间内有多少数据进入网络( 网络中发送分组的速 率) ，可用平均速率或峰值速率表示。网络吞吐量就是它的有效带宽。通过研究网络的 吞吐量，特别是每个数据流的吞吐量，我们可以看出资源的分配是否公平。网络资源分 配的不公平反过来会加重拥塞情况，甚至可能导致拥塞崩溃。 2 端到端的时延( d e l a y ) ：指发送端与接收端之间发送和接收数据包的时间间隔， 它主要是由分组在路由器中的等待时间和服务时间引入的。 3 时延抖动( j i t t e r ) ：指端到端传输时延的变化，即相邻两个分组到达接收端的 时间间隔相对与发送端发送这两个分组的时间间隔之间的差值。 4 丢包率( l o s s ) ：指在分组传输过程中，丢失的分组数与源端发送的分组数之比。 分组的丢失主要是由出错或者网络拥塞引起的。在q o s 解决方案设计时应充分考虑到 不同业务对丢包率的要求1 1 7 j 。 2 2 队列管理机制 路由器是基于分组交换的设备，每个端口采用带宽统计复用，所以路由器必须在端 口上维护一个或多个队列，否则路由器无法处理多个数据包同时向同一端口转发以及端 第二章i n t e r n e t 拥塞控制基础及主动队列管理算法的公平性问题 口q o s 等问题。对队列进行管理直接影响路由器性能、拥塞管理能力以及o o s 能力。路 由器有两类控制和管理队列的算法：队列管理算法和队列调度算法。前者主要是在必要 时通过丢弃分组来管理队列长度。后者决定下一个要发送哪个分组，主要用来管理各流 之间带宽的分配。 由于i n t e r n e t 数据本质上是突发的，因此允许传输突发的数据包非常必要，而路由 器中队列的重要作用就是吸收( a b s o r b ) 突发的数据包。较大的队列能够吸收更多的突 发数据，提高吞吐量，但t c p 机制往往会保持较高的队列占用，从而增加了数据包的排 队延迟。因此需路由器对队列进行管理，维持较小的队列长度。因为维持较小的队列长 度除了降低排队延迟，提高吞吐量外，还能保持较大的队列空间来吸收突发数据包。拥 塞控制机制就是要维持网络处于低延迟高吞吐量的状态。 根据拥塞控制的实施位置，也可将拥塞控制算法分为两大类：源算法( s o u r c e a l g o r i t h m ) 和链路算法( l i n ka l g o r i t h m ) 。而链路算法可以分为三大类：队列调度算法、 队列管理算法、队列缓存管理算法。其中队列管理算法又可以分为两大类：被动式队列 管理( p a s s i v eq u e u em a n a g e m e n t ，p q m ) 和主动式队列管理a q m 。详细分类如图2 - 2 。 本文的研究工作是围绕队列管理算法中的主动队列管理算法展开的。 图2 - 2 拥塞控制算法分类 第二章i n t e r n e t 拥塞控制基础及主动队列管理算法的公平性问题 2 2 1 被动式队列管理及其缺陷 被动式队列管理p q m 的传统技术是对每个队列设置一个最大值( 以分组为单位) ， 然后接受分组进入队列直到队长达到最大值，接下来到达的分组就要被拒绝进入队列直 到队长下降。这种技术也就是所谓的“去尾 ( d r o p - t a i l ) 算法。虽然这个方法在当 前i n t e r n e t 上得到了广泛的使用，但其存在几个重大缺陷1 9 j ： 死锁( 1 0 c k o u t ) 问题：在某些情况下，“去尾 算法会让某个数据流或者少数几 个数据流独占队列空间，阻止其他流的分组进入队列。这种“死锁 现象通常是由于同 步( 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 上数据的突发本质，到 达路由器的分组也往往是突发的。如果队列是满的或者几乎是满的，就会导致在短时间 内连续大量地丢弃分组。而t c p 流具有自适应特性，源端( 发送端) 发现分组丢失就急 剧地减小发送窗口，分组到达速率就迅速下降，于是网络拥塞得以解除，但源端得知网 络不再拥塞后又开始增加发送速度，最终又造成网络拥塞，而且这种现象常常会周而复 始地进行下去，从而在一段时间内网络处于链路利用率很低的用状态，降低了整体吞吐 量，这就是所谓地“t c p 全局同步”现象。 除了“去尾机制，p q m 还有另外两种在队列满时进行队列管理的机制，它们是“随 机丢弃 ( r a n d o m d r o p ) 和“从前丢弃 ( d r o p - f r o n t ) 机制。当队列满时，前者从 队列中随机找出一个分组丢弃以让新来的分组进入队列；后者从队列头部丢弃分组，以 便让新分组进入队列。这两种方法虽然都解决了“死锁”问题，但仍然没有解决“满队 列”问题。由于这几种方法都是在队列满了被迫丢弃分组，因此称为被动式队列管理。 2 2 2 主动式队列管理及其优点 在当前的i n t e r n e t 上，丢弃分组是对端节点进行拥塞通知的重要机制，解决路由器 “满队列”的方法便是在队列充满之前丢弃分组，这样端节点便能在队列溢出前对拥塞 作出反应。这种方法便称为主动式队列管理a q m 。 a q m 是一族基于f i f o 调度策略的队列管理机制，使得路由器能够控制在什么时候丢 多少分组，以支持端到端的拥塞控制。a q m 有以下优势1 9 j ： 1 减少了路由器中丢弃的分组的数量：i n t e r n e t 中数据包的突发本质是不可避免 的，a q m 通过保持较小的平均队