（计算机应用技术专业论文）基于red算法的拥塞控制机制研究.pdf

摘要 摘要 随着计算机网络的持续快速发展，各种网络应用需求不断涌现，造成网 络数据流量激增。传统的网络服务机制“尽力而为 的服务模型已经不能 够满足网络发展的需要，网络拥塞问题变得越来越严重，网络拥塞控制也 一直是网络研究的关键热点问题之一。 目前，t c p i p 网络拥塞控制的策略主要包括两类：基于t c p 的拥塞 控制和基于i p 的拥塞控制。本文研究了t c p 的拥塞控制过程，包括慢启 动、拥塞避免、快速恢复和快速重传，并较为详细地研究了t c pt a h o e 。 r e n o ，s a c k ，v e g a s 等拥塞控制算法。在i p 拥塞控制部分，主要研究了l p 拥塞控制的基本思路，i p 拥塞控制中的队列调度和队列管理，重点研究了 具有代表性的队列管理算法r e d 的基本原理、特点，并对当前主要的r e d 改进算法等做了分析比较。 随后，重点针对原始r e d 算法的稳定性不足、平均队列长度不能完 全反映网络拥塞状况等问题，研究出一种改进算法，使它能更有效的对网 络拥塞进行控制。并通过使用n s 2 仿真工具对改进算法的性能进行分析 验证，最终证明了改进算法的性能较原始算法有了很大提高。 最后，本文还简要介绍了仿真实验所采用的工具n s 2 的原理及进行 仿真的一般步骤。 关键词：t c p 拥塞控制，i p 拥塞控制，随机早期检测，n s 2 a b s t r a c t a b s tr a c t w i t ht h er a p i dd e v e l o p m e n to fi n t e r n e t v a r i o u sa p p l i c a t i o n sb a s e do ni n t e r n e th a v e e m e r g e da n dt h ed a t af l o w so ni n t e m e ta r ei n c r e a s e da b r u p t l y t h et r a d i t i o n a l “b e s t - e f r o r t s e r v i c em o d e ic a n n o ts a t i s f yt h en e e do fn e t w o r k sd e v e l o p m e n t n e t w o r k c o n g e s t i o nh a sb e c o m eas e r i o u sp r o b l e ma n dc o n g e s t i o nc o n t r o lh a sb e e nt h ef o c u so f a t t e n t i o ni nt h ef i e l do fn e t w o r k c u r r e n t l y , t h e r ea r et w ok i n d so ft h es c h e m e so fn e t w o r k sc o n g e s t i o nc o n t r 0 1 t h e f i r s ti st c pc o n g e s t i o nc o n t r o ls t r a t e g i e s 。t h es e c o n di si pc 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 i sp a p e ew eh a v ed e e p l yr e s e a r c h e dt h et w ot y p e so fc o n g e s t i o nc o n t r o ls t r a t e g y w e s t u d yt c pc o n g e s t i o nc o n t r o lp r o c e s si n c l u d i n gs l o ws t a r t 、c o n g e s t i o na v o i d a n c e 、f a s t r e c o v e r ya n df a s tr e t r a n s m i t ，a n dt h e nw ei n t r o d u c et h ec o n g e s t i o nc o n t r o ls c h e m e so f t c pt a h o e ，r e n o ，s a c ka n dv e g a s w ei n t r o d u c et h ef u n d a m e n t a lo fi pc o n g e s t i o n c o n t r o ls t r a t e g i e s 、q u e u em a n a g e m e n ta n dq u e u es c h e d u l i n g ，a n dt h e nw es t u d yt h e f u n d a m e n t a lo fr e d ，i n t r o d u c es o m ei m p o r t a n ta m e l i o r a t i o nr e d a l g o r i t h m s t h i sp a p e r a n a l y s e st h ew e a k n e s so fr e da n di m p r o v e st h ea l g o r i t h m t h e nt h ep e r f o r m a n c e so f r e da n dt h ei m p r o v e dr e da r ec o m p a r e db ym a n ys i m u l a t i o ne x p e r i m e n t s t h er e s u l t s i n d i c a t et h a tt h ei m p r o v e dr e da l g o r i t h mc a na c h i e v eb e t t e rn e t w o r kp e r f o r m a n c e st h a n r e d a l g o r i t h m i na d d i t i o n t h i st h e s i sa l s oi n t r o d u c e ss i m u l a t i o nt o o in sw h i c hi su s e di na l it h e s i m u l a t i o ne x p e r i m e n t so ft h i sp a p er i n c l u d i n gt h ep r i n c i p l e so fn sa n dh o wt op e r f o r ma n e ws i m u l a t i o ng e n e r a l ly k e y w o r d s ：t c pc o n g e s t i o nc o n t r o l ，i pc o n g e s t i o nc o n t r o l ，r e d ，n s 2 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。本论文除了文中特另t l d i ：l 以标注和致谢的内容外，不包含其他人或其他机 构已经发表或撰写过的研究成果，也不包含为获得南京信息工程大学或其他教育 机构的学位或证书而使用过的材料。其他同志对本研究所做的贡献均已在论文中 作了声明并表示谢意。 学位论文作者签名：扬丝 签字日期：丝! ：篁：型一一 关于论文使用授权的说明 南京信息工程大学、国家图书馆、中国学术期刊( 光盘版) 杂志社、中国科 学技术信息研究所的中国学位论文全文数据库有权保留本人所送交学位论文 的复印件和电子文档，可以采用影印、缩印或其他复制手段保存论文，并通过网 络向社会提供信息服务。本人电子文档的内容和纸质论文的内容相一致。除在保 密期内的保密论文外，允许论文被查阅和借阅，可以公布( 包括刊登) 论文的全 部或部分内容。论文的公布( 包括刊登) 授权南京信息工程大学研究生部办理。 耐么丌 口保密( 一年月) 学位论文作者签名：物缝 指删币虢奶施左 ( 保密的学位论文在解密后应遵守此协议) 签字日期：趔之：受型 签字日期：o 矽矽8 - o 易 第一章绪论 1 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 的流量急剧 增长。与此同时，越来越严重的网络拥塞状况也不断显现，该问题已引起人们密切 的关注，拥塞控制技术已成为网络领域的核心技术。 从早期的综合服务数字网( i n t e g r a t e ds e r v i c ed i g i t a ln e t w o r k ，i s d n ) 蛩j 集成服务 ( i n t e g r a t e ds e r v i c e 。i n t s e r v ) 资源预留( r e s o u r c er e s e r v a t i o np r o t o c o l ，r s v p ) ，再到后 来的区分服务( d i f f e r e n t i a t e ds e r v i c e ，d i f f s e r v ) ，无论最终采取哪种网络体系结构，其 技术的核心都需要在恰当的层次和粒度上对流量进行必要的管理，其中包括接纳控 制、流量成形、队列管理、调度和拥塞控制等诸多方面，但最基本和核心的依旧是 拥塞控制，因为很难想象一个时常有可能出现严重拥塞且无法及时加以恢复的网络 能够实现良好的服务质量( q u a l i t yo f s e r v i c e ，q o s ) 保证。实现拥塞控制应该是其他 服务质量保证机制正常工作的必要前提r 。 1 2 网络的拥塞问题 1 2 1 拥塞的含义 所谓拥塞，就是指当通信子网中存在过多的数据分组时，由于存储转发节点的 资源有限而造成的网络传输性能随之下降的现象【n j 。拥塞是一种持续过载的网络状 态，就i n t e r n e t 的体系结构而言，拥塞的发生是其固有的属性，而其导致的直接结果 是分组丢失率提高、端到端时延加大，甚至有可能使整个系统发生崩溃。拥塞崩溃 对i n t e m e t 的威胁可以追溯到其早期的发展中，1 9 8 4 年，n a g l e 3 报告了由于t o p 连 接中不必要的重传所诱发的拥塞崩溃，1 9 8 6 - 1 9 8 7 年间这种现象曾经多次发生，严重 时一度使l b l 到u cb e r k e l e y 之间的数据吞吐量从3 2 k b p s 跌落到了4 0 b p s 【4 j 。对于 拥塞现象，可以用图1 1 来描述，该图刻画了负载与吞吐率之间的关系：当负载较 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 之外是拥塞崩 溃区间。 吞 吐 且 里 膝点崖点 负载 图1 1 负载与吞吐量之间的关系图 1 2 2 拥塞产生的原因 拥塞发生的根本原因是资源的相对不足。这些资源包括链路带宽、可分配的处 理器时间、缓冲区、内存等。考虑某个具体的流，如果在某个时间内对所到达的流 量控制不力，使之超出了可分配的网络资源，那么将引发网络拥塞。拥塞总是发生 在网络中资源相对短缺的位置。拥塞发生位置的不均衡反映了i n t e m e t 的不均衡性， 如图1 2 所示【5 】的两种情况。上图反映的是资源分布的不均衡，当以1 m b i t s 的速率 从s 向d 发送数据时，在网关r 会发生拥塞。下图则是反映了流量分布的不均衡， 虽然图中带宽分布是均衡的，但是，当a 和b 都以1 m b i t s 的速率向c 发送速率时， 在网关r 也会发生拥塞。 2 第一章绪论 1m b i t s10 0 k b i t s 图1 2 互联网的不均衡性 拥塞是网络中的一种中间状态。当用户所期望占有的网络资源与对应的网络资 源接近，甚至超过网络所能提供的资源时，则出现网络拥塞，产生拥塞的主要原因 可小结如下。 ( 1 ) 存储空间不足； ( 2 ) 带宽容量不足： ( 3 ) c p u 处理速度慢； ( 4 ) 不合理的网络拓扑结构及路由选择。 1 3 拥塞控制策略的研究现状与发展 为了最大限度地利用资源，网络工作在轻度拥塞状态时应该是较为理想的，但 这也增加了滑向拥塞崩溃的可能性，因此需要一定的拥塞控制机制来加以约束和限 制。拥塞控制的目的是在有限网络资源的情况下，通过通信量的约束与调配减少数 据丢失，提高网络吞吐量，充分利用已有网络资源。 从控制理论的角度，拥塞控制可以分为开环控制和闭环控制两大类。当流量特 征可以准确规定、性能要求可以事先获得时，适于使用开环控制；当流量特征不能 准确描述或者当系统不提供资源预留时，适于使用闭环控制。i n t e m e t 中主要采用闭 环控制方式。根据算法的实现位置，可以将拥塞控制算法分为两大类：链路算法( l i n k a l g o r i t h m ) 和源算法( s o u r c e a l g o r i t h m ) 6 3 。链路算法在网络设备( 如路由器和交换机) 3 第一章绪论 中使用，链路算法主要有传统的“弃尾算法”( d r o p t a i l ) 和主动队列管理( a c t i v eq u e u e m a n a g e m e n t ) a q m 算法。源算法在主机和网络边缘设备中使用，在拥塞控制的源算 法方面，大量的工作集中在对t c p 协议的研究上。链路算法的研究集中在队列管理 与队列调度方面，其中主动管理技术成为研究热点。由于i n t e r n e t 上9 5 的数据流 使用的是t c p i p 协浏7 】，因此t c p i p 拥塞控制受到了广泛的关注。 t 3 1t c p 拥塞控制 t c p 拥塞控制是一种端到端的控制机制，通过改变参数来实现。早期t c p 的实 现只使用了一些简单的机制，并没有对拥塞进行什么控制。直到1 9 8 6 年，拥塞所引 起的网络崩溃发生后，j a c o b s o n 等人开始对此进行研究，并在t c p 4 中增加了拥塞 控制算法( a pt c pt a h o e ) ，提出了著名的“慢启动”( s l o ws t a r t ) 、“拥塞避免” ( c o n g e s t i o na v o i d a n c e ) 算法、“快速重传”( f a s tr e t r a n s m i t ) 算法，随后t c p 版本增加 了“快速恢复”( f a s tr e c o v e r y ) 算法，避免了在网络拥塞尚不严重时采用“慢启动” 机制反而给网络带来大幅减小发送窗口的现象。上述算法是当前网络中主要采用的 端系统拥塞控制机制，当网络出现拥塞，t c p 连接通过丢失分组来发现拥塞，调整 发送窗口的大小来降低发送流量，t c p 拥塞机制在网络中的执行有效地避免了拥塞 崩溃现象的发生。从年代至今，许多学者进行了更深入和细致的研究，不断完善 和改进t c p 拥塞控制存在的缺陷，相继提出5 个版本的t c p 拥塞控制算法：t a h o e 4 、 r e n o 8 、n e wr e n o 9 、s a c k 1 0 、v e g a s 1 1 。 1 3 2i p 拥塞控制 在端系统的拥塞控制机制中，数据发送和接收端对网络的拥塞程度并无掌握， 因此仅仅依赖源端的拥塞控制很难为网络用户提供良好的q o s 保证。而事实上网络 传输中的大部分丢包事件是由于路由器节点的缓冲区溢出造成的，只有路由器才对 网络的拥塞程度有最直接的了解。所以要提高网络服务质量，减少拥塞发生，网络 中间节点都必须参与资源的控制工作。所以应该在路由器处引入拥塞控制机制，作 为对端系统拥塞控制机制的补充并与之协作。近几年关于i p 层拥塞控制的研究逐渐 增多，形成了一个新的研究热点f l z 】目前，f p 拥塞控制的处理方法主要有：传统的路 4 第一章绪论 由器采用先来先服务( f i f o ) 的调度算法：随机早期检测算法 1 3 ( r a n d o me a r l y d e t e c t i o n ，r e d ) ：显示拥塞指示算法 1 4 - 1 6 ( 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 ) ；公平 排队算法( f a i rq u e u i n g ，f q ) ：加权公平排队算法( w e i g h t e df a i rq u e u i n g ，w f q ) 和随 机指数标记算法( r a n d o me x p o n e n t i a lm a r k i n g ) 。这些算法的重点是设定出对在路由 器中排队等待处理的数据队列的处理策略和数据分组的丢弃标准，其目的是使拥塞 可以避免或快速解除，同时保证对用户的服务质量和公平性。 1 4 论文的目标与组织安排 1 4 1 论文的内容与目标 本文主要从t c p 拥塞控制和i p 拥塞控制两方面对网络拥塞控制机制进行研究， 在分析了t c p 拥塞机制中的慢启动、拥塞避免、快速重传和快速恢复之后，着重研 究的是l p 拥塞控制，重点研究主动队列管理( a q m ) 策略，在分析和研究现有的a q m 算法原理基础上，重点分析随机早期检测算法( r e d ) 并且提出了一种改进的r e d 算 法，使它更有效的对网络拥塞进行控制。并且在网络模拟器( n e t w o r ks i m u l a t o r ) 5 b 进 行了仿真实验、性能分析，证明了算法的有效性。 1 4 2 论文章节组织安排 本章简要介绍了论文研究的背景，从当今网络发展的角度提出了拥塞控制的现 状和造成网络拥塞的原因，引示出解决网络拥塞的必要性和迫切性。 第二章对t c p 拥塞控制进行综述，介绍了基于端节点的- p 拥塞控制机制，陈 述了t c p 拥塞相关的基本概念，对t c p 拥塞控制的几个不同算法进行阐述说明。 第三章重点介绍了i p 拥塞控制的基本思路，对队列调度和队列管理机制进行了 说明，并就当前比较典型的几种主动队列管理算法的设计原理和特点进行了比较。 其中重点介绍了具有代表性的队列管理算法r e d ，以及当前主要的r e d 改进算法。 第四章针对r e d 算法的稳定性不足、平均队列长度不能完全反映网络拥塞状况 等问题，介绍一种改进r e d 算法，对改进算法的主要思想进行了详细说明，并利用 网络仿真软件n s 2 对改进算法前后做了详细的对比分析。证明了算法的有效性。 5 第一章绪论 第五章介绍了本论文中所使用的仿真软件网络模拟器( n e t w o r ks i m u l a t o r ) ，着重 介绍了n s 的原理，安装及进行仿真的步骤。网络仿真工具的学习是进行网络研究 的必要条件，为研究提供了实验和分析的便利。 第六章对全文进行总结，并对拥塞控制机制的前景和发展方向进行展望。 6 第二章基于t c p 的拥塞控制 第二章基于t c p 的拥塞控制 t c p 是目前i n t e m e t 上应用广泛的传输层协议，实施拥塞控制是t c p 的两个主 要任务之一，由于i p 层在发生拥塞时不向端系统提供任何显式的反馈信息，因而 t c p 拥塞控制采用的是基于窗口的端到端的闭环控制方式。t c p 协议中使用的拥塞 控制算法己成为保证i n t e r n e t 正常运行的重要因素。深入研究t c p 的拥塞控制具有 重要意义。 2 1t c p 拥塞控制策略 t c p 拥塞控制策略主要涉及慢启动( 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 ) 、快速恢复( f a s tr e c o v e r y ) 。 2 1 1 慢启动( s l o ws t a r t ) 窗口管理是t c p 流量控制的关键，t c p 流量控制的多个版本的焦点都集中在窗 口管理上。t c p 使用的发送窗口越大，t c p 源端在必须等待一个确认之前可以发生 的报文段就越多。在正常情况下，t c p 的自同步特性会为t c p 确定适当的速率。然 而，当一个连接刚刚初始化的时候，不存在同步机制使其稳定工作在适当的速率。 可以采取的一种策略是让t c p 源端从某个相对较大的窗口开始发送，希望在此 过程中能快速逼近网络所能支持的窗口大小。但是这样做所存在的危险就是，因为 发送方在从超时上认识到流量出现过量之前就可能造成互联网的流量泛滥。因此， 保守的策略是逐渐增加窗口，直到同步机制起作用。 j a c o b s o n 设计了一种称为慢启动窗口调节策略，t c p 使用了一个拥塞窗口 ( c w n d ) ，该窗口以报文段而非字节来计算大小。在任意时刻，t c p 源端发送报文的 速率受限于下列关系式嘲： m i n c w n d ，a w n d ( 式2 1 ) 其中，c w n d 是拥塞窗口，单位为报文段，是t c p 在启动阶段或在拥塞时为减少流 量而使用的窗口，由源端确定它的大小；a w n d 为接收端宣告允许的窗口，单位是报 文段。一条新建连接c w n d 被初始化为1 ，也就是说t c p 源只被允许发送1 个报文 7 第二章基于t c p 的拥塞控制 段，等待确认后，再传输第二个报文段。每次收到一个确认，c w n d 的值就被加1 ， 一直加到某个最大值为止。借助慢启动机制，t c p 源端可以有效地探测网络负载状 态，确保不会盲目地向已经出现拥塞的网络注入过量业掣1 7 】。 慢启动其实并不慢，因为c w n d 实际上是以指数规律增长的，当第一个a c k 到 达时，t c p 将c w n d 增加到2 ，允许发送两个报文段。当这两个报文段被确认之后， t c p 自然可以发送4 个报文段，以此类推。图2 1 示意了慢启动的过程。 c w n d = l c w n d = 2 c w n d = 3 c w n d = 4 c w n d = 5 c w n d = 6 c w n d = 7 c w n d = 8 c w n d = 9 c w n d = 1 0 c w n d = 1 1 c w n d = 1 2 c w n d = 1 3 c w n d = 1 4 c w n d = 1 5 c w n d = 1 6 信源信宿 图2 1 慢启动期间传送的分组 慢 启 动 实际上，慢启动机制探测互联网，以确保它不会把太多报文段发送进一个已经 拥塞的环境。随着确认的到达，t c p 就可以扩大其拥塞窗口，直到流量最终由到来 的确认a c k 而非c w n d 所控制。慢启动的运作在两种情况下发生，第一种情况发生 在网络刚开始连接的时候，源端不知道自己在给定时间内可以被允许发送多少分组， 此时启用慢启动机制；第二种情况发生在连接无效而等待超时的时候。当一个分组 丢失，源最终到达某一点，在此点上它已经发送通知窗口允许的最多的分组，但由 于它等待着一个不会到达的确认信息，所以它处于阻塞状态。最终导致超时，但在 这段时间中并没有传送分组，所以源收不到确认信号去传送。源应收到一个要求重 8 第二章基于t c p 的拥塞控制 新打开通知窗口的a c k ，然后用慢启动方法重新启动数据流，而非将整个窗口值的 数据一下都送到传输链路上。 2 1 2 拥塞避免( c o n g e s t i o na v o i d a n c e ) 慢启动算法在初始化连接时工作的很有效，它使得t c p 发送方可以快速地为连 接确定合理的窗口大小。但是，当主机开始发送数据时，如果立即将较大的发送窗 口中的全部数据字节都注入到网络，那么由于这时还不清楚网络的状况，因而就有 可能引起网络饱和甚至拥塞。 j a c o b s o n 指出“网络进入饱和状态很容易，但让网络从饱和状态中恢复却很难”。 也就是说，一旦拥塞发生了，要将拥塞清除掉可能需要更长的时间。而慢启动中c w n d 的指数增加的太激进，它可能会加重拥塞程度。这就说明，我们需要提出一种更加 保守的、合理的方法来控制源端数据的发送。j a c o b s o n 提出开始使用慢启动然后采 用拥塞避免机制，改变c w n d 的调节策略，让c w n d 线性增长，这一过程就是拥塞避 免阶段。具体规则如下。 一旦探测到拥塞超时： ( 1 ) 将慢启动阈值( s s t h r e s h ) 设为当前拥塞窗口的一半，即s s t h r e s h = c w n d 2 。 ( 2 ) 设置c w n d = l 并执行慢启动过程，直到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 时，则大约每一个往返时间对c w n d 加1 。 虽然拥塞避免和慢启动是两个具有不同目标的独立算法，但在r e n o t c p 中，慢 启动和拥塞避免算法是一起实现的【1 8 1 ，算法描述如下： 初始化：c w n d = l s s t h r e s h = 6 5 5 3 5b y t e s w i n = m i n ( c w n d ，a w n d ) 当新的a c k 确认到达时， f o re v e r ya r d v e dp a c k e t s i fc w n d s s t h t r s h 的时候，发送端从慢启动进入拥塞避免阶段，其间每个r t t 1 4 第二章基于t c p 的拥塞控制 中c w n d 增加大约1 ，当发生重传超时的时候，发送端重新进入慢启动阶段，并且将 s s t h r e s h 设置为c w n d 2 。 ( 3 ) 快速重传 在t a h o e 中，源端在收到3 个或3 个以上重复a c k 时，就断定分组已经被丢失， 并重传分组，同时将s s t h r e s h 设置为当前c w n d 的一半。 2 3 2r e n o 1 9 9 0 年，j a c o b s o n 在t a h o e 的基础上提出了改进版本r e n o 2 2 - 2 4 。r e n o 在t a h o e 的基础上增加了“快速恢复”算法，在快速恢复阶段，同一时刻在网络中传输的数 据包数量是恒定的。如果发送方收到一个重复的a c k ，则认为己经有了一个数据包 离开了网络，于是将拥塞窗口增加1 。该算法避免了网络拥塞不够严重时采用“慢 启动”算法而造成过大的减小发送窗口尺寸的问题，从而避免了快速重传之后通道 为空的现象。t c pr e n o 是当前i n t e m e t 上应用最广泛的t c p 。 虽然目前互联网上的t c p 主要是r e n o 版本，但是r e n o 也有其自身的性能瓶颈。 首先，源端在检测到拥塞后，要重传从分组丢失到检测到丢失时发送的全部分组， 而这中间有些分组被正确地传到接收端，并不必重传。另外，在大多数t c p 实现中， r t o 计数器的值被认为是r 1 r 的均值和方差的估计值的函数。r t t 的测量从理论上 说比较简单，只是分组从发出到确认a c k 返回源端的时间。但由于t c p 使用的是 用一个a c k 确认所有己收到数据的“累积”确认方式，所以实际中r 丌的估计往 往很复杂。 2 3 3s a c k 当一个窗口丢失多个数据包时，t c p 的性能可能会变得很差。根据累积确认 得到有限信息，t c p 源端在每个往返时间内仅能推测一个包的丢失。不排除会产生 有些源端可能选择了提前重传包，但这种重传的包却已经成功地到达了接收端的情 况。基于此，m m a t h i s 等人在1 9 9 5 年提出了s a c k 算法【z 5 l ，该算法在连接创建阶 段，源端和目的端进行“协商”，以确定本次连接是否可用s a c k 选项。如果目的端 同意，那么在随后的数据传输中，若目的端缓存队列中出现了序列号不连续的数据， 1 5 第二章基于t c p 的拥塞控制 就向源端发送承载有s a c k 选项的重复a c k 。这样，源端得以知道哪些数据已正确 接收或正在接收缓冲区中排队，从而有选择地重传确实丢失的数据包，实现在一个 r 1 _ r 内选择重传多个丢失的数据包，提高了t c p 的性能，它是目前公认的最好的 a c k 反馈机制之一。 不过，需要指出的是，也有许多研究者对s a c k 的安全性和性能表现提出质疑 嗍。 2 3 4v e g a s t c p v e g a s 2 7 是基于测量的t c p 技术，它于1 9 9 4 年由l s b r a k m o 等人提出。 传统的t c p 拥塞机制只有在检测到数据报丢失的时候，才会启动拥塞避免算法，这 实际上是在网络已经存在拥塞的情况下采取的补救措施，而v e g a s 算法采用了一种 独特的拥塞避免机制，它通过3 种与众不同的技术来提高吞吐率，降低分组丢弃率， 分别为新的重传机制、新的拥塞避免机制和扩展的“慢启动”机制。t c p v e g a s 使用 排队时延作为拥塞度量，借助比较预期传输率和实际传输率，以决定是否增加或者 减少拥塞窗口的值。由于v e g a s 是基于回路响应延时阳- r 估计的，它比基于丢包探 测的r e n o 拥塞控制机制性能优越。v e g a s 算法克服了r e n o 算法的几个缺点，比r e n o 算法提高3 7 一7 1 的吞吐量 2 s - 3 0 。 2 3 5t c p 拥塞算法的比较 在上面几个小节中，论文对t c p 拥塞算法的几种目前比较流行的算法进行了简 要的介绍，下面，就这几种涉及到的算法，进行一个大致的比较。 1 6 第二章基于t c p 的拥塞控制 算法优势劣势 t c p 拥塞控制的基础，可以有效避免机制较为简单，未引入快速恢复机 t a h o e拥塞崩溃制，轻度拥塞时，窗口下降过大，未 能有效利用网络，降低网络的吞吐量 增加了快速恢复机制，可以有效提高丢包一旦被检测到，将重传丢失事件 r e n o网络利用率，提高吞吐量发生时刻到检测到丢失事件这一时 间段里的所有报文，浪费带宽 s a c k选择性重传丢失的数据，避免了带宽实现机制较为复杂 的浪费 发送端主动控制发送速率，使用排队 v e g a s时延作为拥塞度量，以决定是否改变与其他t c p 拥塞算法并存时性能将 拥塞窗口的值。能较好的提高网络吞急速下降 吐量，减少丢包率 2 4 本章小结 表2 1 几种t c p 拥塞算法的比较 本章主要介绍了t c p 拥塞控制的基本机制，对其中的部分重要机制进行了仿真 实验。随后，对t c p 拥塞控制的几种不同的算法t a h o e 、r e n o 、s a c k 、v e g a s 进行 了简要的介绍，并对这些常见的拥塞控制算法进行了对比。本章将与下面的第三章相 结合，为从总体上掌握网络拥塞控制机制作铺垫。 1 7 第三章基于i p 的拥塞控制 第三章基于ip 的拥塞控制 i n t e r n e t 由众多异构的自治域通过耦合的方式组成，具有分散特性，对于其资源 的管理和利用，考虑到业务需要，应该从端到端原则出发。但是，端到端的拥塞控 制绝大多数功能都是在主机端实现的，对网络中间节点所能发挥的作用考虑较少。 随着应用要求的日益丰富和技术的不断发展，要想完全依赖实现在终端系统上的策 略与算法是很难满足诸如q o s 这样复杂的应用要求的。于是，开始将部分研究注意 力转向网络中的路由器等中间节点设备，期望通过增强它们的功能来实现主机端无 法达到的技术目标。 3 1i p 拥塞控制简述 路由器等网络中间节点设备是拥塞的发生点，因此在中间设备上进行拥塞控制 是十分必须且很有意义的。目前，路由器这类中间设备主要依据以下方法来控制拥 塞： ( 1 ) 拥塞信号。当发生或者即将发生拥塞时，路由器可以给网络中的源发送节点发送 拥塞信号； ( 2 ) 缓存管理。路由器有很多队列，用于接受和存放突发的大量报文。好的路由器缓 存管理算法可以为端到端的拥塞控制的实现提供很好的激励； ( 3 ) 调度。调度决定了当多个连接共享一个路由器时，应该先发送哪个报文。通过在 路由器的端口上维护一个或多个队列，以处理多个数据包同时向同一端口转发以及 端口q o s 问题。对队列进行的管理直接影响路由器的性能、拥塞管理能力和q o s 能 力。 路由器中有两类与拥塞控制相关的路由算法p 1 】：队列调度和队列管理。 3 2 队列调度 3 2 1 队列调度原理 调度是系统资源管理的核心机制之一，是解决多个业务共享资源问题的有效手 1 8 第三章基于l p 的拥塞控制 段。队列调度规则决定数据分组接受服务的次序，实现对链路带宽的管理，使得所 有输入业务流能够按照预定的方式共享输出链路带宽。它影响的主要性能参数包括 带宽分配、时延和时延抖动等，是实现网络服务质量控制的核心技术。 队列调度算法运行在网络节点中发生冲突需排队等待调度之处，按照一定的服 务规则对交换节点的不同输入业务流分别进行调度和服务，使得所有的输入业务按 预定方式共享交换节点的输出链路带宽。如图3 1 所示。 ，- i 队列1 、，_ ， ， 输入业务 输出业务 ， l ，天 ， ， ， ， ， 交换节点输出模块 、 、 、 、 、i 队列m | ， i 调度算法 图3 1 队列调度算法的原理 输入业务到达交换节点后，分别暂存到相应队列中，假设共有m 个队列，队列 调度算法就是处理如何从这m 个队列中选择下一个要传输的分组这个问题。当然， 队列调度算法的种类有很多，不同的调度算法有着不同的服务规则、控制目的和复 杂度。 3 2 - 2 队列调度算法 数据流的排队可以分为单队列方式和多队列方式。单队列排队是指将所有到同 一个输出出口的数据流无区别地排成一个队列，按一定的调度算法传输队列中的数 据包；多队列排队根据一定的规则把输入数据流对应到不同的队列，每个队列再按 照一定的调度算法进行数据传输。 最简单的调度算法是传统的先进先出( f i f o ) 队列实现的“先来先服务”( f c f s ) ， 1 9 第三章基于i p 的拥寒控制 因为它按照占用队列的多少分配带宽，无法实现公平性。于是便有了归一化共享处 理g p s ( g e n e r a l i z e dp r o c e s s o rs h a r i n g ) 晔】。数据分组位于不同的逻辑队列，在有限的 时间间隔，每一个非空队列都有机会接受服务，至少一次。如果为队列赋予一定的 权值，接受的服务与权值成比例，那么g p s 便可以实现最大最小比例公平性。g p s 仅仅是一种理论模型，最简捷的实现是轮循队列( r o u n d - r o b i n ) ，它用每次服务一个数 据分组代替了g p s 中的无穷小业务量。当为队列赋予权值后，相应的策略称为加权 轮循队列( w e i g h t e dr o u n d - r o b i n ，w r r ) 。为了实现公平的带宽分配，w r r 需要了解各 队列中分组的平均长度，这是不现实的，因为它与业务源的特性有关。g p s 的另一 个近似实现是加权公平队列( w e i g h t e df a i rq u e u e ，w f q ) 3 3 ，它无须知道分组的平均大 小，而是通过一种新机制仿真g p s ，即给分组一个与服务时间相联系的完成号( f i n i s h n u m b e r ) ，服务者依f i n i s hn u m b e r 的顺序服务分组。 ( 1 ) f l f o 算法，通过f i f o 队列实现“先来先服务”( f c f s ) 。即当第一个数据包到达 路由器时首先被传输，接着到达的数据包在路由器中排队等待输出。每个路由器的 缓存是有限的，如果数据包到达时缓存己满，那么路由器不得不丢弃包。这种方法 最大的优点是实施简单，但没有考虑被丢弃分组的重要程度。 ( 2 ) w r r 算法，在轮循机制的基础上为每个队列赋予一个权值，同时，为每个队列 维护一个计数器。在每次轮循时，计数器为非零的队列可以发送一个信元。计数器 的计算方法为：初值为权值，每发送一个信元就减一，当所有队列的计数器为零时， 都重置为权值。w r r 算法能提供很好的公平性，同时以较为平滑的方式调度输出业 务。 ( 3 ) w f q 算法，将分组按照不同的业务流、不同的i p 优先级，自动按照规则，划分 成不同的队列，在保证高优先级业务的同时，按照配置权重，将带宽公平地分给低 优先级别的业务。w f q 的优点是对所有应用都能比较公平地提供服务质量，对于要 求较高的业务可以通过设置权重保障优先级，能智能划分队列和调度，配置相对简 单：缺点是策略计算复杂，比较消耗路由器处理能力。 第三章基于l p 的拥塞控制 3 3 队列管理 3 3 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 机制出现之前，路由器中最常用的队列管理策略是“弃尾”( d r o pt a i l ) ， 从拥塞控制的角度分析，它是一种拥塞恢复机制，已经在i n t e m e t 上成功工作了许多 年，但是它的缺陷也较为严型矧： ( 1 ) 持续的满队列状态。由于弃尾算法只有在队列满时才会发出拥塞控制信号，因此 会使得队列在相当长的时间内处于充满的状态。而队列管理最重要的目标之一就是 降低稳定状态下队列的长度，因为端到端的延迟主要是由于在队列中排队等待造成 的。另外，满队列也容易导致突发数据的丢弃。 ( 2 ) 业务流对缓存的死锁。在某些隋况下，弃尾算法会让某个流或者少部分流垄断队 列空间，阻止其他流的分组进入队列。 ( 3 ) 业务流的全局同步。由于i n t e m e t 上数据的突发本质，到达路由器的包往往也是 突发的。如果队列是满的，就会造成在短时间内连续大量分组丢弃。受此影响，大 量t c p 数据源将几乎同时降低自己的发送速率，在短期内造成网络负载过轻，降低 了网络资源利用率；然后，所有t c p 数据源又将同时逐步增加自己的发送速率，导 致下一轮网络拥塞的出现，周而复始的影响网络的运行效率。 随着研究的深入，人们把控制理论引入网络拥塞控制中，a q m 可以解决被动队 列管理的缺点，它基本上是一个反馈控制机制。近年来，a q m 成为端到端拥塞控制 研究中的一个热点。在a q m 中，通告拥塞的信号不再是唯一的分组丢弃，而可以 采用标记分组来通知信源减速，这样会进一步提高连接的有效吞吐量。a q m 的主要 技术目标是在减少排队时延的同时保证较高的吞吐量，具体分析，a q m 的优势有以 下几个方面： ( 1 ) 早期探测路由器可能发生的拥塞，并通过随机丢弃或标记分组来通知源端采取措 施避免可能发生的拥塞； 2 1 第三章基于i p 的拥塞控制 ( 2 ) 公平地处理包括突发性、持久性和间隙性的各种t c p 业务量； ( 3 ) 避免多个t c p 连接由于队列溢出而造成同步进入“慢启动”状态； ( 4 ) 维持较小的队列长度，在高吞吐量和低时延之间做出合理平衡。 虽然b r a d e n 等人在i e t f 提出a q m 的研究动议是在1 9 9 8 年【3 1 l ，但与其密切相 关的r e d ( r a n d o me a r l yd e t e c t i o n ) 算法的研究却由来已久。早在1 9 9 3 年，f l o y d 和 j a c o b s o n 就提出了r e d l l 习，当时的主要目的是克服“早期随机丢弃”( e a r l yr a n d o m d m p ) 网关偏袒突发业务而造成的不公平问题。因为在提出a q m 的研究时，r e d 算 法是唯一能实现其技术目标的算法，所以r f c 2 3 0 9 3 1 将其推荐为a q m 的唯一候选 算法。未来的发展方向必定是主动队列管理会逐渐取代被动队列管理，而研究并开 发有效的主动队列管理算法是当前的一个热门研究方向，对于网络拥塞的避免和控 制也具有十分重要的意义。近些年来，围绕着a q m 和r e d 的研究逐渐丰富起来。 下面本文选取几个主要的队列管理算法进行介绍。 3 3 2 弃尾算法( d r o p t a i l ) 传统的i p 网络中链路的队列管理采用“弃尾算法”即d r o p t a i l ，在网络设备中 使用f i f o 来缓冲到达的分组，当f i f o 满时，丢弃其后到达的队尾分组。d r o p t a i l 本身实质上是被动队列管理的一种，它自身不参与拥塞控制，只是在队列满了的时 候被动丢包。一般操作是对每个队列设置一个最大值，当到达最大值时就不再接受 后续的分组，直到队列长度不再是最大值( 比如