（控制科学与工程专业论文）tcpip网络拥塞控制策略研究.pdf

浙江大学博士学位论文 摘要 由于具有资源共享、信息沟通、可靠性、节约成本等方面的作用，i n t e r n e t 得到飞速的发展与应用，已成为一个重要而无处不在的基础设施。网络应用的巨 大需求导致网络系统经常会出现拥塞现象，虽然网络设备的处理速度不断加快、 网络带宽持续增长，但是硬件的建设的速度有时赶不上应用需求的增长。更关键 的是，i p 网络因其固有的无连接、分组交换的特性，不可避免地会造成网络拥 塞。因此，拥塞控制对i p 网络的鲁棒性和稳定性具有重要作用。目前，t c p i p 网络的拥塞控制策略主要包括两类：基于端主机的拥塞控制策略和基于通信子网 的拥塞控制策略，两种策略存在着相互影响、相互作用的关系。 一般来说，基于端主机的拥塞控制策略主要包括t c p 拥塞控制策略和非t c p 流的拥塞控制。本文针对t c p 经常会出现一个窗口的数据中有多个分组丢失的 情况，对现有t c p 拥塞控制策略的快速恢复算法做出了改进。i n t e m e t 的发展带 来了多媒体等实时应用不断得到增长，这些实时多媒体一般采用u d p 协议，而 目前的u d p 缺乏拥塞控制，在共存的网络环境下对t c p 应用造成t c p 流得不 到公平的带宽、甚至“饿死”，严重的话有可能造成网络崩溃，严重影响了网络 的性能。因此，我们提出了一种新的t c p 友好的u d p 拥塞控制策略。 目前，基于通信子网的拥塞控制策略的研究重点是路由器的队列管理策略。 一个良好的控制策略应该基于对系统的准确描述，但由于缺乏对网络系统动态特 性的了解，目前的队列管理控制策略大都基于专家经验，缺少一定的理论支持。 我们以单一瓶颈链路的简单i p 网络为对象，通过建立网络基本单元状态方程模 型来实现整个网络系统的数学解析模型。并在模型实验分析的基础上，对路由器 队列管理策略的控制目标和算法设计进行了研究。 论文的主要研究内容和创新点包括以下几个方面： 1 针对网络拥塞时t c p 应用出现同一回程时间( r 盯) 内多个分组丢失、 及丢失恢复过程中又出现分组丢失的情况，提出了一种新的t c p 拥塞控 制快速恢复算法：即时恢复算法。仿真结果表明：该算法跟同类的算法 相比，实现相对简单，性能较好； 2 提出了一种t c p 友好的、基于显式速率的u d p 拥塞控制策略：通过端 主机和网络中的路由器相互配合，使得实时u d p 应用能够根据网络的反 馈以瓶颈链路的公平带宽为速率发送数据。该算法跟同类算法相比，在 吞吐量、t c p 友好性等方面性能有较大提高； 3 基于流体流理论，从数据传输的角度，根据网络设备情况将网络系统分 浙江大学博士学位论文 解为各个独立的子对象，通过建立子对象的模型来构造i p 网络系统的数 学解析模型； 4 运用混杂系统来描述t c p 拥塞控制策略的数据传输过程。结合上述的i p 网络系统模型，实现了对t c p i p 网络数据传输动态过程的描述，并通过 m a t l a b 仿真与n s 仿真的实验结果对比，验证了t c p i p 动态模型的正确 性与有效性； 5 基于上述t c p i p 数学解析模型，对现有的主动队列管理策略进行了分 析，提出了队列管理策略的主要控制目标，然后设计了一种带有非线性 补偿的新的主动队列管理策略，仿真显示了该算法的性能要优于目前的 r e d 、p i 等算法。 关键词：拥塞控制，t c p ，t c p 友好，i p ，网络模型，主动队列管理 h 浙江大学博士学位论文 s i n c ei th a sm a n yf u n c t i o n sa n de f f e c t s ，i n t e m e th a sb e e nd e v e l o p e dr a p i d l ya n d b e c o m e 1 1 1i m p o r t a n tb a s i co f t o d a y ss o c i a ll i f e b e c a u s eo f t h eg r e a tr e q u i r e m e n to f n e t w o r ka p p l i c a t i o n s ，t h en e t w o r ks y s t e m so f t e nr e s u l ti nt h es t a t u so fc o n g e s t i o n a l t h o u g h t h ec p uo ft h en e t w o r k e q u i p m e n t s b e c o m em o r e q u i c k l y a n dt h e b a n d w i d t ho fn e t w o r k sc o n t i n u ei n c r e a s i n g ，t h en e t w o r k sc a nn o ts a t i s f yt h em o r e i n c r e a s eo f a p p l i c a t i o nr e q u i r e m e n t f o rt h ei pn e t w o r k s h a v et h ec h a r a c t e r i s t i c s ，s u c h a sc o n n e c t i o n l e s sa n dp a c k e ts w i t c h ，t h e yc a nn o ta v o i dt h ec o n g e s t i o ni n d e e d s ot h e s c h e m e so f c o n g e s t i o nc o n t r o la r ev e r yi m p o r t a n tf o rt h er o b u s t i c i t ya n ds t a b i l i t yo f t h ei p n e t w o r k s c u r r e n t l y , t h e r e a r et w ok i n d so ft h es c h e m e so fn e t w o r k s c o n g e s t i o nc o n t r 0 1 t h ef i r s t i s c o n g e s t i o nc o n t r o ls t r a t e g i e s i nh o s t s ，s u c ha st h e a l g o r i t h m so f t c p c o n g e s t i o nc o n t r 0 1 t h es e c o n di sc o n g e s t i o nc o n t r o ls t r a t e g i e si n s u b n e t ，s u c ha st h es c h e m eo f a c t i v eq u e u em a n a g e m e n t ( a q m ) a g o o ds c h e m eo fc o n g e s t i o nc o n t r o ls h o u l db a s eo nt h ee x a c td e s c r i p t i o no f t h e n e t w o r ks y s t e m f o rn o tu n d e r s t a n d i n gt h ed y n a m i cc h a r a c t e r i s t i co ft h en e t w o r k s y s t e m ，t h e c u r r e n ts c h e m e so f c o n g e s t i o n c o n t r o lm o s tc a m ef i o m e x p e r t s e x p e f i e n c ea n dl a c ko ft h es u p p o r ti nt h e o r y t h i st h e s i sp r o p o s e sad y n a m i cm o d e l f o ras i m p l ei pn e t w o r kw i t has i n g l eb o t t l e - n e c kl i n k f i r s tw e d e c o m p o s et h es i m p l e n e t w o r ki n t os e v e r a lb a s i cp a r t sa n ds e tu pt h ec o r r e s p o n d i n gd y n a m i cm o d e l s t h e n t h em o d e lo ft h ew h o l en e t w o r kc a nb ee a s i l yc o m b i n e d o nt h eb a s eo f e x p e r i m e n t a l a n a l y s i s ，w ed i dt h er e s e a r c h e so nc o n t r o lo b j e c t sa n da l g o r i t h md e s i g n i n go ft h e s c h e m e so f q u e u e m a n a g e m e n t c u r r e n t l y , t 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 o ft c pi sd o m i n a n ti nn e t w o r k s y s t e m t os o l v et h ep r o b l e mt h a tm u l t i p l ep a c k e t sw e r el o s tf r o mt h es a m ew i n d o w i nt c pc o n n e c t i o n s ，t h i st h e s i sp r o p o s e st h ei n s t a n tr e c o v e r ya l g o r i t h m ，an e w r e c o v e r ya l g o r i t h mf o rt c pc o n g e s t i o nc o n t r 0 1 w j t l lt h ed e v e l o p i n go fi n t e m e t t h e r e a l - t i m ea p p l i c a t i o n s ，s u c ha sm u l t i m e d i a , h a v ec o n t i n u o u s l yi n c r e a s e d c o m m o n l y , r e a l - t i m en e t w o r ka p p l i c a t i o n su s eu d pt ot r a n s m i td a t ai nc o n s t a n tr a t e ，w h i c hm a y a f f e c tt h ep e r f o r m a n c eo ft h eo t h e rt r a n s m i s s i o n ss u c ha st c p c o n n e c t i o n s ，a n dr e s u l t i ns e v e r en e t w o r kc o n g e s t i o n t os o l v et h i sp r o b l e m ，t h i st h e s i sp r o p o s e san e w u d p c o n g e s t i o nc o n t r o ls c h e m eb a s i n go ne x p l i c i tr a t e ，w h i c hi st c p - f r i e n d l y i ng e n e r a l ，t h em a i nc o n t e n t sa n dc o n t r i b u t i o n si nt h i st h e s i sc o u l d b es u m m a r i z e d i i l 浙江大学博士学位论文 a sb e l o w ： ( 1 ) t os o l v et h ep r o b l e mt h a tm u l t i p l ep a c k e t sw e r el o s tf r o mt h es a m e w i n d o w i nt c pc o n n e c t i o n s ，t h i st h e s i sp r o p o s e st h ei n s t a n tr e c o v e r ya l g o r i t h m t h r o u g hd y n a m i c a l l ys e t t i n gt h e t h r e s h o l df o re x i t i n gt h er e c o v e r yp e r i o d ，t h e i n s t a n tr e c o v e r ya l g o r i t h mc a nr e c o v e rt h ef i r s tl o s tp a c k e t sa n dt h ep a c k e t s l o s tl a t e ri nt h e r e c o v e r yp e r i o d t h e s i m u l a t i o nr e s u l t ss h o wt h a tt h e p e r f o r m a n c eo f t h i sa l g o r i t h mi sm u c hb e r e rt h a nt c p n e w - r e n o ，a n di sn o t w o r s et h a ns a c kt cp ( 2 ) p r o p o s e d an e wu d p c o n g e s t i o nc o n t r o ls c h e m eb a s e d o n e x p l i c i tr a t e i nt h e n e w s c h e m e ，t h ee n d - s y s t e m sg e tt h ef a i rb a n d w i d t ho f t h eb o t t l e n e c kl i n ki n t h ec o n n e c t i o n w i t ht h es u p p o r to ft h er o u t e r si nn e t w o r k s t h e nt h es e n d e r r e g u l a t e s t h es e n d - r a t et ot h i s f a i rb a n d w i d t h s m o o t h l y t h e n e wu d p c o n g e s t i o n c o n t r o ls c h e m eh a sb e t t e r p e r f o r m a n c e t h a nt h eo t h e ru d p c o n g e s t i o n c o n t r o ls c h e m es u c ha s t c p f r i e n d l y r a t ec o n t r o l f t f r c ) p r o t o c o l ，e s p e c i a li nt h et h r o u g h p u t a n dt c p f r i e n d l i n e s s ( 3 ) b a s e do nt h ef l u i d b a s e dd a t at r a n s m i s s i o n ，t h i st h e s i sp r o p o s e sad y n a m i c m o d e lf o ras i m p l ei pn e t w o r kw i t ha s i n g l eb o t t l e - n e c kl i n k w ed e c o m p o s e t h e s i m p l en e t w o r ki n t o s e v e r a lb a s i cp a r t sa n ds e t u pt h ec o r r e s p o n d i n g d y n a m i cm o d e l s a n dt h e nt h em o d e lo f t h ew h o l en e t w o r kc a nb ee a s i l y c o m b i n e d ( 4 ) ah y b r i ds y s t e mi su s e dt od e s c r i b et h ed a t at r a n s m i s s i o np r o c e s so ft c p c o n g e s t i o nc o n t r o ls c h e m e c o m b i n i n gt h ed y n a m i cm o d e lf o ri pn e t w o r k s ， w e g o t t h em o d e l d e s c r i p t i o no f d a t at r a n s m i s s i o n p r o c e s si nt c p i p n e t w o r k s y s t e m t 1 l i sm o d e li sw e l lv a l i d a t e db yc o m p a r i n gt h ea n a l y t i c a r e s u l t sw i t h t h en ss i m u l a t i o nr e s u l t s ( 5 ) f r o m t h ee x p e r i m e n t sb a s e do nt h em o d e lo f t c p f i ps i m p l en e t w o r k s y s t e m ， w e a n a l y z et h ec u r r e n ts c h e m e so fa q m t h e nw ep r o p o s et h em a i nc o n t r o l o b j e c t so fq u e u em a n a g e m e n ts c h e m e s ，a n dd e s i g nan e wa q ms c h e m ew i t h t h en o n l i n e a rc o m p e n s a t i o n t h er e s u l t si nn ss i m u l a t i o ns h o wt h i s n e w s c h e m ei sb e t t e rt h a nt h eo t h e r a q ms c h e m e s ，s u c ha sr e d a n dp i 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 , t c p f r i e n d l y , i p , m o d e lo fn e t w o r k s ，a c t i v e q u e u em a n a g e m e n t ( a q m ) 浙江大学博士学位论文 致谢 值此论文完成之际，我首先对导师吴铁军教授表示深深的谢意! 在三年多的 学习和研究中，吴教授给予了我精心的指导，为我创造了不少学习的条件。同时 吴教授还为提供了一个宽松的学习科研环境，培养了我独立从事科研的能力。吴 教授认真严谨的治学态度和踏实的工作作风，给我留下了深刻的印象并为我树立 了榜样，他对知识孜孜以求的精神和忘我的工作态度，将指引我一生的前进。在 此表示最诚挚的敬意和感谢! 在本论文的形成过程中，我幸运地得到了许多老师、同学和朋友的关心和帮 助。感谢戴连奎副教授和刑卫副教授，本文的一些成果得益于他们的交流和讨论。 感谢智能所的其他老师给予我的许多帮助。 感谢韩斌、董苗波、郭斯羽、李艳君、闻育、王华东、范听炜、程志强、武 晓莉、常爱英、徐伟强、纪竹亮等师兄弟们，他们的无私帮助使我在研究工作中 克服了很多困难。 感谢我的好友，系统工程研究所的陈尚兵博士、仪表研究所的彭司华博士， 他们和我在研究工作的相互支持、相互鼓励，相伴度过了博士期间的求学路。感 谢尹建伟、吴飞、高利新、宋晓峰等好友的关心和帮助。 感谢父母的养育和谆谆教诲，他们这些年来在背后默默的无私支持，给了我 在求学路上不断前进的动力。感谢姐姐、姐夫的帮助和支持。 感谢岳父母对我生活上的无私照顾、关心和支持。 最后，感谢我的妻子王雪峰，多年来她以柔弱的身躯坚强地支撑着这个家， 免除了我生活上的后顾之忧，是她对我的支持、鼓励和爱，使我在求学的道路上 心无旁骛、可以一直向前。最后，谨以此文献给我深爱的妻子。 v 王彬 2 0 0 4 年2 月 第一章绪论 摘要 本章分析了网络拥塞现象和拥塞发生的原因，简述了拥塞控制及其研究意义，对现有的 t c p i p 网络的拥塞控制策略作了分类。在分类的基础上，对基于端主机的拥塞控制策略、 基于通信子网的拥塞控制策略以及与拥塞控制紧密相关的网络模型等方面的研究现状进行 了总结。最后简要介绍了论文的研究内容和总体结构。 关键词：t c p i p ，网络拥塞，拥塞控制，端主机，通信子网，网络模型 i n t e m e t 的快速发展与应用，导致网络系统经常会出现拥塞现象。虽然网络设 备的处理速度不断加快、网络带宽持续增长，但由于i p 网络固有的无连接、分 组交换的特性，不可避免地会造成网络拥塞。因此，拥塞控制对i p 网络的鲁棒 性和稳定性具有重要作用。 1 1 网络拥塞控制与拥塞控制系统的结构、分类 网络中的拥塞来源于网络资源和流量分布的不均衡性，要提高网络的性能， 需要对网络进行拥塞控制。根据网络协议的层次结构、以及控制策略实现的位置， 网络拥塞控制可以分为两类：基于端主机的拥塞控制策略和基于通信予网的拥塞 控制策略。 1 1 1 网络拥塞和拥塞发生的原因 当网络中存在过多的数据包时，网络的性能就会下降，这种现象称为拥塞 ( a n d r e ws t a n e n b a u m ，1 9 9 6 ；j a i nr e ta l ，1 9 8 8 ) 。拥塞导致的直接后果是分 组丢失率增加，端到端延迟加大，甚至有可能使整个系统发生崩溃( c o n g e s t i o n c 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 ( j a c o b s o n v ，1 9 8 8 ) 。当网络处于拥塞崩溃状 态时，微小的负载增量都将使网络的有效吞吐量( g o o d p u t ) 急剧下降。 图1 1 描述了网络负载和吞吐量之间的关系。当负载较小时，吞吐量的增长 和负载相比基本成线性关系，延迟增长缓慢；在负载超过k n e e 点后，吞吐量增 长缓慢，延迟增长较快；当负载超过c l i f f 点之后，吞吐量急剧下降，延迟急剧 上升。通常将k n e e 点附近称为拥塞避免区间；k n e e 到c l i f f 之间是拥塞恢复区 间；c l i f f 之外是拥塞崩溃区间。可以看出，负载在k n e e 附近时网络的使用效率 最高。 第一章绪论 吞吐量 载 图1 1 吞吐量和负载的关系图 拥塞控制就是由网络节点来采取措施避免拥塞的发生或者对拥塞的发生作出 反应( p e t e r s o nl l e ta l ，2 0 0 0 ) ，使得网络能够传输较大的有效吞吐量，在图 1 1 中就是使负载保持在k n e e 附近。 拥塞现象的发生和t c p i p 网络的设计机制有着密切都联系。t c p i p 网络具 有如下几个特点( p e t e r s o nl l e ta l ，2 0 0 0 ) ： ( 1 ) 分组交换( p a c k e t s w i t c h e d ) 网络。与电路交换( c i r c u i t s w i t c h e d ) 相比，分组交换通过共享提高了资源的利用效率，但这会引起分组 在网络中滞留，造成分组数据可能出现“乱序”现象( b e n n e t tj c r e ta l ，1 9 9 9 ) ，增加了端系统处理乱序分组的复杂性。 ( 2 )无连接( c o n n e c t i o n l e s s ) 网络。t c p i p 网络中，从网络层的角度来 看，节点之间在发送数据之前不需要建立连接。无连接模型简化了 网络的设计，在网络的中间节点上不需要保存与连接到有关信息。 但是无连接模型难以引入“接纳控制”( a d m i s s i o nc o n t r 0 1 ) 机制，在 用户需求大于网络资源时，难以保证服务质量( q o s ) ；无连接也是 网络中出现分组乱序的一个主要原因。 ( 3 ) “尽力而为”的服务模型。所谓“尽力而为”的服务，是指网络不 对数据传输的服务质量提供保证。这与网络早期的应用有关，传统 的网络应用主要是数据业务，它们对网络性能( 带宽、延迟、丢失 率等) 的变化不敏感，“尽力而为”服务能够满足需要。但“尽力而 为”服务不能很好地满足新出现的多媒体应用的要求，这些应用对 延迟、速率等性能的变化比较敏感。 虽然随着科技的发展，网络设备的处理速度不断加快、网络带宽持续增长， 但是硬件的建设的速度有时赶不上应用需求的增长。而且，很多时候，即使局部 的网络资源很充足，仍然会出现网络拥塞、分组数据丢失，从而导致性能下降。 浙江大学博士学位论文 这是因为由于互连网络是一一个及其复杂的分散系统，网络中总是存在资源“相对” 短缺的位置，成为网络性能提高的瓶颈。 网络中拥塞现象发生的原因是“需求”大于“供给”。网络中有限的资源由多 个用户共享使用。由于没有“接纳控制”策略，网络无法根据资源的情况限制用 户的数量；同时，互连网络是一个分散控制系统，由于缺乏中央集成控制，网络 无法控制用户使用资源的数量。目前，因特网上不断增长的用户和应用的数量， 必然会导致网络发生拥塞。虽然拥塞源于资源短缺，但增加资源并不能避免拥塞 现象的发生，有时甚至会加重拥塞程度( j a i nr ，1 9 9 0 ) 。例如，增加路由器的队 列缓存会增大分组通过路由器的延迟，如果总延迟超过端系统重传时钟的设定 值，就会导致分组重传，反而加重了网络拥塞。 田些p 田 ( a ) 带宽分布不均衡( b ) 流量分布不均衡 图1 2 网络的不均衡性示意图 拥塞总是发生在网络中资源“相对”短缺的地方，这反映了互连网络的不均 衡性。这个不均衡性一方面表现在资源的不均衡，如图1 2 ( a ) 中带宽分布不均 衡：当s 以1 m b p s 的速率向d 发送数据时，在路由器r 处会发生拥塞。另一方 面是由于流量的不均衡，如图1 2 ( b ) 中带宽分布是均衡的，但当s 1 和s 2 都以 1 m b p s 的速率向c 发送数据时，在路由器r 也会发生拥塞。因特网中资源和流 量分布的不均衡是广泛存在的，由此导致的拥塞不能通过增加资源的方法解决。 1 1 2 拥塞控制及其研究意义 拥塞控制策略包括拥塞避免( 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 n c o n t r 0 1 ) 这两种不同的机制。拥塞避免是“预防“机制”，它的目标是避免网络 进入拥塞状态，使网络运行在高吞吐量、低延迟的状态下。拥塞控制是“恢复” 机制，它用于把网络从拥塞状态中恢复出来。 在网络控制的研究中，拥塞控制和流量控制是网络的经典问题( 罗万明，林 闯，阎保平，2 0 0 1 ；任立勇。卢显良，2 0 0 2 ) ，但它们两个的概念比较容易混淆。 拥塞控制必须确保网络能进行数据传输，这是全局性的问题，涉及到所有主机、 路由器以及所有其他将导致削弱网络负荷能力的因素。而流量控制只与发送者和 接受者之间的点到点的数据传输有关，它的任务是确保一个快速发送方的发送速 第一章绪论 率不超过接收方的最大接受速度。可以看到，流量控制的功能实现位于网络的传 输层，实现比较简单；而拥塞控制从广义上讲，涉及网络的所有层次，在具体的 实现中，拥塞控制一般通过网络层和传输层相互协调来完成。 从不同的角度，拥塞控制可以被分为很多类。对目前网络拥塞控制研究现状 的分类我们将在下一小节中进行介绍。 拥塞控制的研究目的不是要完全避免拥塞，而是研究怎样的拥塞程度是合适 的。这是因为：t c p i p 网络采用分组交换技术来提高网络链路的利用率，造成 路由器的队列缓存经常被占；如果路由器的队列缓存总是空的，虽然传输延迟小， 但是网络的利用率也低；如果路由器队列缓存总是被占，传输延迟变大，但是网 络利用效率也高。拥塞控制的目标是实现网络利用率和传输延迟等综合性能指标 的最优化。 由此可以看到，通过网络的拥塞控制，可以提高网络的总体性能，保证网络 系统长期的稳定性和鲁棒性。 1 1 3 拥塞控制系统的结构及分类 由于网络系统的异构性、复杂性和不可预测性，现有的拥塞控制策略基本上 是基于闭环方式的。在拥塞闭环控制中，源端通过反馈信号来调节发送速率，因 此反馈机制是拥塞控制的一个重要环节。一般有两种反馈方式：隐式和显式。隐 式反馈中，终端系统自己负责监测数据传输状况，并由此推测网络拥塞状态，进 而调节发送速率。但是终端的功能有限，难以从有限的信息中准确推断出网络的 负载状况。隐式反馈一般指采用分组丢失信息或标记分组作为反馈信号。在网络 拥塞控制中，显式反馈方式主要见于a t m 网络的a b r 方式的拥塞控制中，通 过a t m 交换机的支持，拥塞控制通过r m 信元来反馈连接所通过的网络路径上 的连接数和可用带宽等信息( 张宏科，裘正定，1 9 9 6 ) 。 针对已有的各种闭环的拥塞控制策略，根据网络模型的层次结构、以及实现 的位置，t c p i p 网络拥塞控制可以分为两种不同的闭环拥塞控制模型：基于端 主机的拥塞控制策略和基于通信子网的拥塞控制策略( l o ws h ，2 0 0 0 ) ，如图 1 3 所示。由于t c p 应用占i n t e m e t 上流量的总字节数的9 5 和总报文数的9 0 ( t h o m p s o nk ，m i l l e rg j a n dw i l d e rr ，1 9 9 7 ) ，基于端主机拥塞控制的研究一开 始主要集中在t c p 的拥塞控制上。随着新兴的非t c p 应用( 特别是实时多媒体 应用和多播) 不断得到增长，提出了针对u d p 和多播的t c p 友好的拥塞控制算 法的研究，现在已经称为拥塞控制研究的一个热点。基于通信子网的拥塞控制策 略包括数据包调度策略和队列管理算法，后者是主要的研究方向。数据包调度策 略通过数据流如何排队( 单队列或多队列) 决定那些包可以传输来分配带宽。队 列管理通常通过分组丢弃策略来维护队列长度的大小，实现网络的控制，同时丢 4 包的信息可以反馈到端主机的上层进行拥塞控制。 基于端主机拥塞控制策略 基于通信子网拥塞控制策略 图1 3t c p i p 网络拥塞控制策略结构图 基于端主机的拥塞控制策略中，源端采用某种拥塞控制策略，而反馈信号主 要来自瓶颈链路上的分组丢失标记信息。从控制理论的角度看，源端的速率调 节算法是系统的控制器，系统的广义对象为路由器和链路组成的网络系统，这样 的闭环控制系统如图1 4 所示。 图1 4 基于端主机拥塞控制模型 基于通信子网的拥塞控制策略中，队列管理策略是主要的拥塞控制策略。路 由器的主动队列管理( a q m ) 策略根据队列长度q 的变化情况，在队列缓存溢 出之前，对到达的分组数据以概率p 丢弃，标记，分组的丢弃标记概率经过一些 延迟后被源端检测到，源端由此判断网络的状态，根据控制算法调节发送速率， 从而路由器队列缓存中的队列长度得到控制。从这个角度看，a q m 才是系统的 控制器，其输出p 为系统的控制信号，而源端的速率控制算法是系统的执行器， 它和路由器的队列长度特性以及链路延迟一起，组成系统的广义对象，这样的控 第一章绪论 制系统如图1 5 所示。 4 亘卜母醒兰 l g 阿司毒 广义对象 图1 5 队列管理策略控制模型 这两种闭环模型有着不同的先决条件和目的，第一种模型一般假设路由器采 用了某种固定的队列管理策略( 如尾部丢弃法) ，强调源端的速率控制，适用于 设计和分析源端的速率控制算法；而第二种模型假设源端采用已知的速率控制算 法( 如t c p 的拥塞窗口控制技术) ，适合用来设计和分析路由器的队列管理策略。 由此可见，基于端主机的拥塞控制策略与基于通信子网的拥塞控制策略是相 互影响、相互作用的。基于端主机策略需要根据来自于队列管理策略的反馈信号 进行发送速率的调整；而队列管理策略除了可以通过分组丢弃来维持合理的队列 长度变化，还可以通过丢弃，j 示记概率的变化来影响端主机的发送速率。两者结 合在一起实现完整的网络拥塞控制。 从上面的分析可以看到，这两种模型中拥塞控制策略所在的位置不同，第一 种模型中控制器位于端主机，在网络分层模型中处于传输层及以上层，目前最为 人熟悉的是t c p 拥塞控制策略，而基于u d p 协议的t c p 友好的拥塞控制策略 研究也在得到不断发展；第二种模型中控制器在路由器，处于网络层，一般是指 队列管理策略，现有的队列管理研究主要集中于主动队列管理( a q m ) 策略。 根据闭环拥塞控制模型的分类，结合网络的分层结构和拥塞控制的实现位 置，下面分别介绍基于端主机的拥塞控制策略和基于通信子网的拥塞控制策略。 1 2 基于端主机的拥塞控制策略 基于端主机的拥塞控制是从数据传输的角度出发，通过控制网络终端数据发 送来调整网络中间节点的状态，从而提供给应用具有一定质量的连接。从网络层 次结构的角度，基于端主机的拥塞控制策略位于传输层及其以上层。目前的研究 主要集中于t c p 拥塞控制策略和t c p 友好的非t c p 流的拥塞控制策略。显式拥 塞指示( 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 ) 是一种需要路由器支持的拥塞控 浙江火学博上学位论文 制策略，这里也作了简要的介绍。 1 2 1t c p 拥塞控制策略及改进 网络中拥塞控制的大部分工作是由t c p 来完成的，因为对拥塞现象最切实的 办法是降低数据传输速率。t c p 拥塞控制是基于窗口方式的。由于要同时考虑网 络容量和接收方的容量，发送方要维持两个窗口：接收方的建议窗e l ( r e c e i v e r s a d v e r t i s e dw i n d o w ，r w n d ) 和拥塞窗口( c o n g e s t i o nw i n d o w ，c w n d ) 。取两个窗口 的最小值作为可以发送的数据量。 1 2 1 1t c p 拥塞控制的基本算法 t c p 拥塞控制包括四个部分：慢启动、拥塞避免、快速重传和快速恢复。在 慢启动阶段：当建立新的t c p 连接时，发送方发送一个t c p 报文段数据( 缺省 为5 1 2 字节) ，即c w n d 为一t c p 报文段，以后发送方每收到一个来自接收方的 确认( a c k ) ，c w n d 就增加一个报文段。因一个r t t 定义为从发送一报文段到 收到该报文段的a c k 的时间间隔，c w n d 的大小将随i 玎t 呈指数增长。 拥塞避免阶段：当发现超时或收到3 个相同a c k 时，t c p 认为网络发生拥 塞( t c p 这一假设是基于：由传输引起的数据包损坏和丢失的概率很小，小于 1 ( j a c o b s o nv ，1 9 8 8 ) ) 。此时，就进入拥塞避免阶段。慢启动阀值( s s t h r e s h ) 就设置为当前c w n d 的一半，精确地说，s s t h r e s h = m a x 2 ，m i n ( c w n d 2 ，r w n d ”。 如果是超时，c w n d 还要被置1 。如果此时c w n d s s t h r e s h ，t c p 就执行拥塞避免算法，发送方每收到一个 a c k ，就对c w n d 增加1 c w n d 个报文段。所以，在拥塞避免算法中，c w n d 的增 长是线性的。 快速重传和快速恢复阶段：发送方等到数据包超时时，c w n d 要被置为1 ，重 新进入慢启动，这样过大地减少发送窗口大小，会导致t c p 连接吞吐量的较大 降低。所以快速重传就是在发送方收到3 个或以上重复a c k 时，就断定数据包 已经丢失，马上重传该数据包，同时将s s t h r e s h 置为当前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 。给s s t h r e s h 加3 是因为三个重复a c k 表明已经有三个数据包离开网络被接收方缓存起来。( 2 ) 每次有一个更多的重复 a c k 到达，把c w n d 加1 并在可能的情况下传输一个报文段。这是因为又有一个 数据包离开网络并触发了重复a c k 。( 3 ) 当确认新数据的下一个a c k 到达时， 设置c w n d = s s t h r e s h ，进入拥塞避免。 第一章绪论 c w n d l s s t h r e s h c w n d l 2 时间 图1 6 慢启动和拥塞避免( 不含快速重传和恢复) 图1 6 反映了拥塞控制窗口在不含快速重传和快速恢复、只有慢速启动和超 时重传时的变化情况，图1 7 则反映了拥塞控制窗口在加入了快速重传和快速恢 复后的变化情况。 c w n d l c w n d l 2 图1 7 快速重传和快速恢复 根据上面可以看出，t c p 使用的是一种和式增加积式减少( a d d i t i v ei n c r e a s e m u l t i p l i c a t i v ed e c r e a s e ，a i m d ) 的基于窗口的基于端主机拥塞控制机制。t c p 发 送方的发送速率由拥塞窗口控制，如果有个数据包丢失，发送窗口就要减半： 否则就增加一个数据包的发送量。 1 2 1 2t c p 拥塞控制算法的改进 由于因特网规模、应用的不断发展，t c p 拥塞控制的适用性也在不断发生变 化，因此需要不断改进。 8 ( 1 ) 慢启动的改进。 浙江火学博士学位论文 i n t e r n e t 自从出现后得到急剧发展，w e b 流占了因特网流量的很大部分，而 这些t c p 连接的流量基本都是很短小的( s h s i k h a ，1 9 9 9 ) 。这些短t c p 流主要 工作于慢速启动( s l o ws t a r t ) 阶段，在和长t c p 流竞争时处于不利地位。由于 长t c p 流工作于拥塞避免阶段，因此具有较大的拥塞窗口( c w n d ) ，可以在一个 回程时间r t t 内从多个分组丢失恢复到正常状态，而短t c p 流常常会因为出现 一个分组丢失而等待直到重传定时器超时，这样就会造成在网络的拥塞节点长 t c p 流会挤掉短t c p 流的现象( m a t t a i e ta l ，2 0 0 0 ) ，导致它们所获得的平均带 宽不相同。关键的是，短t c p 流的传输的常常是交互的、时延敏感的应用，如 w w w 、t e l n e t 等。 由此可以看到，传统的慢启动存在两个问题：( 1 ) 数据发送从一个数据包开 始，要经过多个r t t 才能达到较大的吞吐量，这对流量小但是链路延迟又比较 大的t c p 流很不利：( 2 ) 发送方不了解网络的可用带宽，但采用指数增长的方 式发送数据造成了数据突发，从而引起瓶颈链路的拥塞( 陈尚兵，2 0 0 3 ) 。 针对第一个问题，研究者们提出了采用大的初始窗口和t c p 连接信息共享等 方法。大初始窗口的方法将初始窗口从1 m s s ( m a x i m u ms e g m e n ts i z e ) 增加到 4 m s s ，从而减少从小初始窗口探寻可用网络带宽造成的额外的r t t ( a l l m a n m e ta l ，1 9 9 8 ) 。这在一定程度上可以改善慢速启动的性能，但是当网络带宽情况 改变时，这种固定初始窗口的方法就显得不够灵活而影响性能。将各个t c p 连 接的信息共享( p a d m a n a b h a nv e ta l ，1 9 9 8 ；t o u c hj ，1 9 9 7 ；s a v a g es e ta l ，1 9 9 9 ) ， 后面的连接可以使用具有相同目的地址连接的信息，从而可以减少慢速启动造成 的时延。但是这样会使连接马上就遭遇到网络拥塞，而短t c p 的长度往往都比 较小( w e b 文件的平均大小大约为3 0 k 3 ( m a