（信号与信息处理专业论文）internet中拥塞控制策略研究.pdf

四j 1 1 大学倾士学位论文 i n t e r n e t 中拥塞控制策略研究 信号与信息处理专业 研究生：余莉指导老师：舒勤 近年来，网络中出现了许多新的应用，如实时话音和图像业务，这给拥有 有限资源的网络又增添了很大的负担，越来越严重的网络拥塞问题逐渐暴露出 来。为解决这些问题，仅增加互联网的容量是远远不够的，还需要有灵敏的和 有效的网络拥塞控制的方法。在网络通信中，拥塞容易造成延迟和吞吐量等q o s 性能指标下降，是影响带宽、缓存等网络资源利用率的关键因素，因此有效解 决拥塞问题对于提高网络性能具有重要意义。 研究表明，仅仅靠端到端的t c p 层基于滑动窗口的流量控制已很难满足网 络中日益增长的业务量的要求，因此网络本身必须采用某种手段参与拥塞控制。 最好的办法是让i p 层参与资源的分配控制工作，在路由器中引入相应的拥塞控 制机制对拥塞进行监测和预防。主动队列管理( a q m ) 作为目前路由器中广泛采 用的拥塞控制策略在保证较高的吞吐量的基础上有效地控制队列长度，从而实 现了控制端到端时延，保证服务质量的目的。随机早期检测( r e d ) 算法是a q m 中有效的实现算法，有关它的性能也是近来网络研究的个热点。 本文首先介绍了i n t e r n e t 中的拥塞控制机制，主要讨论了i p 层的拥塞控制 策略，针对目前广泛使用的主动队列管理策略中的r e d 算法进行了详细研究。 r e d 利用e w m a 形式计算平均队列长度只在分组到达时进行，所以平均队列 长度的计算反映的更多的是分组到达速率而不是缓存的当前占用情况。即使当 前队列为空，丢弃可能还在继续。这将造成链路利用率的大大降低。针对这一 问题，本文提出了一种改进的r e d 算法，在平均队列长度的计算中考虑当前队 四j i l 大学领士学位论文 列的实际情况，并将两者结合起来进行丢弃决策，最后在网络模拟软件n s 中 进行仿真，实验结果表明，改进r e d 算法在分组丢弃比例和链路利用率上都优 于r e d ，增强了r e d 的自适应性。但是改进r e d 算法中新参数的引入对r e d 其他性能的影响还有待进一步研究。 关键词：拥塞控制随机早期检测，主动队列管理，平均队列长度，链路 利用率 四川大学硕上= 学位论文 t h er e s e a r c ho f 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 nt h ei n t e r n e t m a j o r ：s i g n a la n di n f o r m a t i o np r o c e s s i n g g r a d u a t e ：1 y i l i a d vis o r ：s h u q i n c o n g e s t i o ni nt h ei n t e r a c th a sg r o wm o r es e r i o u sa sm a n yn e wa p p l i c a t i o n sh a v e a p p e a r e di nt h ei n t e r n e tt h e s ey e a r s ，s u c ha sr e a lt i m ev o i c ea n di m a g e ，w h i c hh a v e i n c r e a s e dt h eb u r d e no f t h ei n t e r n e tl o a d i no r d e rt os o l v et h e s ep r o b l e m s ，i n c r e a s i n g t h ec a p a b i l i t yo ft h ei n t e r n e ti sn o te n o u g h t h e r es h o u l db es e n s i t i v ea n de f f e c t i v e m e a s u r et oc o n t r o lt h ec o n g e s t i o n i nn e t w o r kc o m m u n i c a t i o n ，c o n g e s t i o nw i l ll e a d t od e g r a d a t i o no fq o s ，s of i n d i n ga ne f f e c t i v ew a yt os o l v et h ec o n g e s t i o np r o b l e m h a sm u c hs i g n i f i c a n c et oi m p r o v et h ep e r f o r m a n c eo f t h en e t w o r k r e c e n tr e s e a r c hh a si n d i c a t e dt h a te n dt oe n df l o wc o n t r o lo ft c pc a n ts a t i s f yt h e i n c r e a s i n gd e m a n do fb u s i n e s si nt h en e t w o r k ，s ot h en e t w o r ki t s e l fs h o u l dt a k ep a r t i nt h ec o n g e s t i o na v o i d a n c ea n dc o n t r 0 1 t h eb e s tw a yi st ol e ti pl a y e rt a k ep a r ti n t h ed i s t r i b u t i o no fr e s o u r c e si nt h en e t w o r k ，t h a ti st os a y ，c o n g e s t i o nc o n t r o l m e c h a n i s mi si n t r o d u c e di n t ot h er o u t e rt os u p e r v i s ea n dp r e v e n tt h ec o n g e s t i o na sa w i d e l yu s e ds t r a t e g yi nc o n g e s t i o nc o n t r o l ，a c t i v eq u e u em a n a g e m e n t ( a q m ) c a n c o n t r o lt h el e n g t ho ft h eq u e u ei nac e r t a i nr a n g ee f f e c t i v e l yt og u a r a n t e eap r e f e r a b l e t h r o u g h p u ta n dq o s r a n d o me a r l yd e t e c t i o n ( r u e d ) i so n eo ft h em o s te f f e c t i v e a l g o r i t h m so fa q m i t sp e r f o r m a n c ei s ah o t s p o ti nt h ec u r r e n tr e s e a r c ho f c o n g e s t i o nc o n t r o l ， 四川大学杠贞士学位论文 i n t h i sp a p e r , t h ep r i n c i p l e so fc o n g e s t i o nc o n t r o lm e c h a n i s m sa r ei n t r o d u c e d f i r s t l y , a n dt h ec o n g e s t i o nc o n t r o li nt h ei pl a y e ri s d i s c u s s e di nd e t a i l ，r e d a l g o r i t h mi nt h ea q m i st h ef o c u so ft h i sp a p e r , a sr e d j u s tu p d a t e dt h ea v e r a g e q u e u el e n g t hw h e np a c k e t sa r r i v e s ，t h u st h ec o m p u t a t i o ns h o w sa v e r a g i n go fp a c k e t a r r i v a lr a t er a t h e rt h a nt h ec u r r e n tb u f f e ro c c u p a n c y t h ed r o p p i n go fp a c k e t sw i l l c o n t i n u ef o ral o n gt i m ee v e na f t e rt h eq u e u eh a sb e c o m ee m p t y t h i sw i l ll e a d st oa r a p i dd e g r a d a t i o no ft h el i n ku t i l i z a t i o n s oa ni m p r o v e dr e da l g o r i t h mi sp r o p o s e d w h i c hc o m b i n e se w m aw i t hi n s t a n t a n e o u sq u e u es i z ef o rd r o p p i n gd e c i s i o n sa n d w h i c ha l s oi n c o r p o r a t e st h ea d j u s t m e n t st ot h ee w m aw h e nq m i n mo v e ra s u s t a i n e dp e r i o d s i m u l a t i o ns t u d i e ss h o wt h a tt h ei m p r o v e dr e da l g o r i t h mg i v e sa b e t t e rl o s sr a t ea n dl i n ku t i l i z a t i o nc o m p a r e dt ot h eo r i g i n a lr e da l g o r i t h m s 、i ti s s u g g e s t e dt h a tm o r es t u d i e sb ed o n et oe x p l o r et h eo p t i m u mv a l u e so f “a n dc f o r d i f f e r e n tt o p o l o g k sa n dt h e ys h o u l db et i e dt oo t h e rr e dp a r a m e t e r s k e y w o r d s ：c o n g e s t i o nc o n t r o l ，r a n d o me a r b d e t e c t i o n ，a c t i v eq u e u e m a n a g e m e n t ，a v e r a g eq u e u el e n g t h ，l i n ku t i l i z a t i o n 叫川人学顺卜学位论文 1 绪论 本章首先分析了i n t e m e t 中存在的网络拥塞现象及其产生的本质，然后介绍 了拥塞控制策略的发展及研究现状，分析了目前存在的问题，并在此基础上指 出本文所做的主要工作及文章的内容安排。 1 1i n t e r n e t 中网络拥塞原因 正当i n t e m e t 和一些专用的互联网的规模目益扩大时，许多新的应用也随之 出现了。小容量的t e l n e t 会话已跃为大容量的客户服务器应用。而最近在这 方面还增加了非常大容量的、越来越多的图形密集的万维网通信量。现在实时 话音和图像业务又给网络增添了负担。网络中不同的数据流在路由器处交汇， 给网络的路由节点造成很大的负担，越来越严重的网络拥塞问题逐渐暴露出来。 为解决这些问题，仅增加互联网的容量是远远不够的，还需要有灵敏的和 有效的网络拥塞控制的方法。在网络通信中，拥塞容易造成延迟和吞吐量等q o s q u a l i t yo f s e r v i c e ) 性能指标下降，是影响带宽、缓存等网络资源利用率的关 键因素，因此有效解决拥塞问题对于提高网络性能具有重要意义。 网络产生拥塞的根本原因是用户提供给网络的负载大于网络资源容量和处 理能力。在i n t e r n e t 中，网络中的资源( 如缓存空间不足、通信信道带宽容量 不足、处理机处理能力等) 的有限是产生拥塞现象的直接原因“1 ，但是无论增加 缓存容量或是提高处理器及链路的速度都不能从根本上解决问题，相反，某些 情况下甚至可能会进一步加剧拥塞“1 。例如，如果增加路由器的缓冲，那么报文 通过路由器的延迟就会增大，当延迟超过源端系统中重传定时器的值时，就会 导致报文的重传，而这种重传反而增加了拥塞的程度。值得指出的是，拥塞总 是发生在网络中那些资源“相对”短缺的位黄，而拥塞发生在地理上的不均衡 性反应了i n t e r n e t 的不均衡性。i n t e r n e t 中的不均衡性首先体现在资源分布的不 均衡，这些资源包括链路带宽、网关中的缓存和网关中的处理能力等。在图1 一l ( a ) 中，路由器分别和1 m b i t s 和l o o k b i t s 的链路相连。当报文以i m b i t s 的 速率从s 发送d 时，在r 处会发生拥塞。i n t e m e t 的不均衡性还体现在流量分 四j 】i 大学帧，l 学忙论文 布的不均衡。在图l - l ( b ) 中a 、b 、c 、d 四个节点通过r 相连。四条链路的 带宽都是1 m b i t s ，也就是说系统中资源的分布是均衡的。当a 和b 都以1 m b i t s 的速率向c 发送数据时，在r 处同样会发生拥塞。在i n t e r n e t 中，资源分稚的 不均衡和流量分布的不均衡都是广泛存在的，由网络中的不均衡性所导致的拥 塞是不能依靠增加资源的方法来解决。 吖下雕 ( a )( b ) 图1 1i n t e r n e t 中的不均衡性造成网络拥塞 在网络流量非常大的情况下，网络甚至会完全瘫痪，几乎没有数据报能送 达接收方。网络拥塞已经成为制约网络发展和应用的一个瓶颈，如何更好地避 免和控制拥塞一直是近年来网络研究的热点问题。 1 2 拥塞控制策略的发展进程及现状 1 2 1t c p 拥塞控制 拥塞控制的主要目标是控制进入网络的数据流量，保证通信子网不会被用 户发送的数据流湮没，合理地使用瓶颈资源。直观上，解决网络拥塞可以从两 方面下手，一是拥塞避免，即尽量避免拥塞的发生，使网络运行在最佳状态： 另外就是在拥塞发生后采取补救措施消除拥塞。完全避免网络拥塞必然会牺牲 网络的资源利用率，在追求公平、高效、高利用率的网络环境下，采取这种保 守的方法显然是不适宜的，因此，采用拥塞避免与拥塞控制相结合的方法更为 合理。拥塞控制策略主要由反馈机制和控制机制两个部分组成。网络通过反馈 机制向源端或目的端通告它的当前状态，端系统则根据接收到的反馈信息，利 用控制机制完成对负载的调整，达到消除拥塞的目的”1 。 四j l i 大学硕上学位论文 由于目前i n t e r a c t 上9 5 的数据流使用的是t c p i p 协议，因此t c p i p 拥塞 控制受到了广泛的关注。 早期t c p 的实现只是使用累计确认、超时重传和后退n ( 源端检测到拥塞 时，重传从丢失数据包开始一直到检测到丢包时所发送的全部数据包) 等机制， 对于网络拥塞几乎没有进行什么控制。拥塞控制的研究开始于8 0 年代中期，1 9 8 4 年，n a g l e 首次提出了复杂t c p i p 网络中存在的拥塞问题，特别是在由路由器 连接的带宽差异较大的网络中，容易发生“拥塞崩溃”现象”1 ，但在科研界没有 引起足够的重视。直到1 9 8 6 年1 0 月，i m e m e t 首次出现了一系列的拥塞崩溃现 象，网络吞吐量急剧下降，从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 e o b s o n 等人开始对此进行研究，发现这是由于在网络拥塞状态 下t c p 的行为失常所致，为此j a c o b s o n 在t c p 中增加了拥塞控制算法( 即t c p t a h o e ) ，于1 9 8 8 年提出了著名的“匣启动”( 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 t ) “1 ；1 9 9 0 年的t c p r e n o 版本 增加了“快速恢复”( f a s tr e c o v e r y ) 算法，避免了网络拥塞不够严重时采用“慢 启动”带来的大幅度减小发送窗口大小的现象。后来又相继产生了几个主要版 本的t c p 端系统拥塞控制算法，即t c pn e w r e n o 、t c ps a c k 、t c pv e g a s 。 虽然版本不同，但都是遵守a i m d ( 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 ，加 性增加倍乘减小) 的窗口管理算法原理，即网络出现拥塞时，t c p 连接通过丢包 发现拥塞，窗口从w 减少至( 1 一b ) w 。t c p 拥塞控制机制在i n t e r n e t 中的执行有 效地避免了拥塞崩溃现象的发生。 1 2 2 主动队列管理 在i n t e m e t 中，i p 层在指示和控制拥塞方面不提供任何支持。在复杂的网络 环境中，由源端发送到目的端的分组要经过多个中i n j 节点( 路由器) ，每一个中 问节点需要为其分配资源并将其转发到下一站，如果分组在到达目的地之前丢 弃，则在传输过程中消耗的所有资源都被浪费，这样无疑造成了网络资源利用 率的降低。随着i n t e m e t 的规模不断扩大，新的应用不断出现，仅仅寄希望于所 有应用都实现端到端的拥塞控制是不现实的，网络本身必须采用某种手段参与 拥塞控制。由于路由器是i n t e r n e t 的核心部件，也是网络拥塞状态的最直接的感 妇门人学硕士学位论文 受者，所以由i p 层参与资源的分配控制工作，在路由器中引入相应的拥塞控制 机制更能有效地对拥塞进行监测和预防。因为路由器无法提前预测通信流量， 它通过检测当前负载来要求端系统增加或减少注入网络的流量。所以在路由器 处引入拥塞控制应作为对端系统拥塞控制机制的补充并与之协作，这样才能有 效地解决i n t e r n e t 中的拥塞问题。事实上，现有路由器对拥塞控制的主要扩展功 能是路由器队列缓存管理，并没有与i n t e r n e l 将流状态信息保存在主机端的早 期设计理念相冲突。它通过控制路由器缓存与队列的占用间接影响带宽的分配， 协助传统的端到端拥塞控制解决网络拥塞。近几年关于i p 层拥塞控制的研究逐 渐增多，形成了一个新的研究热点。这也是本课题的研究动机。 队列管理通过选择何时丢弃何种业务流分组来控制队列长度，因为分组的 丢弃通常被t c p 的流量控制作为拥塞发生的信号，因此，队列管理和流量控制 存在密切的联系。以前路由器中最常用的队列管理是“尾丢弃”( t a i ld r o p ) ， 从拥塞控制的角度分析，它是一种拥塞恢复机制，已经在i n t e r n e t 上成功工作了 许多年，但它有三个严重的缺陷： ( 1 ) 满队列问题：由于“尾丢弃”算法只有在队列满时才会发出拥塞信号， 因此会使得队列在相当长时间内处于充满( 或几乎充满) 的状态。 ( 2 ) 死锁问题：在某些情况下，”尾丢弃“算法会让某个流或者少数几个流独 占队列空间，阻止其他流的包进入队列。 ( 3 ) 全局同步问题：由于i n t e m e t 上数据的突发本质，到达路由器的分组也往 往是突发的。如果队列是满的或几乎是满的，就会导致在短时间内连续 大量地丢弃分组。而t c p 流具有自适应特性，源端发现分组丢失就急剧 地减少发送窗口，分组到达速率就迅速下降，于是网络拥塞得以解除， 但源端得知网络不再拥塞后又开始增加发送速度，最终又造成网络拥塞， 而且这种现象常常会周而复始地进行下去，从而在一段时间内网络处于 链路利用率很低的状态，降低了整体吞吐量，这就是所谓的“t c p 全局 同步”现象。 “首丢弃”( f r o n td r o p ) 是另一种由队列溢出触发的缓存管理策略，当有 新的分组到达时，选择位于队列头部的分组丢弃。l s k s h m a n 等人”1 指出该策略 优化了t c p 的性能，譬如改善了公平性、防止了死锁，因为“首丢弃”使得分 组的丢失分布服从链接对缓存的占用。为了进一步解决全局同步问题，在分组 四川大学硕士学位论文 丢弃策略中引入了随机概念，使得那些导致拥塞的主要链接在拥塞的恢复中承 担了主要的责任，文献指出：“随机丢弃”网关增强了公平性，提高了大时延 链接的吞吐量，随之而来的计算歼销却是不可避免的。 “首丢弃”和“随机丢弃”有效地解决了死锁和全局同步问题，但仍然没 有解决持续的满队列问题。由于这几种方法都是在队列满了被迫丢包，因此称 为被动式队列管理。 如果路由器在拥塞发生前能采取一些预防措施，那么满队列问题是可以得 到解决的。主动的而非响应性的分组丢弃就是一种有效的手段，相应的队列管 理策略被称为“主动队列管理”( a c t i v eq u e u em a n a g e m e n t ，a q m ) 。它是近年： 来队列管理研究中的一个热点，a q m 和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 ， 显式拥塞指示) 结合，使得通知拥塞的信号不再是唯一的分组丢弃，而可以采 用标记分组来通知源端减速，这样会进一步提高链接的有效吞吐量( g o o d p u t ) 。 a q m 的主要技术目标是在减少排队时延的同时保证较高的吞吐量。a q m 解决 的问题主要包括以下四方面： ( 1 ) 早期检测路由器可能发生的拥塞，并通过随机丢弃或标记分组来通知源 端采取措施避免可能发生的拥塞。 ( 2 ) 对突发性、持久性和间隙性的各种t c p 业务流进行较公平地处理。 ( 3 ) 避免多个t c p 链接由于队列溢出而造成同步进入“慢启动”状态。 ( 4 ) 维持较小的队列长度，在高吞吐量和低时延之间作出合理权衡。 虽然b r a d e n 等人在1 e t f 提出a q m 的研究是在1 9 9 8 年1 ，但与其密切相 关的“随机早期检测”( r a n d o m e a r l y d e t e c t i o n ，r e d ) 算法的研究却是由来已 久了。早在1 9 9 3 年，f l o y d 和j a c o b s o n 就提出了r e d 。，当时的主要目的是克 服“早期随机丢弃”( e a r l yr a n d o md r o p ，e r d ) 路由器偏袒突发业务而造成的 不公平性问题。因为在提出a q m 的研究时，r e d 是唯一一个能实现它技术目 标的算法，所以r f c 2 3 0 9 将其推荐为a q m 的唯一候选算法。本课题的研究重 点也就是r e d 及对它的改进研究。 1 3 本文的主要工作及内容安排 本文详细阐述了r e d 算法原理，并简单介绍了已有的一些r e d 改进算法；分 四川大学硕士学位论文 析了r e d 算法中e w m a ( 指数加权滑动平均：e x p o n e n t i a lw e i g h t e dm o v i n g a v e r a g e ) 形式计算平均队列长度并由此决定何时丢弃及丢弃概率大小的局限 性，并在此基础上，提出了一种改进的r e d 算法，通过仿真实验验证了该算法 较r e d 在某些性能上的提高及其有效性。 本文的文章结构组织如下： 第二章介绍了t c p 基于滑动窗口的端到端的拥塞控制机制和当前i p 层的各 种拥塞控制策略，并着重介绍了基于分组丢弃的缓存管理技术，为第三章介绍 r e d 给出理论基础。 第三章着重介绍了r e d 基本原理及算法实现，并介绍了其已有的改进算法， 对其性能进行了简单比较。 第四章是本文的重点，在分析r e d 算法以e w m a 形式计算平均队列长度的局 限性的基础上，将当前队列长度引入到丢弃概率的计算上，并减小当前队列长 度小于m i n 。时e w i a 计算值的作用。仿真结果表明改进的r e d 算法提高了瓶颈 链路的利用率，减小了链路丢包率。 四川大学坝士学位论文 2t c p i p 拥塞控制策略 本章首先详细讨论了i n t e r n e t 中t c p 基于滑动窗口的端到端的拥塞控制机 制及其改进方案，然后介绍了当前i p 层的各种拥塞控制策略，并对它们进行了 比较分析。 2 1 拥塞控制的基本原理 当网络中的分组太多，导致网络无法即时传送所有的分组，从而引起网络 性能的降低，这种情况称为网络拥塞。从控制论角度出发，拥塞控制策略可以 被分为两类：开环拥塞控制和闭环拥塞控制。 开环拥塞控制的关键在于，它致力于通过良好的设计来保证拥塞在一开始 就不发生。典型的使用开环拥塞控制的算法包括广泛应用于a t m 网络中的流量 整形的各种方法，如令牌桶算法等，以及应用于虚电路子网中的接入允许控制 等等。 因为t c p i p 网络是一个规模巨大的分组网，仅仅依靠源端的通信量整形， 不足以维护整个网络的正常运转，所以必须依靠网络本身对流入的业务量进行 管理，也就是必须依靠闭环拥塞控制。 闭环拥塞控制的基本思想是建立在反馈环路的概念之上的。它分为三个部 分： 1 ) 监视系统：检测何时何地发生了拥塞。 2 ) 将此信息传送到可能采取行动的地方。 3 ) 调整系统作出相应操作以解决拥塞问题。 t c p 仃p 网络中，检测拥塞的一般方法是源端发现有分组丢失或者收到了 i c m p ( i n t e m e tc o n t r o lm e s s a g ep r o t o c o l ，i n t e m e t 控制消息协议) 源端抑制报文。 i c m p 源端抑制报文来自于网络中的路由器，当路由器发现用于接收分组的缓存 空间溢出或者达到某一门限时，则可能向引起问题的源端发送i c m p 源端抑制 报文，通知源端降低发送速率。 源端降低发送速率是最常采用的拥塞解决方案，它降低了向网络输入的负 四川九学坝上学位论文 载量。除了降低向网络输入的负载量以外，还有一种方案就是增加网络的承受 力，即增加网络的资源，事实上这就相当于暂时性地增加了网络的带宽。比如， 在t c p i p 网络中，当发生严重摘塞时，可以启用备份路由器以暂时提高网络容 量，缓解拥塞。显然，这不能从根本上解决网络拥塞。 t c p i p 网络中通常用于减少网络流量的方法是在源端采用滑动窗口技术， 在接收到路由器发送来的i c m p 源端抑制报文或者出现分组丢失时，源端通过 降低t c p 的发送窗口大小，并通过对留在窗臼内的分组的重传定时器进行指数 加权而降低向网络中注入的业务流量，从而能够很好地缓解并最终消除网络上 的拥塞。 2 2t c p 基于窗口的端到端的拥塞控制机制 t c p 是目前i n t e m e t 上应用广泛的传输层协议，实施拥塞控制是t c p 的两 个主要任务之一，由于i p 是一个无连接、无状态的协议，所以i p 层在发生拥 塞时不向端系统提供任何显式的反馈信息“，因而t c p 拥塞控制采用的是基于 滑动窗口的端到端的闭环控制方式。为方便后面t c p 拥塞控制策略介绍，下面 将先介绍下t c p 拥塞控制中的一些基本概念。 2 2 1 基本概念 拥塞窗口( c w n d ，c o n g e s t i o nw i n d o w ) ：拥塞控制的关键参数，t c p 在启 动阶段使用或在拥塞时期为减少流量而使用的窗口，控制源端在拥塞情况下一 次最多能发送多少数据包。 允许窗口( a w n d ，a d m i s s i o n w i n d o w ) ：接收端对源端发送窗口大小所做的 限制，在建立连接时由接收方通过a c k 确认捎带给源端。 慢启动闽值( s s t h r e s h ，s l o ws t a r tt h r e s h o l d ) ：拥塞控制中用来限制发送 窗口大小的门限值，它是慢启动阶段与拥塞避免阶段的分界点，初始值设为 6 5 5 3 5 b y t e s 或c w n d 的大小。 回路响应时间( r t t ，r o u n dt r i pt i m e ) ：一个分组从源端发送到接收端直至 源端收到接收端对该分组的确认信息所经历的时间间隔。 四川大学硕士学位论文 重传定时器( r t o ，r e t r a n s m i s s i o nt i m e o u t ) ：描述分组从发送到失效的时间 间隔，是源端用来判断分组是否丢失和网络拥塞的重要参数，通常设为2 r t t 或5 r t t 。 2 2 2t o p 拥塞控制算法 t c p 拥塞控制可以分为四个阶段”“ 慢启动 拥塞避免 快速重传 快速恢复 用图表示这四个阶段的关系如下： j j j j j j l 说重传和快速 黼却 图2 1t c p 源端拥塞窗口变化情况 恢复 1 ) 慢启动 t c p 中使用的发送窗口越大，t c p 源端在必须等待一个确认之前可以发送的 分组数就越多。t c p 实体可以发送数据的速率是由对以前发送的分组的a c k 确认 到达的速率所确定的，然而a c k 到达速率是由源端与目的端之间往返路径上的 瓶颈所确定的，而瓶颈既可能是目的端也可能是互联网。这样一来，t c p 实体就 能通过a c k 到达的快慢来自动感知网络瓶颈并对其流量作出调整，这就是t c p 9 四川大学硕士学位论文 的自同步特性。在正常情况下，t c p 的自同步特性“23 会为t c p 确定恰当的速率。 然而，当一个连接刚刚初始化时，就不存在这样的同步机制使其确定适当的速 率。 可以采取的一种策略是让t c p 发送方从某个相对较大的窗口开始发送，希 望在此过程中逼近连接所最终能提供的窗口大小。但这比较危险，因为发送方 在从超时上认识到流量出现过量之前可能已经造成互联网的流量泛滥。相反地， 我们应该采取某种逐渐扩展窗口的方法，直到同步机制起作用。 j a c o b s o n “。推荐了一种称为慢启动的规程。t c p 使用了一个拥塞窗口，窗口 以分组而非字节来计算大小。在任意时刻，t c p 传输受限于下列关系式： a w n d = m n c r e d il ，c w 叶q d 其中，c r e dj t = 最近一次确认所许可的可以使用的信用量，单位是分组。当一个 确认被收到时，这个值由“窗口分组大小”来计算，其中“窗口”由到来的t c p 分组中的一个字段( 对等t c p 实体所愿意接受的数据量) 给出。 一条新连接建立的时候，t c p 实体初始化c w n d = l 。这就是说t c p 只被允 许发送1 个分组然后就必须等待确认再传输第二个报文段。每次收到一个确认， c w n d 的值就被加l ，一直加到某个最大值为止。 实际上，慢启动机制探测 n t e r n e t 以确保它不会把太多分组发送进一个已 经拥塞的环境或防止在启动一个连接时向网络发送过多的分组而造成网络拥 塞。随着确认的到达，t c p 就可以扩大其窗口，直到流量最终由到来的a c k 而非 c w n d 所控制。源端每收到一个a c k 确认，将c w n d 增加一个分组长度，这 样，c w n d 随r t t 呈指数级增长：1 个、2 个、4 个、8 个，因此源端向网络 中发送的数据量将会急剧增加。实际上，慢启动算法并不慢，要达到可利用的 最大窗口w ，需要的时间为r l o g ，w ( r 为往返时间) “1 。 2 ) 拥塞避免 慢启动算法在初始化连接的时候工作得很有效。它使得t c p 发送方可以快 速地为连接确定合理的窗口大小。在出现拥塞时上述同一种技术是否有用? 具 体地，我们设想一个t c p 实体发起一个连接并经过慢启动过程。在某个时刻， 在c v v 3 q d 达到另一方分配的信用量大小之前或之后，一个分组被丢弃了( 超 时) 。这是发生拥塞的信号。拥塞的严重程度并不清楚。因此，一种明智的方法 是复位c w n d = 1 并重头开始慢启动过程。 四j 1 1 人学颤j 学位论义 这似乎是一种合理的保守的方法，但实际上它还不够保守。j a c o b s o n 指出 “让网络进入饱和状态很容易，但让网络从中恢复却很难”“j 。换一种说法即 一旦拥塞发生了，要将拥塞清除掉要花很长时间”。因此慢启动中c w n d 的指 数增加就可能太激进，它可能使拥塞更严重。j a c o b s o n 指出丌始使用慢启动然 后则让c w n d 线性增加。具体规则如f 。当超时发生的时候： l 。将慢启动门限设置为目前拥塞窗口的一半大小，即设置 s s t h r e s h = c w n d 2 。 2 设置c w n d = i 并执行慢肩动过程直到c w n d = s s t h r e s h 。在这个阶段， c w n d 在每收到一个a c k 时都加1 。 3 当c w n d s s t h r e s h 时，则每经过一个r t t 对c w n d 加1 。 ： ) 快速重传 发送t c p 实体用来确定什么时候对一个分组进行重传的重传定时器( r t 0 ) 通常比该分组a c k 到达发送方所花的实际往返时间( r t t ) 要长许多。原来的 r f c 7 9 3 算法和j a c o b o s o n 算法都把r t o 的值设胃得比估计的往返时间r t t 要长 一些。 但这种设置的结果是如果一个分组丢失了，t c p 可能不能及时重传。如果目 的t c p 用按序接收策略“”，那么就会导致许多分组的丢失。即使目的t c p 实体 使用按窗口接收策略时，不及时重传也会引起问题。针对此，j a c o b s o n 提出了 两种舰程，分别叫做快速重传和快速恢复“1 。使用这两种规程在某些情况下可以 提高重传的性能。快速重传利用t c p 中的下列规则：如果一个t c p 实体收到一 个失序分组，它必须立即发出一个对于最后一个收到的按序分组的a c k 。对于每 一个到来的分组t c p 将继续重复发送这个a c k ，直到丢失的分组到达填补了它的 缓存中的空隙。当空隙填充后，t c p 就对所有迄今为止按序收到的分组发送一个 积累a c k 。 当源端t c p 收到一个重复的a c k 时，这就意味着分组丢失或分组乱序。通 常假定如果是分组乱序，在目的端处理之前源端只可能收到一个或两个重复的 a c k ；如果源端连续收到三个或更多的重复a c k ，表嘎网络中菜处已经发生了捅 塞，这时，源端立刻重传这个可能丢失的分组，而不是等到超时才重传。这就 是快速重传算法的基本思想。 4 ) 快速恢复 四j i i 大学帧上学位论文 当快速重传算法重传了可能丢失的分组之后，如果让t c p 重新进入慢启动 阶段，将拥塞窗口减为l ，重新开始探测网络带宽，7 a c o b s o n 论证说这种方法 过分保守”。所以j a c o b s o n 提出了一种快速恢复技术：重传丢失的分组，把 c w n d 减半，然后继续以线性规律增加c w n d 。这样就避免了最初的指数慢启 动过程，而直接转向拥塞避免阶段，避免过大地减小发送窗口。 快速恢复和快速重传算法通常一起实现，其算法用伪码描述如下： s t e p l ：if( d u p a c k s = - 3 )当第三个重复a c k 到达时， s s t h r e s h = m a x ( 2 ，c w n d 2 ) ： c w n d = s s t h r e s h + 3 ；)考虑已经离开网络，并且收端已经缓 存起来的分组的个数 s t e p 2 ：重传丢失的分组 s t e p 3 ：此后每收到一个重复的a c k 确认时，c v v 2 q d = c w n d + i s t e p 4 ：当收到对新发送数据的a c k 确认时，c w n d = s s t h r e s h ，这个a c k 能够对那些在丢失的分组之后，第一个重复a c k 之前发送的所有分组进行确认。 以上四个基本算法互相联系，成为目前在in t e r n e t 上主要使用的端系统拥 塞控制机制。 2 2ip 拥塞控制策略及缓存管理技术 i p 拥塞控制策略是指在路由器中采用包调度算法和缓存管理技术。当前， i n t e r n e t 中的路由器一般采用简单的先来先服务( f 1 f 0 ) 调度算法和尾部丢弃 ( d r o pt a il ) 缓存管理方法。本文主要研究的r e d 算法属于缓存管理技术的范 畴，所以在这里就不对包调度算法做介绍了，关于包调度的研究可以参看有关 文献。下面拟就基于分组丢弃技术的缓存管理技术进行主要阐述。 2 2 1 缓存管理的职能 i n t e r n e t 中，缓存管理( 又称为队列管理) ，通常是指利用特定的技术和算 法维护缓存的占用量及缓存的分配方式，并影响下游链路的带宽分配，从整 四j i i 犬学颀上学位论立 体上优化网络的运行性能。基于分组丢弃的缓存管理算法就是指用特定时刻特 定的分组丢弃来达到缓存管理的目的。由于日前的t c p i p 协议尚不能对明晰速 率的反馈信号发生反应( 尽管某些试验性的t c p 版本支持这种功能) ，在一般情 况下，数据源端和目的端仍将分组丢失作为网络拥塞的信号，据此调整发送速 率，所以，从反馈控制的角度讲，如果源端支持t c p 或与之相似的端到端协议， 缓存管理所采用的有针对性的分组丢弃就可以对经过该缓存的流的通信效果发 生影响，而这正是基于分组丢弃技术的缓存管理所能发挥的一个重要作用。 为了更清晰地说明基于分组丢弃技术的缓存管理的职能，需要对分组转发 设备中各个功能模块及其相互关系作个简单的介绍。 图2 2 分组转发设备的基本功能模块 分组转发设备的基本功能包括交换( s w i t c h i n g ) 、路由( r o u t i n g ) 、队列 调度( s c h e d u l i n g ) 和缓存管理( b u f f e rm a n a g e m e n t ) ，如果要支持区分优先 级的分组转发，还需考虑接纳控制( a d m is si o nc o n t r 0 1 ) 、资源预留( r e s o u r c e r e s e r v a t i o n ) 、流分类( c l a s s f y jn g ) 、警管( p o l i c i n g ) 等功能。 在图2 2 中，对于传统的i n t e r n e t 分组转发设备( 如传统i p 路由器) ，所 有业务都以同样等级的b e s te f f o r t ( 尽力传送) 方式转发( 即不支持多优先级) 。 当分组到达时，由缓存管理模块决定是否对该分组进行缓存，最简单的缓存管 理是t b ( t a i ld r o p ，尾丢弃) ，为了提高网络的性能，需采用其他的算法。 当缓存中存放有多个分组之后，就需由分组调度器( p a c k e ts c h e d u l e r ) 决定分组的转发次序，最简单的调度算法就是先进先出f i f o ，它又称为先烈先 泅川大学硕上学位论文 服务f c f s ( f ir s t c o m e f i r s t s e r v e d ) ，也有其他的调度算法可供选用，如f q ( f a i rq u e u e i n g ，公平排队) ，w f q ( w e i g h t e df a i rq u e u e i n g ，加权公平排队) 等。 分组转发的方向由路由控制( r o u t i n gc o n t r 0 1 ) 模块决定，该模块按照某 种路由算法，根据网络的拓扑状态和链路的开销情况，决定将位于输入端口的 分组转发到哪个输出端口。而将分组从输入端口转发到输出端口的具体操作则 由交换结构( s w it c h i n gf a b r i c ) 控制。 随着i n t e r n e t 的发展，人们对网络提出了更高的要求，不仅希望网络能转 发带宽占用较少的普通的数据业务，也希望它转发高带宽的业务( 如包括大量 高清晰度图象的数据文件) 、以及对时延敏感的业务( 如i p 电话) ，这就要求网 络能提供不同的优先级服务，从而可以根据用户的业务需求和付费等级来决定 网络的运作。在这种情况下，分组转发设备必须支持流分类的功能，对到达分 组进行归类，该功能由分类器( c l a s sif i e r ) 实现，之后，不同类别的分组将 在缓存管理、调度，甚至路由和交换等过程中受到不同的对待。 由于b e s te f f o r t 方式难以满足多优先级服务的要求，为了协调用户需求 和网络有限的资源之间的矛盾，需要一种用户方与网络方协商的机制来为