（模式识别与智能系统专业论文）基于变负载网络的拥塞控制新方法研究.pdf

摘要 摘要 2 0 世纪9 0 年代以来，随着i n t e r n e t 的迅速发展，网络拥塞发展成了十分重要 的问题。拥塞会造成传输时延、吞吐量等服务质量( q u a l i t yo fs e r v i c e ，q o s ) 指 标的下降，严重影响带宽、缓存等网络资源的利用率。随着新型网络应用的不断 涌现，网络规模、用户数量、业务量的爆炸式增长，网络拥塞也愈发严重、复杂， 成为了i n t e r n e t 发展的瓶颈。 对拥塞进行预防和控制的拥塞控制机制对保证i n t e r n e t 的稳定运行具有十分 重要的意义；同时，作为其他q o s 机制正常工作的必要前提，拥塞控制对有效提 高网络性能也意义重大。端到端t c p 拥塞机制已经无法满足复杂网络中日趋丰富 的应用需求，必须在网络中间节点引入主动队列管理( 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 能够在尽力而为服务的网络中， 降低数据包的排队时延、时延抖动和丢失率，保证网络较高的吞吐量。 随机早期检测( r a n d o me a r l yd e t e c t i o n ，r e d ) 算法作为最为著名的a q m 机制，通过不断调整丢包率，对控制进行调整，在保证较高吞吐量的基础上有效地 控制了队列长度，但其稳定性等系统性能却受限于r e d 参数配置的难题。为了更 好地配置r e d 的参数，本文提出了三种a q m 新策略： 1 i n t e r v a lr a n d o me a r l yd e t e c t i o n ( i r e d ) 。i r e d 中，平均队长的阈值从 固定不变的单值，变为了一个阈值区间。 2 a d a p t i v et h r e s h o l dr a n d o me a r l yd e t e c t i o n ( a t r e d ) 。a t r e d 中，阈值 能够随着缓存队列平均占用率的变化动态调整。 3 c o m p e n s a t o r yf u z z y n e u t r a ln e t w o r kr a n d o m e a r l y d e t e c t i o n ( c f n n r e d ) 。算法使用补偿模糊神经网络来得到r e d 的丢弃率。 论文还在采用i r e d 和a t r e d 策略的t c p a q m 动态模型中对进行了系统稳 定性的相关分析。最后，通过仿真验证了新算法的可行性和优越性。 关键词：拥塞控制；a q m ；r e d ； i r e d ；a t r e d ；c f n n r e d 广东工业大学工学硕十学位论文 a b s t r a c t w i t ht h er a p i dd e v e l o p m e n to fi n t e r n e ts i n c e19 9 0 s ，n e t w o r kc o n g e s t i o nh a s b e c o m ea ni m p o r t a n ti s s u e c o n g e s t i o no f t e nr e s u l t si nd e c l i n eo fq u a l i t yo fs e r v i c e ( q o s ) i nt e r m so ft r a n s m i s s i o nd e l a ya n dt h r o u g h p u ta n ds oo n ，w h i c ha f f e c t st h e u t i l i z a t i o no fn e t w o r kr e s o u r c el i k eb a n d w i d t ha n db u f f e r sa n ds oa n w h a t sw o r s e ， n o w a d a y s ，t h es c a l e ，u s e r sa n dt r a f f i c so fi n t e r n e th a v ee x p e r i e n c e da ne x p l o s i v e g r o w t h ，c o n s e q u e n t l yn e t w o r kc o n g e s t i o nh a sb e c o m et h eb o t t l e n e c ki ni n t e r n e t o b v i o u s l yc o n g e s t i o nc o n t r o lm e c h a n i s mi si m p o r t a n ti nk e e p i n gt h es t a b i l i t yo f i n t e r n e t ；m e a n w h i l ec o n g e s t i o nc o n t r o li si n d i s p e n s a b l et oo t h e rq o sm e c h a n i s m sa n d i m p o r t a n tt oe f f e c t i v e l yi m p r o v et h ep e r f o r m a n c eo fn e t w o r k e n d - t o - e n dc o n g e s t i o n c o n t r o lo ft c pa l r e a d yc o u l d n ts a t i s f yv a r i o u sd e m a n d so fa p p l i c a t i o no nt h e c o m p l e xn e t w o r k s oi t sn e c e s s a r yf o rr o u t e r st op e r f o r ma c t i v eq u e u em a n a g e m e n t ( a q m ) ，w h i c hc o u l dd e t e c ta n dp r e v e n tc o n g e s t i o ne f f e c t i v e l y a q ma st h er o u t e r b a s e dm e c h a n i s mc o u l dp r o v i d el o w e rd e l a y ，s m a l l e rj i t t e r sa n dh i g h e rt h r o u g h o u t ， a n dt om i n i m i z ep a c k e tl o s sr a t e s ，e t c a m o n ga l la q m s ，r a n d o me a r l yd e t e c t i o n ( r e d ) i st h ee a r l i e s ta n db e s t w e l l - k n o w n ，w h i c hp r o b a b i l i s t i c a l l yd r o p sp a c k e t st oa d ju s tt h es t r e n g t ho fc o n t r o l a n dk e e p sb u f f e r sc h a n g es m o o t h l y r e dc o u l dm a i n t a i nas h o r t e ra v e r a g eq u e u e l e n g t hw i t hh i g h e rt h r o u g h o u t ，b u ti t sp a r a m e t e r sa r eh a r dt oc o n f i g u r a t e i no r d e rt o p r o p e r l yc o n f i g u r a t er e d ，t h r e en o v e lr e d v a r i a n t sa r ep r o p o s e d ： 1 i n t e r v a lr a n d o me a r l yd e t e c t i o n ( i r e d ) i r e d st w ot h r e s h o l d sa r en o tt w o s t a b l ep o i n t sb u tt w oi n t e r v a l s 2 a d a p t i v et h r e s h o l dr a n d o me a r l yd e t e c t i o n ( a t r e d ) a t r e d st w o t h r e s h o l d sa r ed y n a m i c a l l ya d j u s t e da st h eb u f f e ro c c u p a n c yc h a n g e s 3 c o m p e n s a t o r yf u z z yn e u t r a ln e t w o r kr a n d o me a r l yd e t e c t i o n ( c f n n r e d ) c f n n r e du s e sc o m p e n s a t o r yf u z z yn e u t r a ln e t w o r kt og e td r o pp r o p a b i l i t y w h a t sm o r e ，c l a s s i cc o n t r o lt h e o r yi si n t r o d u c e dt oa n a l y z et h es t a b i l i t yo fn e t w o r k i i a b s t r a c t b ym e a n so ft h et c p a q mm o d e lp e r f o r m i n gi r e da n da t r e d i nt h ee n dw eu s e s i m u l a t i o np l a t f o r mt oa n a l y z et h en e w l yp r o p o s e da 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 q m ；r e d ；i r e d ；a t r e d ；c f n n r e d i i i 广东t 业大学工学硕十学位论文 独创性声明 秉承学校严谨的学风与优良的科学道德，本人声明所呈交的论文是我个人在 导师的指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以 标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，不包 含本人或其他用途使用过的成果。与我一同工作的同志对本研究所做的任何贡献 均已在论文中作了明确的说明，并表示了谢意。 本学位论文成果是本人在广东工业大学读书期间在导师的指导下取得的，论 文成果归广东工业大学所有。 申请学位论文与资料若有不实之处，本人承担一切相关责任，特此声明。 指导教师签字： 0 yi , l 论文作者擗倪岛 如文年6 窍弓 第一章绪论 1 1 研究背景 第一章绪论 近年来，随着用户数量的急速增加和新型应用的不断涌现，i n t e r n e t 的业务量 急剧增长，除了传统的w w w 、f t p 、t e l n e t 等业务外，还出现了大量的实时多媒 体业务，越来越多的数据流在路由器交汇，而现有带宽却不能完全满足需求，给 路由器造成了极大负担，网络拥塞的发生不可避免。如果网络中有许多资源同时 发生了拥塞，网络性能就会明显变坏，拥塞节点处缓冲区的排队队长急剧增长， 以致队列溢出、时延增大，整个网络的吞吐量随着输入负荷的增加而下降，严重 时出现拥塞崩溃，甚至死锁等网络无法正常工作的情况【卜3 1 。这些极端情况的发生 主要是因为，源端重传溢出的丢失分组不但会加重源端的负担，而且在拥塞造成 时延增加后，又会使得更多的分组因为超过生存时间而失效，需要重传，如此恶 性循环让越来越多的缓存变得饱和，系统的有效传输几乎为零，严重时，造成系 统瘫痪。可见，随着越来越严重的网络拥塞问题的暴露，网络拥塞己成为i n t e r n e t 发展中函待解决的重要课题。 1 2 研究现状 拥塞控制是保证i n t e r n e t 稳定运行不可或缺的重要机制。其中，端到端的t c p 拥塞控制机制能在拥塞发生时使t c p 源端降低数据的发送速度，保证了大量的 t c p 连接能够共享一条拥塞链路，在防止拥塞崩溃方面取得了巨大成功【4 s 】。 随着i n t e r n e t 的飞速发展，出现了许多不受t c p 拥塞控制机制约束的应用， 加重了拥塞崩溃的可能，此外t c p 拥塞控制还存在自相似、效率、公平性等问题。 所以需要中间节点的i p 拥塞控制机制对t c p 拥塞控制机制进行补充，让主机端 难以达到的控制目标得以实现，如队列管理机制。弃尾法是目前广泛使用的队列 管理机制，但其会带来满队列等一系列问题【6 】。这就将研究引入了对满队列的控 制上，将队列管理的研究引入到了从被动队列管理( 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 ) 的转变中。 s f l o y d 等提出的随机早期监测( r a n d o me a r l yd e t e c t i o n ，r e d ) 是i e t f 推 广东工业大学t 学硕十学位论文 荐的a q m 候选算法d 4 1 。但作为启发式算法，r e d 依旧存在很多缺陷，如，参数 难以配置，在特定的网络状况下会导致t c p 同步，造成队列震荡，吞吐量降低和 时延抖动加剧；r e d 的公平性和稳定性也存在问题i s 9 1 。 a q m 算法的研究是目前拥塞控制的研究热点，涌现了很多新颖的策略。比如， r e m 、g r e e n 、a v q 、p i 、b l u e 等d o - 1 2 3 2 ，3 3 3 3 3 ，】；同时，基于r e d 的内核进行了改 进，得到了诸如s t a b i l i z e dr e d 、f r e d 、g e n t l er e d 、a d a p t i v e r e d 、b a l a n c e dr e d 、 f l o wr e d 等r e d 变种算法【9 13 4 0 】。 在a q m 算法的分析验证上，有从理论角度分析算法缺陷，有通过仿真或实 验验证算法有效性等等，但大多数研究工作在很大程度上依赖于直觉，只针对局 部问题，缺乏系统的理论来进行分析和设计【，s 】。近年来，非线性规划理论、系统 理论、和优化控制理论被引入到拥塞控制中来，特别是v m i s r a 给出的t c p a q m 控制模型和c h o l l o t 等提出的小信号分析法，为研究开辟了新路 1 6 1 。 1 3 论文的课题来源 论文的课题来源如下： 1 国家一广东联合基金“复杂传感与控制网络的建模，控制和优化” ( u 0 7 3 5 0 0 3 ) 。 2 国家自然科学基金“概率模糊逻辑系统及其在自相似业务流拥塞控制机理 的研究”( 6 0 6 0 4 0 0 6 ) 。 3 广东省自然科学基金”概率模糊系统的统一信息处理机制及其在网络系统 的研究”( 6 0 2 1 4 5 2 ) 。 1 4 论文的总体框架 论文的总体框架如图1 一l ： 1 对i n t e r n e t 的拥塞控制机制进行了探讨，介绍拥塞控制相关的基本理论。 2 以拥塞控制的发展进程为线索，对流量控制机制、t c p 拥塞控制机制和 i p 拥塞控制机制进行研究。 3 针对r e d 算法性能受负载影响严重的缺陷，提出了性能增强的r e d 变种 算法，并在t c p a q m 动态模型下，研究了算法的稳定性等性能。 2 第一章绪论 4 通过仿真证明：新算法能够在变负载的网络环境下获得更好的性能。 1 5 论文的创新设计 图1 1 论文的总体框架 f i gl 一1t h ef r a m e w o r ko fp a p e r 在i n t e r n e t 及其子网中，网络负载量、链路容量、网络延时、抖动和链路拓 扑等等网络环境都是不确定和变化的。然而，网络环境一旦发生变化，r e d 中原 来匹配的参数就无法适合新环境，并直接表现为队列振荡的加剧，导致不必要的 延迟和抖动，使得客户获得的服务质量下降。其中，在一段固定的测试时间内， 网络负载量的变化对网络性能的影响是最显著也是最根本的。如何改善网络在负 载多变网络环境下的性能也就成为了论文创新的第一要务。 如图1 2 ，论文创新的总体设计可概述如下： 1 创新的对象一一r e d 算法。 2 创新的目标一一降低负载变化对r e d 控制性能的影响，得到性能增强的 一 一 rlllllll一 广东工业大学1 = 学硕士学位论文 新算法。 3 创新的方法一一结合控制理论改进r e d 算法。 4 创新的成果一一提出了三种新颖的a q m 算法 1 6 新算法的设计 图1 2 论文创新的规划 f i g l 一2t h ed e s i g n e di n n o v a t i o no ft h e s i s 如图1 3 所示，新算法的设计是论文的精髓所在： 1 结合“参数不确定系统的稳定鲁棒性”概念，使用扩大的阈值范围来换取 算法的鲁棒性，得到i n t e r v a lr a n d o me a r l yd e t e c t i o n ( i r e d ) 算法。 2 沿着自适应控制的研究路线，让队列阈值随着“队列占用率”的变化自适 应调整，得到自适应性增强的a d a p t i v et h r e s h o l dr a n d o me a r l yd e t e c t i o n ( a t r e d ) 算法。 3 结合自动控制的新兴理论一一智能控制，即使用补偿模糊神经网络来调整 队列阂值，得到c o m p e n s a r yf u z z yn e u r a ln e t w o r kr a n d o me a r l yd e t e c t i o n ( c f n n r e d ) 算法。 4 第一章绪论 1 7 论文的章节组织 图1 3 新算法的设计 f i g1 3t h ed e s i g no fn e wa l g o r i t h m s 第一章绪论，介绍了在i n t e r n e t 飞速发展的背景下，网络拥塞控制面临的新 形势、出现的新发展和论文的对策。 第二章介绍了拥塞控制的相关基础知识，最后概述了网络服务质量和网络仿 真的相关知识。 第三章介绍了t c p 拥塞控制机制和i p 拥塞控制机制，分析了一些著名的a q m 算法，最后介绍t c p a q m 流体模型。 第四章对r e d 的阈值进行的新颖的改进，将其由单值转变为了区间，得到了 i r e d 算法；并对t c p i r e d 系统的稳定性进行了一系列分析。 第五章提出了队列占用率的概率，并以此为基准对r e d 的最大、最小阂值进 行自适应调整，得到了a t r e d 算法。并对t c p a t r e d 系统的稳定性进行了分析。 第六章将能够很好处理不确定性、非线性和其他不适定问题的补偿模糊神经 网络应用在拥塞控制算法的设计中，得到了c f n n r e d 算法。 广东 二业大学工学硕士学位论文 第二章拥塞控制的基本理论 当网络中存在过多的报文时，网络的性能下降，这种现象称为拥塞【1 7 】。拥塞 发生时，整个网络的资源利用率下降，用户感受到网络服务质量降级，严重时产 生拥塞崩溃。拥塞控制则能通过采用合理的算法与机制确保网络不因传入数据流 过大耗尽网络节点的资源而导致网络崩溃。本章主要介绍了拥塞和拥塞控制的相 关背景和基本理论。 2 1 拥塞的原因和拥塞控制的必要性 在研究的初始阶段，滞后发展的硬件条件( 低速链路、较慢的处理器和较小 的缓存等等) 被当作是造成网络拥塞的元凶，但后来发现单纯为网络扩容，只能 局部地解决眼前问题，拥塞在全局范围依然存在；特别是在现今高速链路、高性 能处理器和大容量缓存相当普遍的情况下，拥塞反而有进一步恶化的趋势。例如， 增加节点缓存容量表面上可以防止或者缓解拥塞引起的分组丢弃，但这样却使端 到端时延增大，导致更多的分组重传，反而浪费了带宽，加重了拥塞。 可见，单纯的增加网络资源是无法解决拥塞问题的，必须从各方面入手对网 络流量进行必要的管理，包括接纳控制、流量成形、队列管理、调度和拥塞控制 等等。对任一机制而言，对其最基本、最重要的要求就是防止网络出现拥塞崩溃， 使网络运行在轻度拥塞的最佳状态，最大限度的利用网络瓶颈资源，保障用户的 服务质量。其中，拥塞控制能够实现网络利用率和传输延迟等综合性能指标的最 优化，提高网络的总体性能，保证网络系统长期的稳定性和鲁棒性，是网络稳定 运行是不可或缺的机制。 2 2 拥塞控制的意义和目的 网络拥塞的发生不可避免，而如果网络的许多资源同时发生了拥塞，网络性 能会明显变坏，拥塞节点缓冲区的排队队长急剧增长，队列溢出而导致分组丢失、 时延增大，整个网络的吞吐量随着输入负荷的增加而下降，严重时出现拥塞崩溃 等网络无法正常工作的情况。拥塞控制在网络节点采取措施来避免拥塞发生或者 6 第二章拥寒控制的基本理论 对拥塞做出反应。可见，拥塞控制对提高网络性能有着重要意义。 拥塞控制的目的不是要完全避免拥塞，而是研究怎样的拥塞程度才合适。因 为：i n t e r n e t 使用分组交换技术来提高网络链路的利用率，使得路由器队列经常被 占。如果队列缓存总为空，传输延迟小，但网络利用率低；如果队列缓存总被占， 网络利用率高，但传输延迟大。拥塞控制的目标就是实现网络利用率和传输延迟 等综合性能指标的最优化。 2 3 拥塞控制与控制理论 拥塞控制算法的设计与稳定性分析是近几年网络、通信和控制等几个交叉学 科的一个研究热点，短时间内已经取得了很大进展。 1 m i s r a 等提出了t c p a q m 的微分方程模型。 2 m a s c o l o 基于s m i t h 原理设计了一个稳定的拥塞控制算法1 2 0 1 。 3 p a g a n i n i 等利用多变量鲁棒控制理论，设计了一个拥塞控制系统，它对于 任意网络拓扑、容量和时延能保持局部稳定性。 4 l i 等利用混杂控制系统模型探讨了多个t c p 共享带宽的暂态行为。 5 s h o r 等用状态空间分析t c p 的极限环行为。 6 m a t h i s 等在假设数据丢失是可预测的周期性前提下，用随机模型得到的 平均吞吐量表达式。 7 p a d h y e 等把稳态时t c p 流吞吐量近似表示为丢失率和i 汀t 的函数1 2 h 。 8 l o w 等则基于优化理论提出了t c p a q m 对偶模型【：) 。 9 考虑到神经网络的学习能力，可以让神经网络对网络的动态特性进行学 习、概况，在次基础上调节发送速率来避免和解除拥塞。 1 0 在预测控制方面。熊辉等采用直接预测的方式来实现拥塞控制。在不增加 网络附加信息的基础上，仅依靠a c k 就可以实现预测【2 4 】。 2 4 拥塞控制的分类 从控制理论的角度出发，可对拥塞控制进行分类： 1 从控制方式出发可分为开环控制和闭环控制。开环控制事先设定，在网络 运行后，就不再采取措施。当流量特征和性能要求明确时，适合开环控制， 7 广东1 = 业大学工学硕j 二学位论文 比如音频和图像业务。闭环控制通过反馈机制及时了解网络的运行状况， 并反馈给端系统，端系统相应降低发送速率。当流量特征不能准确描述或 者系统不提供资源预留时，适合闭环控制。 2 从反馈机制来看，反馈信息分为显式和隐式。显式信息描述带宽、缓存容 量等，可以直接通告控制端网络的状态；隐式信息则为超时和重复a c k 等隐含信号，控制端则根据隐式信息对网络状态进行推断 3 从控制实施的位置出发可分为：端到端拥塞控制和路由器拥塞控制。端到 端拥塞控制在主机和网络边缘设备中执行，根据反馈调整发送速率。由于 t c p 是使用最广泛的传输协议，t c p 协议中的拥塞控制算法也是使用最 广泛的端到端拥塞控制。路由器拥塞控制在路由器中执行，不但可以检测 拥塞的发生，反馈源端拥塞信息，还能采取相应的拥塞预防措施。 4 从实施控制的手段出发可分为：基于窗口和基于速率的拥塞控制。t c p 拥塞控制是典型的基于窗口的控制，通过调整滑动窗口的大小来控制发送 到网络的数据量。基于速率的控制通过对t c p 窗口机制建模来得到t c p 连接的吞吐量与网络参数间的解析式，用来指导源端发送速率的大小，本 质上适合多媒体数据流的传输。 2 50 uiit yo fs ervic o ( 0 0 s ) 尽力而为的i n t e r n e t 的网络体系结构缺乏一定的隔离和保护机制，如何保证 用户信息的传输质量就成为了一个不容忽视的重要问题。q u l i t yo fs e r v i c e ( q o s ) 机制也成为了i n t e r n e t 增加服务内容、提高服务质量的关键技术。 i t u t 在建议书e 8 0 0 中给出了q o s 的定义：q o s 是服务性能的总效果，决 定了用户对服务的满意程度。q o s 技术就是为某个保证级别提供充足的网络资源 使应用程序能有效地利用共享网络带宽。q o s 约定了用户和服务提供商之间的关 于信息传输的质量，即当用户申请了服务以后，供应商用何种方式来满足用户需 求的问题，这些约定需求涉及到业务可用性、带宽、时延、时延抖动、丢失率、 吞吐量等参数【l 。】。q o s 实现的常用手段有： 1 接纳控制。 2 流量控制。 第二章拥寒控制的基本理论 3 分组调度。 4 缓冲区管理。 5 拥塞控制。 6 q o s 路由。 q o s 技术的本质就是让网络摆脱尽力而为的服务模式，使网络核心也参与到 网络流量的约束中来，对网络带宽、队列进行管理，有效地检测和控制网络拥塞。 无论网络采用哪种模型和机制，拥塞控制都是q o s 机制不可或缺的，是网络q o s 保证的前提。如果网络出现拥塞而无法及时处理，就谈不上任何q o s 保证，只有 具备有效的拥塞控制机制才能保证网络的运行效率和端到端服务质量【2 5 1 。 2 6 网络仿真 在对新的网络方案进行验证和分析等研究时，采用的基本方法有：分析建模、 实验测试和网络仿真。仿真方法的抽象化程度比分析建模低，耗费的时间比实验 测试少，其低成本和有效性是传统方法不可替代的。而且在很多时候，仿真是唯 一可用的网络研究方法。随着新技术的不断出现和网络的日趋复杂，网络仿真的 应用也日趋广泛，已经成为研究、规划、设计网络不可或缺的工具。 2 6 1m a tia b m a t l a b 是m a t h w o r k s 公司在1 9 8 4 年推出的一套科学计算软件，分为总包和 若干个工具箱。它具有强大的矩阵计算和数据可视化能力，一方面可以实现数值 分析、优化、统计、偏微分方程数值解、自动控制、信号处理等若干个领域的数 学计算，另一方面可以实现二维、三维图形绘制、三维场景创建和渲染、科学计 算可视化、图像处理、虚拟现实和地图制作等图形图像方面的处理1 2 6 。 到9 0 年代初期，m a t l a b 已经成为攻读理工学科的大学生、硕士生、博士生必 须掌握的基本工具；在国际学术界，m a t l a b 是准确、可靠的科学计算软件的标准， 在许多国际一流学术刊物上，都可以看到m a t l a b 的应用；在设计研究单位和工业 部门，m a t l a b 是进行高效研究、开发的首选软件工具。 9 广东工业大学工学硕上学位论文 2 6 2n s 2 网络仿真的最终目的是改善网络运行状况，包括网络拓扑仿真、协议仿真和 通信量仿真，不仅适用于网络模型的构造和设计、协议性能的评价和分析，还适 用于网络协议研发以及真实网络的故障诊断。知名的网络仿真软件主要有m a t l a b 、 o p n e t 、n s 2 、c a s s a p 、s p w 、g l o m o s i m 等等。而n s 2 作为免费的开源软件， 在国内外具有极高的知名度，是进行网络仿真的首选1 3 0 1 。 n s 2 是一个面向对象的仿真工具，来源于美国d a r p a 项目v i n t 中的基础和 核心部分，由u s i i s i 、x e r o xp a r c 、l b n l 和u cb e r k e l e y 研发。以其对有线和 无线( 本地或卫星) 网络、局域网和广域网、网络分层模型各协议的丰富支持、强 大的二次开发能力以及可扩展、易配置、易编程的事件驱动特性，n s 2 在国际网 络研究界得到了广泛的应用。 2 7 本章小结 本章简单介绍了与拥塞控制相关的基础知识： 1 给出了拥塞的定义并介绍了与拥塞控制相关的基础知识。 2 介绍了自动控制理论在拥塞控制中取得的成果。 3 介绍了拥塞控制的分类。 4 对网络服务质量( q o s ) 的相关知识和背景进行了介绍，并以此引出了拥 塞控制在保证网络q o s 中起到的不可或缺的基础性作用。 5 对目前论文使用的仿真工具m a t l a b 和n s 2 进行了扼要的介绍。 1 0 第三章拥塞控制与网络模型 第三章拥塞控制与网络模型 3 1 拥塞控制的基本思想 直观上，解决网络拥塞可以从两方面入手：一是拥塞避免，即尽量避免拥塞 的发生，使网络运行在最佳状态；一是在拥塞发生后采取补救措施消除拥塞。完 全避免拥塞必然会牺牲网络的资源利用率，在追求公平、高效、高利用率的网络 环境下，采取这种保守的方法是不适宜的，因此采用拥塞避免和拥塞控制结合的 方法更为合理。 拥塞控制技术包括控制机制和控制策略。控制机制从宏观上确定拥塞控制的 模式，比如是主动还是被动模式。控制策略则从微观上明确描述实现拥塞避免和 控制所采取的策略，比如拥塞控制算法就是策略的描述。控制策略由反馈机制和 控制机制组成，网络通过反馈机制向源端或目的端通告它当前状态，源端则根据 接收到的反馈信息，通过控制机制完成对负载的调整来消除拥塞。 3 2 流量控制机制 最初的t c p 协议并没有拥塞控制机制，只有基于滑动窗口的流量控制( f l o w c o n t r 0 1 ) 机制一一通过控制发送端的数据发送量和发送速率，来保证数据的发送 不超过接收端的承受能力。 流量控制和拥塞控制密切相关。流量控制可以避免或推迟拥塞的发生；而拥 塞控制可以抑制源端发送数据，起到流量控制的作用。两者的差异是：前者只涉 及收发双方的端到端传输，是为了确保发送方发送的数据不会超过接收方的接收 能力，解决接收方的瓶颈问题，是一种双方的“个人 行为，不涉及到公平问题； 而后者是一个关系到网络全局的问题，意在解决中间设备的瓶颈问题，具有“社 会性”，要求做到公平合理。由于流量控制是i n t e r n e t 发展初期惟一可行的拥塞控 制方法，从而造成了流量控制和拥塞控制概念的混淆，实际上，前者只是后者的 一种技术实现途径。流量控制技术的著名协议有： 1 停止等待协议 2 连续a r q 协议 广东t 业夫学工学硕上学位论文 3 滑动窗口协议 3 3 端到端t c p 拥塞控制机制 流量控制没有考虑网络的传输能力，导致了拥塞崩溃的发生。为了有效解决 网络易发生拥塞崩溃的问题，拥塞控制机制应运而生。其中，端到端t c p 拥塞控 制机制将数据包的丢失作为拥塞发生的信号，源端确认发出的数据丢失后，立即 降低发送速率。t c p 拥塞控制提高了网络的传输性能，保证了网络的稳定运行， 避免了拥塞崩溃的发生。 3 3 1t c p 拥塞控制机制的发展 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 r n e t 首次出现了一系列的拥塞崩溃现象，网络吞吐量急剧下降，从l b l 到u cb e r k e l e y 的数据流量从3 2 k b p s 降到了4 0 b p s 。此后，j a c o b s o n 等人开始对此进行研究，发 现这是由于在网络拥塞状态下t c p 的失常行为所致，为此，j a c o b s o n 在t c p 中 增加了拥塞控制算法( t c pt a h o e ) ，提出了著名的慢启动( 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 ) 、快速重传( f a s tr e t r a n s m i t ) 算法【2 s 】。1 9 9 0 年的t c p r e n o 版本增加了快速恢复( f a s tr e c o v e r y ) 算法，避免了拥塞不够严重时采用慢 启动带来的大幅度减小发送窗口的现象。慢启动和拥塞避免通常一起实现，快速 重传和快速恢复通常在一起实现。这四个算法也构成了端到端的t c p 拥塞控制的 核心，算法使用加性增加倍乘减小( 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 ， a i m d ) 的窗口管理算法来控制发送速率。 进入9 0 年代，为了克服由窗口的慢增快减所引起的震荡，出现了d u a l 、 t c pv e g a s 3 s 等机制。然而，这些机制与t c pr e n o 的兼容性不强，甚至可能带来 负面影响，无法在实际应用中得到广泛支持。9 0 年代后期，研究转入了对快速恢 复算法的改进。t c pn e w r e n o 、选择性应答( s e l e c t i v ea c k ，s a c k ) 等算法都取 得了有效的进展【4 3 】。 1 2 第三章拥塞控制与网络模型 3 3 2t c p 拥塞控制的工作原理 t c p 拥塞控制主要基于a i m d 算法，a i m d 的参数有： 1 拥塞窗口( c w n d ) 。发送端在拥塞时一次最多能发送的分组数量。 2 通告窗口( a w n d ) 。连接建立及传输的过程中，接收端向发送端通告的最 大可接收速率。 3 发送窗口( w i n ) 。发送端实际发送数据的窗口大小， w i n = m i n ( c w n d ，a w n d ) 。通常有w i n = c w n d 。 4 慢启动门限( s s t h r e s h ) 。慢启动阶段和拥塞避免阶段的分界点，初始值通 常为6 5 5 3 5 b y t e s 。 5 往返时延( r t t ) 。一个数据包收到接收端确认的总时间间隔。 6 重传超时值( r t o ) 。描述数据包从发送到失效的时间间隔，是判断丢包 与否，是否拥塞的重要参数。 7 快速重传阈值( t c p r e x m t t h r e s h ) 。能够触发快速重传的发送端收到的重复 确认包a c k 的个数，其缺省值是3 ；当实际的重复a c k 超过此值时，网 络开始快速重传。 a i m d 的具体工作过程为： 1 发送端每收到一个a c k ( 即如果每个发出的分组都在最近的r t t 时间内 获得确认) 就将c w n d 加l ，即加法增加。 2 发生超时时，t c p 判断拥塞发生，减小发送速率，发送端将c w n d 减半， 即倍性减少。 t c p 拥塞控制主要涉及慢启动、拥塞避免、快速重传、快速恢复。 1 慢启动 t c p 在启动一个连接或者超时后，发送端将c w n d 初始化为一个数据包大小， 按c w n d 大小发送数据；每收到一个a c k ，c w n d + + ，e w n d 就随着r t t 呈指数级 增长，发送端发送的数据量急剧增长。 2 拥塞避免 发送端发生超时，判断网络发生拥塞，进入拥塞避免： 设置s s t h r e s h = c w n d 2 。 设置c w n d = l ，进入慢启动过程直到c w n d = s s t h r e s h 。 广东工业大学工学硕t 学位论文 c w n d s s t h r e s h 时，c w n d + + ( 在每个r t t 内线性增长) 。 3 快速重传 快速重传算法建立的前提为： 发送端收到重复a c k ，意味着该数据包丢失或失序到达；如果收到了3 个重复a c k ，则数据包丢失的可能性很大。 发送端使用r t o 来判断数据包是否丢失，但r t o 通常比实际的r t t 长许 多，这样就会使t c p 可能无法及时重传。 所以，发送端不会等到超时，在收到3 个重复a c k 后，立即重传。 4 快速恢复 当发送端根据三个重复a c k 重传后，由于没有超时，如果使用慢启动，会保 守地置c w n d 为1 ，重新探测网络带宽，吞吐量大幅下降。快速恢复在快速重传后 执行拥塞避免，避免了网络重新进入慢启动后的网络性能下降，其具体机制为： 当第三个重复a c k 到达时，设置s s t h r e s h = c w n d 2 ，重传数据包并设置 c w n d = s s t h r e s h + 3 。 每次有一个过多的重复a c k 到达时，c 1 d + + ，并在可能的情况下发送 一个数据包。 新的a c k 到达时，设置c w n d = s s t h r e s h 。 3 4 中间节点的ip 拥塞控制机制 3 4 1lp 拥塞控制实施的必要性 t c p 拥塞控制对i n t e r n e t 的鲁棒性起到了关键作用，但随着网络的飞速发展， t c p 拥塞控制面临着如下的诸多问题： 1 i n t e r n e t 的快速发展促进了t c p 各种版本的产生，有些没有t c p 拥塞避免 机制，如接收端驱动分层多播( r e c e i v e r d r i v e nl a y e r e d m u l t i c a s t ，r l m ) ； 有些采用了更为贪婪的拥塞控制算法。 2 t c p 的重传机制和突发的时延抖动，导致了大多数的多媒体和组播业务 采用了没有拥塞控制机制的u d p 协议，i n t e r n e t 又可能进入拥塞崩溃。 3 用户有意或无意地改动了t c p 拥塞控制算法。如，修改t c p ，使窗口的 初值很大且保持不变，即所谓的“快速t c p 。 1 4 第三章拥塞控制与网络模型 i n t e r n e t 仅仅依靠源端的t c p 拥塞控制机制来处理拥塞的能力十分有限，必 须引入中间节点的i p 拥塞控制，让网络本身也参与到拥塞控制中去d 2 。i p 拥塞 控制策略包括路由器中采用的调度( s c h e d u l i n g ) 算法和队列管理( q u e u e m a n a g e m e n t ) 技术。 3 4 2 队列调度 调度就是从一个或多个队列中选择下一个待转发的分组输出到链路，使所有 输入业务能够按照预定的方式共享输出链路带宽，是解决多个业务共享资源的有 效手段，与队列管理有着本质区别，是实现q o s 控制的核心技术之一。 根据排队和出队策略的不同，调度算法可分为：先进先出( f i f o ) 、优先队 列( p q ) 、定制队列( c q ) 、加权公平队列( w f q ) 等。其中，最简单也是使用 最广泛的调度算法就是f i f o 一一把要从某队列端口输出的报文，按照到达的先后 顺序将其放入该队列尾部；在端口发送报文时，从队列头部开始依次发送。所有 报文在发送过程中没有任何区别，也不对报文传送的质量提供任何保证。 3 4 3 队列管理 队列管理为到达的分组分配存储空间，在适当时候选择丢弃某些分组来控制 队长以及哪些流可以占用队列，通过控制队列的占用间接影响带宽的分配。主动 队列管理( a c t i v eq u e u em a n a g e m e n t ，a q m ) 通过预测拥塞的发生，在拥塞尚未 发生时就开始随机地丢弃或者标记数据包，来避免拥塞的发生。其特点包括： 1 早期探测路由器可能发生的拥塞，并通过随机丢弃或者标记分组来通知发 送端采取措施避免拥塞，减少了路由器的分组丢失。 2 公平地处理包括突发性、持久性、间隙性的各种t c p 业务流。 3 避免死锁。a q m 能确保到达的分组几乎总有可用缓存，从而防止了死锁 的发生。 4 维持较小的队长，在高吞吐量和低时延间取得合理平衡，也解决了全局同 步问题。同时，较小的队长增强了路由器容纳突发流量的能力。 广东工业大学工学硕士学位论文 3 5 常见的a q m 算法 直到f l