（计算机应用技术专业论文）基于公平性的主动队列管理（aqm）算法研究.pdf

武汉科技大学 硕士学位论文第1 页 摘要 随着网络技术发展的日新月异，网络规模迅速扩大，特别是进入9 0 年代后，以i p 为 基础的i l l t e m e t 呈现出爆炸式增长，1 1 1 t e m e t 己逐渐发展成为全球性的信息基础设施。随着 新型网络应用的不断涌现和用户数量的迅速增加，i i l t e m e t 的数据流量也在急剧增长。 i n l e m e t 已由以往的单一数据传送网发展成为传送数据、语音、视频等多媒体信息的综合业 筋网，成为最重要的信息交换手段。 由于网络的高速发展和各种业务类型的实施，互联网本身已成为复杂的异构网络，在 目前的状况下不可避免的出现拥塞现象，造成业务指标下降和网络资源利用率低下等情 况。不断发展的拥塞控制机制是保证网络运行与鲁棒性的重要机制，拥塞控制中作用于网 络中间节点的主动队列管理策略( a q m ) 是解决网络拥塞问题和保证q o s 的重要途径。面对 新的形势，对该领域的研究有着重要的现实意义和应用价值。 目前，主动队列管理作为控制网络拥塞的主要实现方法越来越受到人们的关注。在实 现拥塞控制的同时，带宽分配的公平程度也成为衡量一个主动队列管理算法性能很重要的 方面。由此，本文在研究了经典r e d 算法的基础上重点研究了一种无状态公平队列管理 算法( c h o k e 算法) 的公平性。通过对该算法的分析，发现该算法实际表现出来的公平性并 不理想。进而提出了一种改进的无状态公平队列管理算法( w f c h o k e 算法) ，并通过n s 2 对新算法进行仿真实验来验证其公平性。仿真结果表明，改进算法其表现具有更加优良的 公平性。 关键词：拥塞控制；公平性；主动队列管理；c h o k e 第1 l 页武汉科技大学硕士学位论文 a b s t r a c t w i t ht h ed e v e l o p m e n to fn e t w o r kt e c h n o l o g yt h en e t w o r ks c o p ee x t e n d e dr a p i d l y , e s p e c i a l l y i n1 9 9 0 s ，t h ei n t e r n e tb a s e do ni pp r e s e n t e dat r e m e n d o u si n c r e a s ea n di n t e r n e th a sg r o w nu pt 0 b et h ee s s e n t i a lg l o b a li n f o r m a t i o nf a c i l i t y w i t ht h en e t w o r ko fn e w p a t t e r na v a l a n c h e da n dt h e n e t w o r ku s e ri n c r e a s e dr a p i d l y , t h ei n t e m e td a t af l o wi si n c r e a s i n gs h a r p l y i n t e r n e ti sn ol o n g e r an e t w o r ko n l yf o rt r a n s m i t t i n gd a t a ；i th a st u r n e dt ob et h em o s ti m p o r t a n tm e t h o do f i n f o r m a t i o nc o m m u n i c a t i o na n dt h em o s tc o m p o s i t i v en e t w o r kw h i c hc a r r ya l lk i n d so f m u l t i m e d i ai n f o r m a t i o n ，s u c ha sd a t a ，s o u n d ，v i d e oe t c t h e r a p i dd e v e l o p m e n to fn e t w o r ka n dt h ei m p l e m e n to fa l lk i n d s o fn e t w o r kb u s i n e s sm a k e t h ei n t e r n e tah u g ea n di n t r i c a t en e t w o r k a sar e s u l tt h ep r o b l e mo fn e t w o r kc o n g e s t i o nh a s c o m ef o r t hi n e v i t a b l y ，a n di tc a u s e sad e c r e a s i n gb u s i n e s si n d e xa n dai n e f f i c i e n tn e t w o r k s o p e o p l ea r ep a y i n gm o r ea t t e n t i o nt ot h ec o n g e s t i o nc o n t r o lw h i c hi sg o i n gt ob eai m p o r t a n tr u l e t og u a r a n t e et h er o b u s t n e s sa n dn e t w o r kw o r k i n gs m o o t h l y c u r r e n t l y ，a m qa st h em a j o r s c h e m eo fc o n g e s t i o nc o n t r o lh a sa r o u s e dt r e m e n d o u si n t e r e s t a n dv a s es t u d i e s a tt h et i m eo fc a r r y i n go u tc o n g e s t i o nc o n t r o l ，f a i rb a n d w i d t ha l l o c a t i o n b e c o m e sav e r yi m p o r t a n ta s p e c to fm e a s u r i n ga q ms c h e m e sp e r f o r m a n c e s s o ，t h ep a p e r f o c u s e so nf a i r n e s so ft h ec h o k e ( c h o o s ea n dk e e pf o rr e s p o n s i v ef l o w sc h o o s ea n dk e e p f o ru n r e s p o n s i v ef l o w s ) a l g o r i t h mb a s e do nr e s e a r c ho nr e d ( r a n d o me a r l yd e t e c t i o n ) a l g r i t h m i tp r o p o s e sa l li m p r o v e dc h o k e ( w f c h o k e ) a l g o r i t h ma n dv e r i f i e si t sf a i r n e s sb y t h es i m u l a t i o no nn s 2 t h es i m u l a t i o nr 毛s u l t si n d i c a t et h a tt h ef a i r n e s sp e r f o r m a n c eo ft h e w f c h o k e a l g o r i t h mi sb e t t e rt h a nt h eo r i g i n a lo n e k e yw o r d s ：c o n g e s t i o nc o n t r o l ；f a i r n e s ；a c t i v eq u e u em a n a g e m e n t ；c h o o s ea n dk e e pf o r r e s p o n s i v ef l o w sc h o o s ea n dk e e pf o ru n r e s p o n s i v ef l o w s 武汉科技大学硕士学位论文第1 页 第一章绪论 本章首先介绍了i n t e r n e t 中存在的网络拥塞现象及其产生的本质，然后介绍了拥塞控制 策略的发展及研究现状，分析了目前存在的问题，并在此基础上指出了本文所做的主要：【 作及组织结构。 1 1 引言 i n t e r n e t 中现有的传输模式仍为单一的尽力而为( b e s t e f f o r t ) h 艮务，在这种服务模型下， 所有的业务流将被一视同仁的公平竞争网络资源，路由器对所有的数据包都采用先来先处 理的工作方式，尽最大努力将数据包传输到目的地，但对数据包的可靠性，延迟等不能提 供任何保证。这些方式适合f t p 、w w w 、e m a i l 等业务，但对那些对带宽、延迟、延迟抖 动等有特殊要求的应用来说现有的尽力而为服务显然是不够的。尽管由于网络技术的发 展，网络带宽和网络速度都得到了极大的提高，但网络上的数据传输量也以相同的速度增 长，甚至超过了网络发展的速度。因此以提高网络资源利用率，为用户提供更高的服务质 量( q o s ，q u a l i t yo fs e r v i c e ) 成为目标的研究领域成为目前的研究热点问题，也是当前学术 界计算机网络通信领域研究的热点问题。 拥塞现象的发生和i n t e m e t 的设计机制有着密切的联系。最初设计的i n t e n r e 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 r n e t 上用户和应用的数量都在迅速增长，当多个用户对网络的需求总量大于网络实际传输能力 时，必然会导致网络拥塞的发生。虽然拥塞源于资源短缺，但增加资源并不能避免拥塞的 发生，有时甚至会加重拥塞程度。例如，增加网关缓存表面上看可以防止或缓解由于拥塞 引起的分组丢弃，但随着缓存的增加，端到端的时延也相应增大。因为分组的持续时间是 有限的，超时的分组同样需要重传。因此，过大的缓存空间有可能使总延迟超过端系统重 传时钟的值从而导致分组重传。这些分组白白浪费了网络的可用带宽，反而加重了拥塞。 传统网络中采用的服务模式为尽力而为服务模式( b e s t e f f o r t ) 。这个选择和早期网络中 的应用有关i lj 。传统的网络应用主要是f r p 、w w w 、s m t p 等，它们对网络性能( 带宽、 第2 页武汉科技大学硕二e 学位论文 延迟、丢失率等、) 的变化不敏感，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 fs e r v i c e ) t 2 l 保i i e 。实施拥塞控制应该是其它o o s 机制正常工作的必要前提。 拥塞控制算法的分布性、网络的复杂性和对拥塞控制算法的性能要求又使拥塞控制算 法的设计具有很高的难度。到目前为止拥塞问题还没有得到很好的解决。 1 2 拥塞控制算法分类 我们对拥塞控制算法从以下几个角度分类： ( 1 ) 从控制论角度出发，可以分为开环控制和闭环控制，前者又称为预防式控制，它事 先设计一个好的网络，确保它不会发生拥塞，而网络一旦运行起来，就不再采取措施，这 类控制机制较适用于音频和活动图像业务。而对于复杂的网络系统来说仅有开环控制是不 够的。闭环控制，又称为反应式控制，能够使得网络中的拥塞状态信息( 反映了系统资源的 占用情况) 能及时反馈至端系统，从而调整端系统的数据传输速率，这样既保证了传输质量 又能充分利用网络资源。 ( 2 ) 从实施控制的类型上，拥塞控制可以分为基于窗口( w i n d o w b a s e d ) 和基于速率 ( r a t e b a s e d ) 两种类型【3 1 。t c p 采用的是典型的基于窗口的控制方式，t c p 通过调整滑动窗 口的大小控制发送到网络的数据量，基于窗口的控制易于实现，并且可以限制注入网络的 最大流量；基于速率的控制方式则是通过每秒发送的比特数来控制数据流的发送，如果传 输速率能够匹配网络可用带宽，就可以减少路由器的缓冲区长度，所以它本质上更适合于 多媒体数据流的传输。 ( 3 ) 从推断网络状态的反馈信息的类型上，可以分为显式拥塞控制( e x p l i c i t ) 和隐式拥塞 控s j j ( 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 1 ，端到端的拥塞控制仅在端系统执行，此时中间节点仅负责向端系统产生和 转发必要的反馈信息；后者是在网络的中川节点处执行的，路由器除了转发数据包外还要 负责通知端系统发送多少数据进入网络。 武汉科技大学硕士学位论文第3 页 1 3 国内外相关的研究现状 t c p 的流量控制是i n t e n r e t 正常运行的基础，围绕着t c p 流量控制的拥塞控制一直是 i n t e m e t 研究的一个热点。在i n t e r n e t 发展仞期，拥塞控制主要是通过t c p 协议中端到端基 于滑动窗口的流量控制完成的1 5 j ，t c p 的流量算法中也逐步增加了慢启动、拥塞避免、快 速重传与快速恢复等算法，以期对网络流量进行控制。随着应用需求的丰富和技术的发展， 研究者_ 歼始认识到想完全依赖实现在终端系统上的策略与算法很难满足越来越多的复杂 应用需求。于是，人们把注意力转向网络中的路由器等中间节点设备，期望通过增强它们 的功能来实现主机端无法达到的目标。就拥塞控制而言，网络中间节点有可能更及时，甚 至提前准确了解网络的拥塞状态，并依此实施有效的资源管理策略，使网络能有效地避免 拥塞，或尽早从严重的拥塞状态中恢复过来。当然，对路由器功能的扩展要受继承性和延 续性的限制，否则将影响技术的实用性。事实上，现有的路由器扩展功能主要包括队列调 度和队列缓存管理。调度( 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 ) i7 j 算法为候选算法。然而，在随后的研究中，发现r e d 仍 有一些缺陷。近年来，不断有一些新的主动队列管理算法出现，大多数有关r e d 算法的 研究都将注意力集中到了改进和完善已有的不足与缺陷，产生了不少r e d 的变种算法， 较有影响力的有p u b ( e x p e d i t e df o r w a r d i n gp e rh o pb e h a v i o n 【8 1 ，s t a b i l i z e dr e d 9 , l o l ， a d a p t i v er e d l l l l ，f l o wr e d l l 2 】和b a l a n c e dr e d 【1 3 】和r e m ( r a n d o me a r l ym a r l 【i n g ) 策略等 4 l 引。目前，主动队列管理算法已经成为了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 8 0 等。为了提高a t m 交换机中非限定比特 率u b r ( u n s p e c i f ：i e db i tr a t e ) 业务支持t c p 连接的性能，采用r e d 作为帧丢弃算法新业务 g f r ( g u a r a n t e ef r a m er a t 0 的实现也以r e d 作为首选的队列管弹算法。在d i f f s e r v 的业务 第4 页武汉科技大学硕士学位论文 框架下，由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 ) 的基本算法【1 6 】。由此叮见，r e d 算法己被广泛使用在网络队列管理r ，来提高系统的综合性 能。 目前，人们已经提出了许多的主动队列算法以解决这些问题，根据其分类方式的不同 可以分成多种不同的类型。按照主动队列算法发现拥塞之后处理方法的不同可以将主动队 列算法分为两类： ( 1 ) 通过对数据包打标i ! ( 1 l i i 说e c n l l 7 1 ) ，通过这种方法实现的主动队列算法主要有 b l u e 1 8 l 以及针对b l u e 的改进算法s f b 1 9 j ； ( 2 ) 通过丢弃数据包，通过这种方法实现的主动队列算法比较多，主要有r e d l 7 j ， s r e d 9 1 f r e d i1 2 1 ，c h o k e 2 0 , 2 1 】，c s f q l 2 2 , 2 3 j ，p f e d l 2 4 1 等。 实际上，这些算法为了解决非适应流影响带宽分配的公平性问题主要采用完全状态和 无状态两种类型，它们基本上都是通过对不同的流，计算出与其对应的包丢弃概率来实现 公平性。f r e d ( f l o wr e d ) 算法通过考察每个流的当前队列缓存占用量来决定该流的包被丢 弃的概率，它是完全基于流的状态信息来提高队列管理公平分配带宽的算法。在f r e d 算 法中，可以对不同的流的包采用不同的包丢弃概率，能够大大地提高了r e d 算法的公平 性。但是，由于需要在路由器管理每流的状态信息和对包进行分类，因此随着网络中流的 数目的增多，算法的整体性能会急剧下降，因此f r e d 算法在高速网络中存在着严重的可 扩展性问题。c s f q ( c o r es t a t e l e s sf a i rq u e u e ) 算法则是网络核心无状态的公平队列管理算法， 它是在网络边缘仍然保持流状态信息，而在网络核心的核心节点可以无需在本地维持每个 流的状态信息。c s f q 算法实际上是通过采用d p s ( d y n a m i cp a c k e ts t a t e ) 技术充分利用边缘 网络的状态流信息对不同流的包实现不同的丢弃概率。c s f q 算法减轻了网络核心节点的 负担，能够适应区分网络的发展趋势，提高了算法的可用性和可扩展性。c h o k e ( c h o o s ea n d k e e pf o rr e s p o n s i v ef l o w sc h o o s ea n dk i l lf o ru n r e s p o n s i v ef l o w s ) t 2 0 l 算法也是从r e d 改进的 目前唯一无须任何单流状态信息而实现近似公平分配的算法。它是一种典型的惩罚非适应 流的无状态主动队列管理算法，根据缓存中属于同一个流的包的多少来确定该流的到达包 的丢弃概率，是根据缓存器占有量的大小来决定对非适应流惩罚力度的大小。 p f e d ( p r e d i c t i o nb a s e df a i ra 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 m ) 1 2 4 】是一种基于预测的公平的 主动队列管理算法，通过引入流量预测机制以及采用组合的拥塞判断标准，提高了主动队 列管理算法在稳定性和丢包率等方面的综合性能，同时采用了一种完全无状态的方法对“非 适应流”进行了有效的惩罚，提高了算法的公平性。 1 4 存在的问题 由于i n t e m e t 中绝大部分数据流使用了t c p i p 协议，因此本文将t c p i p 网络中的拥塞 控制问题作为研究的重点内容。 t c p 拥塞控制机制在i n t e m e t 中发挥了彳j ：之有效的作用，但t c p 拥塞控制算法自身存 在的问题也是不容忽视的。 武汉科技大学硕士学位论文第5 页 端系统从发生拥塞到实施控制之间有着明显的时延，而且端系统缺乏对数据传输过程 的动态性了解，无法预知网络资源的使用情况，目前主要是通过降低发送到网络的数掘流 量来减小网络负载从而缓解拥塞。 a c k c o m p r e s s i o n 现象：t c p 源端使用了a c k 自计时技术控制数据包的发送速度i 训， 发送方根据接收到的a c k 确认来触发新数据的发送，所以a c k 的行为也直接影响了发送 方的速度，但是a c k 自计时技术在非对称网中往往会失效【2 5 , 2 6 】，正常情况下，a c k 剑达 源端的间隔为该链路上数据包的传输时间，如果在返回路径中a c k 聚集在路由器的缓冲 区中，这样a c k 到达源端的间隔就成为a c k 的传输时间，由于a c k 比数据包要小得多， 所以会造成源端以超出路由器承受能力的速度向网络发送数据刨2 7 l 。 慢启动算法中存在的问题尤为突出，首先，由于慢启动阶段发送方无法了解瓶颈链路 带宽，每个回路响应时间( r t i ) i 内都会将拥塞窗d ( c w n d 增加一倍，如果慢启动阐值( s s t h r e s h ) 较大，那么发送方窗口增加到足够大时，会丢失接近一半的数据包；其次，t c p 慢启动是 按照事先设定好的参数开始数据传输的，c w n d ，s s t h r e s h 分别取1 个和6 4 个数据包大小， t c p 连接在闲置一段时间后也使用慢启动算法重新开始通信，在网络可用带宽较大时，会 造成网络资源利用率降低及延迟增加；再次，t c p 基于窗口的拥塞控制机制对于传输大批 量文件具有良好的适应性，但是为w w w 应用等短小数据流服务时性能较差，往往需要几 个r 1 盯时间探测合适的网络带宽，传输延迟较大。 t c pr e n o 冽算法在源端检测到拥塞后，重传从丢失数据包至检测到丢失时发送的全部 数据包，而实际上其中有些数据包是正确传到接收端的，不必重传；t c pr e n o 在检测到单 个包丢失时效果不错，但是如果在一个数据发送窗口中出现多个包丢失，由于一个r t r 只 能重传一个数据包，因此它必须等待重传超时才能继续传输数据，导致它在性能上具有较 大的局限性。 公平性问题：i n t e m e t 采取的基于源端的拥塞控制策略是不公平的，t c p 拥塞控制中的 公平性问题主要表现在以下两个方面： ( 1 ) t c p 中拥塞窗口大小可以表示为r t t 的函数，比如慢启动阶段。c w n d 随r t t 呈指 数级增长，拥塞避免阶段c w n d 随i m 线性增长，这样对于长延迟的连接来讲，由于其窗 口增长速度慢，因而在同样的条件下获得的带宽也就越少，特别是在慢启动过程中，r 1 厂r 长的连接的劣势就更为明显； ( 2 ) t c p 提供端到端的可靠传输服务，在检测到拥塞后会自觉地降低发送速度，随着网 络中不遵守t c p 协议的各种数据流的出现，t c p 流在与这些数据流共存时，其竞争力较弱， 往往会丧失应有的带宽，因此公平地共享网络带宽也是一个需要密切关注的问题。 当前在i n t e r n e t 中i p 层实施的控制过于简单，“弃尾”算法容易使缓冲区长时间处f 满 状态，这时到达路由器的数据包会因为缓冲区溢出而全部丢弃，各源端在检测到包丢失后 同时降低发送速率，导致网络吞吐量急剧下降，而在检测到网络空闲时又会同时增加发送 速度，这就是所谓的全局同步( g l o b a ls y n c h r o n i z a t i o n ) t e 象1 2 引，最终的结果是导致网络移f j 塞， 甚至出现拥塞崩溃。为了更加有效地控制网络中的拥塞现象，诸多科研工作者在i p 层戈施 第6 页武汉科技大学 硕士学位论文 捌塞控制方面作了大量研究工作，公平排队算法f q ( f a i rq u e u i n g ) 1 3 0 】、随机早期检测算法 r e d ( r a n d o me a r l yd e t e c t i o n ) 、显式拥塞指示算法e c n ( 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 ) 等 相继被提出，从理论上对解决拥塞问题起到了一定的指导作用，算法的有效性是以其实现 的复杂性为代价的，虽然r e d 算法以其有效性丌始在i n t e r n e t 中部署实施，但是真正让路 由器在i n t e r n e t 中参与拥塞控制仍需要相当长的时间，i p 层拥塞控制还有许多问题有待于 进一步研究。 本文的内容及主要工作 本文的主要研究工作是针对现存的网络服务质量存在的问题而展开的，具体的 兑主要 是针对主动队列管理算法和存在的带宽分配的公平性问题而展开的。 第一章介绍了本文相关的研究背景，阐述了本文的研究目的。分析了目前产生带宽分 配不公平的原因，并简单介绍了目前在路由器上的解决方法。 第二章着重研究了i n t e r n e t 中t c p 协议基于滑动窗口的流量控制和端到端拥塞控制方 法。 第三章对近似公平带宽分配的队列管理算法进行了深入的研究。首先介绍了网络层拥 塞控制的策略并解释了公平带宽分配的重要意义，然后详细的分析了现有的主动队列管理 算法，如：r e d 、a r e d 、f r e d 、c h o k e 等算法。重点研究了r e d 和c h o k e 算法，对 其优缺点进行了详细的研究。最后对这几种算法在其公平性，复杂性以及对t c p 流抑制程 度等方面进行了比较分析。 第四章是本文的重点，研究了c h o k e 算法在性能上的一些问题，提出了一种改进算 法w f ( ! h o k e ，在对非适应流加大惩罚力度的基础上来更好的保护保护适应流，比较好的 解决了适应流与非适应流的带宽分配公平性的问题。最后通过仿真实验对w f c h o k e 的性 能进行了验证。最后给出仿真实验结果，并对w f c h o k e 性能进行了分析。 第五章给出了结论和我们需要做的进一步的研究工作。 武汉科技大学 硕士学位论文第7 页 第二章t c p ip 拥塞控制策略研究 2 1t c p 基于滑动窗口的流量控制 t c p 是面向数据流的，目前i n t e m e t 上应用广泛的传输层协议，实施流量控制是t c p 的两个主要任务之一，t c p 流量控制采用的是基于滑动窗口的流量控制【3 l l 。 2 1 1 基本概念 序号：对发送方所发送报文段的数据以字节为单位进行的编号。 确认号：是接收方期望收到发送方的下一个报文段的数据的第一个字节的序号，也就是期 望收到的下一个报文段首部的序号的值。 滑动窗口：为了提高报文段的传输效率，t c p 采用大小可变的滑动窗口进行流量控制。窗 口大小的单位是字节。在t c p 报文段首部的窗口字段写入的数值就是当前给对方设置的发 送窗口数值的上限【3 2 j 。 2 1 2 流量控制过程 发送窗口在连接建立时由双方商定。但在通信的过程中，接收端可根据自己的资源情 况，随时地动态调整发送对方的发送窗口的上限( 可增大或减小) 。这种由接收端控制发送 端的做法，在计算机网络中经常使用。图2 1 表示的是t c p 中使用的窗口概念。 ( a ) ( b ) ( c ) = = 恢翳调矽列口l 酾够 11 0 0 | i 0 12 2 0 13 0 03 0 1q 0 04 0 15 0 0 5 0 王6 0 0 | 6 0 i7 0 0 7 0 18 0 08 0 19 0 1 i 。一、。 一譬葛f * 碰一 一 21 0 0l o l2 0 0 2 0 13 0 03 0 14 0 0l4 0 15 0 05 0 16 0 06 0 17 0 07 0 18 0 08 0 1 9 0 1l 。鲁一一 一 。 r t j r * _ 、 l l1 0 0l1 0 12 0 0l2 0 l3 0 0 3 0 l4 0 0l4 0 15 0 0 | 5 0 16 0 0i6 0 17 0 0 | 7 0 18 0 08 0 19 0 1i l i l 一一：，。! 。 奢一。，。 一 图2 1 t c p 的窗口概念 图中表( a ) 表示发送端要发送9 0 0 字节长的数据，划分为9 个1 0 0 字节长的报文段，而 发送窗口确定为5 0 0 字节。发送端只要收到了对方的确认，发送窗口就可前移。发送t c p 要维护一个指针。每发送一个报文段，指针就向前移动一个报文段的距离。当指针移动到 第8 页武汉科技大学硕士学位论文 发送窗口的最右端( t i p 窗口前沿) 就不能再发送报文段了。 图中表( b ) 表示发送端已发送了4 0 0 字节的数据，但只收到对前两百字节数据的确认， 同时窗口大小不变。我们注意到，现在发送端还可发送3 0 0 字节数据。 图中表( c ) 表示发送端收到了对方对前4 0 0 字节的数据确认，但对方将窗口减小到4 0 0 字节。于是，发送端最多还可发送4 0 0 字节的数据。 下面再通过图2 2 说明利用可变窗口大小进行流量控制。 主机a 向主机b 发送数据。双方约定窗口值是4 0 0 字节。在设每一个报文段为1 0 0 字 节，序号初始值为1 。主机b 进行了三次流量控制。第一次将窗口减小为3 0 0 字节，第二 次又减为2 0 0 字节，最后一次减至零，即不允许对方发送数据了。这种暂停状态将持续到 主机b 重新发出一个新的窗口值为止【3 2 1 。 i s e q = 1 l t- ia 还能发送3 0 0 字节 s e q = 1 0 1 l l 簟ia 还能发送2 0 0 字节 允许a 再发送3 0 0 字节( 序号2 0i 至5 0 0 ) ：! ! ! 三! ! ! ，：施能发送2 。字节( 序号3 。l 至5 。) ； ! ! 竺三! ! ! ；a 还能发送1 0 0 字节( 序号4 0 l 至5 0 0 ) i i i! ! ! ! ! ! -la 超时重发，但不能发送序号5 0 0 以后的数据 i 竺兰三! ! ! ：坚! ! ! !：允许a 苒发送2 0 0 字节( 序号5 01 至7 0 0 ) l s e q = 5 0 1 l i ia 还能发送2 0 0 字节( 序号6 0 1 至7 0 0 ) ；竺兰三! ! ! ：! ! ! !：不允许a 再发送( 到序号6 0 0 的数据都受到了) 图2 2t c p 利用可变窗口进行流量控制 发送端利用发送窗i = 1 ( 这个窗口取决于对方的接收窗口) 调节向网络注入分组的速率不 仅仅是为了使接收端来得及接收，而且还是为了对网络进行拥塞控制。我们知道，拥塞发 生在通过网络传输的分组数量开始接近对分组处理能力时。从这个角度看，拥塞控制的目 标就是将网络中的分组数量维持在一定的水平之下。若网络中的分组数量超过这个水平， 网络的性能就会急剧恶化。拥塞控制也是运输层必须解决的一个非常复杂的问题。 但是随着大量的网络中间节点不断的将大量数据包发送到通信子网中，势必会引起网 络中间节点的拥塞，使得大量的数据包在网络中间节点被丢弃。但是t c p 连接中的报文段 通常是复用在网络层的口数据报中传送。在这种情况下，如发生了路由器中的严重的丢包 现缘，就可能同时会影响到很多条t c p 连接，结果使许多t c p 连接在同一时间突然都进 入到慢歼始状态。这在t c p 术语中称为全局同步现象( g l o b a ls y n c r o n i z a t i o n ) 。全局同步现 武汉科技大学硕士学位论文第9 页 象使得全刚的通信量突然下降了很多，而在网络恢复正常后，其通讯量又突然增大很多。 2 2t c p 拥塞控制算法 t c p 是目前i n t e m e t 上应用广泛的传输层协议，实施拥塞控制是t c p 的两个主要任务 之一，由于i p 层在发生拥塞时不向端系统提供任何显式的反馈信息，因而t c p 拥塞控制 采用的是基于窗口的端到端的闭环控制方式【6 1 。 2 2 1 基本概念 拥塞窗i 1 ( c w n d ) ：拥塞控制的关键参数，控制源端在拥塞情况下一次最多能发送多 少数据分组。 通告窗e l ( a w n d ) 接收端对源端发送窗口大小所做的限制，在建立连接时由接收方 通过a c k 确认捎带给源端。 慢启动阈值( s s t h r e s h ) ：用来控制源端从慢启动阶段转换到拥塞避免阶段的门限值， 初始值一般设为6 5 5 3 5 b y t e s 或a w n d 的大小。 回路响应时间( 哪：一个数据包从源端发送到接收端直至源端收到目的端对该数据 包确认信息所经历的时间间隔。 超时重传计数器( r 1 r o ) ：描述数据包从发送到失效的时间间隔，是源端用来判断数据 报是否丢失和网络拥塞的重要参数，通常设为2 r t i 或5 r t r 。 最大报文段长度( m s s ) ：最大报文段长度表示t c p 传往另一端的最大块数据的长度。 当一个连接建立时，连接的双方都要通告对方各自的m s s 。 一般，如果没有分段发生，m s s 还是越大越好。报文段越大允许每个报文段传送的数 据越多，相对i p 和t c p 首部有更高的网络利用率。当t c p 发送一个s y n 时，它能将m s s 值设置为外出接口的m t u 长度减去i p 首部和t c p 首部长度。对于以太网，m s s 值可达 1 4 6 0 。如果目的地址为非本地的，m s s 值通常默认为5 3 6 ，是否本地主要通过网络号区分。 m s s 让主机限制另一端发送数据报的长度，加上主机也能控制它发送数据报的长度，这将 使以较小m t u 连接到一个网络上的主机避免分段。 2 2 2t c p 拥塞控制算法 t c p 拥塞控制由慢启动、拥塞控制、快速重传和快速恢复四个核心算法组成【3 3 l 。 ( 1 ) 慢启动 由于端系统不能预测网络资源的使用情况，如果在建立一个新的连接时向网络中发送 大量的数赫j 包，容易导致耗尽路由器的资源，使网络吞吐量急剧下降。为了避免新建立的 连接产生的突发通信量超过网络的承受能力，t c p 使用了慢启动算法来逐渐探测网络的可 用带宽，慢启动算法为每个连接设置两个变量：c w n d 和s s t h r e s h ，在慢启动阶段，当建立 第1 0 页武汉科技大学硕士学位论文 新的t c p 连接时，拥塞窗1 3 ( c w n d ) 被初始化为一个数据包大小( 缺省为5 1 2 或5 3 6 b y t e s ) ， 实际发送窗口w i n 取拥塞窗i - 1 与接收方提供的通告窗f 的较小值，即w i n = m i n ( c w n d ， a w n d ) ，源端每接收到一个a c k 确认，将c w n d 增加一个数据包的发送量，这样，c w n d 随 r t t 呈指数级增长：1 个、2 个、4 个、8 个，因此源端向网络中发送的数据量将会急 剧增加。实际上，慢启动算法并不慢，要达到可利用的最大窗口w ，需要的时间为r l 0 9 2 w ( r 为往返时间) 1 3 3 j 。 ( 2 ) 拥塞避免 拥塞避免阶段是使发送端的拥塞窗口e w n d 每经过一个往返时延i m 就增加一个m s s 的大小( 而不管在时间r t t 收到了几个a c k ) 。这样，拥塞窗1 2 1c w n d 按线性规律缓慢增长， 比慢开始算法的拥塞窗口增长速率缓慢得多。 无论是在慢开始阶段还是在拥塞避免阶段，只要发送端发现网络出现拥塞( 其根据就是 没有按时收到确认或者收到了几个重复的确认 ) ，就要将慢开始门限s s t h r e s h 设置为出现拥 塞时的发送窗1 3 值( 即接收端窗口和拥塞窗1 2 中数值的较小的一个) 的一半( 但不能小于2 ) 。 这样设置的考虑就是：既然出现了网络拥塞，那么就要减小向网络的注入的分组数。然后 将拥塞窗口c w n d 重新设置为1 ，并执行慢开始算法。这样做的目的就是要迅速减少主机发 送到网络中的分组数，使得发生拥塞的路由器能够有足够的时间把队列中积压的分组处理 完毕。 图2 3 说明了上述拥塞控制的具体过程： 拥塞 窗口 c w n d s s l ：h r e s h = c w n d 2 时间 图2 3t c p 的拥塞控制过程 ( 3 ) 快速重传 当一个次序紊乱的数据段到达时t c p 接收端应该迅速发送一个重复a c k 。这个a c k 的目的是通知发送端收到了一个次序紊乱的数据段，以及期望的序列号。从发送端的观点 来看，重复a c k 可以由许多网络问题引起。首先，可以由数据段丢失引起。在这种情况 下，所有在丢失的数据段之后发送的数据段都将触发重复a c k 。第二，可以由网络对数据 的重新排序引起( 这在某些网络路径上并不少见) 。最后，重复a c k 可以由网络对a c k 或 数据段的复制引起。另外，当接收数据段填补了全部或部分序列号间隔时，t c p 接收端应 该立即发送一个a c k 。这将为一个通过重传超时机制来从数据丢失中恢复的发送端提供更 多的及时的信息，此机制可能是一一个快速重传，或者一一个实验性的数据丢失恢复算法，比 武汉科技大学 硕士学位论文第1 1 页 如n e w r e n 0 1 3 3 l 。 t c p 发送端应该使用“快速重传”算法来探测或者修复数据丢失，以收到的重复a c k 为 基础。快速重传算法以三个重复a c k 的到达( 收到四个一样的a c k ，其间没有任何其他包 到达) 为一个数据段已经丢失的标志。在收到三个重复a c k 之后，t c p 不等重传定时器超 时就重传看来已经丢失的数据段。 h ) 快速恢复 在快速重传算法发送了看来已经丢失的数据段之后，“快速恢复”算法支配了新数据的 传送，直到一个非重复a c k 到达。不进行慢启动的原因是收到重复a c k 不仅意味着一个 数据段已经丢失，而且意味着数据段非常可能从网络丢失。换句话说，因为接收端只有在 当一个数据段已经到达时才产生一个重复a c k ，由此我们可以知道，已经脱离网络，存储 在接收端的缓冲区里的数据段不会再消耗网络资源。另外，因为a c k c l o c k ”保存起来了， t c p 发送端可以继续发送新的数据段( 尽管传送必须继续使用一个减小的c w n d ) 。 快速传送和快速恢复算法经常像下面那样一起实现。