（市政工程专业论文）高速网络中拥塞控制研究.pdf

摘要 摘要 通信网络诞生之初，拥塞现象便产生了，它表现为网络某处业务量的聚集。拥 塞的发生不仅深刻地影响着网络性能，严重时甚至会引起网络的瘫痪。因而，对 拥塞的控制是一个关系到网络是否能够稳定可靠地运行的一个重大的课题，更是 通信网络设计面临的一个重要的问题。拥塞控制的主要目的是提高网络资源的利 用率以及为信源提供公平的资源分配。随着通信技术与计算机技术的不断融合和 发展，传统的电话交换网络已发展成为今天的宽带综合业务数字网b 4 s d n ，而且 还将继续向着高速化和智能化的方向发展。在当今的高速网络中，通信协议的分 层结构更加复杂，进入网络的通信业务类型越来越多，它们的传输要求与统计特 性也各不相同，这就使得高速网络中的拥塞现象变得更加复杂，而高速网络的拥 塞控制问题也面临着新的挑战。 本文在吸收国内外有关拥塞控制簧略及其实现算法、描述通信量统计特性和预 测业务流量方法的基础上，研究了a t m 论坛组织定义的对a b r 服务类型实行的 闭环式拥塞控制机制，分析与比较了各种控制算法的优缺点，改进了一个简单有 效的流量控制算法。并研究了对通信业务量建立模型的问题。基于高速网络中通 信流量的自相似性与混沌现象的本质联系，提出了一种网络业务流量的预测方法。 全文的研究内容与主要结果如下： ( 一) 对高速网络中的拥塞控制策略及其实现算法进行了研究。a t m 论坛将 胡塞控裁策略纳入到高速网络的通信量管理方案中，在其定义的遁售量管理文本 中，a t m 的服务类型被分成了五大类。对不同的服务类别，采取不同的控制方法。 其中，对a b r 服务类别采用的是一种基于速率的反馈式控制机翩。在已经实现了 这种反馈式机制的方法中，第一代的方法即二进制方法。二进制方法设计简单， 容易操作，但它的不稳定性降低了其有效性，面且公平经很差。第二代的显示速 率方法在稳定性和公平性方面改进了很多，但它同时带来了速率计算的复杂性， 两且增加了交换枫的负担。 ( 二) 对排队论及其应用的发展过程进行了研究。排队论是交换系统进行性能 分板和系统设计的主要工具。随整通信网络结构及交换与传输技术的发展，摊队 系统的业务输入过程、交换机的服务过程和服务规则已经发生了很大的变化，但 它的基本模式和性能分析指标没有变化。直到现在，它仍是常用的系统分析工具， 由于入网业务流量的复杂性，现在多用仿真实验代替了以往的数学解析分析。在 高速网络中，自相似性的业务输入对排队系统的性能影响仍是一个没有完全解决 的问题。 重庆大学博士学位论文 ( 三) 研究了描述高速网络中业务流量特性的问题。文中描述了高速网络业务 流量自相似性的表现，总结了自相似性的多个等价定义。这些定义从不同的侧面 分别表现了自相似性性质的不同特点，如在时间尺度变换下的不变性。自相关函 数的长期相关性，业务到达分布律的重尾巴性，以及功率谱密度服从的功率定律。 这些特性表明，正是由于业务流量的随机性，使得拥塞控制的问题是一个复杂的 随机控制问题。对此控制对象建立恰当的解析模型是设计性能优良的控制算法的 一个重要的工作。 ( 四) 业务流量预测是资源分配方案的种有效措施。准确的业务流量预测， 能够为各种网络管理方案如a t m 网络中带宽和缓冲区的合理分配提供可靠的数据 依据。并由此提高网络的利用率以及有效地避免拥塞的发生，基于自相似性与混 沌现象的本质联系，本文研究了混沌时间序列吸引予的特往。它的特征由兰个不 变的量，l y a p u n o v 指数五、关联维d 和k o l m o g r o v 熵来表征。运用t a k e n s 的重 构相空间理论和最大l y a p t m o v 指数的定义，对仿真的自相似业务源的速率值作出 了预测，并给出了最大预报时间。该预测模式简单。预测效果好。 ( 五) 深入研究了a b r 服务的反馈式控制机制及其实现算法，改进了一种简 单有效的流量控制算法，即幻影算法。经过改进后的算法在保留了原来算法的优 点，如平滑接入新连接、较强的鲁棒性坟及良好的公平性等以井，还通过对设置 的不同的拥塞级别采取不同的控制措施的方法，增强了网络避免拥塞的能力。 ( 六) 绘出了基于最大l y a p u n o v 指数的预测算法帮改进的幻影算法的仿真实 验结果，并进行了分析。 ( 七) 对本文进行了总结，并展望了今后的研究工作。 关键词：掇塞控制，反馈式控制机制，排队理论，自相似性，混淹，预测，仿真 实验 n a b s t r a c t c o n g e s t i o n o r 也eb u i l d u po ft r r f f i ci nac e r t a i np l a c eo ft h en e t w o r ke x i s t sw h e nt h e c o m m u n i c a t i o nn e t w o r kw a s c r e a t e d c o n g e s t i o nh a sap r o f o u n de f f e c to nt h eo v e r a l l p e r f o r m a n c eo f t h en e t w o r k , a n d i se v e nc a p a b l eo f m a k i n gt h en e t w o r k p a r a l y z e d t h u s ， c o n g e s t i o nc o n t r o l i sa r te s s e n t i a ls u b j e c tl i k e l yt oa f f e c tt h es t a b l ea n dr e l i a b l eo p e r a t i o n o ft h en e t w o r k , a n di sa l s oa ni m p o r t a n ti s s b et ob ec o n s i d e r e di nn e t w o r kd e s i g n n e p u r p o s eo f c o n g e s t i o nc o n t r o li st oi m p r o v et h eu t i l i z a t i o no f t h en e t w o r kr c s o n r c e sa n d t op r o v i d et h et r a f f i cs o u r c e sw i t hf a i rr e s o u r c ea l l o c a t i o n w i t l lt h ec o n v e r g e n c eo ft h e c o m m u n i c a t i o n t e c h n o l o g y a n dt h ec o m p u t e r t e c h n o l o g y , t r a d i t i o n a lt e l e p h o n e s w i t c h i n gh a se v o l v e di n t ot h ep r e s e n tb i s d n ，a n di sg oo nt oa d v a n c et o w a r d st h e t r e n do f h i g h s p e e da n di n t e l l i g e n c e i nc u r r e n th i g h s p e e dn e t w o r k s ，t h ea r c h i t e c t u r e s o fc o m m u n i c a t i o np r o t o c o l sa r eb e c o m i n gi n c r e a s i n g l yc o m p l e x ，a n dt h e r ei sag r o w i n g v a r i e t yo ft r a 伍ct y ) e s w h o s et r a n s m i s s i o nr e q u i r e m e n t sa n ds t a t i s t i cc h a r a c t e r i s t i e s d i f f e r 舶mo n et oa n o t h e r c o n s e q u e n t l y , c o n g e s t i o ni nh i g h - s p e e dn e t w o r k si s b e c o m i n gi n c r e a s i n g l yc o m p l i c a t e d ，w h i c hw i l lu n d o u b t e d l yb r i n gn e wc h a l l e n g e st o t h ec o n g e s t i o nc o n t r 0 1 b a s e do nt h ed e s c r i p f i o no fc o n g e s t i o nc o n t r 0 1m e a s u r e sa n dt h e i ri m p l e m e n t a t i o n a l g o r i t h m s a sw e l la st h es t a f f s t i cc h a r a c t e r i s t i c so ft h ec o m m u n i c a t i o n 饷伍ci n l i t e r a t u r ea th o m ea n da b r o a d ，t h i sp a d e rs t u d i e st h ec l o s e d - l o o pc o n 灯o lm e c h a n i s m d e f m e db y 删f o r u mf o ra b rs e r v i c et y p e s ，f o l l o w e db ya na n a l y s i sa n d c o m p a r i s o n o ft h ea d v a n t a g e sa n dd i s a d v a n t a g e so fv a r i o u sc o n t r o la l g o r i t h m s i tt h e ni m p r o v e sa s i m p l eb u te f f e c t i v ec o n t r o la l g o r i t h mf o rt r a f f i cf l o w t h i sp a d e ra l s od e a l sw i mt h e s e t u po fm o d e l sf o rc o m m u n i c a t i o nt r a 伍c f i n a l l y , o nt h eb a s i so ft h en a t u r er e l a t i o n b e t w e e n 也es e l f - s i m i l a r i t yo ft h ec o m m u n i c a t i o nt r a 伍cf l o wi nh i g h s p e e dn e t w o r k s a n dt h ec h a o s ，t h i sp a p e r p r o p o s e sap r e d i c t i o nm o d e lf o rn e t w o r kt r a g i cf l o w 蹦sp a d e rf a l l si n t ot h ef o l l o w i n g7s e c t i o n s 1 c o n c e r n i n ga b o u tt h ee o n g e s t i o nc o n t r o lm e a s u r e sa n dt h e i ri m p l e m e n t a t i o n a l g o r i t h m si nh i g h - s p e e dn e t w o r k s a t mf o r u mc a t e g o r i z e st h ec o n g e s t i o nc o n t r o l m e a s u r e si n t ot h em a n a g e m e n ta p p r o a c h e st oc o m m u n i c a t i o nt r a 伍ci nh i g h - s p e e d n e t w o r k s 。i nt h cd e f i n e dt i 剖匝cm a n a g e m e n ts p e c i f i c a t i o nv e r s i o n4 0 1 s j ，a n s e r v i c e sa r eg r o u p e di n t o5m a j o rc a t e g o r i z e s d i f f e r e n tc o n t r o lm e t h o d sa r et ob e e m p l o y e df o rd i f f e r e n ts e r v i c et y p e s n l er a t e b a s ef e e d b a c kc o n t r o li su s e df o ra b r s e r v i c et y p e s a m o n gt h ev a r i o u sm e t h o d sw h i c hh a v e i m p l e m e n t e dt h ea b o v e f e e d b a c km e c h a n i s m ，t h ef i r s tg e n e r a t i o nm e t h o d ，i e ，t h eb i n a r ym e t h o di se a s yt o o p e r a t ew i t hs i m p l ed e s i g n i t sl i m i t a t i o n sa r ei ti su n s t a b l e af e a t u r ea b l et od e c r e a s ei t s e f f e c t i v e n e s s a n di th a sp o o rf a i r n e s s t h es e c o n dg e n e r a t i o nr a t em e t h o d m a k e sag r e a t i m p r o v e m e n ti ns t a b i l i t ya n df a i r n e s s ，b u ti tm a k e st h ed e s i g nc o m p l i c a t e da n db r i n g s b u r d e nt ot h es w i t c h 2 d i s c u s s i n gt h eq u e u i n gt h e o r ya n dt h ed e v e l o p m e n to fi t sa p p l i c a t i o n s 前1 e q u e u m gt h e o r yi sam a j o rt o o lf o rs w i t c h i n gs y s t e n x si np l 髓f o m 觚c ea n a l y s i sa n d i i i 重庆大学博士学位论文 s y s t e md e s i g n a st h ea r c h i t e c t u r e s w i t c h i n ga n dt r a n s m i s s i o nt e c h n o l o g i e so f c o m m u n i c a t i o nn e t w o r k se v o l v e ，g r e a tc h a n g e sh a v et a k e np l a c ei n 也es e r v i c ei n p u t p r o c e s s e ss e r v i c er e g u l a t i o n so fs w i t c h e s h o w e v e r , t h eb a s i cp a t t e r n sa n dt h e p e r f o r m a n c ea n a l y s i si n d e x e sr e m a i nu n c h a n g e d u pt od a t e ，t h eq u e u i n gt h e o r yh a s b e e nt h em o s to f t e ne m p l o y e da n a l y s i st o e l a st h et m 琦cf l o wi n t ot h en e t w o r ki s c o m p l i c a t e d ，s i m u l a t i o ne x p e r i m e n t sh a v es u b s t i t u t e dt h ec o n v e n t i o n a lm a t h e m a t i c a n a l y t i ca n a l y s i s i n h i g h - s p e e dn e t w o r k s ，t h e e f f e c to fs e r v i c e i n p u t sf r o m s e l f - s i m i l a r i t yo nt h ep e r f o r m a n c eo f t h eq u e u i n gs y s t e mi sap r o b l e my e tt ob es e t t l e d 3 c o n s i d e r i n gt h ed e s c r i p t i o no ft h et r a f f i cf l o wc h a r a c t e r i s t i c si nh i g h - s p e e d n e t w o r k s 。硒ep a p e rd e s c r i b e s 曲eb e h a v i o r so fs e l f - s i m i l a r i t yo ft h et r a f f i cf l o wi n h i 曲一s p e e dn e t w o r k sa n ds u m m a r i z e st h ev a r i o u sd e f m i t i o n sf o rs e l f - s i m i l a r i t y t h e d e f i n i t i o n sd e m o n s t r a t e ，f r o md i f f e r e n ta s p e c t s ，t h ed i f f e r e n tc h a r a c t e r i s t i e so ft h e s e l f - s i m i l a r i t yn a t u r e ，s u c ha st h eu n c h a n g e a b i l i t yu n d e rc h a n g e a b l et i m es c a l em e t r i c ， t h el o n g r a n g ed e p e n d e n c eo fr e c o r r e l e c tf u n c t i o n s ，t h eh e a v y t a i l e dd i s t r i b u f i o no f r a n d o md i s t r i b u t i o n1 a w s a sw e l la st h ep o w e rl a w sb yw h i c ht h ep o w e rs p e c t r u m d e n s i t ya b i d e 硼1 ec h a r a c t e r i s t i c ss h o wt h a tt h er a n d o m 衄m cf l o wm a k e st h e c o n g e s t i o nc o n t r o lac o m p l i c a t e dr a n d o mc o n t r o lp r o b l e m t h e r e f o r e i ti sa ni m p o r t a n t j o bt os e tu pap r o p e ra n a l y t i cm o d e lf o rt h ec o n t r o lo b j e c t si nt h ed e s i g no fc o n t r o l a l g o r i t h m s 4 t h ep r e d i c t i o no ft r a f f i cf l o wi sa ne f f e c t i v em e t h o df o rr e s o u r c ea l l o c a t i o n a c c u r a t ep r e d i c t i o nc a np r o v i d e sr e l i a b l ed a t at om a n a g e m e n ta p p r o a c h e so fd i f f e r e n t k i n d ss u c ha st h eb a n d w i d t ha l l o c a t i o no fa t mn e t w o r k , r e s u l t i n gi nb e t t e rn e t w o r k u t i l i z a t i o na n da b l et oa v o i dt h eo c c u r r e n c eo fc o n g e s t i o ne f f e c t i v e l y c o n c e r n i n gt h e n a t u r er e l a t i o nb e t w e e ns e l f - s i m i l a r i t ya n dc h a o s t h sp a d e l s t u d i e st h ec h a r a e t e r i s t i c s o fc h a o st i m es e q u e n c , ea t t r a c t o r s ，w h i c hc o n s i s to f3c o n s t a n tv a r i a b l e s ，i e ，t h e l y a p u n o ve x p o n e n tx ，t h ec o r r e l e c td i m e n s i o nd ，a n dt h ek o l m o g o r o ve n t r o p y i n a c c o r d a l i c e 谢t i l 也et h e o r yo fp h a s es p a c er e c o n s t r u c t i o nb yt a k e n sa n d 谢t ht h e d e f i n i t i o no ft h em a x i m u ml y a p u n o ve x p o n e n t ，t h i sp a p e rp r e d i c t st h er a t eo f s i m u l a t i o n ss e l f - s i m i l a rt r a 伍es o u r c e s 。a n ds u g g e s t sam a x i m u mp r e d i c t a b l et i m e p e r i o d ，w h i c hi ss i m p l ea n dh i g h l ye f f c c t i v e 5 g i v i n gad e e di n s i g h ti n t o a b r sf e e d b a c kc e n t r e lm e c h a n i s ma n di t s i m p l e m e n t a t i o na i g o r i t h r n sa sw e l l t h ea u t h o ri m p r o v e sas i m p l ea n de f f e c t i v ef l o w c o n t r o la l g o r i t h mw h i c hi sc a l l e dp h a n t o ma 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 p r e s e r v e s t h eo r i g i n a la l g o r i t h m sa d v a n t a g e s , s u c ha ss m o o t ha c c e s si n t on e w c o n n e c t i o n s t r o n gr o b u s t n e s sa n df m ef a i m e s s b e s i d e s ，i ti m p r o v e st h en e t w o r k s c a p a b i l i t yo fa v o i d i n gc o n g e s t i o nb ys e t t i n g v a r i o u sc o n g e s t i o nl e v e l sf o rw h i c h d i f f e r e n tc o n t r o lm e a s u r e sa r et ob et a k e n 6 s u g g e s t i n gap r e d i c t i o na l g o r i t h mb a s e do nt h em a x i m u ml y a p u n o ve x p o n e n ta n d p r e s e n t st h er e s u l to f s i m u l a t i o ne x p e r i m e n t s o nt h ei m p r o v e dp h a n t o ma l g o r i t h m 7 m a k i n g as u m m a r i z ef o rt h i sp a d e r , a n dl o o k i n gf o r w a r do f f u t u r er e s e a r c hw o r k k e y w o r d s ：c o n g e s t i o nc o n t r o l ，f e e d b a c kc o n t r o l ，q u e u i n gt h e o r y , s e l f - s i m i l a r i t y , c h a o s ，p r e d i c t i o n , s i m u l a t i o ne x p e r i m e n t s i v 1 绪论 1绪论 信息社会的高度发展推动着网络技术的发展。通信网络从传统的电话交换网 络，发展到数据分组交换网络、帧中继网络以及宽带综合业务数字网络 b i s d n ( b r o a d i n t e g r a t e ds e r v i c ed i g i t a ln e t w o r k ) 。作为通信网络的核心技术，交 换和传输的技术也经历了从固定的电路交换方式到存储转发的分组交换方式的重 大变化。这些重大变化带来的通信技术的发展在满足了人们不断增长的通信需求 的同时，也使得通信网络的协议层次结构和拓扑结构越来越复杂，因而网络设计 也面临着更多的难题。既要保证网络的平稳运行以及信息传输的可靠与安全，更 要使网络性能价格比达到最优，使得先进的网络技术在信息社会中获得更加广泛 的应用，并由此促进自身蓬勃的发展。在当今的高速网络中，业务种类不断增多， 业务数量也不断增大，这使得网络设计面临着更严峻的挑战。高速网络的拥塞控 制便是网络设计中众多的重要问题之一。 1 1 拥塞控制研究的意义 1 1 1 拥塞现象及其表征 拥塞是发生在通信网络中各节点处或通信链路上的一种业务量聚集现象。由 于一个实际的通信网络中每一个节点的存储容量和处理1 i e 力以及每一条链路的传 输能力是有限的，这就决定了网络可以运载的业务量是有限的。当外部输入的业 务量大于网络能处理的业务量，或者发端送出的业务量大于接受端可接受的业务 量，这时在网络节点处就会出现已经进入网络的业务量不能及时地被传送而同时， 后续的业务量又源源不断地到来而造成的业务量堆积现象。而且，即使外部输入 的业务量小于网络能处理的业务量，但由于网络拓扑结构以及网络内部各节点处 的设置不同，在网络的某些局部仍然会出现业务量聚集的现象，即拥塞发生了。 在这两种情况中，第二种情况更容易发生。这是因为，对于第一种情况可以采取 增加网络容量或通过简单的流量控制手段就可以解决了。面对于第二种情况的处 理则要复杂得多，它涉及到多方面的问题，如网络正常运行所依赖的一系列的通 信规程和网络内部的分层结构，以及进入网络的业务流量特性等等。因此，对这 种情况下拥塞的处理是一件困难的事情。它是人们研究的重点对象。 要清楚地认识拥塞现象以及定量地表征其特点，需要排队论的基本概念和理 论。实际上，排队理论是通信网络中交换系统性能分析与系统设计的个常用的 重庆大学博士学位论文 基础工具。从排队论的角度看，一个数据网络或互联网实质上就是一个由队列组 成的网络。每一个节点( 数据网络交换机、互联网路由器) 就是一个排队服务系 统。在此系统中，每一个输出信道上都维持着一个分组队歹俨。当分组到达和排队 的速率超过分组能够传输的速率时，没有及时传输出去的分组就在缓冲区中排队 等待。随着越来越多的分组进入缓冲区，排队的队列长度就会不停地增长而分组经 历的时延就变得越来越长。即使分组到达的速率小于分组传输的速率但当它接近 传输速率时，路由选择等因素也可能引起没有传输出去的分组在缓冲区中排队 并且队列长度也将会增长。这种队列长度的增长意味着分组在每一个节点经历时 延的增长。而由于任意一个队列的大小时有限的( 即缓冲池是有限的) ，当队列长 度持续增长时，队列最终一定会溢出，即分组开始丢失。 从上面的描述中，可以看出，一个网络发生了业务量的拥塞现象，通常会有以下 几个征兆： 最直接的反映是发生拥塞的节点的输出队列长度持续增长，以至缓冲区满。 从源站到目的站的个别数据单元的传输时延增加，以至可以观察到这段时 延比信号在正常情况下的固定传输时延长得多。 出现了分组的丢失。 相应于这些网络拥塞现象的表现，有很多的手段和数量化指标来检测网络的 拥塞。主要的一些数量指标是： 平均队列长度。 平均分组时延。 由于缺乏缓冲空间而被丢弃的分组的百分数( 丢失率) 。 超时重传的分组数。 分组时延的标准差等。 上述这些指标的上升都标志着拥塞的增长。此外，还可以通过设置不同的 门槛值来为拥塞状况划分出拥塞级别。 1 1 2 拥塞现象发生的主要原因 业务量的拥塞现象是一个复杂的现象，它涉及到诸多方面的因素。归结起来， 主要的有以下三个方面的原因： 资源共享技术。资源共享是分组交换技术的首要目的。这里的资源包括网 络宽带、缓冲池容量以及交换机的处理能力。资源共享的好处是充分利用了网络 资源，避免了电路交换技术固定线路的交换所带来的资源浪费。然而这一优点的 得来也是有代价的，那就是当共享的网络资源分配不恰当或不足以运载入网的业 在本章中使用广义的分组来表示分组交换网络中的分组、帧中继网络中的帧、a t m 网络中的信元或互 联网络中的i p 数据 2 1 绪论 务流量时，容易引发网络内部的拥塞现象。由此可以看出，网络资源的合理分配 与控制是一件与拥塞现象处理息息相关的重大课题。实践证明，它同时也是一个 难点。这种由控制网络运行的协议机制而引起拥塞发生的原因，是一种内在的原 因。 网络负载在网络结构上分布的不均匀性。由于通信网络结构在地理位置上 的分布性，各个地区产生的通信量受到当地政治经济因素的影响，它们的数量是 各不相同的。而网络控制措施是采用分布式控制，缺乏统筹安排，这就会出现网 络中的部分资源被过度利用而同时另外一部分资源却处于空闲状态。此时“量 满为患”的节点处就极易发生拥塞现象。这是一种外部原因。 如果说上述的内、外因是由于网络内部协议结构及其地理分布性所限定的 因素，那么，下面的原因就是另外一种性质的问题了。这就是入网业务流量类型 与特性的复杂性。在当代的高速网络中，网络业务量的种类繁多，并且具有各自 不同的特性和传输要求( 服务质量q o s ) 。从业务类型上看，有数据业务，如文 件传送、电子自5 件、传真等，这类业务的特点是间歇性与高突发性，它们对网络 时延不敏感但对丢失敏感；有多媒体业务，如各类话音、图像、视频业务，它们 往往具有强烈的自相关性，对时延敏感而对丢失不敏感；还有如交互图形或交互 计算应用，则对时延和丢失都很敏感。此外，不同的通信流具有不同的优先级， 如各种网络管理和控制信令所组成的分组流具有高的优先级。这些不同类型、不 同性质的通信流量严重地影响着网络拥塞现象的发生，也影响着网络的性能以及 网络的设计。人们往往希望网络具有较高的吞吐量和资源利用率，以及交换与传 输系统的较短的时延。对于网络设计，需要根据预期的性能来估计出交换机处理 能力、缓冲池大小和需要的链路容量等。所有这些，均需要对入网的业务流量有 比较清楚的了解与认识，也即需要对它们建立准确恰当的数学模型。然而，对网 络业务流量建立精确的数学模型被证明是一件困难的事情。目前，般采用概率 论、排队论、随机过程的基本理论以及比较新的研究成果即非线性科学的基础理 论来定量地描述这些网络流量。 从上述的这些分析中还可以初步地看出，盲目地扩充网络容量( 链路容量和 缓冲池大小以及交换机处理能力) 并不是一种有效的好方法，并且其费用昂贵。 网络的拥塞需要人们采用某些控制策略来处理。 1 。1 3 拥塞的危害性 拥塞现象产生的直接后果，一是拥塞的节点处缓冲区等待输出的分组队列长 度急尉增长，以至于发生溢出而导致分组丢失；二是网络传输分组的时延增加， 3 重庆大学博士学位论文 以至于无穷大，这样的后果在前面已描述过。但这决不是拥塞造成的最后后果， 相反，它们仅仅是开头。 如果不对这两种情况加以处理，网络的运行情形就会变得很糟糕。对于第 种情况，丢失的分组需要重传，则发送此分组的信源除了传送新的分组外还得重 传被丢弃的分组。这只会加剧下列情况：随着分组被重传，系统的负载增加，越 来越多的缓存交得饱和。当系统正尽力清除积压待发送的分组时，用户还在给系 统输入旧的和新的分组。在这种情况下，系统的有效传输几乎为0 。而且，由于 网络的每一个节点都管理着大量的队列。如果假设某节点处发生了严重的拥塞现 象导致缓冲区耗尽，在某种流量控制机制的作用下，此节点会阻止从相邻节点到 来的分组流量，使得这些分组被储存在相邻节点的缓冲区，这就可能引起上游节 点的输出缓存空间耗尽。于是，网络中某一处的拥塞可以很快地扩散到一个地区 或整个网络。严重时整个网络会全体瘫痪。 对于第二种情况，分组时延的无限增加，也会造成如上所述的种种恶果。不 仅如此，某些对时延敏感的网络业务类型，其分组时延的增加是不允许的。比如 它携带了一个设定的生存时间信息，超过生存时间此分组就变得无效了。因而网 络的有效运输实际上是降低了。 从以上分析可看出，要使两络能够正常地稳定地运行，捅塞控制是必不可少 的手段。实际上，拥塞控制是各种数据网络以及互联网所面临的一个关键的设计 问题。下面的图1 1 描述了在一个实际网络( 指有限缓存) 中不实施拥塞控锚酌 灾难后果与实施后的结果比较。 d 曾 悼 输入负载 图t 1 两终吞吐量的变化趋势匿 1 1 4 拥塞控制综述 前面分折了通信掰络据塞现象的表现、发生拥塞的主要原因及其严重的薅果， 4 1 绪论 从中可以看出，对拥塞进行控制是通信网络设计面临的一个必不可少而且十分重 要的环节。由于拥塞现象的随机性与遍及性，拥塞控制是一个全局性问题，它涉 及到网内所有主机、节点交换机( 路由器) 、交换机中存储转发的过程以及所有其 他减少网络运载能力的因素，因而对拥塞的控制应该是一个策略性问题。对于实 际运行的各种各样的通信网络，人们已经设计并且实现了多种拥塞控制策略。在 早期的基于电路交换的电话网络中，人们设计了立接制( 或损失制) 交换系统， 它对拥塞的处理直截了当，即当交换机的出线全忙时就简单地拒绝新到来的呼叫， 这样显然就损失了不少的业务量。以后改进为缓接制( 或等待制) 系统，即真正 意义下的排队系统，它对拥塞的处理就是在交换机系统内部设计了一个适当大小 的缓冲区( 即排队室) ，当交换系统全忙时，新到来的呼叫在排队室等待。一旦某 个结束了服务的呼叫释放出交换线路，排队室中等待的呼叫立即请求连接并接受 服务( 占有出线) 。 随着通信技术与计算机技术的不断融合，交换技术与传输技术得到了发展， 出现了基于存储转发技术的分组数据网。各个数据网根据不同的网络体系结构而 采用不同的拥塞控制方法。 在基于x 2 5 的分组交换网络中，由于它是种面向连接的网络，它采用的是 一种简单的通过控制分组的流量而实现控制拥塞的方法。由于此方法产生的效果 类似于流过管道的流体产生的反压现象，称之为反压技术。它使用的是反向逐跳 ( 从一个节点到上一个节点) 流量控制的手段。当某个站点正发生拥塞时( 缓存 空间已满) ，此站点就采用反压技术使来自其相邻站点的分组流减慢或停止。对全 网而言，这一流量限制措施的持续作用，最终将反向( 相对于数据流动的方向而 言) 传播到各个信源，这些信源就会减少新的分组流进入网络，从而缓解了网络 的拥塞，达到了拥塞控制的目的。 帧中继网络采用隐式信令控制方法( 如l a p f 控制协议包含这一功能) 。源站 通过检测传输时延的增加以及分组的丢失而间接地推测到网络发生了拥塞。基于 隐式信令的拥塞控制是由端系统单独完成的，不需要网络其他节点( 如交换机或 路由器) 的参与。也有采用显式信令的拥塞控制方法，网络( 交换机完成的功能) 检测正在形成中的业务量拥塞并将此拥塞信息通过显式的信令向端系统发出警 告。在这两种控制方法中，端系统都会采取措施降低对网络的供给负荷。i t i 卜_ t 和a n s i 认为同时使用二者技术能够相互补充，共同完成完整的拥塞控制功能。 在基于i p 的i n t e m e t ( 因特网) 中，早先采用种比较原始的控制方法，如因特 网控制报文协议i c m p ( i n t e r a c tc o n t r o l m e s s a g ep r o t o c 0 1 ) 中的“源站抑制” ( s o u r c e q u e n c h ) 分组，称为阻流分组，是网络中的拥塞节点产生的控制分组。 它被传回信源节点以便限制更多的通信流量进入网络。当路由器由于缓存溢出而 5 重庆大学博士学位论文 不得不丢弃p 数据报文或系统缓存将要满，而它预计到要发生拥塞时就向源端系 统发送这个报文来要求源端系统减少向目的站的数据发送率。一旦收到一个源站 抑制报文，源站主机就降低其对特定目的站的发送速率，直到它不再收到源站抑 制报文为止。此外，目的端系统也可以发送抑制报文。以后又采用了基于隐式信 令的拥塞控制策略。隐式信令在无连接或数据报方式的网络中是一种有效的拥塞 控制方法。为了更好地实施拥塞控制，人们通过在t c p 窗口式流量控制机制中增 添新功能来发展了隐式信令控制技术。由于在i n t e r n e t 协议层次中，互联网层次 上没有逻辑连接的概念，因此不能以连接为单位来管理流量。但在两个端系统之 间有t c p 层的逻辑连接。t c p 中除了包括对收到的报文段进行确认的机制外，还 包括了以t c p 连接为单位的管理数据流量的机制。通过在t c p 报文中设置拥塞 窗口，人们将拥塞控制功能添加到了t c p 窗1 2 式流量控制机制中。于是，端系统 在传输层( t c p 层) 上也能使用显式信令的流量控制技术了。此外，采用最优最 短路径的路由选择策略来平衡网内的业务流量，或避开拥塞的路由器，也是 i n t e m e t 中常用的拥塞控制手段。 图1 2 综合地反映了各种控制方法的设计思想。 图1 2 各种拥塞控制机制 在以异步传输模式a t m 为交换和传输技术的网络中( 以后都称之为a t m 网 络) ，采用的是基于速率的显式拥塞信令的方法。显式信令技术是种复杂的，需 6 1 绪论 要交换机( 路由器) 设置相应功能才能完成的技术。显式技术要实现的目标是既 要充分利用可用的网络资源，又要以公平的方式对拥塞做出及时的反应以便控制 拥塞。 从显式技术的实现过程看，它对拥塞的控制实际上要分为两个阶段。一是拥 塞避免阶段。它适用于拥塞的初期，交换机通过对缓冲区中队列长度增长情况的 观察，启动某种显式的信令机制来触发对拥塞的避免过程。如由网络交换机向端 系统警告拥塞正在增长的情况。而端系统则采取措施减轻其输出负载。二是拥塞 恢复阶段。这是在面临比较严重的拥塞( 如分组己开始丢失) 时防止网络崩溃的一 个控制过程。 本文研究了a t m 网络中的拥塞控制问题。重点研究了a b r 服务类型的反馈 式控制机制。关于a t m 网络中的拥塞控制问题，a