（计算机应用技术专业论文）internet拥塞控制相关算法研究及仿真分析.pdf

西南交通大学硕士研究生学位论文第1 贞 摘要 随着新型网络应用的不断涌现和用户数量的迅速增长，i n t e r n e t 的漉 量正急剧增长，越来越严重的拥寨问题暴露出来。i n t e r n e t 中的拥塞控制 对保 芷i n t e r n e t 的稳定性具有十分重要的作用，使用拥塞控制是其它q o s 机制正常工作的必要前提。 t c p 是i n t e m e t 上最主要的传输协议，当前i n t e r n e t 的稳定性主要归 功于它所采用的端到端拥塞控制。尽管t c p 非常适合于诸如批量数据传 输应用，但它不适合予实时应用。为了支持诸如流媒体的实时应用传输， 研究人员提出了许多t c p 友好拥塞控制机制。本文对这些拥塞控制机制 进行了介绍，同时对其性能进行仿真分析。 基于端点的机制实施容易，但它对拥塞的检测是通过拥塞的效果来实 现的，在公平性和应付行为不端的信源方面表现较差。因此，研究人员提 出了在拥塞发生的地方即路由器来检测拥塞。本文对两种典型的路由器支 持的拥塞拄制机制a q m ( a c t i v eq u e u em a n a g e m e n t ) 和e c n ( e x p l i c i t c o n g e s t i o nn o t i f i c a t i o n ) 进行介绍，并对几种典型的a q m 算法进行了仿真 分析。 t c p 拥塞控制机制存在的另一个晦题是：t c p 难以实现相互竞争的连 接之间的公平带宽共享。目前，实现公平带宽共享的机制主要有三种：依 流调度机制、依流丢弃机制和无状态公平队列算法。其中，无状态公平队 列算法与前两种机制相比，实现复杂度低。具有较好的扩展性。核心无状 态算法是用于实现公平带宽分配的典型算法，它在降低算法实现复杂度啦 同时保留了较好的公平性，但它仍然存在诸多需要改进之处。本文作者提 出了一种结合队列长度的c s f q ( c o r e s t a t e l e s s f a i rq u e u i n g ) 改进算法，并 对其性能进行了仿真分析。改进的算法能够达到近似公平带宽分配，在傍 持c s f q 其它优点的基础上，进一步改善了总体吞吐曩，减少了分组转发 时延，并更有效地利用了链路带宽，且仍能避免拥塞的产生。尤其对小流 量和突发性间歇性流量，该改进算法在性能上有显著提高。 关键词：拥塞控制；t c p 友好拥塞控制；a q m ；c s f q ；仿真分析 西南交通大学硕士研究生学位论文第1 i 页 a b s t r a c t w i t ht h e e m e r g e n c e o f m a n y n e wn e t w o r k a p p l i c a t i o n s a n d r a p i a e x p a n s i o n o ft h eu s e r , i n t e r a c tt r a f f i ch a sb e e n i n c r e a s i n gd r a m a t i c a l l y , a n dt h e n e t w o r kc o n g e s t i o na p p e a r st ob eam o r ea n dm o r ec r i t i c a li s s u e c o n g e s t i o n c o n t r o lm e c h a n i s m sa r ev e r yi m p o r t a n ti ng u a r a n t e e i n gt h es t a b i l i t yo fi n t e r n e t m o r e o v e r , as u i t i b a l ec o n g e s t i o nc o n t r o lm e c h a n i s mb e c o m e st h en e c e s s a r y p r e m i s e f o ro t h e r q o s ( q u a l i t y o fs e r v i c e ) m e 吐a n i s mt ow o r k e f f e c t i v e l y t c pi st h ed o m i n a n tt r a n s p o r t p r o t o c o l o ni n t e r n e t ，a n dt h ec u r r e n t s t a b i l i t yo fi n t e r a c td e p e n d so ni t se n d t o e n dc o n g e s t i o nc o n t r o l ，w h i c hu s e s a na 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 e a t i v ed e c r e a s e ) a l g o r i t h m a l t h o u g h t c pc o n g e s t i o nc o n t r o li s a p p r o p r i a t ef o ra p p l i c a t i o n s s u c ha sb u l kd a t a t r a n s f e r ，i ti sn o ts u i t a b l ef o rr e a l - t i m ea p p l i c a t i o n s i no r d e rt os u p p o r tt h e t r a n s f e ro fr e a l - t i m e a p p l i c a t i o n s u c ha s s t r e a m i n gm u l t i m e d i a ，v a r i o u s t c p - f r i e n d l yc o n g e s t i o nc o n t r o lm e c h a n i s m sh a v eb e e np r o p o s e d i nt h i s t h e s i s ，s o m eo ft h e s em e c h a n i s m sa r ed e s c r i b e d ，a n dt h ep e r f o r m a n c eo ft h e m a r ec o m p a r e da n d a n a l y z e dt h r o u g h s i m u l a t i o n c o n g e s t i o n c o n t r o lm e c h a n i s m sb a s e do ne n d p o i n t a r e e a s y t ob e i m p l e m e n t e d ，b u t ap r o b l e mw i t ht h e mi st h a tt h e c o n g e s t i o n i sd e t e c t e d t h r o u g ht h ee f f e c t so fc o n g e s t i o nr a t h e rt h a nt h ec o n g e s t i o ni t s e l f a n da l s o t h e r ea r ep r o b l e m sw i t hf a i r n e s sa n dn o n - c o m p a l i a n ts o u r c e s t h e r e f o r e ，：! s e e m sl o 西c a lt op a l c et h ec o n g e s t i o nc o n t r o lm e c h a n i s ma tt h el o c a t i o no f c o n g e s t i o n ，i e ，t h er o u t e r t w ot y p i c a ls c h e m e s ，t h a ti s ，a q m ( a c t i v eq u e u e m a n a g e m e n t ) a n de c n ( e x p ! i c i tc o n g e s t i o nn o t i f i c a t i o n ) ，a r ei n t r o d u c e di n t h et h e s i s t h ep e r f o r m a n c eo fs o m e t y p i c a la q ma l g o r i t h m si sa l s oa n a l y z e d t h r o u g h s i m u l a t i o n a n o t h e r p r o b l e m w i t ht c p sc o n g e s t i o nm e c h a n i s mi st h a ti ti sd i f f i c u l t t oa c h i e v ef a i rb a n d w i d t hs h a r i n ga m o n gv a r i o u sc o m p e t i n gc o n n e c t i o n s c u r r e n t l yt h r e ea p p r o c h sa r eu s e dt o a c h i e v ef a i rb a n d w i t hs h a r i n g ，t h a ti s ， p e r - f l o ws c h e d u l i n ga l g o r i t h m ，p e r - f l o wd r o p p i n ga l g o r i t h ma n d s t a t e l e s sf a i r 西南交通太学硕士研究生学位论文第1 i i 员 q u e u e i n ga l g o r i t h m a m o n gt h e m ，s t a t e l e s sf a i rq u e u e i n ga l g o r i t h mh a sb e t t e r s c a b i l i t ya n dl e s si m p l e m e n t a t i o nc o m p l e x i t yt h a nt h eo t h e rt w os h c e m e s ， c s f q ( c o r e s t a t e l e s s f a i r q u e u i n g ) a l g o r i t h mi s a t y p i c a l s t a t e l e s sf a i l q u e u i n gs c h e m ed e s i g n e dt oa c h i e v ef a i rb a n d w i d t ha l l o c a t i o nw i t hm i n i m a l i m p l e m e n t a t i o nc o m p l e x i t y b u t t h e r ea r es t i l ls e v e r a l p o s s i b i l i t i e s f o r i m p r o v i n gc s f q t h ea u t h o ro f t h i st h e s i sp r o p o s e sa ni m p r o v e m e n tt oc s f q a n d a n a l y z e s i t b y s i m u l a t i o n t h er e v i s e d a l g o r i t h mi m p r o v e s t h e p e r f o r m a n c eo fc s f q a ts o m e a s p e c t ss u c ha st h r o u g h p u t ，f o r w a r d i n gd e l a y a n dl i n kb a n d w i d t h e s p e c i a l l y ，i ti m p r o v e st h ep e r f o r m a n c ee f f i c i e n t l yf o r s h o r tf l o wa n db u r s tf l o w 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 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 ；a q m ； c s f q ；s i m u l a t i o na n a l y s i s 匿南交通大学硕士研究生学位论文第1 页 第一章绪论 i n t e m e t 在过去十几年里按指数方式增长。目前，i n t e r n e t 已经成为最 重要的信息交换手段。人们利用i n t e r n e t 接受教育、娱乐、处理个人财务、 购物等。随着i n t e r a c t 越来越重要，人们对i n t e r n e t 的要求也越来越高， 用户需要更宽的带宽，更好的服务质量，更高的安全性。 随着新型网络应用的不断涌现和用户数量的迅速增长，使得i n t e r n e t 的流量急剧增长，除了传统的w e b 、f 1 p 、t e l n e t 等传统数据流外，还出 现了大量的实时多媒体数据流，由于网络中不同的数据流在路由器处交 汇。越来越严重的网络拥塞问题暴露出来。解决网络的拥塞问题成为了 i n t e r a c t 发展所面临的重要问题之一。 1 1 拥塞控制的研究现状 目前拥塞控制的研究主要分为： ( 1 ) 从控制论的角度出发，拥塞控制算法可以分为开环控制 ( o p e n - l o o p ) 和闭环控制( c l o s e d - l o o p ) 两大类【l 】o 当业务的特征可以 准确规定、性能要求可以事先获得时，适于使用开环控制。开环控制的典 型例子是就是资源预留( r s v p 协议) 。这种方法虽然是一种很直接的控 制拥塞的方法，但由于实现确定精确的业务特征几乎不可能，因此为保证 服务质量、避免拥塞，往往需要预留多余的网络资源( o v e r - p r o v i s i o n ) ： 很容易造成网络资源利用率下降。当流量特征不能准确描述或者当系统：不 能提供资源预留时，适用于使用闭环控制。闭环的拥塞控制建立在反馈环 路的概念上，它首先检测网络中拥塞的发生，然后将拥塞信息传递到拥塞 控制点，最后拥塞控制点根据拥塞信息进行调整，以消除拥塞。闭环的拥 塞控制可以动态适应网络的变化，但是它的一个缺陷是算法的性能受到反 馈延迟的影响。当拥塞发生点和拥塞控制点之间的延迟很大时，拥塞控制 算法的性能会严重下降。 ( 2 ) 根据拥塞控制的实施位置，可以将拥塞控制算法分为两类：链 路算法( l i n ka l g o r i t h m ) 和源算法( s o u r c ea l g o r i t h m ) 1 3 】。链路算法在 西南交通大学硕士研究生学位论文第2 页 网络设备( 如路由器和交换机) 中执行。它的主要作用是检测网络拥塞的 发生，生成拥塞反馈信息。源算法在主机和网络的边缘设备中执行。它的 主要作用是根据反馈信息调整发送速率。拥塞控制算法设计的关键问题是 如何给出反馈信息和如何对反馈信息进行响应。 在源算法中，目前使用最广泛的是t c p 协议中的拥塞控制算法，如 t c p t a h o e ，t c p r e n o 等。在链路算法方面，目前的研究主要集中在“主 动队列管理”( a c t i v eq u e u em a n a g e m e n t ，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 ) 两个方面。 ( 3 ) 从实施控制的类型上，拥塞控制可以分为基于窗口和基于速率 两种类型。t c p 采用的是典型的基于窗口的控制方式，t c p 通过调整拥 塞窗口的大小控制发送到网络中的数据量，其易于实现，且可以限制注入 网络的最大流量；基于速率的控制方式是通过对t c p 的窗口控制机制进 行建模，得到t c p 连接吞吐量与网络参数之间的解析式，用来控制源端 发送速率的大小，一般适合于多媒体数据流的传输控制，重点的性能指标 是t c p 友好性。 ( 4 ) 从推断网络状态的反馈信息的类型上，可以分为显式拥塞控制 和隐式拥塞控制。在显式控制方式中，网络使用显式信号向执行控制的端 点通告其状态( 可用带宽、缓存容量等) ；在隐式控制方式中，控制端使 用流量估计或者通过超时、重复a c k 等隐含信号来推断网络状态。 1 一论文的研究内容 随着i n t e m e t 规模的增长，互连网上的用户和应用都在快速增长，拥 塞已经成为了一个重要的问题，如果不在i n t e r n e t 中使用有效的拥塞控制 算法，拥塞崩溃的发生会严重降低网络性能。在i n t e r n e t 中使用拥塞控制 算法对i n e t e m e t 的稳定性和提高网络服务质量( q o s ) 【2 】具有十分重要的 意义。 论文主要从网络服务质量及网络资源分配公平性两个方面，对 i n t e m e t 拥塞控制相关算法进行研究。主要研究工作包括以下几个方面： 1 对i n t e r a c t 拥塞控制相关算法进行了分析和综述； 2 对几种典型的t c p 友好拥塞控制算法进行了介绍和分析，并通 西南交通大学硕士研究生学位论文第3 页 过仿真对其性能进行了评价； 3 对几种典型的主动队列管理算法进行了仿真评价； 4 提出以一种c s f q 算法的改进算法，并利用仿真对改进算法的。e 能进行了与原算法和其它几种算法进行比较和分析。 1 3 论文结构安排 论文的后续章节组织如下： 第二章对i n t c m c t 中的端到端拥塞控制机制进行了介绍，重点介绍了 t c p 拥塞控制机制； 第三章对几种典型的t c p 友好拥塞控制算法进行了介绍，在此基础 上，通过仿真对其性能进行评价； 第四章对支持端到端拥塞控制的路由器机制进行了介绍，重点对主动 队列管理( a q m ) 机制进行了研究。同时利用仿真对几种主动队列管理 算法的性能进行分析； 第五章对实现i n t c r n c t 公平带宽分配的c s f q 算法进行分析和研究， 提出了一种c s f q 算法的改进算法，并对改进算法的性能进行了仿真分 析。 第六章对论文工作进行了总结。 西南交通大学硕士研究生学位论文第4 页 第二章i n t e r n e t 拥塞控制基础 2 1 基本概念 2 1 1 拥塞和拥塞控制 当网络中存在过多的报文时，网络的性能会下降，这种现象称为拥塞 。”。拥塞是一种持续过载的网络状态，此时用户对网络资源( 包括链路带 宽、存储空间和处理器处理能力) 的需求超过了网络可提供的容量。拥塞 导致的直接结果是分组丢失率提高，端到端时延急剧增加，严重时会发生 “拥塞崩溃”现象【钔。当网络处于拥寨崩溃状态时，微小的负载增加都将 使网络的有效吞吐量( g o o d p u t ) 急剧下降。图2 1 ( a ) ( b ) ( c ) 描述了网络负 载与吞吐量、响应时间和网络性能的关系。从图2 1 可以看出，当网络负 载较轻时，吞吐量与负载之间呈线性关系，响应时间增长缓慢；到达膝点 ( k n e e ) 之后，随着负载的增加，吞吐量增加最逐渐变小，而响应时间大 幅度增加；当负载越过崖点( c l i f f ) 之后，吞吐量急剧下降。通常将k n e e 点附近称为拥塞避免区间，k n e e 和c l i f f 之间是拥塞恢复区间，而c l i f f 之 外是拥塞崩溃区间。为了最大限度地利用网络资源，网络工作在轻度拥塞 状态时应该是较为理想的，但这也增加了滑向拥塞崩溃的可能性，因此需 要一定的拥塞控制机制来加以约束和限制。 拥塞控制就是网络节点采取措施来避免拥塞的发生或者对拥塞做出 的反应【5 l 。使用图2 1 来说明，拥塞控制的目标就是使网络工作在k n e e 点附近。拥塞控制分拥塞避兔( c o n g e s t i o na v o i d a n c e ) 和拥塞控制 ( c o n g e s t i o nc o n t r 0 1 ) 两种不同的机制【6 l o 其中，拥塞控制是恢复机制 它用于将网络从拥塞状态中恢复出来；而拥塞避免为预防机制，它的目 是避免网络拥塞的发生，使网络运行在高吞吐量、低延迟的状态下。 西南交通大学硕士研究生学位论文第5 页 j 响k n e ec l i 芷 应 i ： 时 细一 间 r 负载 2 1 2 拥塞崩溃 性 能 ( c ) 圈2 1 负载与吞吐量、响应时间和性能的关系 当网络负荷增加导致网络有用工作量非正常下降时，我们有时就称之 为拥塞崩溃发生了。严格来说，拥塞崩溃的现象是网络的占有率很高但分 组不能达到信宿。这种现象第一次发生在i a t e m c t 的发展初期，即2 0 世纪 8 0 年代中期【4 】，在此之后，拥塞控制被引入了i n t e r n e t f j 。 有几种原因可以引起拥塞崩溃，如不必要的分组重传、未投递的分组 等。下面将对两种主要的拥塞崩溃进行分别介绍，并指出其可能的解决办 法。 2 1 2 1 传统豹拥塞崩溃 拥塞崩溃最初是于2 0 世纪8 0 年代被提出的【4 1 ，拥塞崩溃的产生大多 是由于t c p 连接不必要的重传一些分组，而这些分组或是正在传输过程中 西敲通大学硕士研究生学位论文第6 页 或是已到达接收方。通常将不必要的分组重传所造成的拥塞崩溃称为传统 的拥塞崩溃。如上所述，j a c o b s o n 提出的拥塞避免机制已经可以解决这 种拥塞崩溃。 2 1 2 2 未投递分组造成的拥塞崩溃 未投递分组造成的拥塞崩溃是另外一种形式的拥塞崩溃。这种拥塞崩 溃可能是今天的i n t e r n e t 所未能解决的最危险的拥塞崩溃。 未投递分组造成的拥塞崩溃【8 】是由于网络宽带浪费在传递那些在到达 最终信宿前就被丢弃的分组所造成的。这种拥塞崩溃主要是不采用端到端 拥塞控制机制的开环应用而引起的，如基于u d p 的应用。 图2 2 和图2 3 说明了未投递分组所导致的拥塞崩溃。在强2 2 中，三 个t c p 连接和一个u d p 连接竞争同一条1 5 m b p s 的拥塞链路。除了u d i ， 流的接收方的接入链路带宽为1 2 8 k b p s ，仅占共享链路带宽的9 外，所 有节点的接入链路带宽都是1 0 m b p s 。当u d p 流发送方的数据发送速率趣 过了1 2 8 k b p s 时，大部分u d p 分组将在到达信宿的链路的最终输出端口 被丢弃。图2 3 则是圈2 2 仿真的结果。图中分别显示了1 5 m b p s 的拥塞 链路上u d p 的到达速率、u d p 和t c p 以及总的有效吞吐量( g o o d p u t ， 为到达接收方的u d p 或t c p 的分组所占用的带宽) 。从图2 3 中可以看出， 随着u d p 信源发送速率的增加，t c p 的有效吞吐量急剧下降，而u d p 的有效吞吐量在其发送速率超过其接收端链路带宽之后基本保持不变。雨 总的有效吞吐量也随蓿u d p 流的发送速率增加呈线性下降。可见，未投 递的分组所造成的拥塞崩溃危害是相当大的，将导致链路的有效利用率急 剧下降。 u d p 图2 2 三个t c p 连接和一个u d p 连接竞争 同一条1 5 m b p s 链路拓扑图 西南交通大学硕士研究生学位论文第7 页 图2 3 三个t c p 连接与一个t c p 连接的仿真结果 消除未投递分组造成的拥塞崩溃只有两种方法。第一种是在网络端节 点使用有效的端到端的拥塞控制机制。第二种方法是网络保证将已经被拥 塞链路接收的分组送至信宿，即网络的端到端宽带保证。两种方法可以棚 互结合。 2 1 3 拥塞控制算法的评价方法 对于拥塞控制算法，通常可从用户和系统两个不同的角度进行评价。 通常用户所关心的性能指标主要包括端系统吞吐量、分组丢失率和传输延 迟及时延抖动等。 ( 1 ) 吞吐量：单位时间内在一个连接上传输的最大字节数。通常用 户期望其所获得的吞吐量，特别是有效吞吐蠹( g o o d p u t ) 尽可能高，同 时吞吐量标准方差接近于0 。 ( 2 ) 延迟：也称时延，描述的是分组从源端开始传输直到最后成功 传送到目的地的时间间隔。端到端的延迟包括：节点处理延迟、排队延迟、 传播延迟和传输延迟。 ( 3 ) 分组丢失率：数据传输过程中丢失的分组数与抟输的总的分组 数的比率。通常数据分组在传递过程中如果出现拥塞，将在交换机和路由 器等网络设备中进行缓存。如果拥塞持续时阀过程，网络设备的缓存空间 将耗尽，这样一些分组将被丢弃。分组丢失率通常作为反映网络拥塞状态 的一个指标。 f量蠹、日蔷暑i、5号善 西南交通大学硕士研究生学位论文第8 页 ( 4 ) 时延抖动：延迟的变化就是抖动。如果所有分组都通过相同的 路径到达接收端，则这些分组具有相同的传播延迟。如果分组大小一样， 那么传输延迟也基本相同。但是网络业务是动态变化的，不同的业务负参 情况下，网络节点的处理延迟和排队延迟具有很大差别，因此相应的分组 之间时延差别将出现很大变化。在拥塞发生时，网络的延迟的时延抖动都 会急剧增大。 由于拥塞控制算法对整个网络系统都有影响，在评价拥塞控制算法 时，更应该从整个系统的角度出发进行考虑。两个重要的系统评价指标是 资源分配的效率和分配的公平性。 ( 1 ) 资源分配的效率( e f f i c i e n c y ) 。资源分配的效率可以使用p o w e l - 函数【5 , 6 1 来评价。p o w e r 函数的定义为： p o w e r t r h o u g h p u t 9 r e s p o n s e t i m e ( 2 1 ) 在上面的式子中，一般取口= 1 。如果在评价时更偏重于吞吐量，则 取口 l ；如果在评价是更偏重于反应时间，则取盯 s s t h r e s h 时，则每收到一个a c k ，c w n d 增加1 c w n d 。 2 。2 2 3 快速重传和快速恢复 当分组发送超时时，c w n d 被置为1 ，重新进入慢启动，这会导致过大 减小发送窗1 ：i 的尺寸，降低t c p 连接的吞吐量，因此采用快速重传和快 速恢复来提高拥塞恢复的性能。快速重传就是在发送端收到3 个或3 个以 上的重复a c k 时，就认为分组已经丢失，立即启动重传，而不必等待r t o 超时，同时将s s t h r e s h 设置为当前拥塞窗口的一半。 当发送端接收到的重复a c k 超i 寸l t c p r e x m t t h r e s h ( 通常设定为3 ) 之后， 进入快速恢复阶段。在快速恢复阶段，每接收到一个重复的a c k ，将c w n d 西南交通大学硕士研究生学位论文第1 1 页 增加一个1 个分组大小。进入快速恢复阶段后，发送端可用窗口的控制规 则变为m i n ( a w n d ，c w n d + n d u p ) ，其中a w n d 为接收端的通告窗口大小，c w d ? 进入快速恢复阶段时减半，l 却为收到重复a c k 数小于c p ，巴聊n 砌，骶 之前 为0 ，之后为再收到的重复a c k 个数。当接收到新发出的分组的确认之后， 退出快速恢复。快速重传和快速恢复伪代码如下： i f ( d u p a c k s = = 3 、 s s t h r e s h _ m a x ( c w n d 2 ，2 ) c w n d = s s t h r e s h + 3 r e t r a n s m i tl o s tp a c k e t c w n d - c w n d + n d u p i f ( m i l l o w n d ，c w n d ) f l i g h ts i z e ) t r a n s m i tn c w p a c k e t ( s ) o n n o n d l l pa c k c w n d _ s s t h r e s h e n t e r c a 2 2 3t c p 协议的主要版本 2 2 _ 3 1t c p1 _ 曩h o e t a h o e 7 l 是t c p 的早期版本，包括三个最基本的拥塞控制算法：慢启 动、拥塞避免和快速重传。快速重传根据3 个重复的确认分组来判断分组 丢失，减少了藿传超时的发生。此外，t a h o e 对往返时间( r t t ) 的估算 做了相应的改进，更准确的设定超时重传的时间。 2 2 3 2t c pr e n o r c n o 1 4 , 1 5 l 在t a h o e 的基础上增加了快速恢复算法来提高拥塞恢复的效 率。快速恢复基于“管子( p i p e ) ”模型的“报文守恒”特性【”。源端每接 收到一个重复的a c k ，就认为已经有一个分组离开网络，于是将发送方的 拥塞窗口增加1 。r e n o 的快速恢复优化了单个分组数据窗口丢失的情况， 比t a h o e 的性能大有改进，但多个分组从阍一个数据窗口丢失时，仍旧存 在性能问题。 西南交通大学硕士研究生学位论文第1 2 页 2 2 3 3t c pn e w - r e n o n e w r e n o 1 6 】对r e n o 中的快速恢复算法进行了补充。它考虑到个发 送端口内多个分组丢失的情况。在快速恢复算法中，发送方收到一个不重 复的a c k 就退出快速恢复阶段。而在n e w r e n o 中，只有所有在快速快速 恢复阶段开始时出现的分组都被确认，才会退出快速恢复阶段。 2 2 3 4t c ps a c k s a c k ( 选择性重传) 【1 7 】也关注一个窗口内多个报文丢失的情况。进入 快速恢复过程与r e n o 相似，当重传分组本身被丢弃后，s a c k 用重传超时 探测丢失，再次重传后进入慢启动过程，在确认了所有出现在进入快速恢 复阶段的分组后，发送端将从快速恢复阶段退出。s a c k 在快速恢复阶段 维护了一个称为“p i p e ”的交量，用于估计出现在网络中的分组。在p i p e 小于拥塞窗口大小时，发送端发送新的或需要重传的分组，并将变l p i p e 增加1 。当发送端接收了一个带s a c k 选项的重复a c k 时，将p 扛埠变量减i 。 同时发送端利用一个特殊的数据结构( s c o r e b o a r d ) 对s a c k 确认信息进行 记录。因此，s a c k 能够很好应付一个窗口内多个分组丢失的情形。 2 2 3 5t c p v e g a s v e g a s 1 8 , 1 9 】对r e n o 进行了三项重要的技术改进。一是采用了新的重传 触发机制，即用一个重复的a c k ( 瓶非r e n o 中的三个) 来启动超时判定 规程，这样可以更及时地检测到拥塞的发生。第二，在慢启动阶段，采用 了更谨慎的方式来增加窗口大小，减少了不必要的分组丢失。第三，改进 了“拥塞避免”阶段的窗口调整算法，v e g a s 通过观测t c p 连接中的r t t 值的变化来调节拥塞窗口。如果发现r t r 变大，则认为网络发生拥塞， 相应地减小c w n d 的值；如果r t t 变小，则认为拥塞已- 经解除，并增加 c w n d ：如果r t r 不变，则不改变拥塞窗口的大小。由于t c pv e g a s 没有 采用分组的丢失来估计网络的可用带宽，而是通过改用r t t 的变化进行 判断，因此能更准确地预测网络的可用带宽，对小缓存的适应性较强，其 公平性、效率都较好。但使用t c p v e g a s 的流在带宽竞争能力方面不及未 使用t c p v e g a s 的流，从而导致网络资源共享的不公平。 西南交通大学硕士研究生学位论文第1 3 页 从以上算法中，可以总结t c p 拥寨控制的几个特点： ( 1 ) 将拥塞控制分为“慢启动”和“拥塞避免”两个主要阶段。“慢 启动”用于探测网络的带宽，这个阶段使用指数增长的方式；“拥塞避免” 试图避免拥塞的发生，这个阶段使用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 e a t i v ed e c r e a s e ) 的方式。 ( 2 ) 假设报文的丢失是由网络的拥塞引起的。t c p 把分组丢失作 为拥塞发生的指示。 ( 3 ) 从解决一个发送窗口内单个报文豹丢失到解决一个发送窗口 内多个报文的丢失。 2 2 4t c p 拥塞控制机制的改进 ( 1 ) 对慢启动过程的改进i 纠。包括： 增大拥塞窗口豹初始值。r f c2 4 1 4 中推荐将拥塞窗口的初始值 由1 m s s ( m a x i m u m s e g m e n ts i z e ) 增加到4 m s s 。 将慢启动过程分为多段，使从“慢启动”到“拥塞避免”的过渡更 为平滑。在文献f 2 3 】中，建议将“慢启动”过程分为多个阶段，逐步减小 窗口的增长的速度。 在多个连接或主机之间共享网络状态信息，使初始域值的选择根据 网络状况决定。这方面的研究包括s p a n d e 2 4 j 和“t c pf a s t - s t a r t ” 2 5 1 , ( 2 ) 基于速率的控制策略f 2 6 挪l 。在t c p 中使用的窗口控制策略本身 机制存在一定的缺陷，例如：容易导致突发报文的出现；速率受到窗口大 小的限制；一个窗口内多个报文的丢失不容易恢复等。针对这些问题， 些研究者提出了r a t e - b a s e dp a c i n g ( r b p ) 的概念，将基于窗口的控制和 基于速率的控制结合起来。r b p 生要的问题是【2 8 】：在拥塞发生时，会导 致多个连接同时丢失报文，从而出现“全局同步”的现象，严重降低了网 络的吞吐量。另外r b p 机制在实现中需要大量高精度的时钟，消耗的资 源过多。 ( 3 ) a c k 过滤( a c k f i l t e r ) 。该研究的主要目的是保持t c p 的“自 时钟”( s e i f - c l o c k i n g ) 机制【7 l 。t c p 的“自时钟”机制有利于减轻突发报 文对网络的冲击，而“a c k 压缩”( a c kc o m p r e s s i o n ) b 州破坏了“自时 钟”机制。文献【3 0 】建议在网络中增加特殊的设备( p e r f o r m a n c ee n h a n c e 、 西南交通大学硕士研究生学位论文 7 第1 4 页 p r o x y ) 来确保a c k 报文之间的间隔。 ( 4 ) 减少不必要的“重传时钟”超时和“快速重传”。在“重传时钟” 超时和“快速重传”发生时，t c p 都会减少拥塞窗口，从而降低传输的速 率。r t t 测量的准确性和“乱序报文”的出现都会影响t c p 作出正确的 判断。文献【3 1 】中提出的e i f e l 算法通过在应答报文中增加特殊的信息来解 决这个问题。 ( 5 ) “显式拥寨通知”( 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 e c n ) 1 3 i 。 当拥塞发生时，网关通过在报文中设定标志位通知端系统，而不等待发送 方的时钟超时。这改变了原来t c p 依赖报文丢失来判断拥塞发生的方法。 在无线的网络环境中，e c n 的使用有利于将报文损坏( p a c k e tc o r r u p t i o n ) 和报文丢失区分开来。 ( 6 ) “t c p 友好”( t c p f r i e n d l y ) 的拥塞控制【3 2 , 3 3 1 。在一些实时多媒 体的应用中，要求传输的速率不变化太激烈，这是t c p 所不能做到的。 但是如果不使用拥塞控制，这些应用的传输会对i n t e r a c t 的稳定性产生很 大的危害，于是针对这个需求提出了“t c p 友好”的拥塞控制。在文献【1 2 1 将“t c p 友好”定义为：常时间的吞吐量不超过相同条件下t c p 连接的 吞吐量。 西南交通大学硕士研究生学位论文第1 5 页 第三章t c p 友好拥塞控制算法及仿真评价 随着i n t c m e t 的迅速发展，它所支持的业务类型也越来丰富。目前， i n t e m e t 上的多媒体应用层出不重，多媒体信息的数量与臼俱增，构成了 i n t e m e t 的流量相当大的一部分。i n t e m e t 已逐步由单一的数据传送网络向 数据、语音、图像等多媒体信息的综合传输网络演化。如何支持在i n t e r n e t 高效传输多媒体应用流成为了当前网络研究的个热点问题。 3 1t c p 友好算法的提出背景 由于实时多媒体流的时延敏感性、半可靠性和基于速率的特征，它们 需要等时处理和端到端的服务质量( q o s ) 。然而，当前的i n t e m e t 无法提 供端到端时延的上限和可用带宽的下限。因此，实时应用服务质量难以得 到保证。 t c p 是i n t e r a c t 上的最主要传输协议，它所采用的拥塞控制机制是 i n t e m e t 保持健壮性( r o b u s t ) 的主要原因。t c p 在探测网络可用带宽、 拥塞避免和拥塞恢复等方面起到了非常重要的作用。但t c p 在探测空闲 带宽和响应拥塞的过程中，其信源的速率会出现大幅度的变化。这种突然 的、经常的速率变动会造成多媒体应用的质量急剧下降。因此，t c p 不适 合于实时多媒体应用流的传输。 由于t c p 不能为实时多媒体流传输提供有效支持，目前i n t e r n e t 上大 量多媒体应用都采用u d p 进行传输。但u d p 对拥塞是无响应的，即在拥 塞发生时，它不会降低其发送速率。这样，会引发两个方面的问题：其一， 由于u d p 不对拥塞作出响应，因此，在拥塞发生时，它将导致拥塞状况 的进一步恶化，甚至引发拥塞崩溃；其二，在拥塞发生时，u d p 流占用 的资源将远远高于t c p 流等响应流所占用的资源，造成了严重的不公平 性。为了防止大量的非响应流涌入网络，导致网络崩溃，在i n t e r n e t 上进 行多媒体应用流传输时必须采取一定的拥塞控制机制。 针对i n t e m e t 上支持实时多媒体流传输所存在的上述问题，研究人员 提出了t c p 友好拥塞控制算法。t c p 友好( t c p f f i d n d l y ) 的定义为【j 纠 西南交通大学硕士研究生学位论文第1 6 页 “非t c p 流在长期范围内吞吐量不超过相同情况下的t c p 流的吞吐量”。 与t c p 相比，各种t c p 友好拥塞控制算法在速率调节和对拥塞进行响应 时具有更好的平滑性，因此，更适合与多媒体流的传输。 3 2 几种典型的t c p 友好拥塞控制算法 t c p 友好拥塞控制算法在近几年来得到了大量的研究，“t c p 友好性” 概念的引入给拥塞控制的研究注入了新的活力，打破了拥塞控制由t c p 拥塞控制机制垄断的格局【3 6 】。目前，已经提出了不少新的机制和算法，其 中包括t c p 友好速率控制( t c p - f r i e n d l yr a t ec o n t r 0 1 ) 和其它基于方 程的拥塞控制【3 8 j 、二项式拥塞控制【3 9 】、具有不同越m d 参数的拥塞控制 算法【柏l 以及接收端t c p 仿真( t c pe m u l a t i o n a tr e c e i v e r ，t e a r ) 等。 这些拥塞控制机制在对分组丢失进行响应时，不像t c p 流量控制那样， 将拥塞窗口( 或传输速率减半) ，而是采用了较为缓慢的速率调节算法。 3 2 1 二项式拥塞控制算法 文献【3 9 】提出的二项式拥塞控制算法是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 ，p 四个 参数来描述此类算法。在二项式算法中，在没有拥塞发生时，增大拥塞窗 口；一旦探测到有拥塞发生，则减小拥塞窗口。窗口增加和减小符合公式 ( 3 1 ) ： i ：彬+ _ 彬+ 石哥；a 0 d ：矸+ _ 形一声( 彬) 。；o 卢t l( 3 - 1 ) 其中r 代表r 1 广r ，职为t 时刻拥塞窗口大小。口，p 为常数。文献【6 7 】 通过对二项式算法的发送速率分析，指出t c p 友好的二项式算法的参数 a ，p 应满足条件：a l f l = 3 2 。通常取口= 1 ，胃= 0 6 6 。 从上述公式可看出，二项式控制算法是所有线性控制算法的超集。通 过选取不同的k 和f 的值，可获得所有的线性控制算法。例如，令k = 0 ，f = 1 ，可获得a i m d 算法，而k = 1 ，f = 1 ，可获得m i m d ( m u l t i p l i c a t i x ，e i 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 ) 算法。 西南交通大学硕士研究生