（计算机系统结构专业论文）网络拥塞控制及red算法改进策略研究.pdf

摘要 随着互联网规模和高速网络中多媒体应用的发展，人们对网络服务质量( q o s ) 的需求越来越高，不但对网络有很高的带宽要求，而且要求信息传输的低延迟和 低抖动等，需要提供端到端的q o s 控制和保证。而网络拥塞是影响网络服务质 量的重要因素，实施拥塞控制也是其它q o s 机制正常工作的必要前提。因此， 如何避免拥塞、如何进行拥塞控制保证q o s 是当前的研究热点。 主动式队列管理机制( a q m ) 是i e t f 推荐的基于路由器拥塞控制的关键技术， 它和t c p 端到端的拥塞控制相结合，是解决目前h l t 锄e t 拥塞控制问题的一个主要 途径。a q m 通过评估网络状态、预测拥塞的出现，对分组进行有目的的丢弃， 从而可以使发送端更及时地了解到网络状况并调整发送速率。r e d ( r a n d o m e a r l yd e t e c t i o n ) 算法就是a q m i 拘- - 个典型代表，但是现有算法在响应速度、稳定 性及环境敏感性等方面仍有缺陷。对此，本文通过对的r e d 算法进行详细分析的 基础上，总结出已有算法的优势和不足，提出了一种新的a q m 算法c a r e d ( c a u c h ya d a p t i v er e d ) 算法。 c a i 通d 算法对原有r e d 算法的分组丢弃概率p b 的计算方法和参数p m a x 的 取值进行修改。其一：利用模糊理论中的升半哥西分布的隶属函数代替原来的线 性增加分组丢弃概率的函数。c 恹e d 分组丢弃概率计算采用升半哥西分布函数， 以平均队列长度为样本来获得，将控制范围扩展为最小阈值到最大缓冲之间，实 现了分组丢弃概率变化的平滑化，保证在每一阶段系统都能迅速地对拥塞作出反 应。 其二：c a r e d 通过计算出路由器队列单位时间间隔内的平均队列长度，分 别与最大阂值或最小闽值的比较，根据二者差值的大小动态地调整p m a x 的大小， 调整向源端发送拥塞通知的速率，维持队列长度的稳定，避免不必要的传输延时 和抖动。并且p m a x 的值不是每个时间间隔都更新，而只有当连续两个时间间隔 内s t a t u s 都处于相同状态，那么就可以更精确的认为缓冲队列中负载过大或过小， 算法就会动态增加或减少p m a x 的值，这样避免了p m a x 的改变过于频繁，从而提 高了链路的利用率。 其三：c a r e d 算法的健壮性来自它对p m a x 的规律性调整，如果大量突发数 据包导致网络拥塞程度发生急剧变化，则p m a ) 【则需要过一段时间甚至l o 秒或2 0 秒才能适应。为了保证算法在这段时间里性能不会过度下降，本文将p m a x 的范 围限制在【o0 1 ，o 5 】之间，这样，即使这段时间内平均队列长度q a v 不在目标范 围内，平均延时和吞吐量也不会下降太多，使算法虽然在理论使不能得到最优， 但其性能可得到保证。 在n s 2 网络仿真器上对算法进行了验证，一系列仿真实验表明，c a r e d 能 够有效地适应网络流量的变化，保持队列长度的稳定，减少了队列溢出和空闲现 象的发生，在保持队列长度稳定以及提高链路利用率方面明显优于r e d 算法。 关键词：拥塞控制：主动队列管理；早期随机检测( r e d ) ；网络服务质量 i i a b s t r a c t w i t ht l l e u n c e a s i n gd e v e l o p m e n t o fi n t e m e ts c a l e ，p e o p l eh a v ea l l e v e r - g r o w i n gd e m a n df o rt h eq u a l i t yo fs e r v i c eo fc o m p u t e rn e t w o r k s ( q o s ) a n d n o w a d a y s ，i nt h eh i g h s p e e dn e t w o r km u l t i m e d i a sa p p l i c a t i o nn o to n l yh a st h ev e r y h i g hb a n d w i d t hr e q u i r e m e n tt o t h en e t w o r k ，b u ta l s o r e q u i r e si n t e l l i g e n c e t r a n s m i s s i o nl o wd e l a ya n dt h el o wv i b r a t i o na n ds oo n ，n e e d st op r o v i d et h e e n d t o e n dc o n t r o la n dg u a r a n t e eo fq o s t h en e t w o r kc o n g e s t i o ni sag r e a tf a c t o r t oa f f e c tt h en e t w o r kq u a l i t yo f s e r v i c e ，s ot h ei m p l e m e n t a t i o nc o n g e s t i o nc o n t r o li s p r e r e q u i s i t ef o ro t h e rq o sm e c h a n i s m n o r m a lw o r k a tp r e s e n t ，c o n g e s t i o nc o n t r o l m e c h a n i s mo fi n t e m e ta n dq u a l i t yo fs e r v i c ea r et h ec e n t r a li s s u e so ft h ec u r r e n t r e s e a r c h 1 1 1 ea c t i v eq u e u em a n a g e m e n tm e c h a n i s m ( a q m ) i s ，w h i c ht h ei e t f r e c o m m e n d s ，t h ee s s e n t i a lt e c h n o l o g yb a s e do nt h er o u t e rc o n g e s t i o nc o n t r o l ， w h i c hc o m b i n e sw i t l lt h et c pe n d - t o - e n dc o n g e s t i o nc o n t r o l ，b e i n gam a i nm e t h o d t os o l v et h ec o n g e s t i o nc o n t r o lq u e s t i o no f t h ep r e s e n ti n t e m e t b ye v a l u a t i o nt h es t a t e o fn e t w o r ka n df o r e t e l l i n gt h ea p p e a r a n c eo ft h ec o n g e s t i o n , a q mg u nd r o pt h e p a c k e tp u r p o s e f u l l ys ot h a tt h es e n d i n ge n dc a nb ei n f o r m e do ft h es t a t eo fn e t w o r k a n dt h e na d j u s ti t ss e n d i n gr a t e b u tt h ec u r r e n ta l g o r i t h m sa r e n ts t i l lp e r f e c ti nt e r m s o fr e s p o n s e st i m e - s t a b i l i t ya n ds e n s i t i v i t yt ot h ee n v i r o n m e n ta n ds of o n h i nt h i s p a p e r ，t 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 ft h ee x i s t e n ta l g o r i t h m sa r ec o n c l u d e d b a s e do na n a l y s i n gt h ec u r r e n tp r e v a l e n tc o n g e s t i o nc o n t r o la l g o r i t h m sr e di nd e t a i l ， a l li m p r o v e da l g o r i t h mc a r e do f a c t i v eq u e u em a n a g e m e n t ( a q m ) i s p r o p o s e d a sar e s u l t , c a r e da l g o t i t h mh a sm a d et l l em o d i f i c a t i o n so fo r i g i n a lr e d a l g o t i t h mi nt h ec o m p u t a t i o n a lm e t h o do fp r o b a b i l i t yo fp a c k e td r o p - p ba n dt h e a d a p t i n go ft h ep a r a m e t e r p - f i r s t , b a s e do nt h ef 缸巧m a t h ，i n s t e a do ft h e p r o b a b i l i t yf u n c t i o no fd r o p ，w eu s et h em e m b e r s h i pf u n c t i o no f a s c e n dd e m i c a u c h y d i s t r i b u t i o n o r i g i n a lr e da l g o r i t h mb a s e do nt h ea v e r a g eq u e u es i z eo ft h eb u f f e rt o 1 1 1 a d j u s tp r o b a b i l i t yo fd r o p ，a n dw h e nt h ea v e r a g eq u e u es i z er e a c h e st h eq b 。( d e n o t e d b yq k “) ，t h ed r o p p i n gr a t ei n c r e a s e sl i n e a r l yf r o mp m 。t o1 t h i s j u m pw i l la g g r a v a t e t h ej i t t e ro fb u f f e rq u e u e c a r e di m p r o v ep r o b a b i l i t yc a l c u l a t i o nu s e daa s c e n d h a l f - c a u c h yd i s t r i b u t i o nf u n c t i o n ，t oe x t e n dt h es c o p eo fc o n t r o lf r o mt h em i n i m u m t h r e s h o l dt ot h eb u f f e r s i z ei tc a na l s oa c h i e v et h es m o o t h n e s sf r o mp a r tt oc o m p l e t e m a r k i n go rd i s c a r d i n g s e c o n d ：c a r e dc a l c u l a t e st h ea v e r a g eq u e u el e n g t hi nt h e r o u t e ru n i t - t i m e - g a p ，a n db yc o m p a r i n gi tw i t ht h em a x i m t u nv a l u ea n dt h e m i n i m u mv a l u e ，t h ei n t e r p o l a t i o nc a l lb eo b t a i n e d b a s e do nt h ei n t e r p o l a t i o n ss i z e ， c a r e dc a l la d j u s t 匆枷c a l l yt h es i z eo f p m “，a n dt h e r e f o r ea d j u s tt h es e n d i n gr a t e o fc o n g e s t i o nn o t i f i c a t i o nt ot h es o u r c ee n di nt i m ea n dm a i n t a i nt h es t a b i l i t yo ft h e q u e u el e n g t h ，i no r d e rt oa v o i dt h eu n n e c e s s a r yd e l a yo f t r a n s m i s s i o na n dv i b r a t i o n t h ea l g o r i t h mi sv e r i f i e di nn s 2n e t w o r ks i m u l a t i o nm a c h i n ea sw e l l 、b yt h e i n d i c a t i o no fas e r i e so fs i m u l a t i o ne x p e r i m e n t s ，c a r e dc a nv a l i d l ya d a p tt h e c h a n g eo fn e t w o r kf l o we f f e c t i v e l y ，h o l ds t a b i l i t yo fq u e u el e n g t h ，r e d u c e p h e n o m e n o no c c u l t e n c eo f t h eq u e u eo v e r f l o wo rt h ei d l e g r e a t l y a n di ti ss u p e r i o r t ot h er e d a l g o r i t h mi nm a i n t a i n i n gt h es t a b i l i t yo fq u e u el e n g l ha n de n h a n c i n gt h e u t i l i z a t i o nr a t i oo f t h el i i l k s 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 ( a c t i v eq u e u em a n a g e m e n t ) ；r e d ( r a n d o m e a r l yd e t e c t i o n ) ；n e t w o r kq o s i v 原创性声明和关于论文使用授权的说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究所取得的成果。除文中已经注明引用的内容外，本论文不 包含任何其他个人或集体已经发表或撰写过的科研成果。对本文的研 究做出重要贡献的个人和集体，均己在文中以明确方式标明。本声明 的法律责任由本人承担。 论文作者签名：邋日期：业 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学 校保留或向国家有关部门或机构送交论文的复印件和电子版，允许论 文被查阅和借阅；本人授权山东大学可以将本学位论文的全部或部分 内容编入有关数据库进行检索，可以采用影印、缩印或其他复制手段 保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：龇师签名夕拯毒喜一日期：牲 1 1 研究的背景 第1 章绪论 随着i n t e m e t 的普及，网络同人们的生活和工作已经密切相关。通过网络进 行的数据和信息传输已经成为现代商业社会重要且不可缺少的组成部分和赖以 生存的基础。近年来，随着信息技术的迅猛发展，各个领域的网络应用大量增加， 使得原来已经存在的庞大的数据传输量成倍地增长。而网络硬件资源的增长速度 是无法满足如此快速的传输需求增长的，于是网络拥塞就产生了。当网络拥塞产 生的时候，将无法使吞吐量维持在网络固有的传输能力水平，实际上网络吞吐量 急剧下降，产生拥塞崩溃。在1 9 8 6 年l o 月，由于拥塞崩溃的发生，美国l b l 到 u cb e r k e l e y 之间的数据吞吐量从3 2 k b p s 跌落到4 0 b p s 【3 】。之后，网络拥塞控制成 为了研究热点。 拥塞现象的发生和i n t e r n e t 的设计机制有着密切的联系。最初设计的i n t e m o t 是非面向连接的分组交换网络，所有的业务分组被不加区分地在网络中传输。网 络能给出的唯一承诺就是尽自己最大的努力( b e s t - e f f o r t ) 传输进入网络的每一 个分组，但它无法给出一个定量的性能指标，譬如，吞吐量、端到端时延和分组 丢失率等参量。而无连接网络的节点之间在发送数据之前不需要建立连接。这使 得在网络的中间节点上不需要保存和连接有关的状态信息。但是使用无连接模型 难以引入“接纳控制”( a d m i s s i o nc o n t r 0 1 ) 算法，在用户需求大于网络资源时难 以保证服务质量。因此网络的性能不仅仅是其本身可以确定的，还受用户施加负 载的影响，很显然，这种网络体系结构缺乏一定的隔离和保护机制。网络中有限 的资源是由多个用户共享使用的。由于没有“接纳控制”算法，网络无法根据资 源的情况限制用户的数量。又由于缺乏中央控制，网络也无法控制用户使用资源 的数量。目前，i n t e m e t 上用户和应用的数量都在迅速增长，当多个用户对网络的 需求总量大于网络实际传输能力时，必然会导致网络拥塞的发生。虽然拥塞源于 资源短缺，但增加资源并不能避免拥塞的发生，有时甚至会加重拥塞程度1 4 1 。例 如，增加网关缓存表面上看可以防止或缓解由于拥塞引起的分组丢弃，但随着缓 存的增加，端到端的时延也相应增大。因为分组的持续时间是有限的，超时的分 组同样需要重传。因此，过大的缓存空间有可能使总延迟超过端系统重传时钟的 值从而导致分组重传。这些分组白自浪费了网络的可用带宽，反而加重了拥塞。 传统网络中采用的服务模式为尽力而为服务模式( b e s t - e f f o r t ) 。这个选择和早 期网络中的应用有关【”。传统的网络应用主要是f t p ，t e l n e t ，s m t p 等，它们对 网络性能( 带宽、延迟、丢失率等) 的变化不敏感，b e s t e f f o r t 模型可以满足需要。 随着网络的发展，其应用领域不断拓展，应用模式不断丰富。多媒体应用等服务 对网络延迟、传输速率等网络性能比较敏感。传统的b e s t e f f o r t 模型已不能很好 地满足其应用需求。加之商业化进程等的推动，越来越需要对网络所传输的业务 类型有一个较为具体和明确的定义，需要在恰当的层次和粒度上对流量进行必要 的管理，包括接纳控制、流量成形、队列管理、调度和拥塞控制等各个方面。 因此，引进更多、更合理的控制机制对己有网络的稳定运行将是至关重要 的。其中一个最基本和最重要的要求就是防止网络出现拥塞崩溃。要使网络运行 在轻度拥塞的最佳状态。很难想象一个时常有可能出现严重拥塞且无法及时加以 恢复的网络能够实现良好的q o s ( q u a l i t yo f s e r v i c e ) 保证。实施拥塞控制应该 是其它q o s 机制正常工作的必要前提。 拥塞控制算法的分布性，网络的复杂性和对拥塞控制算法的性能要求又使 拥塞控制算法的设计具有很高的难度。到目前为止拥塞问题还没有得到很好的解 决。 1 2 国内外相关的研究现状 t c p 的流量控制是i n t e r a c t 正常运行的基础，围绕着t c p 流量控制的拥塞控制 一直是i n t e m e t 研究的一个热点。在i n t e m e t 发展初期，拥塞控制主要是通过t c p 协议中端到端基于滑动窗口的流量控制完成的 3 1 ，t c p 的流量算法中也逐步增加 了慢启动、拥塞避免、快速重传与快速恢复等算法，以期对网络流量进行控制。 随着应用需求的丰富和技术的发展，研究者开始认识到想完全依赖实现在 终端系统上的策略与算法很难满足越来越多的复杂应用需求。于是，人们把注意 力转向网络中的路由器等中间节点设备，期望通过增强它们的功能来实现主机端 无法达到的目标网。就拥塞控制而言，网络中间节点有可能更及时，甚至提前准 确了解网络的拥塞状态，并依此实施有效的资源管理策略，使网络能有效地避免 2 拥塞，或尽早从严重的拥塞状态中恢复过来。当然，对路由器功能的扩展要受继 承性和延续性的限制，否则将影响技术的实用性。事实上，现有的路由器扩展功 能，主要包括调度和队列缓存管理。调度( s c h e d u l i n g ) 直接管理下次发哪个分组 和分配各个流的带宽。而队列，缓存算法管理路由器缓冲区中分组队列的长度， 即在必要或适当的时候丢掉一些分组。 早期的队列管理算法采用尾丢弃算法( d r o p t a i l ) ，即当路由器缓存仍有空间 时，接受并缓存一切来不及处理的分组。当缓存空间耗尽时，丢弃所有新到来的 分组。由于发送到路由器的分组呈一个序列状态，在该算法中这个序列末尾的分 组被丢弃，所以被称为尾丢弃算法。目前i n t e m e t 中广泛采用的传输控制协议仍 是t c p 协议，在该协议下，当发送方检测到发送数据有所丢失时会降低并重新 调整发送速率。当发送方的发送速率大于网络的处理能力时，路由器缓存会被不 断消耗，直至耗尽。此时发送方新发的数据分组会被丢弃，当它检测到这一情况 时，它会降低发送速率。因此可以想象，如果在路由器中增加智能预测环节，使 得在路由器缓存被耗尽前就有计划的丢掉一部分分组，就可以提早通知发送方降 低发送速率，避免可能出现的危险。这就是主动队列管理的由来。 1 9 9 8 年，r f c 2 3 0 9 中强烈建议在路由器队列管理算法中使用主动队列管理 策略，并推荐r e d ( r a n d o me a r l yd e t e c t i o n ) 口1 算法为候选算法。然而，在随后的 研究中，发现m 仍有一些缺陷。近年来，不断有一些新的主动队列管理算法出 现，大多数有关r e d 算法的研究都将注意力集中到了改进和完善已有的不足与缺 陷，产生了不少r e d 的变种算法，较有影响力的有w r e d 8 ，s t a b i l i z e d r e d 【9 1 ， s e l f c o n f i g u r a t i o nr e d t ，a d a p t i v er e d p ”，f r e d 1 2 】和b a l a n c e d r e d t l 3 1 和虚队 列a q m 策略等14 】【”】。目前，主动队列管理算法已经成为了t c p 端到端拥塞控制 研究中的技术热点之一。它通过网络中间节点有控制的分组丢弃机制实现了较低 的排队延时和较高的有效吞吐量。 在业界出于产品性能的考虑，路由器厂商纷纷在自己的产品中支持r e d 算 法，如c i s c 0 7 5 0 0 等系列路由器，j u n i p e r 的m 4 0 、m s 0 等。为了提高a t m 交换 机中u b r 业务支持t c p 连接的性能，采用r e d 作为帧丢弃算法新业务 g f r ( g u a r a n t e 圯f r a m eg a t e ) 的实现也以r e d 作为首选的队列管理算法。在 d i f f s e r v 的业务框架下，由r e d 演化出来的r i o ( r e dw i t hi n o u t ) 成为提供确 保服务( a s s u r e ds e r v i c e s ) 的基本算法。由此可见，r e d 算法已被广泛使用在网络 队列管理中来提高系统的综合性能。 1 。3 本文研究的内容 网络的拥塞控制和服务质量是密不可分的研究课题，鲁棒的拥塞控制机制 是保证口网络正常运作的基础，也是保障口网络服务质量的基础。没有鲁棒的 拥塞控制机制，保障用户的服务质量根本无从谈起。t c p 端到端的拥塞控制机制 是确保互联网鲁棒性的重要因素，互联网的成功己证明t c p 拥塞控制机制在防 止拥塞崩溃方面的巨大作用。但随着近十年来计算机网络的爆炸式增长，特别是 多媒体业务的广泛应用，互联网己经不可能再仅仅依靠端节点提供的t c p 拥塞 控制机制。路由器直接掌握着互联网上各种网络传输信息，能够有效地监控队列 的长度，从而尽早检测到早期的拥塞。另外，路由器能够全面地审视各个流对拥 塞造成的影响，从而决定将拥塞信息通知哪个源端，使其降低数据发送速度。因 此采用基于路由器的拥塞控制和t c p 端到端拥塞控制相结合的方法，是解决目 前互联网拥塞控制问题的一个主要途径。基于路由器的拥塞控制主要是通过对其 队列进行管理来实现的，目前的队列管理主要还是被动式队列管理( p a s s i v e q u e u em a n a g e m e n t ，p q m ) 。本质上p q m 并没有参与到网络拥塞管理中去，只 是在队列溢出的情况下被动地丢包。i e t f 推荐在路由器上使用主动式队列管理 ( a c t i v eq u e u em a n a g e m e n t ，a q m ) 机制来控制在什么时候丢多少包，从而有效地 管理队列长度，以支持端到端的拥塞控制。 r e d 算法是最常用的一种a q m 技术，其基本思想是通过监控路由器输出 端口队列的平均长度来探测拥塞。一旦发现拥塞逼近，就随机地选择源端来通知 拥塞，使它们在队列溢出导致丢包之前降低发送数据速率，从而缓解网络拥塞。 r e d 算法存在的一个主要问题就是其参数是静态配置的，而互联网是基于带宽 统计复用的，一条链路上往往有很多活跃流，并且流量变化很大，r e d 算法不 能适应这种变化导致其在很多情况下性能会大大下降。我们的研究目的就是对 r e d 算法的参数配置进行改进，使其能够根据流量的变化来自动配置参数，从 而保证性能的稳定。 4 1 4 论文的组织结构 第一章绪论介绍网络拥塞控制的研究概况及研究背景，最后对本文的研究内 容进行了概述。 第二章网络网络拥塞控制机制对网络拥塞的原因，网络拥塞的现象及拥塞控 制的基本机制进行了阐述，对t c p 拥塞控制源算法、链路算法及算法的评价标 准逐一进行了讨论。 第三章对队列管理机制进行了详细综述。a q m 是i e t f 为了解决t c p 拥塞 控制机制存在的问题而提出的一种队列管理技术，r e d 算法就是a q m 的典型代 表。本章介绍了r e d 算法的基本原理，分析了r e d 算法的优点以及存在的问 题，包括公平性问题、参数敏感性问题等。 第四章介绍了一种新的a q m 算法c 舢也d ( c a u c h ya d a p t i v er e d ) 。 r e d 是一种常用的a q m 算法，它通过计算平均队长来感知拥塞，较好地解决了 传统的“去尾”算法存在的一些问题。但是由于r e d 算法对参数设置和流量变 化的敏感，导致其在网络流量发生变化时不能很好地控制队列长度。c a r e d 分 组丢弃概率计算采用升半哥西分布函数，以平均队列长度为样本来获得，将控制 范围扩展为最小阈值到最大缓冲之间，实现了分组丢弃概率变化的平滑化，保证 在每一阶段系统都能迅速地对拥塞做出反应。根据数据包的到达速率及单位时间 内的平均队列长度来自动配置相关参数，从而调整向源端发送拥塞指示的速率， 以适应流量的变化，维持队列长度的稳定，避免不必要的延时和丢包。最后通过 仿真实验对c a r e d 的性能进行了验证。最后给出仿真实验结果，并对c a r e d 性能进行了分析。 第五章结论与展望总结了本文进行的研究工作，并提出进一步深入研究的方 向。 第2 章网络拥塞控制机制 从早期的i s d n 到i n t s e r v ，再到后来的d i f f s e r v ，这些都是结合应用的需要 和技术的发展提出来的，但是无论最终采取哪种业务体系结构，其技术核心都需 要在恰当的层次和粒度上对流量进行必要的管理，其中包括接纳控制、流量成形、 队列管理、调度和拥塞控制等诸多方面，但最基本和最核心的应该依旧是拥塞控 制，因为很难想象一个时常有可能出现严重拥塞且无法及时恢复的网络能够实现 良好的q o s 保证。因此，实施拥塞控制应该是其它q o s 机制正常工作的必要前 提。 2 1 网络拥塞的基本概念及互联网模型 当网络中存在过多的数据包时，网络的性能就会下降，这种现象称为拥塞。 在网络发生拥塞时，会导致吞吐量下降，严重时会发生“拥塞崩溃”( c o n g e s t i o n c o l l a p s e ) 现象。一般来说，拥塞崩溃发生在网络负载的增加导致网络效率的降低 的时候。f l o y d 总结出拥塞崩溃主要包括以下几种：传统的崩溃、未传送数据包 导致的崩溃、由于数据包分段造成的崩溃、曰益增长的控制信息流造成的崩溃等 等。 拥塞现象的发生和的互联网的设计机制有着密切关系， e i n t e m e t 中使用的 网络模型包括： ( 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 ) 网络相 比，由于报文交换网络对资源的利用是基于统计复用( s t a t i s t i c a lm u l t i p l e x i n g ) 的， 因此提高了资源的利用效率。但在基于统计复用的情况下，很难保证用户的服务 质量( q o s ) ，并且很容易出现数据包“乱序”的现象，对乱序数据包的处理会大 大增加拥塞控制的复杂性。 ( 2 ) 无连接( c o n n e c t i o n l e s s ) 网络：互联网的节点之间在发送数据之前不需 要建立连接，从而简化了网络的设计，网络的中间节点上无需保留和连接有关的 状态信息。但无连接模型很难引入接纳控匍 ( a d m i s s i o nc o n t r 0 1 ) ，在用户需求大 于网络资源时难以保证服务质量：此外，由于对数据发送源的追踪能力很差，给 6 网络安全带来了隐患，无连接也是网络中出现乱序数据包的主要原因。 ( 3 ) “尽力而为”( b e s t - e f f o r t ) 的服务模型：即不对网络中传输的数据提 供服务质量保证。在这种服务模型下，所有的业务流被“一视同仁”地公平地竞 争网络资源，路由器对所有的数据包都采用先来先处理唧r s tc o m ef i r s ts e r v i c e f c f s ) 的工作方式，它尽最大努力将数据包送达目的地。但对数据包传递的可靠 性、延迟等不能提供任何保证。这很适合e m a i l ，v t p ，w w w 等业务。但随着互 联网的飞速发展，口业务也得到了快速迅猛的发展，特别是随着多媒体业务的兴 起，计算机己经不是单纯的处理数据的工具。这对互联网也就相应地提出了更高 的要求。对那些有带宽、延迟、抖动等特殊要求的应用来说，现有的“尽力而为” 服务显然是不够的。 2 2 网络拥塞产生的原因 拥塞发生的主要原因在于网络能够提供的资源不足以满足用户的需求，这些 资源包括缓存空间、链路带宽容量和中间节点的处理能力。由于互联网的设计机 制导致其缺乏“接纳控制”能力，因此在网络资源不足时不能限制用户数量，而 只能靠降低服务质量来继续为用户服务，也就是“尽力而为”的服务。当通信子 网中有太多的报文时其性能降低，就产生拥塞。拥塞会导致传输时延的急剧增加， 造成大量的分组丢失，以及网络吞吐量的急剧下降。 拥塞产生的直接原因有如下三点p 6 】： ( 1 ) 存储空间不足：如果几个输入数据流共同需要同一个输出端口，那么在 这个端口就会建立排队。如果没有足够的存储空间，数据包则会被丢弃。对突发 数据流更是如此。增加存储空间在某种程度上可以缓解这一矛盾，但当路由器有 无限存储量，拥塞只会变得更坏，而不是更好，因为在网络里数据包经过长时间 排队完成转发时，它们早已超时，源端认为它们已经被丢弃，而这些数据包还会 继续向下一个路由器转发，从而浪费网络资源，加重网络拥塞。 ( 2 ) 带宽容量不足：低速链路对高速数据流的输入也会产生拥塞。所有信源 发送的速率必须小于或等于信道容量。所以在网络低速链路处就会形成带宽瓶 颈，当其满足不了通过它的所有源端带宽的要求时，网络就会发生拥塞。 ( 3 ) 处理器处理能力弱、速度慢：如果路由器的c p u 在执行排队缓存、更新 7 出丕盔堂至i 堂焦盐塞 路由表等功能时，处理速度跟不上高速链路，也会产生拥塞。 图3 1 显示了负载与吞吐量的关系硎，当负载较小时，吞吐量与负载之间呈 现性关系，到达膝点( k n e e ) 之后，随负载的增加，吞吐量的增量逐渐变小。当负 载越过崖点( c l i f f ) 之后，吞吐量却急剧下降，此时网络陷入了严重拥塞状态， 若不及时进行控制，则有可能导致网络崩溃。拥塞控制的目的就是使吞吐量尽量 保持在膝点与崖点之间，使网络的负载始终保持在一个相应的区间之间。通常将 k n e e 点附近成为拥塞避免区，k n e e 和c l i f f 2 间是拥塞恢复区，而c i i 位艺外是拥塞 崩溃区间。 吞吐量 负载 图2 - 1 负载与吞吐量之间的关系曲线 2 3 拥塞崩溃的表现形式 通常而言，当网络负载增加导致的网络可用资源下降的时候拥塞崩溃才会出 现。但是一些现有的机制也可能导致在网络拥塞并未达到最大负载的情况下出现 拥塞崩溃1 3 8 1 1 3 9 】m 1 。 拥塞崩溃最早是在上世纪八十年代被报告的，主要有由于t c p 连接不必要 的重传那些已经在传输中或者已经被接收端接收的分组。我们把由于不必要的分 组重传导致的拥塞崩溃称为经典拥塞崩溃( c l a s s i c a lc o n g e s t i o nc o l l a p s e ) 。关于经 典拥塞崩溃的问题已经通过现在的t c p 中的时钟和拥塞控制机制得到基本解决。 拥塞崩溃的第二种形式是，未送达分组导致的崩溃( c o n g e s t i o nc o l l a p s ef r o m u n d e l i v e r e dp a c k e t s ) 。这种崩溃源于那些浪费了网络带宽的分组在到达最终目的 地前被丢弃了。普遍认为这是当前i n t e m e t 拥塞崩溃中最大的且没有解决的问题。 未送达分组导致的崩溃主要是由于当前的一些不支持端到端拥塞控制的开环应 用程序的大量应用。更具破坏性的应该是一些b e s t - e f f o r t 服务应用程序对于丢包 率的响应方式，这些程序在丢包率增加的情况下会增加它们的发送速率。除了以 上描述的两种拥塞崩溃外，其它可能的拥塞崩溃形式还包括基于碎片的拥塞崩溃 ( f r a g m e n t a t i o n - b a s e dc o n g e s t i o nc o l l a p s e ) ，控制流增加导致的拥塞崩溃 ( c o n g e s t i o nc o l l a p s ef r o mi n c r e a s e dc o n t r o lt r a f f i c ) 以及陈旧分组导致的拥塞崩 溃( c o n g e s t i o nc o l l a p s ef r o ms t a l ep a c k e t s ) 。 基于碎片的拥塞崩溃是由那些将要在接受端被丢弃的分组碎片所导致的，这 些碎片在传输的过程中其网络层的部分分组被丢弃，因而在接受端无法重新组装 为一个有效的分组。但是这些碎片浪费了拥塞链路上的带宽，从而导致了拥塞崩 溃。这种崩溃的危险来自于链路层的传输单元和高层的重传单元之间的不匹配， 可以通过两层之间的确认机制来避免这种拥塞崩溃的发生。还有一种导致这种拥 塞崩溃的情况是，在目的节点，传输层正确的接收了分组，但是随后它们被应用 程序丢弃了。由于网络的延迟，应用程序退出正在进行中的部分完成的t c p 传 输，重新请求相同的数据，导致可用带宽的浪费。在高延迟和大的分组丢失率的 情况下最有可能发生这种崩溃形式，可以通过允许端节点储存和重新利用部分完 成的传输数据来减少这种崩溃的发生。 另一种可能的拥塞崩溃控制流增加导致的拥塞崩溃是由于控制用数据 分组在拥塞链路上的传输导致的。在这种情况下，不断增加的网络负载导致的拥 塞的不断严重，从而用于缓解拥塞的指示信息被更加频繁的发送到拥塞链路上， 加剧了网络拥塞。 2 4 拥塞控制算法分类 根据算法的实现位置，可以将拥塞控制算法分为两大类：源算法( s o u r c e a l g o r i m m ) 和链路算法( l i n k a l g o r i t h m ) 。源算法在主机和网络边缘设备中执行， 作用是根据获得的反馈信息调整发送速率。链路算法在网络设备( 如路由器和交 换机) 中执行，作用是检测网络拥塞的发生，产生拥塞反馈信息。 2 4 1 拥塞控制源算法 源算法中使用最广泛的是t c p 协议中的拥塞控制算法。t c p 是目前在 9 i n t e m e t 中使用最广泛的传输协议。根据m c i 的统计，总字节数的9 5 和总报文 数的9 0 使用t c p 传输。近年来，t c p 中采用了很多新的拥塞控制算法，包括 慢启动( 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 0 、 快速恢复( f a s tr e c o v e r y ) 、选择性应答( s a c k ) 等，大大提高了网络传输的性能。t c p 中使用的拥塞控制算法己经成为保证i n t e m e t 稳定性的重要因素。 t c p 的拥塞算法是基于窗口的和式增加积式减少( a d d i t i v ei n c r e a c e m u l t i # i c a t i v ed e c r e a c e ，a i m d ) 的控制机制。流量控制由两个窗口来执行：发 送端的拥塞窗口( c w n d ) 和接收窗口的通告窗口( r e v w n d ) 。1 9 8 8 年、，锄j a c o b s o n 在文献9 l 中指出t c p 在控制网络拥塞方面的不足，并提出了“慢启动”( s l o w s t a r t ) 、“拥塞避免”( c o n g e s t i o n a v o i d a n c e ) 算法。1 9 9 0 年出现的t c p r e n o 版本 增加了“快速重传”( f a s t r e t r a n s m i t ) 、“快速恢复”( f a s t r e c o v e r y ) 算法，避免 了网络拥塞不严重时采用“慢启动”算法而造成过大地减小发送窗口大小、网络 资源得不到充分利用的现象。 目前的拥塞控制算法有t a h o e 、r e n o 、s a c k 、v e g a s 等。这些算法的基本拥 塞控制机制主要就是由“慢启动”、“拥塞避免”、“快速重传”、“快速恢复”这四 个算法组合而成。不同算法对某些初始值的操作及拥塞产生后的反应均有所不 同。 ( 1 ) 慢启动阶段 旧的t c p 在启动一个连接时会向网络中发送许多分组，由于一些路由器必 须对分组排队，这样就有可能耗尽存储空间，从而导致t c p 连接的吞吐量 ( t h r o u g h p u t ) 急剧下降。 避免这种情况发生的算法就是慢启动。当建立新的t c p 连接时，拥塞窗口 ( c w n d ) 初始化为一个分组大小( 通常一个分组缺省为5 1 2 b y t e s ) ，即c w n d = 1 个t c p 分组。发送端按c w n d 大小发送数据，以后每收到一个来自接收端的 a c k ( a c k n o w l e d g e ，确认) ，c w n d 就增加分组发送量。所以在慢启动阶段，e w n d 将随r t i 呈指数级增长：1 个、2 个、4 个、8 个。 ( 2 ) 拥塞避免阶段 当发现超时或收到3 个重复a c k 确认帧时，即认为网络发生拥塞。此时就 进入拥塞避免阶段。慢启动闽值( s s t h r e s h ) 被设置为当前c w n d 的一半。如果是超 时，c w n d 还要被置l 。如果此时c w n d s t h r e s h ，t c p 就重新进入慢启动过程：如果 a , v n d s s t h r e s h ，t c p 就执行拥塞避免算法：c w n d 在每次收到一个a c k 时只增加 l c w n d 个分组。所以在慢启动阶段和拥塞避免阶段中，c w n d 相应于每个r t r ， 分别对应指数变化和线性