（信号与信息处理专业论文）宽带通信网中拥塞控制机制的研究.pdf

中国科学技术大学硕士学位论文 摘要 摘要 i n t e r n e t 在今天所取得的巨大成功很大程度上应该归功于t c p i p 模型，i p 协 议的通用互联能力和t c p 协议的传输控制能力为i n t e r n e t 提供了强大的稳定性和 鲁棒性。但直至今天，拥塞控制一直是困扰i n t e m e t 的一个难题，本文就是从源 端和路由端两个方面对宽带通信网中的拥塞控制进行了积极的探讨以试图提高 拥塞控制系统的性能。 本论文的主要内容及创新研究成果如下： 1 对t c p 的慢启动机制进行了改进，提出一种新的拥塞窗口增最方式：本 文首先分析了网络中拥塞现象的起因以及“尽力而为”服务模型中的传输控制体 系。然后介绍了源端t c p 拥塞控制的思想及几种典型的t c p 协议，在此基础上 本文对t c p 协议中的慢启动机制做了改进，使之能自适应地改变拥塞窗口增量 的大小，从而能更平滑地过渡到t c p 拥塞控制的下一阶段；并且可以通过一个 调节因子来适应不同的网络环境。这样可以减少慢启动后期的突发数据量，从而 提高了t c p 拥塞控制机制的性能。 2 提出一种新的主动队列管理算法m r e d ：路由器中采用主动队列管理机 制能更有效地预防和避免拥塞，但最流行的r e d 算法使用平均队列长度作为衡 量拥塞的指标却不是十分准确，因此本文提出了一种新的基于r e d 及r q 的算 法m r e d 。m r e d 以数据包到达速度和平均队列长度两个变量作为衡量拥塞的 指标，这样能更准确地反映网络中当前和一段时间内的拥塞状况。 在源端和路由端两部分做了改动后，宽带通信网中的拥塞控制机制将更加准 确有效，从而提高了网络的整体性能。仿真实验的结果也验证支持了我们所提改 进算法的正确性和有效性。因此，本文具有一定的理论意义和应用价值。 关键词：拥塞控制，传输控制协议，主动队列管理，随机早期检测 璺型堂茎查奎兰堡圭兰堡垒苎! ! 里 a b s t r a c t i n t e r n e ts h o u l do w em u c ho fi t sg r e a ts u c c e s st 0t h et c p i pm o d e l t h e c o n n e c t i v i t yo fi pa n d t h et r a n s f e rc o n t r o la b i l i t yo ft c p p r o v i d e i n t e m e tw i t h o u t s t a n d i n gs t a b i l i t ya n d r o b u s t n e s s b u tt i l lt o d a y ，c o n g e s t i o nc o n t r o li ss t i l la b i gp r o b l e mt oi n t e m e t r o u t e r sa n dh o s t sa r et w o m a i nc o m p o n e n t so ft h e c o n g e s t i o nc o n t r o ls y s t e ma n dt h i st h e s i sc o n c e r n st h e s et w oa s p e c t sw i t h i n t e n s i v ed i s ；c u s s i o n ss oa st oi m p r o v et h ep e r f o r m a n c eo ft h ec o n g e s t i o n c o n t r o ls y s t e m t h em a i nr e s e a r c hi s s u e si nt h i st h e s i sa r el i s t e da sf o l l o w i n g ： 1 m o d i f i e dt h et c p ，ss l o w s t a r ts c h e m e b yp r o p o s i n g an o v e la p p r o a c ht o i n c r e a s et h es i z eo ft h ec o n g e s t i o nw i n d o w f i r s t , w ea n a l y z e dt h ec a u s e so f c o n g e s t i o na n di n t r o d u c e dt h et r a n s f e rc o n t r o ls v s t e mi nt h e 。b e s te f f o r t s e r v i c er o o d e l t h e nw ei n t r o d u c e dt h ec o r ei d e ao ft c p ，sc o n g e s t i o nc o n t r o l a n ds o m e 押p i c a lt c p s b a s e do nt h ed i s c u s s i o n sa b o v e ，an e ws l o w - s t a r t s c h e m ei sp r e s e n t e dw h i c ha p p r o a c h e st h eu p p e rt h r e s h o l do fs l o w s t a r tm o r e g r a d u a l l ya n dc a na d a p ti t s e l ft ov a r i o u sk i n d so fn e t w o r ke n v i r o n m e n tb y u s i n ga na d j u s t i n gv a r i a b l e i nt h i sw a t h eb u r s td a t ac a n b er e d u c e di nt h e l a t e rs t a g eo fs l o w - s t a r ts c h e m e 2 p r o p o s e dan o v e la c t i v eq u e u em a n a g e m e n ta l g o r i t h mm r e d ：a c t i v e q u e u em a n a g e m e n tm e c h a n i s md e p l o y e di nr o u t e r sc a np r e v e n ta n da v o i d c o n g e s t i o nm o r ee f f i c i e n t l y r e d ，t h e m o s tp o p u l a ra l g o r i t h m ，u s e st h e a v e r a g eq u e u el e n g t ha st h ei n d i c a t o ro fc o n g e s t i o n ；h o w e v e li t i sn o tv e r y a c c u r a t e an o v e la l g o r i t h m ( m r e d ) b a s e do nr e da n dr qi s p r e s e n t e di n t h i st h e s i s t h ek e yi d e ao fm 喂e di st oa d o p tb o t hd a t ar a t ea n da v e r a g e q u e u el e n g t h a st h ei n d i c a t o r so fc o n g e s t i o n , w h i c hc a nr e f l e c tt h ec u r r e n ta n d l o n g - t e r ms t a t u so fc o n g e s t i o n i nn e t w o r k sm o r e a c c u r a t e i v w h e nr o o d i f i c a t i o n sa r em a d ea tb o t hh o s t sa n dr o d t e r s ，t h ec o n g e s t i o n c o n t r o lm e c h a n i s mi nb r o a d b a n dc o m m u n i c a t i o nn e t w o r k sb e c o m e sm o r e a c c u r a t ea n de f t i c i e n t a n dt h e nt h e g o a l o f i m p r o v i n g t h eo v e r a l l p e r f o r m a n c eo fn e t w o r k si sa c h i e v e d r e s u l t so fs i m u l a t i o ne x p e r i m e n t sa l s o v a l i d a t e dt h ec o r r e c t n e s sa n d e f f i c i e n c yo ft h ep r o p o s e da l g o r i t h m s ，t h e r e f o r e , t h i st h e s i sh a st h e o r e t i cs e n s ea sw e l ia sa p p l i e dv a l u et os o m ee x t e n t k e y w o r d s ：c o n g e s t i o nc o n t r o l , t r a n s f e r c o n t r o l p r o t o c o l ( t c p ) ，a c t i v e q u e u em a n a g e m e n t ( a q m ) ，r a n d o m e a r l yd e t e c t i o n ( r e d ) i i 中国科学技术大学硕士学位论文 第一章绪论 第一章绪论 i n t e r n e t 中的传统服务模型的机制为“尽力而为”( b e s te f f o r t ) 的服务模型， 这一模型是建立在t c p i p 协议簇的实现基础之上的。自从于上个世纪六十年代 开始投入使用以来，几十年的实践证明了这是一个非常有效，而且获得了巨大成 功的服务模型。其成功在技术上很人程度上应归功予i p 协议的通用互联能力和 t c p 协议的具有自适应能力的传输挎制机制。不可否认，t c p 中的拥塞控制机 制对于i n t e m e t 的稳定发展起了关键作用，在i n t e m e t 的规模、速度以及用户增 加了几个数量级的情况下，这种算法在阻止网络发生拥塞方面仍可表现出较好的 性能。当前t c p 中的拥塞控制算法最早是由j a c o b s o n 在1 9 8 8 年提出的【“，尽管 在过去的十几年中该算法得到了许多改进，例如r f c 2 5 8 1 ( r e n o ) 2 1 ，r f c 2 0 1 8 ( s a c k ) 3 1 ，r f c 2 5 8 2 ( n e w r e n o ) 4 1 ，但是其基本的窗1 ：3 调节模式没有改变。 随着网络业务的不断丰富以及网络规模的进一步扩大，尤其是带宽一时延积的不 断增加，t c p 拥塞控制算法将成为提升网络性能的一个瓶颈口】。 拥塞控制算法通常包括两部分【“，一部分是在源端实施的t c p 算法，其根据 路由路径的拥塞状况，动态地调整发送速度或者拥塞窗口的大小：另一部分是在 路由端进行的链路算法，其不断更新该链路的拥塞量并将拥塞信息反馈给使用该 链路的数据源端。 本章我们将说明网络中发生拥塞的起因，以及i n t e r n e t 所采用的“尽力恧为” 服务模型中的传输控制。然后我们简要介绍了当前i n t e m e t 的拥塞控制算法以及 目前存在的一些问题。 1 1 网络中的拥塞现象 由于路由器往往要把由多条输入链路进来的分组复用到同一条输出链路中， 所以它接收这些分组的速度经常会超出共享链路的带宽。如果这种状况持续下 去，路由器的缓存队列里的分组就会越积越多，最终导致这个队列溢出，而路由 器也不得不开始丢弃分组。这种状态称为“拥塞”，避免和处理拥塞的策略则称 为“拥塞控制”策略。 1 中国科学技术大学硕士学位论义 第- 章鳍论 t c p 是一个面向数据流的、全双工的、为上层提供可靠的数据交付服务的传 输层协议，它使用一个名为“带重传的肯定确认”( p o s i t i v ea c k n o w l e d g e m e n t w i t h r e t r a n s m i s s i o n ) 的技术来实现可靠性【”。这项技术要求接收方收到数据之后向发 送方回送确认报文( a c k ) 。发送方对发出的每个分组都保存一份记录，在发 送下一个分组之前等待a c k 的到达。发送方还在送出分组时估计a c k 到达的 时间( 这个时间称为往返时间，或者尺7 丁：r o u n d t r i p t i m e ) ，并启动一个定时器。 如果定时器超时前a c k 还没有到达，t c p 就重发相应的分组，同时增大对r 玎 的估计，直到这个值达到一个预设的上限。 当拥塞出现时，有的分组被路由器丢弃了，t c p 不得不重发这些分组并增加 r 珊q 估计值。有的分组虽然没有被丢弃，但是其在路由器的排队时间明显变长 了，这同样会引起t c p 发送方的定时器超时，于是t c p “错误”地重发了这些分 组。在最坏的情况下，实际的r 刀超过 t c p 发送方的r r r f d i 计值的j 二限，此时 t c p 会在收到每一个分组的a c k 之前把这些分组都重发好几份，这又加重了已经 处于拥塞中的路由器的负担，它不得不丢弃更多的分组，而且也冈为这些额外的 处理而增加了其它分组的排队时间，从而又增大了r 丁l 这种恶性循环的最终结 果是网络性能严重恶化，有效吞吐量急剧下降，甚至于网络完全瘫痪。这种现象 称为拥塞崩溃( c o n g e s t i o nc o l l a p s e ) ，在1 9 8 4 年t 扫n a g l e 首先观察到【8 】口 1 2 “尽力而为”服务模型中的传输控制 众所周知，i n t e m e t 的基本构架是建立在i p 协议基础之上的。在传统上，i p 协议中所有的分组都受到相同的处理，对于任何分组，不存在明确的传输保证， 这就是所谓的“尽力而为”的服务模型。网络只是尽力地传送递交给它的分组， 除了为了丢弃无效分组而引入的m 以外，分组的传递不受任何定量的传输质 量性能( q o s ) 的约束。这种模型并没有一个正式的规范，i p 协议是v 一种先有实 践后有描述的协议，因此能够适用于各种从低速到高速，可靠性从非常差到非常 好的广泛的网络条件。这一特性是与其设计的要求紧密相关的。 近年来，对于如何扩展i n t e r n e t 体系结构，以试图为不断出现的实时多媒体 的应用提供一种服务质量保证，提出了不少的研究方向。存在有两种极端的情形： 一种是在路由器上进行资源预留和保存“依流”( p e r f l o w ) 状态，但由于网络 中国科学技术大学硕士学位论文 第一章绪沦 的异构性、实现机制的复杂性和可扩展问题，这种模型没有被普遍应用；另一种 是在“尽力而为”服务模型的网络上提供足够的资源，来保证实时多媒体应用能 够获得需要的性能，但这只在局部网络中才存在可能，在太规模网络中，或是在 i n t e m e t 中则是不现实的。为了保护“尽力而为”的服务，需要对网络的传输进 行更多的控制，特别是防止拥塞崩溃的出现、降低拥塞程度并保证公平性。研究 和一部分实践证明，在“尽力而为”服务网络中若采用了适当的控制机制也能够 产生服务“区分”( d i f f e r e n t i a t i o n ) ，这并不会损害i n t e m e t “尽力而为”的服务 特性，也不会超出体系结构和最初设计原则的限制。 网络资源( 包括链路带宽和缓存空间) 是有限的，而“尽力而为”网络中的 资源共享是一种“非合作式”的，这会造成网络拥塞的问题，甚至引发拥塞崩溃 出现。从1 9 8 1 年开始，i n t e m e t 采用了端到端的基于窗口的流控机制的t c p 实 现 r f c0 7 9 3 ，获得了长期稳定的拥塞控制效果。这一流控机制要求所有的用户 是“合作的”，即对于拥塞控制信号能够做出一致的响应。目前，有许多不按 t c p 规则对拥塞信号进行响应的用户，因此，它们获得了超出公平份额的侵占性 带宽，损害了对于“合作的”用户的服务，危及了整个系统的运作稳定性。有些 研究提出，通过对于非t c p 流采取“t c p 友好”( t c p f r i e n d l y ) 【9 1 的行为，使 它们在长时段内吞吐量不超过相同条件下标准t c p 流的吞吐量，但这种定义是 不严格的。另外，现有i n t e r n e t 体系结构对于合作的拥塞控制行为没有激励机制， 反而是不合作的用户得到了侵占性的获益，因丽需要在路由器上对于用户的合作 性进行区分。 由于i n t e m e t 没有显式的接纳控制( a d m i s s i o nc o n t r 0 1 ) 和定量的服务保证， 在多个用户的竞争环境中，需要有恰当的“公平性”定义。在计算机网络领域中， “m a x - m i n 公平性”i i o 】是最常用的，它是指“每个用户的吞吐量至少和其它有 相同瓶颈链路的用户一样多”。公平性可以是沿一条路径进行宏观考察( 全局视 图) ，或是在每条链路上考察( 局部视图) 。要使局部的公平分配转化成全局的 公平分配，每个用户( 流) 应将它的资源占用量限制为其路径上最少的局部公平 分配量。也有人提出m a x m i n 公平性在某些环境中是次优的，为此f k e l l y 引 入了称为“成比例的公平性”( p r o p o r t i o n a lf a i r n e s s ) 1 作为带宽共享时更合适 的公平模型。成比例的公平性有利于短路径流或短矗乃1 流。无论采用何种公平 中国科学技术大学预士学位论文 第一章绪论 性的定义，在流量条件变动频繁的环境中，确定进行公平性检查的合适的时间长 度是很重要的。 公平性并不意味着为所有用户分配相等的资源，它的定义通常还和管理策略 有关。网络级的策略要考虑拓扑、连通性、端到端的性能目标和网络动态变化： 节点级的策略要考虑分类、监控、缓存管理及调度等机制。 i n t e m e t 的体系结构建立在“所有流相关的状态信息应保存于主机”这个概 念之上 1 2 】，因此，拥塞控制机制主要在端主机上实现。在检测到拥塞后，源端 应降低分组的发送速度，这种机制称为“端到端的流量控制”。为了让主机能够 检测到拥塞，路由器必须能提供网络现在( 或将要) 处于超负荷状态的信息，这 种机制称为“反馈”。 网络的反馈和源端的响应是i n t e m e t 拥塞控制的基础，但是，在主机端做出 决策以及将网络视作仅是丢弃分组的黑盒子，限制了对网络资源分配的更多控 制，也限制了网络所能提供服务的范围。因为路由器知道自身的拥塞程度，因此， 在路由器上引入拥塞控制机制能使网络更主动地管理其资源。有两种基于路由器 的控制机制：“调度”，用于直接管理输出链路上的带宽分配；“队列缓存管 理”，用于管理缓存空间和队列的占用，从而间接地影响带宽分配。 1 2 1 端到端的流量控制 流量控制方法一般可以分为两大类：开环控制和闭环控制。开环流量控制只 能用于不必考虑单个用户的行为对其它网络用户所产生影响的环境。在丌环流量 控制方案中，发送方用突发长度( b u r s ts i z e ) 和突发间隔( i n t e r - b u r s ti n t e r v a l ) 等参数向网络描述它的速度。网络检查发送方给出的参数，如果基于资源可用性 或策略原则的接纳控制同意此请求，则网络沿着从发送方到接收方的路径按照这 些参数进行资源预留，发送方只要保证其速度符合给定的描述，这样就能避免网 络的拥塞。这种模式是与面向连接的体系结构相适应的，但不能简单地用端到端 的机制来实现，因为它要求所有路由器上有资源预留机制。 闭环流量控制则用于变动更大的环境中，源端动态地调整它们的速度，以与 网络资源的公平份额相匹配。公平份额是经常变动的，发送方必须能跟踪这种变 中国科学技术大学硕士学位论文 第一章绪论 动并调整其速度，从而实现资源的更有效利用。闭环控制可以是适应性的窗口， 即源端通过变更己发送但未确认的分组的数目( 窗口大小) 来间接控制传送速度； 或者是适应性的速度，即源端每发送一个分组就设置一个定时器( 其超时值等于 合适的传送速度的倒数) ，定时器超时就发送下一个分组。基于窗口的方案相对 容易实现，因为它们不需要在非实时操作系统上难以实现的精确定时器。 1 2 2 反馈机制 将网络拥塞或恰当的发送速度等信息通知给发送方的机制称为“反馈”。闭 环流量控制和网络整体性能都依赖于反馈，如果没有反馈机制，源端就无从知晓 如何调整发送速度，网络将变得不稳定、不公平、或是拥塞或是未充分利用。反 馈包括了系统的状态信息，因此应源自网络且最终传递给发送方。发送方或者直 接从网络接收反馈，或者通过接收方而接收，即有隐式和显式两种形式。 隐式反馈要求端主机负责监视自己的传输性能( 延迟、丢失等) ，从而推断 网络的状态并确定合适的发送速度。最常见的隐式反馈信号是分组丢弃，一般由 路由器产生。但分组丢弃不一定就是拥塞指示，比如在易出错的无线链路上。其 它的隐式反馈方法可以是观察瓶颈链路上的分组转发速度【1 3 l ，或测量发送速度 变化后的端到端延迟的变化【l ”。 隐式反馈的优点是路由器的实现较简单，因为路由器可以专注于资源分配， 而不必计算及产生恰当的反馈信号。但是，端主机必须知道路由器的调度机制， 否则所观察到的性能可能起误导作用，不能真实描述网络的实际拥塞状态。 显式反馈的形式可以是拥塞通知或速度指示。由于协议报头上能够携带的信 息量有限，显式反馈可以是二值( 比如是否经历拥塞) 或多值( 比如经历了几次 拥塞) 的。在二值反馈中，要经过网络反馈和主机调整间的多次反复，才能找到 恰当的操作点。t c p i p 网络中的最式反馈方法是i c m p 源端抑制报文和显式拥 塞通知( e c n ) 0 s oi c m p 源端抑制报文实际极少运用，因为它在出现拥塞时耗 费带宽，对拥塞的处理也是低效和不公平的。在e c n 反馈方案中，每当路由器 检测到拥塞的出现，就给分组报头的c e 位置位，接收方将此位复制到确认分组 的报头中，发送方的流控机制负责按某种算法来调整窗口或速度。速度指示是另 一种显式反馈方法，它将分配的速度传回给源端，但这种方法只在a t m 网络而 s 中国科学技术大学硕士学位沦文 第一章鳍论 非i n t e m e t 中实现。 1 2 3 队列管理及调度机制 分组交换网络的中间系统一般使用“存储转发”( s t o r e ，a n d f o r w a r d ) 技术 来传送分组：每个中间节点( 如i p 路由器或a t m 交换机) 先从某条输入链路中 接收一个完整的分组，将其放入缓存队列中，然后再通过一定的分组调度策略将 其转发出去。当有多个主机的分组需要通过同一条输出链路时，中间节点采用“统 计多路复用”( s t a t i s t i c a lm u l t i p l e x i n g ) 策略在这些主机之间其享其输出链路带 宽。统计多路复用的基本思想是： 1 ) 以分组为单位对输出链路进行时分复用，即在当前被调度的分组被完全 发送到输出链路之前任何其它竞争该输出链路的分组都必须等待。 2 ) 分组调度的时间分配不是事先预留的，而是按需进行的，即当某个数据 流( 比如一个t c p 连接) 没有分组需要转发时，不为它分配任何调度时 间。 “存储一转发”带来了两个基本问题：一是如何决定一个输入分组是否可以进 入缓存队列，即队列管理问题：二是如何决定缓存队列中的哪一个分组应该先被 转发出去，即分组调度问题。在传统的i p 路由器中，队列管理是通过“丢尾”算 法( d r o pt a i l ) 来进行的：当一个分组到达时，如果缓存队列非空则允许其进入 队列，否则就将其丢弃；分组的调度策略则使用“先进先出”的方法，即下一个 被转发的分组总是缓存队列中队头的分组。 在基于统计多路复用的分组交换网络中，中间系统( 如i p 路由器或者a t m 交 换机等) 一般要先将输入的分组缓存到队列中，然后再通过一定的调度规则将其 转发出去。个好的队列管理算法应该能够吸收短时间的突发流量，保持较低的 丢包率和排队时延，同时获得尽量高的链路利用率。 早期的路由器中并没有专门的队列管理算法，其缓存也只是个简单的 f i f o ( f i r s ti n - f i r s to a t ：先进现出) 队列，当分组到达时如果队列已满，就把队 列尾部之外的分组全部丢弃。这种简单的缓存管理方法后来被称为“丢尾”算法。 调度机制决定了分组的服务次序，它通过在一定的时间段内为每个流服务一 6 中国科学技术大学硕士学位论文 第一章绪论 定数量的分组来控制带宽的分配。设计调度原则时要考虑诸多因素，最重要的因 素是要实现的优先级的数量，调度器只在高优先级的用户没有分组等待服务时才 为低优先级的用户服务。某一优先级内部服务次序是需考虑的另一因素，特别是 当同一优先级内部有多个延迟要求不同的聚集流时【1 6 1 。莱一优先级内部的流聚 集度也是需要考虑的，可以是依流调度，也可以是多个流按相同的优先级处理。 另外，要从“w o r k - c o n s e r v i n g ”和“n o n - w o r k - c o n s e r v i n g ”两种调度方式中作选 择，“w o r k c o n s e r v i n g ”调度器只在没有分组需要服务时才空闲，而 “n o n - w o r k - c o n s e r v i n g ”调度器即使在有分组等待服务时也有可能空闲。 调度原则应当易于实现、提供公平性、能够满足某些性能约束，且有高效的 接纳控制过程。最简单的调度算法是用f i f o 队列实现的f c f s ，但f c f s 不能提 供带宽的m a x m i n 公平分配。而g p s 是一种理想化的公平调度算法。它假设 分组可以无限分割，且多个会话可同时由输出链路以不同速度发送分组。最简单 的g p s 仿真算法是轮询法( r o u n d r o b i n ) ，如果队列带有权重，则这种算法称为 带权重的轮询法( w r r ) 。w r r 需要知道每个队列的分组平均大小。w f q t l 8 1 是 另一种近似g p s 的算法。它将每个分组与该分组预计完成服务的时间值相联系， 然后按时间值的次序进行服务。最初的w f q 算法计算复杂度很大，之后出现了 许多变种，如w 2 f q | ，s e l f - c l o c k e df a i rq u e u i n g l 2 。1 。 调度原则是高层资源管理机制( 比如链路共享的重要部分) ，将是未来j p 服 务模型的重要组件。 1 3 当前i n t e r n e t 拥塞控制算法 网络协议设计中要面对的一个重要问题是如何保证在众多用户之间有效和 公平地分配网络资源( 包括链路带宽和路由器的缓存) 。在分组交换网络中，每 个分组在经过路由器时都会先被放到某个队列按一定的规则缓存起来等候发送。 按j a c o b s o n 的说法【2 ”，缓存队列的主要作用是吸收短期内正常的突发流量，当 有太多的分组竞争同一条输出链路时，缓存队列就会溢出，而路由器也不得不开 始丢弃分组。如果这种状况在某个路由器中持续了足够长的时间，则称该路由器 进入了拥塞状态。在图1 1 中，源主机l 和2 到达路由器l 的链路带宽都比较大， 但是路由器1 和2 之间的链路却拥有一个相对小的带宽，所以这是一个很容易出 中国科学技术大学硕士学位论文 第一章绪论 现拥塞现象的网络。此时把路由器称为“瓶颈路由器”，输出链路称为“瓶颈链 路”。 源主机2 图1 1 容易出现拥塞现象的网络示意图 目的主机2 处理拥塞的办法一般可以分为两类：拥塞控制( c o n g e s t i o nc o n t r 0 1 ) 和拥塞 避免( c o n g e s t i o na v o i d a n c e ) 。前者是在网络已经过载的情况下采取的响应措 施，一般通过端到端的传输控制来实现；后者则是为了避免网络出现过载而采取 的预防和检测策略，一般需要路由器端的支持。拥塞控制和资源分配是密切相关 的。一方面，如果网络在资源分配上采取了积极的措旋( 比如强制实施指定的准 入控制和q o s 策略) ，就可以避免出现拥塞，从而也就没有必要进行拥塞控制。 然而，以任意精度分配网络资源是非常团难的，尤其是在i n t e m e t 这样的以松散 方式互联的大型异构网络中，这根本无法实现。另一方面，如果网络允许主机根 据需要想发送多少数据就发送多少数据，那么不管整个网络的带宽有多大，都有 潜在的出现拥塞的危险。一般来说，为了达到较优的资源共享方案，在主机端和 路由器端都必须进行有效的拥塞控制。主机必须控制自己将数据注入网络的速 度，路由器则必须实施积极的队列管理策略。 拥塞控制算法包括源端算法和路由端的链路算法。源端算法依据拥塞信息获 取方式的不同又可分为基于分组丢失的方法和基于队列延时的方法。具体来说， t c pr c n o 以及改进版本都是使用分组丢失作为拥塞指示；而t c pv e 髓s 则主要 是根据队列延时的变化来获得拥塞信息的。 中国科学技术大学硕士学位论文 第一章绪沦 链路算法又包括分组调度和队列管理两部分，由于队列管理方案对于消除缓 冲队列振荡，降低队列延时，提高网络服务质量有着重要的作用，因此目前的研 究热点主要集中在主动队列管理方面。 当前i n t e m e t 的主流拥塞控制算法专要包括信源端的t c pr e n o 算法和路由 器中的队列管理策略。源端的t c p 算法包括慢启动、拥塞避免、快速重传和快 速恢复四个阶段，其核心的拥塞避免算法采用a i m d ( 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 1 m d 的拥塞控制算法可以用口，b 两个参数来刻画，它们分别对应着窗口调节中的递 增常数和倍减常数。当有分组丢失时，拥塞窗口从形减少至( j 一6 j 眠如果没有 分组丢失，在一个往返时间尺z 丁内，拥塞窗口从矽增加为十d 。 链路算法中的队列管理通过选择何时丢弃何种业务流分组来控制队列长度。 “丢尾”算法是目前i n t e m e t 中使用最为广泛的队列管理机制，它使用o n o f f 控 制器来生成反馈，当队列长度大于路由器缓存时，丢弃所有的新到分组。“丢尾” 算法和t c p 相互作用有时候会引起严重的性能和公平性问题，其中一个就是所谓 的“全局同步”( g l o b a ls y n c h r o n i z a t i o n ) 现象。设想有多台主机都同时启动经 过某个瓶颈路由器的t c p 连接，那么每一条t c p 连接都会通过慢启动均匀地、 但很快地抢占完瓶颈链路的带宽。这时“丢尾”算法在路由器上起作用，所有的 t c p 连接都同时被丢掉一个分组，从而在一个r 仃之后同时返回慢启动，这种循 环一直进行下去，大大地降低了本来就很宝贵的瓶颈链路带宽的利用率。 另一个问题是“闭锁”( 1 0 c k o u t ) 现象。设想某个瓶颈路由器上一直只有 一条t c p 连接的分组经过，a i m d 当然能有效地保证该连接能有效地使用路由器 的缓存。但是如果某个时候其它t c p 连接被启动并试图通过该路由器，则“丢尾” 算法会使得路由器维持着先前的那条t c p 连接对缓存的高占用率。这显然是很不 公平的。 为了解决以上问题，i e t f 在r f c 2 3 0 9 f 2 2 3 提出了主动的而非相应性的队列管 理概念，称为“主动队列管理”( a c t i v e q u e u e m a n a g e m e n t ：a q m ) ，以加强i n t e m e t 中间系统的拥塞控制功能。a q m 要求路由器做到： 1 ) 使平均队列长度保持在一个较小的值附近，以吸收突发流量，减小总的 中国科学拄术大学硕士学位论文 第章绪论 丢包量，同时降低分组的平均排队时间。 2 ) 避免大数据流长时间抢占小数据流的队列空间。 r f c2 3 0 9 指出“随机早期检测”( r a n d o m e a r t yd e t e c t i o n ，r e d ) 算法实 现7 a q m ，并推荐所有的路由器实现r e d 。与“丢尾”算法相比，r e d 为队列 管理增添了两种新机制，其一，不是等队列全满后再丢弃分组，而是使用概率判 定机制事先丢掉部分分组来预防可能发生的拥塞；其二，通过平均队列而非即时 队列调整分组丢失概率，由此来尽可能地吸收部分短暂的突发流量。然而，由于 r e d 的性能对算法的参数设置十分敏感，至今没有在i n t e m e t 中得到广泛的应用。 1 4 目前存在的问题 随着i n t e r n e t 规模的不断扩大，业务类型的增多，目前的t c p 拥塞控制算法 将很难适应下代高速i p 网络的要求，具体表现在以下几个方面： 1 ) 高带宽下，源端为获得较高的单流吞吐量，必须保持一个较大的拥塞窗 口，然而当产生拥塞时，目前t c p 拥塞避免算法中的窗口调节机制，需 要较长的恢复时间，不能有效地利用可用带宽，严重降低了网络资源的 利用率。 2 ) 由于t c p 的吞吐量反比于分组丢失率，如果单流数据要获得的吞吐量必 须维持一个不现实的分组丢失率，例如一般要求少于1 0 。2 的b e r ( b i t e i t o fr a t e ) ，即使不考虑无线链路下的传输，就目前的光纤链路来说也很 难实现如此低的b e r 。 3 ) 随着网络应用模式的不断丰富，不同业务类型的传输业务会有不同的服 务质量要求，例如流媒体业务对于发送速度振荡和延时抖动都较为敏感。 目前的t c p 拥塞控制算法加“丢尾”算法的队列管理方案无法实现各种 不同业务的服务质量要求。 4 ) 由于i n t e r n e t 中某些多媒体业务数据流使用u d p 协议进行传输，当网络 发生拥塞时，没有采用相应的拥塞避免机制从而占用了大量的网络带 宽，造成了带宽分配得严重不公平，最终可能会导致i n t e m e t 发生严重 崩溃。 1 0 生旦! ! ! 堂垫查奎兰堡主兰垡至苎 一兰二! ! 丝 5 1 随着网络延时的增加和带宽的提高，目前的t c p r e d 组合方式，将会 在源端和链路端产生强烈的振荡，使i n t e r a c t 运行在一个不稳定的环境 中，很难想象一个时常有可能出现严重振荡且无法及时加以恢复的网络 能够提供良好的服务质量保证。 1 。5 论文主要贡献和内容安排 在查阅了国内外大量相关文献的基础上我们认为，i p 网络的“尽力而为” 服务模型己经使i n t e m e t 在全球范围内取得了巨大的成功，随着新的应用类型的 出现，必须对现有的服务模型引入更多的控制机制，使其灵活性和透应性能够扩 展到新的运用。 针对高带宽一时延积网络中的拥塞控制存在的诸多困难和问题，近几年来出 现了很多新的拥塞控制技术和理论，本文将综述目前拥塞控制研究的最新进展， 分析和比较各种拥塞控制算法，并从源端和路由端两个方面分别提出了一种改进 的t c p 慢启动机制和一种新的基于到达速度和平均队长的主动队列管理算法 m r e d 。 1 ) 当今i n t e m e t 成功的关键因素之一在于t c p 端到端的拥塞控制机制，虽然在 提高网络性能，消除拥塞方面有许多途径，但不可否认，对于端系统算法的 改进凭借其强大的灵活性和良好的扩展性将是一种最为有效可行的方法。 在说明现有t c p 拥塞控制中慢启动机制存在的问题后，本文提出了一种 新的拥塞窗口增量方式，从而改进了慢肩动机制，我们改进后的慢启动机制 根据当前拥塞窗口的大小自适应的调整拥塞窗口的增量，并且可以通过一个 调节因子来适应不同的网络环境，使得慢启动后期平滑增长过渡到t c p 拥塞 控制的下阶段，减少了慢启动后期的突发数据量。从而提高了t c p 拥塞控 制机制的整体性能。 2 ) 完全依赖实现在端系统上的策略与算法是很难满足愈加丰富的应用需求的。 于是，部分研究注意力转向网络中的路由器等中间节点设备，期望通过增强 它们的功能来实现端系统无法达到的技术目标。就拥塞控制雨言，网络中间 节点有可能更及时，甚至提前准确了解网络的拥塞状态，并依此实施有效的 中国科学技术大学硕士学位论文 第章绪论 资源管理策略，是网络能有效地避免拥塞，或尽早从严重的拥塞状态中恢复 过来。其中，主动队列管理( a z t i v eq u e u em a n a g e m e n t ：a q m ) 技术对于降 低丢包率，提高链路利用率，降低队列时延，抑制速度振荡等方面起到了重 要的作用，从而能够确保多媒体业务在i p 网络中传播的服务质量。 在系统分析了a q m 机制的基础上，我们提出了一种基于r e d 及r q 的 主动队列管理算法m r e d 。m r e d 以数据包到达速度和平均队列长度两个变 量作为衡量拥塞的指标，因为根据这两个指标计算出来的标记概率更能当前 和未来一段时间内拥塞的变化趋势。经分析，m r e d 算法在控制平均队长稳 定、提高链路利用率、降低丢包率及减少对参数的敏感性方面都比r e d 要 好，配合端系统的t c p 协议，将使拥塞控制机制更准确有效，从而使网络的 整体性能得到提高。 论文主要内容及结构安排如下： 第二章介绍了t c p 拥塞控制机制的背景、思想及几种具有代表性的t c p 拥 塞控制算法，以及当今学术界在这些论题上的研究进展情况。 第三章提出了改进的源端t c p 慢启动机制，相应的仿真实验验证了理论分析 的正确性和所提算法的有效性。 第四章介绍了路由器端的拥塞控制机制，分析了主动队列管理的思想、设计 目标及几种主流的主动队列管理算法。 第五章在现有主动队列管理算法的基础上，我们提出了种基于速度和队列 长度的主动队列管理算法，并对其进行了深入的沦证分析，仿真结果验证了该算 法的可行性及优越性。 第六章总结全文，并指出以后的研究方向。 参考文献 【1 1 v j a c o b s o n ，”c o n g e s t i o na v o i d a n c e a n d c o n t r o l - “p r o c o f s i g c o m m 8 8 ，a u g1 9 8 8 ，p p 3 1 4 - 3 2 9 【2 】m a l l m a n ，ws t e v e n sa n dvp a x s o n , “t c p c o n g e s t i o n c o n t r o l ，”r f c2 5 8 1 ，1 9 9 9 【3 】m m a t h i s , j m a h d a v ia n ds f l o y d ，”t c ps e l e c t i v ea c k n o w l e d g m e n t o p t i o n s , ”r f c l ， 中国科学技术大学硕士学位论文第一章绪论 2 0 1 8 ，1 9 9 6 【4 】s f l o y da n dth e n d e r s o n , ”t i r en e w r e n om o d i f i c a t i o nt ot c p sf a s tr e c o v e r y a l g o r i t h m s ，”r f c2 5 8 2 ，1 9 9 9 【5 l c j i n , d x w e ia n ds ，h l o w , ”t h ec a s ef o rd e l a yb a s e dc o n g e s t i o nc o n t r o l ，” p r o co f i e e e c o m p u t e r c o m m u n i c a t i o nw o r k s h o p ，2 0 0 3 , p p 9 1 0 4 【6 】6 s h l o w , “t c pc o n g e s t i o nc o n t r o l s ：a l g o r i t h m sa n dm o d e l st u t o r i a ls l i d e s ，” h t t f ：n e t i a b c a l t e c h e d u p u b c o n g c t r l h t r n ，2 0 0 0 阢d e c o m e r ，“i n t e r n e t w o r k i n g w i t ht c p l l p ：v o l l ：p r i n c i p l e s , p r o t o c o l s a n d a r c h i t e c t u r e , ”4 “e d i t i o n , p