（计算机软件与理论专业论文）tcpip网络拥塞控制的研究.pdf

摘要 随着新型网络应用的不断涌现和用户数量的迅速增长，使得 i n t e r n e t 的流量急剧增长，越来越严重的网络拥塞问题逐渐暴露出来。 i n t e r n e t 中拥塞控制机制对保证i n t e r n e t 的稳定具有十分重要的作 用，实施拥塞控制是其它服务质量( q o s ) 机制正常工作的必要前提。 本文从t c p i p 协议的层次出发，回顾t c p i p 网络中己有的拥塞 控制技术；分析了i n t e r n e t 中t c p 的基于窗口的端到端拥塞控制方法 以及i p 层采用的拥塞控制机制，总结了t c p 流量控制和主动队列管理 各研究子方向中需要解决的问题。重点分析了主动队列管理这一热点 领域中已有策略和算法的优缺点。通过对它们中存在的问题以及产生 问题的原因的总结，提出了一种新的主动队列管理算法。 针对平均队列不能完全反映网络拥塞状况，本文结合平均队列和负 载，提出了一种薪的主动队列管理算法一一基于负载的选择性丢包算 法。该算法结合平均队列和负载，给出了一种新的丢包率的计算方法。 在网络负载大于网络目标带宽时，加大丢包率；在网络负载小于网络 目标带宽的时候，减小丢包率。并对丢包率的更新频率进行了讨论。 为了能使网络拥塞信号更及时的反馈到发送端，并让发送端能更有效 的控制拥塞，提出了选择性丢包机制。选择性丢包机制的采用，同时 能区分响应流连接和非响应流连接，惩罚占用超过平均带宽的连接， 达到各连接对链路的公平使用。 本文使用n s 2 作为网络仿真实验平台对上述算法进行了验证和分 析，实验结果表明：基于负载的选择性丢包算法拥有比r e d 算法更好 的稳定性，更低的丢包率和更高的吞吐量；同时它还拥有比f r e d 更好 的公平性。 关键词：拥塞控制，服务质量，主动队列管理，随机早期检测， 虚队列，候选连接 i a b s t r a c t d u et ot h ee m e r g e a c eo fm a n yn e wn e t w o r ka p p li c a t i o n sa n d r a p i de x p a n s i o no ft h en e t w o r k e du s e rg r o u p ，i n t e r n e tt r a f f ic h a sb e e ni n c r e a s i n gd r a m a t i c a l l y ，a n dn e t w o r kc o n g e s t i o na p p e a r s t ob eam o r ea n dm o r ec r i t i c a l is s u e c o n g e s t i o nc o n t r o l m e c b a n is m sa r ev e r yi m p o r t a n ting u a r a n t e e i n gt h es t a b i l i t yo f i n t e r n e t m o r e o v e r ，as u i t a b l ec o n g e s t i o nc o n t r 0 1m e c h a n is i l li s t h eb a s isf o ro t h e rq u a l i t y o f s e r v i c e ( 0 0 s ) m e c h a n is m st ow o r k e f f e c t i v e l y t h isa r t ic l es t a r t sf r o mt h et c p i pp r o t o c 0 1 w i t har e v ie w o nt h ee x is t i n gc o n g e s t i o nc o n t r 0 1t e c h n o l o g yi nt c p i pn e t w o r k i ta n a l y z e st h et c pw i n d o wb a s e de n d t o e n dc o n g e s t i o nc o n t r 0 1 a p p r o a c ho fi n t e r n e ta n dt h ec o n g e s ti o nc o n t r 0 1m e c h a n is m su s e d b yi p1 a y e r i tc o n e l u d e sb yt h et c pf l o wc o n t r 0 1a n da c t i v eq u e u e m a n a g e m e n tt h ep r o b l e m sn e e d e dt ob er e s 0 1 r e di na 1 1a s p e c t s u n d e rs t u d y t h ea n a ly s isisf o c t l s e do nt h ep r o sa n dc o n so f e x is t i n gs t r a t e g i e sa n da l g o r i t h m so nt h eh o tt o p i co fa c t i v e q u e u em a n a g e m e n t b yu n d e r l y i n gt h ep r o b l e m sf a c e da n dt h e r e a s o n sb e h i n d ，an e wa l g o r i t h mo na c t i y eq u e u em a n a g e m e n tis i n t r o d u c e d f o c u s i n go nt h ef a c t t h a ta v e r a g eq u e u ec a n n o tc o m p l e t e l y r e f l e c tt h es it u a t i o no fn e t w o r k c o n g e s t i 0 1 ，t h isa r t i c l e i n t e g r a t e st h ea v e r a g eq u e u ea n d1 0 a da n di n t r e d u c e san e w a l g o r i t h mo na c t i v eq u e u em a n a g e m e n t b a s e do no p t i o n a lp a c k e t 1 0 s sa l g o r i t h mo f1 0 a d s s u c ha l g o r i t h mi n c o r p o r a t e sa v e r a g e q u e u ea n d1 0 a d ，g i v i n gr i s et oan e wa l g o r i t h ma p p r o a c ho fp a c k e t h 1 0 s s t h ed a c k e tl o s sr a t eb e c o m e sh i g h e rw h e nn e t w o r k l o a d s e x c e e dn e t w o r kt a r g e tb a n d w i d t h ，w h i l e t h ep a c k e t1 0 s sr a t e b e c o m e ss m a l l e rw h e nn e t w o r kt a r g e tb a n d w i d t he x c e e d s n e t w o r k l o a d s t h e r ei s a ls od i s c u s s i o no nt h eu p d a t eo fp a c k e t 1 0 s s f r e q u e n c y 。 i no r d e rt h a t n e t w o r kc o n g e s t i o ns i g n a l b e t r a n s m i t t e do f ft i m et ot h et r a n s m is s i o ne n da n dc o n g e s t i o n b e c o n t r 0 1l e de f fj c i e n t ly ，a no p t i o n a lp a c k e t 1 0 s sm e c h a n is mi s i n t r o d u c e d i na p p l y in g s u c ho p t i o n a lp a c k e t1 0 s sm e c h a n is m ， r e s d o n s ef l o wc o n n e c t i o f fa n dn o n r e s p o n s ef l o wc o n n e c t i o n c a n a 1s ob ed i f f e r e n t i a t e d c o n n e c t i o f f so c c u p y i n gb a n d w i d t hb e y o n d t h ea v e r a g eb a n d w i d t h w i l lb ep u n is h e dt oe n s u r e t h a ta 1 1 c o n n e c t i o n sa r eu t i l i z e d i f laf a i rm a n n e r t h isa r t ic l eu s e sn s 2a st h en e t w o r kv i r t u a le x p e r i m e n t a l p l a t f o r mf o rv e r i f i c a t i o na n da n a l y s i so ft h ea b o v ea l g o r i t h m t h er e s u l t si l l u s t r a t e dt h a tt h eo p t i o n a lp a c k e tl o s sa l g o r i t h m b a s e do n1 0 a d sp o s s e s s e sam o r es t a b l e ，al o w e rp a c k e tl o s sr a t e a n dah i g h e rc a p a c i t ya sc o m p a r e dt or e da l g o r i t h m ：af a i r e r 硼a n n e risa ls od e m o n s t r a t e dw h e nc o m p a r e dt o f r e d k e y w o r d s ：c o n g e s t i o nc o n t r o l ，q u a l i t yo fs e r v i c e ，a c t i v eq u e u e m a n a g e m e n t ，r a n d o me a r l yd e t e c t i o n ，v i r t u a l q u e u e ，c a n d i d a t e c o n n e c t i o n 。 i 华南师范大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究工作所取得的成果。除文中已经注明引用的内容外，本论 文不包含任何其他个人或集体已经发表或撰写过的研究成果。对本文 的研究做出重要贡献的个人和集体，均己在文中以明确的方式标明。 本人完全意识到本声明的法律结果由本人承担。 论文作者签名： 日期：弘d 6 年蝴6 日 学位论文使用授权声明 本人完全了解华南师范大学有关收集、保留和使用学位论文的规 定，即：研究生在校攻读学位期间论文工作的知识产权单位属华南师 范大学。学校有权保留并向国家主管部门或其指定机构送交论文的电 子版和纸质版，允许学位论文被检索、查阅和借阅。学校可以公布学 位论文的全部或部分内容，可以允许采用影印、缩印、数字化或其他 复制手段保存、汇编学位论文。( 保密的论文在解密后遵守此规定) 。 保密论文注释：本学位论文属于保密范围，在一年后解密适用 本授权书。非保密论文注释：本学位论文不属于保密范围，适用本授权 书。 论文作者签名： 日期：年月 日 导师签名、j 诩3 日期嘶厂胡6 日 第1 章引言 i n t e r n e t 在过去十几年里按指数方式进行增长。现在i n t e r n e t 已经成为最重要的信息交换手段。人们利用i n t e r n e t 接受教育、娱乐、 处理个人事务、购物等。随着i n t e r n e t 越来越重要，人们对i n t e r n e t 的要求也越来越高。用户需要更宽的带宽，更好的服务质量( q o s ) ，更 高的安全性。 随着新型网络应用的不断涌现和用户数量的迅速增长，使得 i n t e r n e t 的流量急剧增长，其中除了传统的w w w ，f t p ，t e l n e t 等数掘 流外，还出现了大量的实时多媒体数据流，由于网络中不同的数据流 在路由器处交汇，因而给网络的路由节点造成很大的负担，越来越严 重的网络拥塞问题逐渐暴露出来。经常上网的人常常会遇到像坐车遇 到堵车一样的情况，网络上的“堵车”如同生活中的堵车令人恼火。 治理交通拥挤是现代化城市持续发展中必须解决的一个重要问题，同 样，解决网络拥塞问题也是i n t e r n e t 网络发展中必须面临的问题。 1 j1 网络拥塞和拥塞控制 当通信子网中存在过多的报文时，网络的性能就会下降，这种现 象称为拥塞纠( c o n g e s t i o n ) 。在网络发生搠塞时，会导致端到端时 延( d e l a y ) 的急剧增加，并造成大量的分组丢失( p a c k e t1 0 s s ) ，使吞 吐量( t h r o u g h p u t ) 下降，严重时会发生“拥塞崩溃”( c o n g e s t i o n c o l la p s e ) 现象”。图1 1 1 ( a ) ( b ) ( c ) 刻画了负载与吞吐量、响 应时| 日j 和网络性能的关系。当网络负载较小时，吞吐量基本上随着负 载的增长而增长，呈线性关系，响应时间增长缓慢。当负载达到网络 容量时，吞吐量呈现出缓慢增长，而响应时问急剧增加，这一点称为 k n e e 。如果负载继续增加，路由器开始丢包，当负载超过一定量时， 吞吐量开始急剧下降，这一点称为c 1 i f f 。通常将k n e e 点附近称为拥 塞避免区问；k n e e 和c 1 i f f 之间是拥塞恢复区问；c 1 i f f 之外是拥塞 崩溃区问。为了最大限度地利用资源，网络工作在轻度拥塞状态时应 该是较为理想的，但这也增加了滑向拥塞崩溃的可能性，因此需要一 定的拥塞控制机制来加以约束和限制。 拥塞现象的发生和t c p i p 网络的设计机制有着密切都联系。 t c p i p 网络具有如下几个特点： ( 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 ) 相比，分组交换通过共享提高了资源的利用效率， 但这会引起分组在网络中滞留，造成分组数据可能出现“乱序”现象， 增加了端系统处理乱序分组的复杂性。 ( 2 ) 无连接( c o n n e c t i o n l e s s ) 网络。t c p i p 网络中，从网络层的角 度来看，节点之间在发送数据之前不需要建立连接。无连接模型简化 了网络的设计，在网络的中j 日j 节点上不需要保存与连接到有关信息。 但是无连接模型难以引入“接纳控制”( a d m is s i o nc o n t r 0 1 ) 机制， 在用户需求大于网络资源时，难以保证服务质量( q o s ) 。无连接也是网 络中出现分组乱序的一个主要原因。 ( 3 ) “尽力而为”的服务模型。所谓“尽力而为”的服务，是指网 络不对数据传输的服务质量提供保证。这与网络早期的应用有关，传 统的网络应用主要是数据业务，它们对网络性能( 带宽、延迟、丢失率 等) 的变化不敏感，“尽力而为”服务能够满足需要。但“尽力而为” 服务不能很好地满足新出现的多媒体应用的要求，这些应用对延迟、 速率等性髓的变化比较敏感。 拥塞控制就是网络节点采取措施来避免拥塞的发生或者对拥塞的 发生作出反应。它实际上包含拥塞避免( c o n g e s t i o ra v o i d a n c e ) 和拥 塞控制( c o n g e s t i o nc o n t r 0 1 ) 两种不同的机制。拥塞避免是预防策 2 略，它的目的是使网络运行在k n e e 附近，避免网络拥塞发生，使网络 运行在高吞吐量、低延迟的状态；拥塞控制是恢复策略，它用于把网 络从拥塞状态中恢复出来，使得网络运行在c l i f f 的左侧区域，进入 正常的运行状态。 番 趾 量 嗣 络 性 照 孵精负筏 忙) h 络煎载 鹣耋髯负载 网络负载与吞吐量，响应时间及网络性能的关系 在网络控制的研究中，拥塞控制和流量控制是网络的经典问题， j 但它们两个的概念比较容易混淆。拥塞控制必须确保网络能进行数据 传输，这是全局性的问题，涉及到所有主机、路由器以及所有其他将 导致削弱网络负荷能力的因素。而流量控制只与发送者和接受者之间 的点到点的数据传输有关，它的任务是确保一个快速发送方的发送速 率不超过接收方的最大接受速度。可以看到，流量控制的功能实现位 于网络的传输层，实现比较简单；而拥塞控制从广义上讲，涉及网络 的所有层次，在具体的实现中，拥塞控制一般通过网络层和传输层相 3 互协调来完成。 从不同的角度，拥塞控制可以被分为很多类。对目前网络拥塞控 制研究现状的分类我们将在下一小节中进行介绍。 拥塞控制的研究目的不是要完全避免拥塞，而是研究怎样的拥塞 程度是合适的。这是因为：t c p i p 网络采用分组交换技术来提高网络 链路的利用率，造成路由器的队列缓存经常被占；如果路由器的队列 缓存总是空的，虽然传输延迟小，但是网络的利用率也低；如果路由 器队列缓存总是被占，传输延迟变大，但是网络利用效率也高。拥塞 控制的目标是实现网络利用率和传输延迟等综合性能指标的最优化。 由此可以看到，通过网络的拥塞控制，可以提高网络的总体性能， 保证网络系统长期的稳定性和鲁棒性。 一种理想的拥塞控制算法应尽可能具有以下特点：一是高效性， 在满足控制目标前提下，尽可能充分利用网络资源；第二是很好的扩 展性，当网络连接数增多时，算法开销不会成为影响网络性能的一个 主要因素；第三应具有公平性，防止一些网络连接过度占用网络资源 而导致另一些网络连接不能公平使用网络资源：最后，应具有稳定性， 当网络带宽基本不变时，使各网络连接发送速率快速收敛于稳态。 1 2 拥塞控制系统的分类 目前拥塞控制的研究主要分为： ( 1 ) 从控制理论的角度，拥塞控制算法可以分为开坏控制和闭环控 制两大类。当流量特征可以准确规定、性能要求可以事先获得时，适 于使用丌环控制；体流量特征不能准确描述或者当系统不提供资源预 留时，适于使用闭环控制方式。开环的拥塞控制是通过良好的设计来 避免问题的出现，确保问题在一开始就不会发生。一旦系统安装并运 行起来，就不再做任何中问阶段的更正。闭环的拥塞控制是建立在反 4 馈环路的概念上，它首先检测网络中拥塞的发生，然后将拥塞信息报 告到拥塞控制点，最后拥塞控制点根据拥塞信息进行调整以消除拥塞。 i 闭环的拥塞控制可以动态地适应网络的变化，但它的缺点是算法性能 受到反馈延迟的严重影响。当拥塞发生点和控制点之间的延迟很大时， 算法性能会严重下降。i n t e r n e t 中主要采用闭环控制方式。 ( 2 ) 根据实施拥塞控制算法的位置不同，可以将拥塞控制算法分为 两大类：链路算法( 1 i n ka l g o r i t h m ) 和源算法( s o u r c ea l g o r i t h m ) ”1 。 链路算法在网络设备( 如路由器和交换机) 中执行，作用是检测网络拥 塞的发生，产生拥塞反馈信息。链路算法主要有传统的“队尾丢弃法” ( d r o p - t a i l ) 和目前热点研究的主动队列管理( a c t i v e q u e u e m a n a g e m e n t ，a q m ) 算法( 在第3 章中有重点介绍) 。源算法在主机和网 络边缘设备中执行，作用是根据反馈信息调整发送的速率。拥塞控制 算法设计的关键问题是如何生成反馈信息和如何对反馈信息进行响 应。源算法中使用最广泛的是t c p 协议中的拥塞控制算法( 在第2 章 中有重点介绍) 。 ( 3 ) 从实施控制的类型上，拥塞控制可分为基于窗口和基于速率 ( 又称基于方程) ”1 两种类型。t c p 采用的是典型的基于窗口的控制方 式，t c p 通过调整滑动窗口的大小控制发送到网络的数掘量，其易于实 现，且可以限制注入网络的最大流量；基于速率的控制方式是通过对 t c p 窗口控制机制进行建模，得到t c p 连接吞吐量与网络参数之间的解 析式，用柬指导源端发送速率的大小，一般适合多媒体数据流的传输 控制，重点的性能指标是t c p 友好性。 ( 4 ) 从推断网络状态的反馈信息的类型上，可以分为显式拥塞控制 ( e x p l ic i t ) 和隐式拥塞控制( i m p l ic i t ) 。在显式反馈方式中，网络使 用显式信号向执行拥塞控制的端点通告其状态( 有效带宽，缓存容量 等) ：在隐式控制方式中，控制端使用流量测量或者通过超时、重复a c k 等隐含信号来推断网络状态。 1 3 选题的意义 ( 1 ) 拥塞控制的研究一直是互联网发展中倍受关注的问题。 最初设计的i n t e r n e t 是无连接的分组交换网络，所有的业务分组 被不加区分地在网络中传输，网络能给出的唯一承诺就是尽自己最大 的努力传输进入网络的每一个分组，即网络提供“尽力而为”( b e s t e f f o r t ) 的服务模式，b e s t - e f f o r t 无法保证吞吐量和传送延迟等服务 质量( q o s ) 。建立在这种体系结构上的传统网络应用( 如：f t p ，e m a i l ， www ) 和网络协议具有较强的灵活性和适应性，但随着用户数量的急 剧增加和网络组成的日益复杂，网络负载常超过网络的处理能力，网 络的拥塞问题也越来越严重。i n t e r n e t 上主要的互连协议t c p i p 的拥 塞控制( c o n g e s t i o nc 0 1 t r 0 1 ) 机制对保证i n t e r n e t 的稳定具有十 分重要的作用。拥塞控制的研究一直是分组交换网络中倍受关注的一 个技术热点。 ( 2 ) 在强调业务模型的新网络体系结构中，如何通过增强的拥塞控 制为q o s 的实现提供一定的保证，是拥塞控制研究的目标之一。 近几年来，随着1 1 t e r n e t 和各种i p 业务的发展，要求网络不仅 能够支持传统数掘业务，而且能够支持高带宽、低延迟的新型数据业 务。要求i n t e r n e t 扩充尽力服务模型，使对延迟、丢失率和吞吐量有 各种需求的应用程序所提出的请求都能通过网络中的新机制束得到满 足，即必须支持服务质量q o s 。综合服务( i n t s e r v ) 和区分服务 ( d i f f s e r v ) 是结合应用的需要和技术的发展提出的网络业务模型，其 技术的核心都需要在恰当的层次和粒度上对流量进行必要的管理，其 中包括接纳控制、流量成形，队列管理、调度和拥塞控制等，但最基 本和最核心的是拥塞控制，实施拥塞控制是其它q o s 机制正常工作的 必要i j 提。 6 1 4 本文的工作 1 4 1 本文的内容 本文首先回顾了i p 网络中已有的拥塞控制技术，研究了i n t e r n e t 中t c p 的基于窗口的端到端拥塞控制方法，以及i p 层采用的“主动队 列管理”( a q m ) 拥塞控制机制，总结了t c p 流量控制和中间节点增强 机制等各研究方向中需要解决的问题。然后本文还重点分析了主动队 列管理这一热点领域中已有策略和算法的优缺点，以及进一步研究的 方向。在此基础之上本文主要完成的工作包括： 1 针对r e d 算法存在对参数依赖性大；平均队列不能完全反映网 络实际拥塞状况的闯题。本文结合平均队列和负载，提出了种新的 主动队列管理算法一一基于负载的选择性丢包算法。该算法结合平均 队列和负载，给出了一种新的拥塞判断方法和丢包率的计算方法。 2 提出了选择性丢包机制。选择性丢包机制筛选出占用超过平均带 宽的连接，区分r t t 值较大的连接和r t t 较小的连接，区分对拥塞信 息响应的响应性连接和对拥塞信息不响应的非响应性连接。在产生丢 包事件时丢弃占用超过平均带宽的连接或r t t 值较小的连接在缓冲区 头部的数据包，从而实现对各数据流的公平性。 3 最后通过仿真实验，验证了算法在提高网络的稳定性和公平性 方面是有效的。 1 4 2 本文的组织结构 第一章陈述网络拥塞和拥塞控制的基本概念，简单介绍拥塞控 制的研究概况。 第二章对i n t e r n e t 中端到端的拥塞控制和i p 层的拥塞控制机 7 制进行回顾。 第三章具体介绍拥塞控制在i p 层的发展，以及目前一些较为主 流的主动队列管理算法。 第四章提出了一种基于负载的选择性丢包算法。 、 第五章对算法进行了仿真，验证算法的有效性。 第六章最后对本文进行了总结与展望 1 5 小节 本章分析了网络拥塞现象，简述了拥塞控制及其研究意义，对现 有的网络拥塞控制策略作了分类。说明了选题的意义，介绍了论文的 研究内容和总体组织结构。 第2 章t c p i p 网络拥塞控制研究概述 2 1 基本概念 2 1 1 拥塞产生的原因 网络产生拥塞的根本原因在于“需求”大于“供给”，也就是用户 ( 或叫端系统) 提供给网络的负载( 1 0 a d ) 大于网络资源( 包括链路带宽、 存储容量和处理器处理能力) 的容量。从局部看，拥塞产生的直接原因 有三点：( 1 ) 存储空间不足；( 2 ) 带宽容量不足；( 3 ) 处理器处理能力弱、 速度慢”1 。从全局看，拥塞产生的原因有：( 1 ) b e s t e f f o r t 服务模型 网络不对数据传输的服务质量提供保证：( 2 ) 由于没有“接纳控制”算 法，网络无法根据资源的情况限制用户的数量；( 3 ) 缺乏中央控制，网 络无法根据资源的情况限制用户的数量；( 4 ) i n t e r n e t 资源分布的不均 衡性和流量分布的不均衡性，导致拥塞总是发生在资源相对短缺的位 置上。 虽然拥塞是由于网络资源的短缺引起的，但单纯增加资源并不能 避免拥塞的发生。有时甚至会加重拥塞程度。例如增加存储空日j 到一 定程度时，只会加重拥塞，而不是减轻拥塞，这是因为当数据包经过 长时间排队完成转发时，它们很可能早已超时，从而引起源端超时重 发，而这些数据包还会继续传输到下一路由器，从而浪费网络资源， 加重网络拥塞。 l m bl m bl m b 图2 1 1 1 网络链路带宽分御均为l m b 9 l o m bi m b 1 0 m b 图2 1 1 2 网络链路带宽分布不均匀 另外，增加链路带宽及提高处理能力也不能解决拥塞问题。例如， 图2 1 1 1 中，如果四个节点之日j 的链路带宽都是1m b ，传输某个文 件需要用时0 5 分钟；当第一个节点和第二个节点之问、第三个节点 和第四个节点之间的链路带宽提高到1 0 m b p s 时( 如图2 1 1 2 所示) ， 传输完该文件所需时间反而大大增加，这是因为在路由器r l 中，数据 包的到达速率远远大于转发的速率，从而导致大量数据包被丢弃，源 端的发送速度被抑止，使得传输时间大大增加。既使所有链路具有同 样大的带宽也不能解决拥塞问题，例如图2 1 1 3 中，所有链路带宽 都是1 0 m b ，如果a 和b 同时向c 以1 0 m b 的速率发送数据，则路由器r 的输入速率为2 0 m b ，而输出速率只能为l o m b ，从而产生拥塞。 图2 1 1 3 所有链路带宽都为l o m b 单纯地增加网络资源不能解决拥塞问题。因为拥塞本身是一个动态 问题，它不能只靠静态的方案来解决，而需要某种机制避免网络出现 拥塞或在网络出现拥塞时恢复网络的正常运行。 2 i 2 拥塞控制算法的评价方法 从用户的角度出发，可以比较端系统的吞吐量、包丢失率和延迟 0 等指标。 ( 1 ) 吞吐量：描述在单位时闯内被成功传送的信息量，可以是每秒 多少个报文或多少个报文分组。即给定时问内有效传输的数据。 ( 2 ) 延迟：也称时延，描述的是分组从源端开始传输直到最后被成 功地传送到目的所需要的时间。端到端的延迟包括：节点处理延迟 ( p r o c e s s i n gd e l a y ) 、排队延迟( q u e u i n gd e l a y ) 、传播延迟 ( p r o p a g a t i o i ld e l a y ) 、传输延迟( t r a n s m is s i o i ld e l a y ) 1 。 ( 3 ) 包丢失率( p a c k e t1 0 s s ) ：在网络中传输数掘包时丢弃数据包 的最高比率。交换机和路由器等网络设备在链路发生拥塞时通常会把 数据包堆积在缓冲区中。如果链路的拥塞时i 、日j 过长，在缓冲区中积存 的数据包会越来越多，有限的缓冲区空间被耗尽，这时就需要将一些 数据包丢弃。而丢弃的数据包就需要重传，总的传输时日j 必然会加长。 所以，包丢失率通常被用来作为反映网络拥塞状态的一个指标。 ( 4 ) 抖动( j i t t e r ) ：延迟的变化就是抖动。如果所有的包都通过相 同的路由到达接收端，则这些包应该具有相同的传播延迟；如果包大 小也一样，那么，传输延迟也基本一样；但是，如果网络中的业务量 有变化，排队延迟就会不一样，正是排队延迟的变化造成了抖动。拥 塞发生时，网络的延迟和抖动会急剧增大。 ( 5 ) 信道资源利用率：信道传输信息的有效时间与信道总可利用时 间之比。它通常不包括报头开销、传输冲突等各种形式的开销。 ( 6 ) 响应时间：网络服务请求和响应该请求之间的时间。 由于拥塞控制算法对一整个网络系统都有影响，在评价算法时应该 从整个系统的角度出发进行考虑。两个重要的评价指标是网络资源的 使用效率和资源分配的公平性。 ( 1 ) 网络资源的使用效率 网络资源的使用效率是由源端要求的总资源与网络资源的接近程 度决定的。如果源端总资源接近或等于网络所能提供的资源，那么这 种算法的效率就是高的，超载或负载不足都是效率不高的表现。效率 只与总资源的利用率有关，而与各个源端之间的资源利用无关。 效率= 网络负载传输延迟 如图2 1 2 1 ，a 点的搠塞程度是最恰当的，它对应于k n e e 与 c 1 i f f 之间。 效率 瑶l f 受皴 负霞 图2 i 2 1 网络最佳的拥塞状态 ( 2 ) 资源分配的公平性 公平性指的是在发生拥塞时各源端( 或同一源端建立的不同t c p 连 接或u d p 数据报) 能公平地共享同一网络资源( 如带宽、缓存等) 。处于 相同级别的源端应该得到相同数量的网络资源。产生公平性的根本原 因在于拥塞发生必然导致数据包丢失，而数据包丢失会导致各数据流 之间为争抢有限的网络资源发生竞争，争抢能力弱的数据流将受到更 多损害。所以说没有拥塞，也就没有公平性问题。 公平性评价的主要方法包括：m a x m i l 3f a i r n e s s 和f a i r n e s si n d e x 等。m a x - m i n f a i r n e s ：被非正式地定义为：每个用户的吞吐量至少和 其它共享相同瓶颈的用户的吞吐量相同。m a x m i nf a i r n e s s 是一种理 想的状况，但是它不能给出公平的程度。f a i r n e s si n d e x 定义为： m = 夥 他， f a i r n e s si n d e x 的计算结果位于0 和1 之间，并且结果不受衡量 单位的影响。如图2 1 2 2 所示拥塞闭环控制模型，结合此图给出公 平定义：完全公平时，f ( x ) = 1 ( 1 0 0 ) ，此时所有x i 平均分配；当所有 资源只提供给一个源端时，f ( x ) = 1 n 达到最小，当n 一一时，f ( x ) = o ； 如果n 个源端只有k 个平均共享资源，其它n k 个源端没有得到任何 资源，则f ( x ) = k n 。事实上在不同的应用背景中，可以给出不同的定 义公式，结合路由器中几种包调度算法，以网络中第i 个数据流( f l o w ) 在公平分配带宽时应得到的带宽来定义公平性： p 2 曰形丽b w l 其中b w 为该数据流经过链路的总带宽，b w 。为第i 数据流的要求 带宽，式( 2 1 2 ，2 ) 定义实质上与式( 2 1 2 1 ) 是一致的。 图2 1 2 2n 个用户共享一个网络下拥塞的闭环控制系统 2 2 端到端的拥塞控制 目前在i n t e r n e t ( i p v 4 ) 上采用t c p i p 协议，实际使用的拥塞控制 基本上是建立在t c p 的窗口控制基础之上的，i p 层( 网络层) 的路由器 所起的作用相对较小，但现在在i p 层控制拥塞的研究逐渐增多，已经 形成了一个新的研究热点。图2 2 1 显示了t c p i p 在ir l t e r n e t 上拥 塞控制的作用范围。 图2 2 1t c p i p 在i n t e r n e t 上拥塞控制的作用范围 2 2 1 端到端拥塞控制的发展 端到端的拥塞控制是从数据传输的角度出发，增强网络终端的流量 控制功能，从而控制网络中问结点的状态，提供给应用一个具有一定 质量的连接。一早期的拥塞控制方式，路由器通过丢弃分组或显式拥 塞通告( e x p l i c i tc o n g e s t io nn o t i f i c a t i o n e c n ) ”1 来向源端指示拥 塞的发生，路由器是相对被动的，源端系统对这些拥塞信号进行响应。 这种路由器被动而终端主机主动的端到端拥塞控制机制遵守了两个主 要原理：( 1 ) 实现流控自同步( s e l f - c l o c k i n g ) 的分组守恒定理，它基 本确定了什么时候必须改变窗口大小，什么时候应该传输分组；( 2 ) “和 式增加积式减少”( 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 m d ) 曲1 的窗口管理策略。a i m d 依赖简洁的实现机制，在多个相互冲突 的目标之问实现了较为理想的平衡与协调。虽然无法保证具有不同属 性的终端系统( 比如不同r t t 时日j 、不同分组大小、经历不同跳数的拥 塞链路等) 能够分配到等量的带宽，但却能够确保大致相似的用户得到 基本相等的网络资源。 根据m c i 的统计，总字节数的9 5 和总报文数的9 0 使用t c p 传输 “”，因此t c p 拥塞控制机制是端到端的流量控制的最主要的手段。早 期的拥塞控制研究主要集中在t c p 的拥塞控制，近年来各种非t c p 流 的拥塞控制研究逐渐丰富。由于t c p 的拥塞控制对具有相似的r t t 时 日j 、分组大小和拥塞程度的终端能做出大致相似的响应，因此能够确 保大致相似的用户分配到大致相等的带宽等网络资源，从这个角度看， t c p 具有公平性，这是t c p 拥塞控制最本质、最重要的特性。随着 i n t e r n e t 的不断发展，各种应用越来越多、越来越广泛。不仅传统的 基于t c p 的得到广泛应用( 如h t t p ，s m t p ，f t p 等) ，而且新兴的非t c p 应用不断得到增长，特别是在实时多媒体应用和多播( m u l t ic a s t ) 等方 面。t c p 的a i m d 机制对于丢失敏感而时延不敏感的应用非常适合，而 对时延敏感，但不要求可靠传输的实时应用则不能满足需要。在探测 空闲带宽和响应拥塞的过程中，t c p 的拥塞控制算法造成了信源速率的 大幅度变化。虽然有些“尽力传输”的业务能够很好地适应这种变化， 但其它应用则显得极不适应，比如流媒体业务更希望拥塞控制机制对 于拥塞的响应能够缓慢一些，从而有一个较为平滑的带宽占用来更好 地匹配实时生成的业务。因此，许多多媒体因用为保证服务质量，以 固定速率发送数据，而没有采用拥塞控制策略，所以当网络拥塞时， 所有的t c p 流根据拥塞控制策略减少它们的发送速率，这些实时应用 由于不采用拥塞控制策略而继续以固定速率发送数据，这样就会造成 t c p 流得不到公平的带宽。在组播业务中，t c p 的拥塞控制更显得不恰 当。由此带来了新的问题。一方而，需要一致的t c p 拥塞控制来达到 公平的带宽分配。另一方面，为了适应业务的特点而期望放弃t c p 的 拥塞控制机制。这种尴尬的两难局面促使研究者提出新的拥塞控制机 制，于是有了两个相近的概念：t c p 兼容性( c o m p a t i b i l i t y ) 和t c p 友 好性( f r ie n d l i n e s s ) 。近年来出现了许多t c p 友好的拥塞控制算法的 研究。 一些专门针对网络的多媒体应用传输控制协议也在迅速发展中。 t c p 协议提供可靠的端到端的传输控制，但是它的传输速率抖动大，并 且多媒体流并不需要完全可靠的传输；u d p 协议简单实用，但是不提供 拥塞控制，不能和t c p 友好共存，容易引起网络的拥塞，t c p 友好拥塞 控制机制的研究为流媒体的控制做了一定的准备。实时传输协议r t p 、 流媒体传输控制协议s t c p ，数据报拥塞控制协议d c c p ( d a t a g r a m c o n g e s t i o nc o n t r o lp r o t o c 0 1 ) 等是业界最近讨论的热点。 2 2 2t c p 拥塞控制 t c p 拥塞控制是通过控制一些重要参数的改变实现的。t c p 用于拥 塞控制的参数主要有： ( 1 ) 拥塞窗口( c w n d ) ：描述源端在拥塞控制情况下最多能发送数据 包的数量； ( 2 ) 通告窗口( a w i n ) ：是接收端给源端预设的发送窗口大小，它只 在t c p 连接建立的初始阶段使用； ( 3 ) 发送窗口( w i n ) ；是源端每次实际发送数据的窗口大小； ( 4 ) 慢启动阀值( s s t h r e s h ) ：是拥塞控制中慢启动阶段和拥塞避免 阶段的分界点，初始值通常设为6 5 5 3 5 b y t e s ； ( 5 ) 回路响应时间( r t t ) ：一个t c p 数据包从源端发送到接收端， 源端收到接收端确认的时间l b j 隔； ( 6 ) 超时重传计数器( r t o ) ：描述数据包从发送到失效的时问问隔， 通常设为2 r t t 或5 r t t ； ( 7 ) 快速重传阀值( t c p r e x m t t h r e s h ) ：是能触发快速重传的源端收 到重复确认包a c k 的个数。当此个数超过t c p r e x m t t h r e s h 时，网络就 进入快速重传阶段，其缺省值为3 ； 基于源端的拥塞控制策略中，使用最为广泛的是t c p 协议中的拥 塞控制策略，t c p 的拥塞控制采用的是基于窗口的端到端的闭环控制方 1 6 式。t c p 协议是目前互联网中使用最为广泛的传输协议。 t c p 协议的目的是为上层应用提供可靠的服务，其主要特征在 于：( 1 ) 确保各流享用带宽的公平性。( 2 ) 动态发现当前可利用的带宽。 ( 3 ) 拥塞避免及控制机制以避免拥塞崩溃( c o n g e s t i o nc o l l a p s e ) 的 发生。 标准版本的t c p 使用的是一种和式增加积式减少( a i m d ) 的基于窗 口的控制发送速率机制，即是：发送端每收到一个确认，就对拥塞窗 口加1 。当发送端检测到丢包事件，则将当前的拥塞窗口减半，降低发 送速率，并重传丢失的数据包。t c p 采用a m i d 以保证稳定性及带宽享 用的公平性。大量的实践证明这种拥塞控制机制对i n t e r n e t 上大量文 件传输等b e s t e f f o r t 型服务具有较好的适应性。但人们认为它们依 旧不够完善，需要新的策略与算法来完善研究与应用中发现的新问题。 早期的t c p 协议只有基于窗口的流控制( f l o wc o n t r 0 1 ) 机制而没 有拥塞控制机制，因而容易导致网络拥塞。1 9 8 8 年v a nj a c o b s o n 针对 t c p 在网络拥塞控制方面的不足，提出了“慢启动”( s 1 0 ws t a r t ) 和“拥 塞避免”( c o n g e s t i o na v o i d a n c e ) 算法。它们被所有的i n t e r n e t 主 机支持，在很长一段时间内，接收端驱动的t c p 流量控制是唯一可行 的拥塞控制方法。1 9 9 0 年出现的t c pr e n o “2 1 版本增加了“快速重传” ( f a s tr e t r a n s m i t ) ，“快速恢复”(