（模式识别与智能系统专业论文）基于双时间标度qos分层拥塞控制算法.pdf

中目 ： 学技术人学坝1 学位论史 垠 。职时阀拓度q o s 分层拥采拄割算法 摘要 传统的t c p 速率溅半的捌塞退避机制容易引起多媒体流过大的速率波动，其 每包确认机制也是多媒体传输中所不希望的。而不具备拥塞退避机制的u d p 流在 拥塞的网络环境中将大量抢占具有捐j 塞退避机制的协议流韵带宽，列时自身的丢 包也迅速增加，并带来系统拥塞崩溃( c o n g e s t i o nc o l l a p s e ) 的潜在危险。故研 究个适合于多媒体传输，具有捌塞退避机制，且能够与t c p 公平分享带宽的传 输协议，成为i n t e r n e t 传输的一个重要课题。 本文第一章详细的介绍了互联网端到端拥塞控制的发展历程。在解释了_ | j 塞控制及介绍了i n t e r n e t 网络模型等基本概念后，对拥塞控制算法的评价方法、 设计困难及其研究概况进行了阐述，并介绍了拥塞控制的源算法。 接f 来的第二章则由浅入深的介绍了几种t c p 友好的拥塞控制算法，首先 详细的介绍t t c p 4 抖j 塞控制机制，接着介绍了几种比较经典的t c p 友好的捌塞控制 算法，女h r a p 、t e a r 、t f r c 、r 从r m t 等。由此也引出了自相似网络流量预测的 概念。 第三章通过对国外主要文献的综合和分析，对网络通信量具有的自相似特 性进 亍了比较深入的讨论，并对互联网同信量自相似模型作了详细的介绍，为后 面提出的在线预测自相似网络业务流的未来变化趋势的方法奠定了基础。 第四章为本文的核心内容，作者针对自相似网络提出了一种基于双n , t f j 标 度速率控制的t c p f r i e n d l y 拥塞控制算法，该算法对网络服务质量( q o s ) 进行分 层，在小时唰尺度上，根掘网络时延及丢包率等信息，在大时阳j 尺度上，通过预 测未来流量水平的变化趋势，在接收端对业务流进行双时涮尺度的速率控制。实 验仿真表明，同t f r c 算法相比，在自相似的网络条件下该算法能够有效降低业务 流的丢失率，且对于t c p 的友好性、公平性以及速率的平滑性等指标上具有较好的 性能。 文章最后的总结阐述了本算法的一些优点和不足之处，提出了以后的着重 改进方向。 关键词：自相似；服务质量分层；流量预测 中周科学救术人学岫t 学位沧支轼十职时问杯度o o s 分层拥采控制算法 a b s t r a c t t h et r a d i t i o n a lc o n g e s t i o nc o n t r o lm e c h a n i s mb a s e do ut c pm a yc a u s eb i gf l u c t u a t i o n so n s e n d i n gr a t ea n dt h er e c e i v e rh a sa na c k n o w l e d g ef o re a c hp a c k e tr e c e i v i n gf r o mt h es e n d e r , w h i c hi sn o ta p p r o p r i a t ef o rt h em u l t i m e d i af l o wu d pw i t h o u tc o n g e s t i o nc o n t r 0 1m e c h a n i s m m a yo c c u p yag r e a td e a lo fb a n d w i d t hb e l o n g i n gt oo t h e rf l o w sw i t hc o n g e s t i o nc o n t r o l m e c h a n i s ms u c ha st c pw h e nn e t w o r kc o n g e s t i o no c c u r s s o m e t i m ei t m a yc a u s ec o n g e s t i o n c o l l a p s et h e r e f o r e ，i ti sn e c e s s a r yt or e s e a r c hat c p f r i e n d l ym e c h a n i s mw h i c hc a nr e g a l eo n b a n d w i d t hf o ra l lv a r i o u sf l o w si nf a i r n e s si ni n t e r n e tt r a n s p o r t i n g i nc h a p t e ro n e ，w ei n t r o d u c et h ed e v e l o p m e n to fe n d t o e n dc o n g e s t i o nc o n t r o lm e c h a n i s m a f t e re x p l a i n i n gs o m ec o n c e p t i o n ss u c ha s c o n g e s t i o nc o n t r o la n dt h ei n t e r n e tm o d e l ，w e e m p h a s i z eo ne x p l a i n i n gt h ee s t i m a t i o nm e t h o d s ，d e s i g n i n gd i f f i c u l t i e sa n dr e s e a r c hs t a t u sn o w a n di n t r o d u c i n gt h ef o u n t a i na r i t h m e t i co f t c r a tt h ef o l l o w i n gc h a p t e rt w o 、w ei n t r o d u c es e v e r a lt c p - f r i e n d l ym e c h a n i s m s f i r s t l yw e p a r t i c u l a r l yc l a r i f yh o wt c pi sc a r r i e do u ts e c o n d l yw ei n t r o d u c es e v e r a lc l a s s i c a lm e c h a n i s m s w h i c ha t ea l lt c p - f r i e n d l ys u c ha sr a p , t e a r t f r ca n dr a a r m ta tl a s t w eb r i n go u tt h e c o n c e p t i o no ft r a f f i cp r e d i c t i o n f nc h a p t e rt h r e e ，w ei n t r o d u c ei n t e r o e tf r a 衔ci nd e t a i l f i r s t w ei n t r o d u c et h em e a s u r e m e n t o fi n t e r n e tt r a f f i c t h e nw ed i s c u s si n t e r n e tt r a f f i cc h a r a c t e r i s t i ca n dm o d e l i n g a tt h ee n do f c h a p t e rt h r e e ，w ed i s c u s ss o m ei s s u e sa b o u ti n t e r n e tt r a f f i cm a n a g e m e n t s e l f - s i m i l a r i t ) ，i st h e m o s ts i g n i f i c a n tc h a r a c t e r i s t i co fi n t e r n e ti r a f f i c ，w ei n t r o d u c et h ec o n c e p to f s e j f _ s i m i i a m yi nt h i s c h a p t e r , g i v es o m ee v i d e n c e sf o rs e l f - s i m i l a r i t yo fi n t e r n e tt r a f f i ca n ds o m es e l f - s i m i l a rt r a f f i c m o d e l s s i n c et h et r a f f i ci nm o d e r nt e l e c o m m u n i c a t i o nn e t w o r k sa l w a y ss h o w ss e l f - s i m i l a r i t yo r l o n g 。r a n g ed e p e n d e n c e ，i nc h a p t e rf o u r , w ep r o p o s e dan e wt c p f r i e n d l yc o n g e s t i o nc o n t r o l m e c h a n i s mb a s e do nt w o t i m e - s c a l er a t ec o n t r o la l g o r i t h ml nt h es m a l l e rt i m e s c a l ew i t h q o s ( q u a l i t yo fs e r v i c e ) s c a l i n g ，t h es e n d e ra d j u s t st h er a t ei nt h es m a l ls c a l ea n de n s u r e st h e q u a l i t y i nt h el a r g e rt i m e - s c a l e ，t h ea l g o r i t h ma d j u s t st h ed i s t a n c eb e t w e e nt h ea d j a c e n tl e v e l s b a s e do nt h el o n g r a n g ed e p e n d e n c yo ft h et r a f f i c o u rs i m u l a t e dr e s u l ts h o w st h a tc o m p a r e dw i t h t f r c ，i nt h es e l f - s i m i l a rn e t w o r ke n v i r o n m e n tt h ea l g o r i t h mc a ne n h a n c et h et r a c k i n g 曲i l i t yt o t h en e t w o r ka n dg a i n i m p r o v e m e n tj nl o s sr a t e i ti sa l s oh a sab e t t e rp e r f o r m a n c ei n t c p f r i e n d l i n e s s i n t r a p r o t o c o lf a i r n e s sa n ds m o o t h n e s s a tl a s t ，w ea l s oe x p o u n ds o m ei n s u f f i c i e n c yo fo u rm e c h a n i s ma n dm e n t i o no ft h em a i n r e p r o v i n ga s p e c to f t h ea r i t h m e t i c k e y w o r d s ：s e l f - s i m i l a r i t y ，q o sl e v e l ，t r a f f i cp r e d i c t i o n n 牛围车l 学技术大学顶土学位冷文 基于双时间标度0 硝纷层拥塞挂制簧= 法 引言 众所周知，t c p 与u d p 协议都不能很好地满足连续媒体流传输的需要。t c p 速率减半的拥塞退避机制容易引起多媒体流过大的速率波动，其每包确认机制也 是多媒体传输中所不希望的。而不具备摺塞退避机制的u d p 流( 被视为违规流) 在 拥塞的网络环境中将大量抢占具有拥塞退避机制的协议流的带宽，同时自身的丢 包也迅速增加，并带来系统拥塞崩溃( c o n g e s t i o nc o l l a p s e ) 的潜在危险。为保证系 统的稳定性和服务的公平性，业界正在研究各种在拥塞条件下能对违规流进行严 厉惩罚的队列管理机制( 如s f b ，r e dp d ，c h o k e ，s c h o k e 等) ，在这些系统中， 使用u d p 的多媒体流在遭遇拥塞时，将会遇到更为严重的性能衰减。 目前i n t e m e t 中的传输业务主要是基于t c p 的，随着多媒体实时应用在 i n t e r n e t 的迅速增长，研究一个适合于多媒体传输，具有拥塞退避机制，且能够 与t c p 公平分享带宽的传输协议，成为i n t e m e t 传输的一个重要课题。如果一种通 信协议与在同等条件下的t c p 流具有近似相同的吞吐量，则称这种协议是t c p 友 好( t c pf r i e n d l y ) 的。t c pf r i e n d l 3 ，协议的研究得到了业界的广泛重视，目前提出 的t c pf r i e n d l y 协议大致可分为2 类：一类是基于a i m d 的，j 1 t e a r ，r a p ，r a a r 等，另一类是基于数学模型的，如t f r c 等。其中，t f r c 已经成为了i e t f ：i ：作 组的正式草案，协议的标准化进程正在启动。 近十年来，大量网络测量与分析证明，自相似在现代高速通信系统中是一 种普遍存在的现象。网络业务流自相似特性的发现，打破了原有网络流是短相关 的基础性假设，自然会带来许多与原有假设不同的性能特征。自相似网络流量的 长时突发性，通常对网络性能起破坏性的作用，如增加队列长度、时延以及数据 包的丢失率等。但是，新的流量模型的引入也可能为网络流量的控制带来新的更 加高效的解决方案。目前，对在自相似环境中t c pf r i e n d l y 协议的性能研究还属于 一个崭新的研究课题。 本文中，作者将讨论幂用网络业务流具有自相似的特点，在t f r c 协议的 基础上，通过发送端对服务质量q o s 进行分层，不同的层次对应不同的发送速率： 同时接收端在线预测业务流的未来变化趋势。在接收端实施双时间尺度的拥塞控 制策略，在小时间尺度模拟t e a r 协议调节发送速率；在大时间尺度调节不同质 量层之间的分层难易度。从而增强系统对网络变化的跟踪能力，降低业务流的丢 失率，提高传输质量，并在自相似的网络环境中保持良好的t c pf r i e n d l y 性能。 中国科学技术大学钡十学位论文基于双时间标度q 嘣分层拥寒控制算 上 本文由此分为四部分： 第章详细的介绍了互联网端到端拥塞控制的发展。在解释了拥塞控制及 介绍了i n t e r n e t 网络模型等基本概念后，对拥塞控制算法的评价方法、设计困难 及其研究概况进行了阐述，并介绍了拥塞控制的源算法，往我们对端到端拥塞控 制这个课题有了定的了解。 按下来的第二章则由浅入深的介绍了几种t c p 友好的拥塞控制算法，首先 详细的介绍y t c p 拥塞控制机制，因为后面的大多数拥塞控制算法都是以此为基 础的，了解t c p 拥塞控制机制有助于我们更好的把握其它的算法思想。接着介绍 了几种比较经典的t c p 友好的拥塞控制算法，如r a p 、t e a r 、t f r c 、r a a r m t 等。由此也引出了自相似网络流量预测的概念。 第三章通过对国外主要文献的综合和分析，对网络通信量具有的自相似特 性进行了比较深入的讨论，并对互联网同信量自相似模型作了详细的介绍，为后 面提出的在线预测自相似网络业务流的未来变化趋势的方法奠定了基础。 第四章则详细介绍了作者提出的基于双时间尺度q o s 分层的t c p 友好的拥 塞控制算法，在小时间尺度上基于t f r c 数学模型对发送速率进行调节，在大时 1 日 尺度上根据自相似网络的特性，对业务流的未来变化趋势作出预测，将q o s 层 次变化的难易度进行微调，最后进行了仿真实验，从t c p 的友好性，协议的公平 性及速率的平滑性等几个主要方面进行了评估。 文章最后的总结阐述了本算法的一些优点和不足之处，提出了以后的着重 改进方向。 巾囝科学技术夫学硕上学位论文罐f 双时闷标度q o s 分层拥鞋控制尊坛 第一章互联网端到端拥塞控制的发展 端到端拥塞控制是目前i n t e r n e t 的一个研究热点。在最初的t c p 协议中 只有流控制( f i o wc or l t r o ) 而没有拥塞控制，接收端利用1 、c p 报头将接收能力 通知发送端。这样的控制机制只考虑了接收端的接收能力，而没有考虑网络的传 输能力，导致了网络崩溃( g o r l g e s t i o 1c o l l a p s e ) 的发生。1 9 8 6 年1 0 月，由于 拥塞崩溃的发生，美国f u l 到0 cb e r k e 【e y 的数据吞吐量从3 2 k b p s 跌落到 i 1 0 b p s i | l 。在那之后，拥塞控制领域开展了大量的研究工作。拥塞控制算法对保 证1 n e t l el 的稳定具有十分重要的作用。网络中的拥塞来源于网络资源和网络 流量分布的不均衡性。拥塞不会随着网络处理能力的提高而消除。拥塞控制算法 的分布性、网络的复杂性和对拥塞控制算法的性能要求又使拥塞控制算法的设计 具有很高的难度。到目前为止，拥塞问题还没有得到很好的解决。本章第1 节 介绍拥塞控制的基本概念，包括拥塞和拥塞控制的概念、i n t e r n e t 的网络模型、 i n t e r n e t 中拥塞发生的原因。第2 节介绍拥塞控制算法的概况，包括拥塞控 制算法的评价方法、拥塞控制算法设计的困难和拥塞控制算法的研究概况。第3 节介绍拥塞控制的源算法，包括“管子”模型、t c p 拥塞控制算法的发展和拥塞 控制源算法的研究热点。第4 节围绕“主动队列管理”算法介绍拥塞控制的链 路算法，包括“主动队列管理算法”的研究概况、“主动队列管理”算法的发展、 网络的流量特征对“主动队列管理”算法的影响和“主动队列管理”算法的反 馈方式。第j 节对全章进行总结。 1 1 基本概念 1 1 1 拥塞和拥塞控制 拥塞是指在要求网络传输的分级数量开始接近网络的分组处理( 传输) 能力 时通信网络不能很好地提供网络通信服务来满足用户要求的情况。拥塞的表现 是分组丢失、分组传输往返时间太长。 拥塞产生的直接原因： ( 1 ) 存储空间的不足。当若干数据流同时需要一条通信链路时，就必须 排队，如果没有足够大的缓存，当队列填满缓存后，这之后到达的 数据就会被抛弃。 ( 2 ) 带宽不足。依据香农公式，一条信道所能传输的信息量( 即信道容量) 是有限的，最多为c = b l o g ，( 1 + s n ) ，c = b l o g ，( 1 + s i - - ) 这是一 条信道可接近但永远无法达到的目标。因此，在某些较差的链路上， 就必然形成瓶颈，j a c o b s o n 对此作了详细描述f 1j 。 ( 3 )处理器能力弱，不能及时处理分组也能造成拥塞。 由于以上三点原因，必然在某些节点处形成排队，队列过长则会导致传输延 时的增加或数据包丢失，最终形成拥塞。 使用图l 1 来描述拥塞的发生。当负载较小时，吞吐量的增长和负载相比基 本呈线性关系，延迟增长缓慢；在负载超过k n e e 之后，吞吐量增长缓慢，延迟 中国示 学挂术，、学硕 学位论文基十积时间际度0 “分层拥采控制箅垃 增长较快；当负载超过( 1 l1 “之后，吞吐量急剧下降，延迟急剧上升。可以看 出，负载在k n o e 附近时网络的使用效率晟高。 拥塞控制就是网络节点采取措施来避免拥塞的发生或者对拥塞的发生作出 反应i ，将网络中的分组维持在一定的水平，维持尽可能高的吞吐量。在图1 1 中就是使负载保持在k n e e 附近。拥塞控制主要考虑端节点之问的网络环境，目 的是使负载不超过网络的传送能力；而流控制主要考虑接收端，目的是使发送端 的发送速率不超过接收端的接收能力。 f k l l 【( jr l “ 图i 1 ：拥塞发生状况描述图 拥塞控制算法一般来讲包含拥塞避免( c or l g e s ti ( ) n 州o i d a n c 。) 和拥塞控制 ( c o n g e h t j o i lc o n t r 0 1 ) 这两种不同的机制。拥塞控制是“恢复”机制，它用于把 网络从拥塞状态中恢复出来；拥塞避免是“预防”机制，它的目标是避免网络进 入捐j 塞状态，使网络运行在高吞吐量、低延迟的状态下。 用于拥塞控制的主要参数有： 拥塞窗口( c w n d ) ：描述源端一次最多能发送的数据量。 慢启动阈值( s s t h ) ：拥塞控制中慢启动阶段和拥塞避免阶段的分界点。 回路响应时间( r t t - - r o u n d t c i pt j m e ) ：一个t c p 数据包从源端发送出去 一直到源端收到宿端的a c k 确认包的时间间隔。 超时重传计数器( r | o r e t r a n s m i m e o u t ) ：指一个数据包从发送到失 效的时间间隔，是判断数据包是否丢失，网络是否拥塞的重要参数。通 常设为2 r t t 或5 r t t 】。 快速度重传阈值( t c p r exm t t hre s h ) ：源端用来判断是否进行快速重传的 一个分界值。是指源端收到的重复a c k 确认包的个数。当此个数大于t c p r e xm t t h r e s h 时，源端进入快速成重传阶段。t c p r exm t t h r e s h 的值通常设 置为3 。 1 1 2i n t e r n e t 的网络模型 拥塞现象的发生和i n t e r n e t 的设计机制有着密切的联系。i nc e r n e t 的网 络模型可以用以下几点来抽象1 2 1 ： ( 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 ) 相比， j 中固毒 学技术大学颂t 学位论文 基于双时间标度qc 分层拥塞控制算拉 报文交换通过共享提高了资源的利用效率。但在共享方式下，如何保证用户 的服务质量是个很棘手的问题。在报文交换网络中可能出现报文“乱序” 现象，对乱序报文的处理增加了端系统的复杂性。 ( 2 ) 无连接( c o i i o c t i o n l e s s ) 网络。i n t e r nf j t 的节点之间在发送数据之前不需 要建立连接。无连接模型简化了网络的设计，在网络的中间节点上不需要 保存和连接有关的状态信息。但是使用无连接模型难以引入“接纳控制” ( a d m is s i o nc o i ll r e l ) 算法，在用户需求大于网络资源时难以保证服务质量； 在无连接模型中对数据发送源的追踪能力很差，给网络的安全带来了隐患： 无连接也是网络中乱序报文出现的一个主要原因。 ( 3 ) b e s t e f f o r z 的服务模型。b e sl _ e f f o r t 即网络不对数据传输的服务质量提 供保证。这个选择和早期网络中的应用有关。传统的网络应用主要是f i p ： t e ln e t 、s 1 p 等。它们对网络性能( 带宽、延迟、丢失率等) 的变化不敏感， b e sl - e f f o r t 模型可以满足需要。但b e s z e f f o r t 模型不能很好地满足新 出现的多媒体应用的要求，这些应用对延迟、速率等性能的变化比较敏感。 这要求网络在原有服务模型的基础上进行扩充。 1 1 3i n t e r n e t 中拥塞发生的原因 拥塞发生的原因是“需求”大于“供给”。网络中有限的资源由多个用，o 苁 享使用。由于没有“接纳控制”算法，网络无法根据资源的情况限制用，o 的数量： 缺乏中央控制，网络也无法控制用户使用资源的数量。目前，inl c f i o l 上用户 和应用的数量都在迅速增长，如果不使用某种机制协调资源的使用，必然会导致 网络拥塞。虽然拥塞源于资源短缺，但增加资源并不能避免拥塞的发生，有时甚 至会加重拥塞程度。例如，增加网关缓冲会增大报文通过网关的延迟，如果总延 迟超过端系统重传时钟的值，就会导致报文重传，反而加重了拥塞。 口悭! 图1 2 ：带宽和流量分布的不平衡 ( b j 拥塞总是发生在网络中资源“相对”短缺的位置。拥塞发生位置的不均衡反 映了i n t e r n e t 的不均衡性。首先是资源分布的不均衡。图1 2 ( a ) 【4 i 中带宽的分 布是不均衡的，当以1 m b s 的速率从s 向d 发送数据时，在网关r 会发生拥 塞。其次是流量分布的不均衡。图1 2 ( b ) 1 4 1 中带宽的分布是均衡的，当a 和b 都 以l 、i b s 的速率向c 发送数据时，在网关r 也会发生拥塞。i n t e r n e t 中资源 和流量分布的不均衡都是广泛存在的，由此导致的拥塞不能使用增加资源的方法 中国科学拄术大学影! “学位论文基十双时问标度q 。s 分层拥塞控制算法 解决。 1 2 拥塞控制算法的概况 1 2 1 拥塞控制算法设计的困难 拥塞控制算法的设计困难体现在以下几方面【4j ： ( 1 ) 算法的分布性。 拥塞控制算法的实现分布在多个网络节点中，必须使用不完整的信息完成控 制，并使各节点协调工作，还必须考虑某些节点工作不f 常的情况。 ( 2 ) 网络环境的复杂性。 i n t e r n e t 中各处的网络性能有很大的差异，算法必须具有很好的适应性。 另外，由于i nl e r n e l 对报文的正确传输不提供保证，算法必须处理报文丢失、 乱序到达等情况。 ( 3 ) 算法的性能要求。 拥塞控制算法对性能有很高的要求，包括算法的公平性、效率、稳定性和收 敛性等。某些性能目标之间存在矛盾，在算法设计时需要进行权衡。 ( ，1 ) 算法的开销。 拥塞控制算法必须尽量减少附加的网络流量，特别是在拥塞发生时。在使用 反馈式的控制机制时，这个要求增加了算法设计的困难。算法还必须尽量降低在 网络节点( 特别是网关j 上的计算复杂性。 目前的策略是将大部分计算放在端节点完成，在网关上只进行少量的操作， 这符合i n t e r n e t 的基本设计思想。 1 2 2 拥塞控制算法的评价方法 在设计和比较拥塞控制算法时，需要一定的评价方法。从用户的角度出发， 可以比较端系统的吞吐率、丢失率和延迟等指标，这些是用户所关心的。由于拥 塞控制算法对整个网络系统都有影响，在评价算法时更应该从整个系统的角度出 发进行考虑。两个重要的评价指标是资源分配的效率和资源分配的公平性。 0 h d 图1 3 ：p o w e r 函数与负载对应图 资源分配的效率：资源分配的效率可以用p o w e r 函数川来评价。p o w e r 函 中国科学技术大学硕卜学位论文基于双时间标度q o s 分层拥塞控制算法 数定义为： p o u l e r = t h r o u g h p u t “r es p o n s e t i m e “1 ) 在上式中，一般取彦= l 。如果评价偏重吞吐量，则取毋 l ；如果评价偏重 反应时问，则取蹦 1 。 如图1 3 所示，当负载位于k n e e 时p o w e r 取最大值。使用p o w er 、函数 有一定的局限性，它主要基于m m 1 队列的网络，并假设队列的长度为无穷。 p o w e r 函数一般在单资源、单用户的情况下使用。 资源分配的公平性： 在多用户情况下，需要考虑资源分配的公平性。公平性评价的主要方法包括 a x m i nf a if n e s s is 】，f a i r f l e s si n d e x l 6 1 和p r o p o r t h a lf a i r n e s s l7 1 等。 m a x m inf a ir n e s s 被非正式地定义为 5 】：每个用户的吞吐量至少和其他共 享相同瓶颈的用户的吞吐量相同。m a x 一 v i i nf a i r n e s s 是一种理想的状况，但是 它不能给出公平的程度。 f a i r n e s si n d e x 提供了一个计算公式，可以计算公平的程度。它定义为d i f y x l l 肌卜耥 ( 12 ) ，f l ， 陌ifnessi n d e x 的计算结果位于0 和l 之间，并且结果不受衡量单位的影响。 它的一个性质是：如果n 个用户中只有k 个用户平均共享资源，而另外( n k ) 个用户没有任何资源，则 = ；算结果为k n 。 一些研究者认为，如果考虑用户的“效用函数”( u t i l i t yf u n c t i o n ) ，在一 些情况下使用m a x - m i nf a i r n e s s 评价并不是最理想的。针对对数的效用函数， 引入了p r o p o r t i o n a lf a ir n e s s 的概念。p r o p o r t i o n a lf a i r n e s s 定义为f j ： 向量x 满足p r o p o r t i o n a lf a ir n e s s ，如果对于其他任何向量y 都满足 。孕- b ) 其中只是报文标记丢失概率，g ，是队列长度。d r o p t a il 的最大问题是反馈变化 比较猛烈，容易造成系统振荡。 r e d 使用“p r o p o r t i o n a l 控制器+ 低通滤波器”的方法计算反馈。 p r o p o r t io n a l 控制器的基本形式为 只= 幻，( 1 5 ) 其中k 是计算使用的比例系数。为了减小“瞬时抖动”对反馈计算的影响，r e d 引入了低通滤波器，将上式中的g ，使用平均队列长度q 。代替。平均队列长度使 中囝科学技术大学硕学位论文 基于双时间标度乜o s 分层拥毫挎制算法 w e i g h t e dm o v jn ga v e r a g e ) 计算： v 。，= ( 1 一“) q 。4 - l 可，( 1 6 ) 其中w 是计算的权重。p f o p o r ti o f ) ；q 控制器的优点是实现简单、反应速度快： 缺点是控制存在“稳态误差”( s t e a d y s t a t ee f f o f ) ，这是平均队列随网络流量 增长的主要原因。另外，r e d 使用低通滤波器降低了系统的反应速度，固定的w 不能适应不同速率的网络链路。 在p i 中使用了p i 控制器。p i 控制器的形式为 p ，+ 1 = p ，十“( q ，+ i q ) + b a q ，+ 1 ， f7 、 q 川= q 川一g 。， 其中q 是控制的目标，a 和b 是比例系数。通过在反馈计算中引入积分项一 p i 控制器可以有效地消除p r o p o r t i o n a l 控制器中出现的“稳态误差”，从而 保证队列长度的稳定。r e m 和a v o 中也使用了pt 控制器。在a v q 中被控制的 对象是队列的入i ：2 速率，而不是队列长度。r e 除了使用p i 控制器以外还引入 了指数函数，但是并没有明确说明使用指数函数的优势。在a o m 算法中使用p f 控制器虽然可以消除“稳态误差”，但同时也会减慢系统的反应速度。当网络 中的流量发生很大变化时，使用i ，i 控制器需要的收敛时间要远远长于使用 p r o p o rl i o n a l 控制器的情况。这是p i 、r e d 和“q 都存在的问题。 1 4 3 网络流量特征对a 伽算法的影响 网络流量特征对a q m 算法的设计和有效性有很重要的意义。大部分a q m 算 法使用模拟器1 3 1 进行验证，模拟时多数采用f t p 流量，这并不符合网络实际测量 得到的结果。文献【9 1 的测量结果中，7 5 的字节、7 0 的报文和7 j 的“流”是w o b 流量，f t p 只占j 的字节、3 的报文和小1 的“流”。“流”是网络资源的用户， 拥塞控制算法负责在多个“流”之间分配资源。在平衡状态下，如果网络中“流” 的数量增加或者资源的数量秽少，在“流”之间必须重新进行资源分配。在重分 配完成之前会暂时出现“需求”大于“供给”，从而发生拥塞。假设网络资源的 数量是相对稳定的，如果“流”的数量不断剧烈地变化，就会不断出现拥塞。这 要求a q m 算法具有很好的反应速度。目前，jn t e r n e t 网络流量特征的研究还不 够充分。 1 4 4a 删算法的反馈方式 a q m 计算出反馈大小以后，需要将反馈传递给端系统。网关可以采用的反馈 方式包括“丢弃”( d r o p p i n g ) 和“标记”( m a r k i n g ) 。 “丢弃”是所有网关都支持的操作，传统的t c p 算法只使用报文丢失作为 拥塞发生的指示。“标记”方式“显式”地通知端系统，可以避免t c p 发送端 调用超时处理。试验结果显示“标记”比“丢弃”具有更好的性能。“标记”方 式的缺点是要求网关提供特殊支持，但随着e c n 的标准化和广泛采用，这个问 题将得到解决。“源抑制”( s o u r c eq u e n c h ，简称s q ) 也是反馈的一种方式。当 中尉 学技术大学两l 上学位论文 基于双时间标度q o s 分层拥塞控莉葬洼 网络流量超过网关的处理能力时，网关在丢弃报文的同时可以向数据源发送i q 报文，由数据源对发送速率进行调整。直观i 二看，s q 与e c x 相比可以提供更决 的反馈。研究表明，e c 、在以f 几方面优于s q ： ( 1 ) 拥塞发生时e c x 不增加网络的负担，会增加反方向网络链路的流量； ( 2 ) s q 在i c 报文处理方面会给网关增加太多的负担； ( 3 ) 报文在e c x 方式中只是被“标记”，可减少报文的丢失，并可以避免发 送方等待超时重传，这对于短连接更为重要； ( 4 ) e c 对“基于发送端”( s e n c l e r b a s e j ) 和“基于接收端”( f e t e jv e f b a s e d ) 的拥塞控制算法都适用，而s q 只能用于“基于发送端”的拥塞控制算 法。 总之，以目前的理解，e c x 与s q 相比是一个更好的选择。 1 5 总结 本章从源算法和链路算法两个方面对互联网端到端拥塞控制的研究现状进 行了总结。本章在介绍研究现状的同时，讨论了拥塞控制领域的研究热点。这些 研究热点可以总结为以下几大类： ( i )对t c p 协议本身的改进，包括对t c p 中各种机制的改进和对i ( p 在各种网络环境下优化的研究。 ( 2 ) 对多媒体传输拥塞控制的研究，包括传输算法的设计和传输公平性 的研究。 ( 3 ) 对“主动队列管理”算法的研究。 近些年来，非线性规划理论和系统控制理论被引入到拥塞控制的研究中来， 一些研究者尝试使用严格的数学模型来描述端系统和网关组成的系统。这对拥塞 控制的研究有很大的推动作用。网络流量特征对拥塞控制中链路算法的设计和 成功有很重要的意义。对实际网络流量的测量和分析还有待于进步深化。下章 将着重介绍几种多媒体传输拥塞控制机制。 中田科学技术、学碗 学位论文基于双时i 可标度s 分层拥塞控制算法 第二章一些t c p 友好的拥塞控制机制详述 随着网络带宽的日益扩大，多媒体服务( 如音频服务与视频服务) 越来越广 泛的应用于因特网上。如今多媒体流量控制技术被广泛应用于许多实时多媒体应 用当中，由于t c p 拥塞控制机制采用窗口a 1 q d ( 加增乘减) 机制，使得发送速率 抖动太大，将影响多媒体的服务质量，故不适用于多媒体流业务。于是，一些t c p 友好的拥塞控制机制被提出以弥 f t c p 的缺点，以适应于多媒体业务流的传输。 r e z ar e j a i e 等人提出了r a p 协议( r a t oa d a p t a ti o np r o t o c 0 1 ) m i ，其主 要部分是在源端实现的。它是一种基于速率的拥塞控制方法。它利用端到端的每 包反馈机制，如果没有探测到拥塞，周期地增加传输速率；如果发现了拥塞，马 上减少传输速率。另外，r a p 为了减低发送速率的剧烈波动还使用了一一个精细增 益速率适配算法。 s f l o y d 提出了一种算法，称为t f r c ( t c p f r i e n d l yr a l ec o n t f 0 1 ) f l ， 一种基于公式的单播业务拥塞控制机制。它以分组丢失率及回路往返时间作为参 数，利用公式表达发送端所能接受的最大发送速率。 i r h e e 提出了另一种算法，称为t e a r ( t c pe m u l a t i o nd tr e c e i 、o f s ) i ”i ， 一种在接收端模拟t c p 的协议，接收端并不把探测到的拥塞信号( 包的丢失) 反馈 回发送端，而是自己马上利用这些信号来修改发送速率，然后把计算后的发送速 率报告发送方。 本章将陆续介绍这些算法实现的原理及优缺点。 2 1t c p 拥塞控制机制 2 1 1t c p 拥塞控制的基本方式 复杂系统的许多问题，都能从控制论角度观察，网络也不例外。拥塞控制的 方法，不论什么形式都可归为两类：开环和闭环控制。开环控制是在事先设计一 个“好的”网络，确保它不发生拥塞，而网络一旦运行起来，就不再采取措施。 显然对网络这样不断变化的复杂系统，开环控制并不是理想的选择。t c p 的拥塞 控制采用的是基于窗口的端到端的闭环控制方式。图2 1 是对拥塞控制机制的一 种描述。 如果在时刻t ，第i 个用户的传送负载为x ( f ) ，那么输入网络的总负载应为 爿，( ，) 。系统状态用n 维向量x ( ，) = ( f ) x 2 ( f ) ，瓦( f ) ) 表示。如果m ) 不大于网络承受能力x 。，所有用户的负载请求都会被接受。这样，x 。( f ) 也同 时表示网络系统资源分配给每个用户的情况。用户与系统通过反馈控制函数y ( t ) 相互作用，实时地改变传送负载大小。假定改变量为( ，) ，则o + 。= ( ，) + v ( f ) ， 变化u ，( r ) 就代表了对第i 个用户的控制。它是用户t 时刻负载和系统反馈的函数 u ，( ，) = f ( x ，( f ) ，r ( ，) ) ，也就是y i ( ，+ a t ) = 肖，( ，) + 厂( 一( f ) ，y ( f ) ) 。 中国科学技术大学碗卜学位论文基于双时间标度0 0 1 分层拥塞控制算法 厂i _ 1一一 厂、， 11 11卜二一- 寸睡圈一 网络 图2 1 ：x - f - 用户共享一个网络下拥塞的闭环控制系统 一 v a n j a c o b s o n 在文献i t 中指出了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 c ) 算法。后 来出现的t c p r e n o 版本增加了“快速重传”( f a s t 阳t r a n s m i t ) 算法、“快速恢复” ( f a s t r e c o v e r y ) 算法，避免了网络拥塞不够严重时采用“慢启动”算法而造成过 大地减小发送窗口尺寸的现象，这样1 、c p 的拥塞控制就由这4 个核心部分组成，最 近几年又出现t c p 的改进版本如o w r e n o l l i i 、s a c k 等。 f c p 拥塞控制是通过控制一些重要参数的改变实现的。t c p 用于拥塞控制的参 数主要有： ( 1 )拥塞窗口( c w n d ) ：是拥塞控制的关键参数。它描述源端在拥塞控制 情况下一次最多能发送数据包的数量。 ( 2 )通告窗口( a wl n ) ：是接收端给源端预设的发送窗口大小，它只在i e p 连接建立的初始阶段起作用。 ( ：j ) 发送窗口( w i n ) ：是源端每次实际发送数据的窗口大小。 ( 慢启动闽值( s s t b r e s h ) ：是拥塞控制中慢启动阶段和拥塞避免阶段 的分界点。初始值通常设为6 5 5 3 5 b y t e s 。 ( j ) 回路响应时间( r t t ) ：一个? c p 数据包从源端发送到接收端，源端收 到接收端确认的时间间隔。 ( 6 ) 超时重传计数器( r t o ) ：描述数据包从发送到失效的时间间隔，是判 断数据包丢失与否、网络是否拥塞的重要参数。通常设为2 r t7 f 或 5 r t t 。 ( 7 ) 快速重传阈值( t c p r e x m t t h r e s h ) ：是能触发快速霆传