（计算机应用技术专业论文）tcpip拥塞控制策略研究.pdf

硕士学位论文 m a s t e r st h e s i s 摘要 进入九十年代以来，以i p 为基础的i n t e r n e t 呈爆炸式增长，新型网络应 用不断涌现，用户数量迅速增加，使i n t e r n e t 的流量急剧增加，由此而引发的 网络拥塞已经成为制约网络发展和应用的瓶颈问题。拥塞容易造成传输延迟 和吞吐量等q o s ( q u a l i t yo fs e r v i c e ) 性能指标下降，严重影响了带宽、缓 存等网络资源的利用率，因此有效地解决拥塞问题对于提高网络性能具有重 要意义，如何更好地预防和控制拥塞一直是近年来国际上网络研究领域的热 点问题。 目前i n t e r n e t 仅提供单一的“b e s te f f o r t ”服务，其资源分配主要在用 户端进行，利用传输控制协议( t c p ) 进行端到端的拥塞控制，可以说，i n t e r n e t 的成功在很大程度上依赖于t c p 拥塞控制机制的有效执行，但是由于i n t e r n e t 的发展及t c p 拥塞控制算法本身存在的问题，使得现有的拥塞控制策略在很 多方面已经不能满足人们的需求。研究表明，t c p 拥塞控制实质上是一种较保 守的策略，它并非在所有的网络条件下都能保证其良好的性能。 i n t e r n e t 中传统的路由器通常采用先来先服务的调度算法以及“弃尾”缓 冲管理方法，在指示和控制拥塞方面不提供任何显式的支持。由于在路由器 中引入相应的拥塞控制机制，使网络本身参与资源的控制工作可以更有效地 实现对拥塞的监测和预防，因此近几年i p 拥塞控制策略成为当前网络研究的 一个热点，e t f ( i n t e r n e t 工程任务组) 建议在i n t e m e t 路由器上采用主动队 列管理机制作为i p 层参与拥塞控制的手段，随机提前检测( r e d ) 算法是i e t f 推荐的一种主动队列管理算法。 本文首先概要介绍了i n t e r n e t 中的拥塞现象产生的背景、原因以及实施 拥塞控制的必要性，探讨了拥塞控制策略的研究与发展现状，从不同角度对 拥塞控制机制进行了分类，并分析了当前拥塞控制中存在的问题。 本论文的研究工作得到国家“9 7 3 ”项目( 批准号：2 0 0 3 c b 3 1 4 8 0 4 ) 和国家自然科 学基金( 批准号：6 0 1 7 4 0 4 3 ) 的资助。 硕士学位论文 m a s t e r st h e s i s 第二章着重研究了i n t e r n e t 中t c p 的基于窗口的端到端拥塞控制方法以 及i p 层采用的拥塞控制机制。首先对t c p 基于滑动窗口的拥塞控制机制的四 个核心算法：慢启动、拥塞避免、快速重传和快速恢复进行了详细阐述，讨 论了当前的各种t c p 拥塞控制改进方案，如n e w r e n o 、s a c k 、t c p v e g a s 等。然后对i n t e r n e t 路由器采用的“弃尾”算法及其存在的问题进行了分析， 介绍了主动队列管理机制的思想，讨论了当前业界在i p 拥塞控制方面所做的 相关工作，并重点分析了r e d 及其相关算法。 在保证网络稳定和不发生拥塞的基础上，公平性是算法设计的另个重要 的性能指标。因此，在第三章我们根据网络层显示拥塞指示技术支持，提出一 种公平窗口算法，使该算法在i p 网络中得以实现。仿真结果证明，此算法在 多瓶颈网络环境下能使t c p 流达到较好的公平性。 在第四章中，我们探索了d r e d ( d y n a m i c r e a d o me a r l yd e t e c t i o n ) 方案 的队列稳定性，并根据控制理论和控制参数优化的仿真实验提出了一种优化 的参数选择方法，从理论上给出了系统稳定的参数选择范围，有效地解决了 以前对r e d 参数选择的盲目性、随机性和不确定性的问题。而且根据对所进 行的理论分析，通过仿真实验验证所提算法的有效性。 在上一章研究的基础上，我们在这一章进一步对主动队列管理算法 p d c o n t r o l l e r 的参数选择进行探讨。尽管最近提出的比例、差分随机早期预测 ( p d r e d ) 机制改进了网络性能，但和其他的r e d 机制一样，仍然存在一个 关键的问题：参数调整的问题。而选择适当的控制参数使动态队列达到稳定对 任何一个r e d 机制来说都是非常重要的。因此，本章利用t c p 动态流量模型 和现代控制理论对主动队列管理机制稳定性进行了分析，从理论上给出了系统 稳定时的参数选择范围。而且通过仿真对所讨论的参数选择方法进行了验证， 仿真结果表明：所提出的参数优化方法很好的保证了系统稳定性，改进了主动 队列管理机制的网络性能。 在第六章中，我们推导出a v q 方案的显示的稳定性条件，对文献 5 3 中 的方案进行了扩展，提出了一种简单、实用的参数调节方案。而且，我们还 通过仿真实验进一步证实了所提方案能更有效地使队列长度趋于稳定，具有 硕士学位论文 m a s t e r st h e s i s 较好的网络性能。 第七章提出了一种新的基于比例差分控制( p r o p o r t i o n a la n dd i f f e r e n t i a l c o n t r 0 1 ) 的自适应虚拟队列管理( a v q ) 算法一p d a v q ，用于对网络链路中 产生的拥塞进行控制，以达到有效利用网络带宽，使整个网络系统达到稳定， 缓解网络拥塞的目的。而且本章对所提算法运用控制理论对系统的稳定性进 行了证明，给出了满足系统稳定性条件的参数选择方法和p d a v q 算法的具 体描述。最后，通过仿真实验与现有的a v q 算法比较，结果表明：所提p d a v q 算法具有较高的吞吐率、较低的链路延迟和数据丢失率，并能更快的使整个 网络系统达到稳定，具有较好的网络性能。 总之，本文在t c p i p 网络的拥塞控制策略方面进行了探索，希望能够对 拥塞控制策略的发展起一定的推动作用。 关键词：拥塞控制，t c p i p 协议，公平性，r e d ，p d r e d ，e c n ，d y n a m i cr e d ， a v o ( a d a p t i v ev i r t u a lq u e u e ) ，p d a v q ，稳定性，r o u t h h u r w i t z 稳 定性规则，n s 2 硕士学位论文 m a s t e r st h e s i s a b s t r a c t i n t e r n e th a se x p e r i e n c e da ne x p l o s i v e l yg r o w t hs i n c e1 9 9 0 s w i d e s p r e a du s e o fc o m p u t e rn e t w o r k s ，a sw e l la st h ea p p e a r a n c eo fv a r i e dn e t w o r ka p p l i c a t i o n s h a sb r o u g h tf o r t hn e t w o r k c o n g e s t i o na sas i g n i f i c a n tp r o b l e m c o n g e s t i o no f t e n r e s u l t si nt h ed e c l i n eo fq u a l i t yo fs e r v i c e ( q o s ) s u c ha st r a n s m i s s i o nd e l a ya n d t h r o u g h p u t ，w h i l et h en e t w o r kr e s o u r c eu t i l i z a t i o nl i k eb a n d w i d t ha n db u f f e r sa r e a l s oa f f e c t e ds e r i o u s l y t h e r e f o r e ，i ti si m p o r t a n tt os o l v et h ec o n g e s t i o np r o b l e m e f f e c t i v e l y f o r i m p r o v i n g n e t w o r k p e r f o r m a n c e h o w t oa v o i da n dc o n t r o l c o n g e s t i o ni so n eo f t h em o s ta c t i v ef i e l d si nt h ec o m p u t e rn e t w o r k s c u r r e n tt c p i pn e t w o r k so n l yp r o v i d eb e s te f f o r ts e r v i c e sa n dt h e i rr e s o u r c e s a l l o c a t i o ni s m a i n l y o ne n dh o s t s t h ee n dh o s t su s et r a n s m i s s i o nc o n t r o l p r o t o c o l ( t c p ) t oi m p l e m e n t e n d t o e n dc o n g e s t i o nc o n t r 0 1 i tc a nb es a i dt h a tt h e s u c c e s so ft o d a y si n t e m e t p r i m a r i l yr e l i e so nt c pc o n g e s t i o nc o n t r o lm e c h a n i s m s w i t ht h ed e v e l o p m e n to fi n t e r n e ta n dt h ep r o b l e m si nt h ei m p l e m e n t a t i o no ft c p , t h ec u r r e n tt c p s t r a t e g i e s c o u l d n tm e e tv a r i o u sd e m a n d so fu s e r sa n yl o n g e r m o r ea n dm o r er e s e a r c h e si n d i c a t et h a tt h et c p c o n g e s t i o nc o n t r o lm e c h a n i s m s ， w h i l e n e c e s s a r ya n dp o w e r f u l ，a r es u b s t a n t i a l l yc o n s e r v a t i v ea n d a r en o ts u f f i c i e n t t op r o v i d eg o o ds e r v i c ei na l lc i r c u m s t a n c e s t h et r a d i t i o n a lt e c h n i q u ef o rm a n a g i n gr o u t e rq u e u ei ni n t e r n e tu s u a l l ya d o p t s f i r s ti nf i r s to u tf f i f o ) s c h e d u l i n ga n d “d r o pt a i l ”q u e u em a n a g e m e n ta l g o r i t h m s ， w h i c hh a v en o p r o v i s i o nf o rt h ed e t e c t i o no fi n c i p i e n tc o n g e s t i o nw h e n t h eq u e u e i sf u l l i nf a c t ，i tw i l lb em o r ee f f e c t i v ef o rd e t e c t i n ga n dp r e v e n t i n gc o n g e s t i o ni f t h er o u t e r s p e r f o r mc o n g e s t i o n c o n t r o l s t r a t e g i e s ，s o i p c o n g e s t i o n c o n t r o l s t r a t e g i e s h a sb e e nd i s c u s s e d w i d e l y i nr e c e n t y e a r s t h ei e t f ( i n t e r n e t e n g i n e e r i n gt a s kf o r c e ) h a sp r o p o s e dt h e s o l u t i o nb yd e p l o y i n ga c t i v eq u e u e m a n a g e m e n t i ni n t e r n e tr o u t e r s i nt h i s p a p e r , c h a p t e ro n e 百v e s ag e n e r a li n t r o d u c t i o nt ot h en e t w o r k c o n g e s t i o nc o n t r 0 1 f i r s tt h eb a c k g r o u n da n dt h ec a u s eo f n e t w o r kc o n g e s t i o na r e j ” 硕士学位论文 m a s t e r st h e s i s i n t r o d u c e d ，a n dt h e nt h en e c e s s i t yo fi m p l e m e n t i n gc o n g e s t i o nc o n t r o li sa n a l y z e d w ea l s od i s c u s st h er e s e a r c ha n d d e v e l o p m e n t o f c o n g e s t i o n c o n t r o ls t r a t e g i e s ，a n d c l a s s i f y t h e mf r o md i f f e r e n t a s p e c t s f i n a l l ye x i s t i n gp r o b l e m s i nc u r r e n t c o n g e s t i o nc o n t r o la r ep r o p o s e d i nc h a p t e rt w ow ef o c u so nt c pe n d - t o e n dc o n g e s t i o nc o n t r o ls t r a t e g i e sa n d t h em e c h a n i s m si m p l e m e n t e di ni pr o u t e r s f i r s tt h ef o u rk e r n e la l g o r i t h m so ft c p c o n g e s t i o nc o n t r o la r ed e s c r i b e d ，a n dt h ei m p r o v e ds c h e m e ss u c ha sn e w r e n o ， s a c ka n dt c p v e g a sa r ed i s c u s s e d e i t h e r t h e nw ei n t r o d u c e “d r o pt a i l ” a l g o r i t h ma n d t h ep r i n c i p a li d e ao fa c t i v eq u e u em a n a g e m e n t f i n a l l yw ed i s c u s s t h er e l a t e dw o r k si ni pc o n g e s t i o nc o n t r o l ，i nw h i c hr e da n de c n a l g o r i t h ma r e e m p h a s i z e d w h e nn e t w o r k s t a b i l i t y a n d c o n g e s t i o n n o n o c c u r r e n c e a r e g u a r a n t e e d ， f a i r n e s si sa ni m p o r t a n tp e r f o r m a n c ei n d e xo ft h en e t w o r k t h e r e f o r e ，an e wf a i r w i n d o wa l g o r i t h mi sp r o p o s e di nt h et h i r dp a r ta n di sr e a l i z e di ni pn e t w o r ki n s u p p o r to fe c n m e c h a n i s mi nn e t w o r kl a y e r t h es i m u l a t i o nr e s u l td e m o n s t r a t e s t h a tr e m a r k a b l ef a i r n e s sa m o n gt c pd a t af l o wi nt h em u l t i p l eb o t t l e n e c kn e t w o r k c a nb ea c h i e v e dw i t ht h ea p p l i c a t i o no ft h i sa l g o r i t h m b a s e do nc o n t r o lt h e o r y , c h a p t e rf o u rp r o v i d e sg u i d e l i n e sf o rt h es e l e c t i o no f t h ec o n t r o lg a i nf o rd y n a m i c - r e dt os t a b i l i z eac o n g e s t e dq u e u ea tat a r g e ta n d h e n c et o i m p r o v en e t w o r kp e r f o r m a n c e s i m u l a t i o n s d e m o n s t r a t et h a ti n d e e d s a t i s f a c t o r yp e r f o r m a n c ec a nb e a c h i e v e di ft h ec o n t r o lg a i ni ss e l e c t e db a s e do n t h e g u i d e l i n e s o nb a s i so ft h es t u d yo ft h ea b o v ec h a p t e r , w ef u r t h e re x p l o r et h ec o n t r o lg a i n s e l e c t i o no fa n o t h e ra q m ( a 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 - - p dc o n t r o l l e r t h o u g h t h er e c e n t l yp r o p o s e dp r o p o r t i o n a la n dd i f f e r e n t i a lr a n d o me a r l yd e t e c t i o n r p d r e d ) s c h e m eh a s b e e nu s e di n e n h a n c i n g t h e p e r f o r m a n c e o fq u e u i n g n e t w o r k s ，o n ek e yi s s u ei na p p l i c a f i o n so ft h i ss c h e m ea sw e l la so fo t h e rr e d v a r i a t i o n si st h es o c a l l e dp a r a m e t e r t u n i n gp r o b l e m t h eg u i d e l i n eo i lc h o o s i n g c o n t r o lg a i n st om e e tt h es t a b i l i t yc o n d i t i o no fq u e u ed y n a m i c i sv e r yi m p o r t a n ti n d e s i g n i n go fa n yr e ds c h e m e i n t h i s c h a p t e r , t h es t a b i l i t y o fp d _ r e di s 硕士学位论文 m a s t e r sn e s i s a n a l y z e db yu s i n gt c pd y n a m i cm o d e la n dc o n t r o lt h e o r y t h eg u i d e l i n e o f c h o o s i n g t h ec o n t r o lg a i n si sg i v e na n da n a l y z e dt h e o r e t i c a l l y f i n a l l y , w ep e r f o r m s i m u l a t i o n sb yn ss i m u l a t o rt ov e r i f yt h ee f f e c t i v e n e s so ft h ep r o p o s e dm e t h o d t h es i m u l a t i o nr e s u l t sd e m o n s t r a t et h a tt h ep r o p o s e dm e t h o di s s a t i s f a c t o r yf o r g u a r a n t e e i n gt h es t a b i l i t yo fd y n a m i cq u e u ea n di ti st h u su s e f u li ne n h a n c i n g t h e n e t w o r kp e r f o r m a n c ei na c t i v eq u e u em a n a g e m e n t ( a q m ) i nc h a p t e rs i x ，w e p r o p o s e a s i m p l e ，s c a l a b l e ，p r a c t i c a la n ds y s t e m a t i c r u l ef o r t u n i n gt h ec o n t r o lp a r a m e t e ro ft h ea d a p t i v ev i r t u a lq u e u e ( a v q ) a c t i v eq u e u e m a n a g e m e n ts c h e m e a ne x p l i c i ts t a b i l i t y c o n d i t i o no fa v qi s p r o p o s e du s i n g c l a s s i c a lc o n t r o lt h e o r y t h e o r e t i c a la n a l y s e sa sw e l la ss i m u l a t i o nr e s u l t sa r eu s e d t ov a l i d a t et h er e s u l t t h e n ，i nc h a p t e rs e v e nw ep r o p o s ean o v e la d a p t i v ev i r t u a lq u e u e ( a v q ) a l g o r i t h mt h a ti sb a s e do nt h ep r o p o r t i o n a la n dd i f f e r e n t i a lc o n t r o lm e c h a n i s m w et e r mt h i sa l g o r i t h mp d a v q i ti su s e dt oa v o i dc o n g e s t i o no fn e t w o r k l i n ka n d t oa c h i e v et h eg o a lo fu t i l i z i n gt h el i n kc a p a c i t ye f f e c t i v e l ya n dr e l i e v i n gt h e n e t w o r kc o n g e s t i o n f u r t h e r , w es t u d yt h es y s t e ms t a b i l i t yu s i n gc o n t r o lt h e o r y ， p r e s e n tt h es t a b i l i t ya r e ao fc o n t r o lg a i n sa n dd e s c r i b et h ei m p l e m e n t a t i o no f t h e p r o p o s e da l g o r i t h m i nd e t a i l f i n a l l y , w ec o m p a r et h ep r o p o s e da l g o r i t h mw i t ht h e k n o w na v q a l g o r i t h mb ys i m u l a t i o n s t h es i m u l a t i o nr e s u l t s d e m o n s t r a t et h a t e x c e l l e n tp e r f o r m a n c ei sa c h i e v e dw i t hh i g h e rl i n ku t i l i z a t i o n ，l o w e r l i n kd e l a y , a n dl o w e rl o s sr a t eb y s t a b i l i z i n gt h e w h o l e s y s t e m m o r e q u i c k l y i ns u m m e r y , t h i sp a p e rd o e ss o m er e s e a r c hi nt h et c p i pn e t w o r kc o n g e s t i o n c o n t r o lf i e l d s ，a n dw eh o p ei t c o u l d p r o m o t et h ed e v e l o p m e n to fc o n g e s t i o n c o n t r o ls t r a t e g i e s k e yw o r d s ：c o n g e s t i o nc o n t r o l ，t c p f l pp r o t o c o l ，f a i r n e s s ，r e d ( r a n d o m e a r l yd e t e c t i o n ) ，p d _ r e d ，e c n ，d y n a m i cr e d ，a v q ，p d a v q ， s t a b i l i t y , r o u t h h u r w i t zs t a b i l i t yr u l e ，n s 2 硕士学位论文 m a s t e r st h e s i s 华中师范大学学位论文原创性声明和使用授权说明 原奄d 性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，独立进行研究 工作所取得的研究成果。除文中已经标明引用的内容外，本论文不包含任何其 他个人或集体己经发表或撰写过的研究成果。对本文的研究做出贡献的个人和 集体，均已在文中以明确方式标明。本声明的法律结果由本人承担a 作者签名 日期：年月 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校 有权保留并向国家有关部门或机构送交论文的复印什和电子版，允许论文被查 阅和借阅。本人授权华中师范大学可以将本学位论文的全部或部分内容编入有 关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位 论文。 作者签名： 日期：年月 目 导师签名： 日期：年 月 日 本人已经认真阅读“c a l i s 高校学位论文全文数据库发布章程”，同意将本 人的学位论文提交c a l i s 高校学位论文全文数据库”中全文发布，并可按“章 程”中的规定享受相关权益。回重迨塞逞套匿进卮! 亘堂生；旦二生；亘三生 蕉查! 作者签名： 日期：年月 目 导师签名： 日期：年月 日 硕士学位论文 m a s t e r st h e s i s 第一章绪论 本章首先介绍了i n t e r n e t 中存在的网络拥塞现象及其产生的本质，然后 介绍了拥塞控制策略的发展及研究现状，分析了目前存在的问题，并在此基 础上指出了本文所做的主要工作及组织结构。 1 1 引言 近年来，网络技术的发展日新月异，网络规模迅速扩大，特别是进入九 十年代后，以i p 为基础的i n t e r n e t 呈爆炸式增长，已经逐渐发展成为全球 性的信息基础设施，随着新型网络应用的不断涌现和用户数量的迅速增加， 使得i n t e r n e t 的流量急剧增长，其中除了传统的w w w 、f t p 、t e l n e t 等数据 流外，还出现了大量的实时多媒体数据流，由于网络中不同的数据流在路由 器处交汇，因而给网络的路由节点造成很大的负担，越来越严重的网络拥塞 问题逐渐暴露出来。 在网络通信中，拥塞容易造成延迟和吞吐量等q o s ( q u a l i t yo fs e r v i c e ) 性能指标下降，是影响带宽、缓存等网络资源利用率的关键因素，因此有效 解决拥塞问题对于提高网络性能具有重要意义。网络产生拥塞的根本原因是 用户提供给网络的负载大于网络资源容量和处理能力，在i n t e r n e t 中，存储 空间不足、通信信道带宽容量不足、处理机处理能力较弱等都是产生拥塞现 象的直接原因 8 7 ，但是无论增加缓存容量或是提高处理器及链路的速度都 不能从根本上解决问题，相反，某些情况下甚至可能会进一步加剧拥塞。网 络中发生拥塞后如果不加以控制，往往会导致恶性循环，这时如果路由器没 有空余的缓存空间，它就必须丢掉新到的数据包，当数据包丢弃时，源端可 能会因为超时而重传此包，由于源端在未收到确认之前不能丢弃数据包，相 应的缓存不能释放，使缓存进一步消耗，导致拥塞加重，在网络流量非常高 的情况下，网络甚至会完全瘫痪，几乎没有数据包能够送达接收方。网络拥 塞已经成为制约网络发展和应用的一个瓶颈，如何更好地预防和控制拥塞一 直是近年来网络研究的热点问题。 硕士学位论文 m a s t e r st h e s i s 拥塞控制的主要目标是控制进入网络的数据流量，保证通信予网不会被 用户发送的数据流淹没，合理地使用瓶颈资源。直观上，解决网络拥塞可以 从两方面入手，一是拥塞避免，即尽量避免拥塞的发生，使网络运行在最佳 状态；一是在拥塞发生后采取补救措施消除拥塞。完全避免网络拥塞必然会 以牺牲网络的资源利用率为代价，在追求公平、高效、高利用率的网络环境 下，采取这种保守的方法显然是不适宜的，因此，采用拥塞避免与拥塞控制 相结合的方法更为合理。拥塞控制策略主要由反馈机制和控制机制两个部分 组成，网络通过反馈机制向源端或目的端通告它的当前状态，端系统则根据 接收到的反馈信息，利用控制机制完成对负载的调整，达到消除拥塞的目的 1 。 拥塞控制可以在网络协议的各个层次上实施。由于数据链路层靠近拥塞 的发生点，所以在数据链路层进行控制可以快速响应拥塞，但它只能对短期 的拥塞现象进行控制，一般来说，不同网络层次中的控制机制具有不同的目 标，拥塞现象持续的时间越长，实现控制的层次也应该越高，明确的拥塞控 制主要在网络层和传输层实现。 1 2 拥塞控制策略的研究与发展 目前在i n t e r n e t 中以数据包的丢失作为拥塞信号，当路由器缓冲区满后， 就会丢弃随后到达的数据包，这时源端根据超时等隐含的网络信号推测到网 络发生了拥塞，然后调整发送方的拥塞窗口以减少注入网络的流量 2 。由于 i n t e r n e t 上9 5 的数据流使用的是t c p i p 协议 3 ，因此t c p i p 拥塞控制受 到了广泛的关注。 早期t c p 的实现只是使用累计确认、超时重传和后退n ( 源端检测到拥 塞时，重传从丢失数据包开始一直到检测到丢包时所发送的全部数据包) 等 机制，对于网络拥塞几乎没有进行什么控制。拥塞控制的研究开始于8 0 年代 中期，1 9 8 4 年，n a g l e 首次指出了复杂t c p i p 网络中存在的拥塞问题，特别 是在由路由器连接的带宽差异较大的网络中，容易发生“拥塞崩溃”现象【4 】， 但在科研界没有引起足够的重视。直到1 9 8 6 年1 0 月，i n t e m e t 首次出现了一 2 硕士学位论文 m a s t e r st h e s i s 系列的拥塞崩溃现象，网络吞吐量急剧下降，其间从i j 3 l 到u cb e r k e l e v 的 数据流量从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 中增加了拥塞控制算法f 即t c p t a h o e ) ，于1 9 8 8 年提出了著名的“慢启动”( s l o ws t a r t ) 、“拥塞避免”( c o n g e s t i o n a v o i d a n c e ) 算法、“快速重传”( f a s tr e t r a n s m i t ) 【2 ；1 9 9 0 年的t c pr e n o 版本增加了m 陕速恢复”( f a s tr e c o v e r y ) 算法，避免了网络拥塞不够严重时采 用漫启动”而造成大幅度减小发送窗口尺寸的现象。上述四个算法是当前 i n t e r n e t 上主要使用的端系统拥塞控制机制，当网络出现拥塞时，t c p 连接通 过丢包发现拥塞，调整发送窗口，降低发送流量，t c p 拥塞控制机制在i n t e r n e t 中的执行有效地避免了拥塞崩溃现象的发生。 在i n t e r n e t 中，i p 层在指示和控制拥塞方面不提供任何支持，传统的路 由器采用先来先服务( f i f o ) 的调度算法，使用“弃尾”( d r o pt a i l ) 算法 实现缓冲管理，弃尾算法是指在发生拥塞时路由器缓冲区溢出而丢弃队列尾 部的数据包。在复杂的网络环境中，由源端发送到目的端的数据包要经过多 个中间节点( 路由器) ，每个中间节点需要为其分配资源并将其转发到下一 站，如果数据包在到达目的地之前丢弃，则在传输过程中消耗的所有资源都 被浪费，这样无疑造成了网络资源利用率的降低。随着i n t e r n e z 的规模不断 扩大，新的网络应用不断出现，仅仅寄希望于所有应用都实现端到端的拥塞 控制是不现实的，网络本身必须采用某种手段参与拥塞控制，由于路由器是 i n t e r n e t 的核心部件，也是网络拥塞状态的最直接的感受者，所以由i p 层参 与资源的控制工作，在路由器中引入相应的拥塞控制机制更能有效地对拥塞 进行监测和预防。因为路由器无法提前预测通信流量，它通过检测当前负载 来要求端系统增加或减少注入网络的流量，所以在路由器处引入拥塞控制应 作为对端系统拥塞控制机制的补充并与之协作。近几年关于i p 层拥塞控制的 研究逐渐增多，形成了个新的研究热点。 随着i n t e r n e t 的发展和网络带宽的提高，数据流量急剧增加，同时数据 流的本质也开始发生变化。基于u d p ( u s e rd a t a g r a mp r o t o c 0 1 ) 协议的实时 多媒体应用如i p 电话、视频会议等开始成为网络中的重要应用，由于这些数 硕士学位论文 m a s t e r st h e s i s 据流不遵守t c p 协议，如果它们不能对网络拥塞做出正确响应，将会使网络 面临拥塞崩溃的危险。例如当基于u d p 的应用和基于t c f 的应用共享网络时， 由于u d p 没有端到端的拥塞控制机制，接收方并不反馈信息给发送方，这样 发送方始终以固定的速率发送数据，导致u d p 数据流占用的带宽越来越多， 当t c p 检测到网络拥塞时，t c p 发送方会将发送速率减半，如果t c p 不断检测 到拥塞，t c p 发送方就会不断降低发送速率，甚至可能导致拥塞崩溃。基于 u d p 协议的t c p 友好拥塞控制是当前拥塞控制研究中的开放问题。另外，目前 已有越来越多的移动用户通过无线网络接入i n t e r n e t ，卫星网络也以其独特 的覆盖面广、通讯费用与距离无关等特点而成为必不可少的一种传输手段， 由于无线通信和卫星网络固有的特点，使得拥塞控制的研究更加困难，极具 挑战 8 7 8 9 。 1 3 拥塞控制算法分类 我们对拥塞控制算法从以下几个角度分类： ( 1 ) 从控制论角度出发，可以分为开环控制和闭环控制 5 ，前者又称 为预防式控制，它事先设计一个好的网络，确保它不会发生拥塞，而网络一 旦运行起来，就不再采取措施，这类控制机制较适用于音频和活动图像业务。 而对于复杂的网络系统来说仅有开环控制是不够的。闭环控制，又称为反应 式控制，能够使得网络中的拥塞状态信息( 反映了系统资源的占用情况) 能及 时反馈至端系统，从而调整端系统的数据传输速率，这样既保证了传输质量 又能充分利用网络资源。 ( 2 ) 从实施控制的类型上，拥塞控制可以分为基于窗口( w i n d o w b a s e d ) 和基于速率( r a t e b a s e d ) 两种类型。t c p 采用的是典型的基于窗口的控制方 式，t c p 通过调整滑动窗口的大小控制发送到网络的数据量，基于窗u 的控制 易于实现，并且可以限制注入网络的最大流量；基于速率的控制方式则是通 过每秒发送的比特数来控制数据流的发送，如果传输速率能够匹配网络可用 带宽，就可以减少路由器的缓冲区长度，所以它本质上更适合于多媒体数据 流的传输。 4 硕士学位论文 m a s t e r st h e s i s ( 3 ) 从推断网络状态的反馈信息的类型上，可以分为显式拥塞控制 ( e x p l i c i t ) 和隐式拥塞控制( i m p l i c i t ) ；在显式反馈方式中，网络使用显 式信号向执行流量控制的端点通告其状态( 有效带宽，缓存容量等) ；如果控 制端使用流量测量或者通过诸如超时、重复a c k 等隐含信号来推断网络状态， 则为隐式控制方式。 ( 4 ) 从实施控制的位置，可以分为端到端的拥塞控制( e n d - t o e n d ) 和 路由器拥塞控制( r o u t e r b a s e d ) ，端到端的拥塞控制仅在端系统执行，此时 中间节点仅负责向端系统产生和转发必要的反馈信息；后者是在网络的中间 节点处执行的，路由器除了转发数据包外还要负责通知端系统发送多少数据 进入网络。 1 4 存在的问题 由于i n t e r n e t 中绝大部分数据流使用了t c p i p 协议，因此本文将t c p i p 网络中的拥塞控制问题作为研究的重点内容。 t c p 拥塞控制机制在i n t e r n e t 中发挥了行之有效的作用，但t c p 拥塞控 制算法自身存在的问题也是不容忽视的。 端系统从发生拥塞到实施控制之间有着明显的时延，而且端系统缺乏 对数据传输过程的动态性了解，无法预知网络资源的使用情况，目前主要是 通过降低发送到网络的数据流量来减小网络负载从而缓解拥塞。 a