（计算机应用技术专业论文）基于自相似模型的路由拥塞控制策略研究.pdf

江苏大学硕士学位论文 摘要 随着互联网规模日益增大，高速网络中多媒体应用的发展，网络用户对网 络服务质量( q o s ) 的需求越来越高，不但对网络带宽有很高的要求，而且对信息 传输的延时和抖动等也有较高的要求，以提供端到端的q o s 控制和保证。而网络 拥塞是影响网络服务质量的重要因素，实施拥塞控制也是其它o o s 机制正常工作的 必要前提。因此，如何避免拥塞、如何进行拥塞控制保证o o s 是当前的研究热点。 然而，近年来一系列的测量结果表明，网络业务流量显示自相似、长相关性， 原有网络流量是短相关( s r d ) 的基础性假设被推翻，网络业务的自相似性特征对 网络的分析、设计、控制和性能评价等均有重大的影响。传统的网络模型在描述 实际网络业务时，忽略了这个重要的特性，不能真实地刻画网络业务的真实情况。 首先，本文对网络拥塞机制进行研究。主动式队列管理机制( a q m ) 是i e t f 推荐的基于路由器拥塞控制的关键技术，它和t c p 端到端的拥塞控制相结合，是 解决目前i n t e r n e t 拥塞控制问题的一个主要途径。 然后，本文对自相似、长相关理论以及估计h u r s t 指数的方法与实现进行了 研究。通过实验比较及理论分析得出e b p ( e m b e d d e db r a n c h i n gp r o c e s s ) 方法优 于7 种传统方法的结论。同时，介绍了n s 2 的仿真原理并利于n s 2 仿真实现自相 似数据流量。 最后，本文在对r e d 算法以及自相似理论详细研究的基础上对r e d 算法进行 改进，并在模糊分布的升半柯西分布和e b p 方法的基础上提出一种适应自相似网 络环境的队列管理算法一基于升半柯西分布和h u r s t 指数自适应r e d 算法 - c h a r e d ( a s c e n d i n gs e m i - c a u c h y d i s t r i b u t i o na n dh u r s tc o e f f i c i e n t s a d a p t i v e r a n d o me a r l yd e t e c t i o n ) 。该算法利用业务流的长相关性来预测未来时间段的业 务流量对网络的需求情况，动态调节队列算法的丢包概率函数，能充分利用网络 资源，有效的避免拥塞。通过n s 2 网络仿真器对所提出的c h a r e d 算法进行了仿 真实验分析，结果表明该算法能有效地减小时延、降低丢包率和网络抖动，具有 较好的实用性。 江苏大学硕士学位论文 关键词：拥塞控制，主动队列管理，随机早检测算法，自相似性，h u r s t 指数 江苏大学硕士学位论文 a b s t r 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 a c t ，p e o p l eh a v ea ne v e r - g r o w i n gd e m a n df o r t h eq u a l i t yo fs e r v i c eo fc o m p u t e rn e t w o r k s ( q o s ) p r e s e n t l y , i nt h eh i 【g h s p e e d n e t w o r km u l t i m e d i a sa p p l i c a t i o nn o to n l yh a st h ev e r yh i g hb a n d w i d t hr e q u i r e m e n t t ot h en e t w o r k , b u ta l s or e q u i r e si n t e l l i g e n c et r a n s m i s s i o n ，l o wd e l a y ，t h el o w v i b r a t i o nt ob ep r o v i d e dt h ee n d t o e n dc o n t r o la n dg u a r a n t e eo fq o s 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 en e t w o r kq u a l i t yo fs e r v i c e m o r e o v e r , as u i t a b l ec o n g e s t i o nc o n t r o lm e c h a n i s mi st h eb a s i sf o ro t h e ro o s m e c h a n i s mn o r m a lw o r k a n dn o w a d a y s c o n g e s t i o nc o n t r o lm e c h a n i s mo fi n t e r a c t a n dq u a l i t yo fs e r v i c ea r et h ec e n t r a li s s u e so ft h ec u r r e n tr e s e a r c h h o w e v e r , i nr e c e n ty e a r s ，as e r i e so ft e s tr e s u l ts h o wt h a tn e t w o r kt r a f f i cf l o wi s s e l f - s i m i l a ra n dl o n g - r a n g ed e p e n d e n t ( l r d ) ，w h i c hb r e a kt h eo l db a s i cs u p p o s et h a t n e t w o r k 仃a f f i cf l o wi ss h o r t - r a n g ed e p e n d e n t ( s r d ) t h e r ea r em a n ya s p e c t so ft h e n e t w o r k , s u c ha sn e t w o r ka n a l y s i s ，n e t w o r kd e s i g n ，n e t w o r kc o n t r o l ，n e t w o r k p e r f o r m a n c ee s t i m a t i o na n ds oo n ，a f f e c t e db yt h es e l f - s i m i l a r yc h a r a c t e r i s t i co f n e t w o r kt r a f f i cf l o w t h a ti s t h ec o n v e n t i o n a lm e t h o dh a sn o tb e e na p p l i e dt ot h e s e t r a f f i c s a n dt h et r a d i t i o n a ln e t w o r km o d e li g n o r e st h ei m p o r t a n tc h a r a c t e r i s t i e so f n e t w o r kt r a f f i cf l o w , a n df a i lt or e f l e c tt h er e a ls i t u a t i o no ft h en e t w o r k f i r s t l y , t h i sp a p e rd o e ss o m er e s e a r c ho nt h ec o n g e s t i o nc o n t r o lm e c h a n i s mo f i n t e r a c t n ea c t i v e q u e u em a n a g e m e n tm e c h a n i s m ( a q m ) w h i c ht h e r e c o m e n d s ，i st h ee s s e n t i a lt e c h n o l o g yb a s e do nt h er o u t e rc o n g e s t i o nc o n t r o l ，w h i c h c o m b i n e sw i t ht h et c pe n d t o - e n dc o n g e s t i o nc o n t r 0 1 b e i n gam a i nm e t h o dt os o l v e t h ec o n g e s t i o nc o n t r o lq u e s t i o no ft h ep r e s e n ti n t e r a c t s e c o n d l y , t h es e l f - s i m i l a r , u mt h e o r ya n dt h ec a l c u l a t i o no fh u r s tc o e f f i c i e n ti s i n t r o d u c e di nd e t a i l e b p ( e m b e d d e db r a n c h i n gp r o c e s s ) m e a s u r ei sc o n c l u e d ，w h i c h i sa d v a n t a g et ot h es e v e nt r a d i t i o n a lo n e s ，b a s e do ne x p e r i m e n t sa n dt h e o r i e s f i n a l l y , r e di si m p r o v e db a s e do nt h es e l f - s i m i l a rt h e o r y aq u e u em a n a g e m e n t a l g o r i t h m c a l l e da s c e n d i n gs e m i c a u c h yd i s t r i b u t i o na n dh u r s tc o e f f i c i e n t sa d a p t i v e r a n d o me a r l yd e t e c t i o n ，c h a r e df o rs h o r t , w a sp r o p o s e db a s e do na s c e n d i n g s e m i c a u c h y d i s t r i b u t i o na n dr e a l t i m eh u 硌tc o e f f i c i e n t sc a l c u l a t e db ve b p c h a r e d a l g o r i t h m w h i c hc a na d j u s td y n a m i c a l l yt h ep a c k e td r o p p i n gp r o b a b i l i t yo f t h eq u e u em a n a g e m e n ta l g o r i t h mb yf o r e c a s t i n gt h er e q u r i m e n to ft r a f f i cf l o wt ot h e n e t w o r ki nt h ef u t u r eb a s e do nt h es e l f - s i m i l a ra n du c a l lm a k ef u l lu s eo fn e t w o r k r e s o u r c e sa n da v o i dn e t w o r kc o n g e s t i o ne f f e c t i v e l y a tt h es a m et i m e t h ep r i n c i p l eo f n s 2a n dt h es i m u l a t i o np r o c e s st og e n e r a t et h es e l f - s i m i l a rt r a f f i cd a t ab vn s 2i j s i n t r o d u c e d t l l l ea l g o r i t h mi sv e r i f i e di nn s 2n e t w o r ks i m u l a t i o nm a c h i n e 弱w e l l b yt h e i n d i c a t i o no fas e r i e so fs i m u l a t i o ne x p e r i m e n t s c h a r e dc a r lv a l i d l ya d a p tt h e c h a n g eo fn e t w o r kf l o we f f e c t i v e l y s i m u l a t e dr e s u l t sd e m o n s t r a t et h a tt h ec h a r e d c a nb eu s e dt or e d u c ep a c k e tl o s sr a t i o ，q u e u ed e l a ya n dq u e u ed e l a y v a r i a b i l i t y i n 江苏大学硕士学位论文 k e yw o r d s ：c o n g e s t i o nc o n t r o l ，a q m ( a c t i v eq u e u em a n a g e m e n t ) ，r e d ( r a n d o m e a r l yd e t e c t i o n ) ，s e l f - s i m i l a r , h u r s tc o e f f i c i e n t i v 独创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究工作所取得的成果。除文中已注明引用的内容以外，本论 文不包含任何其他个人或集体己经发表或撰写过的作品成果。对本文 的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本 人完全意识到本声明的法律结果由本人承担。 学位论文作者签名，槲 日期：歹钟咯年) 月j 7 e t 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定， 同意学校保留并向国家有关部门或机构送交论文的复印件和电子版， 允许论文被查阅和借阅。本人授权江苏大学可以将本学位论文的全部 内容或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫 描等复制手段保存和汇编本学位论文。 本学位论文属于 保密口，在年解密后适用本授权书。 不保密团。 学雠文储虢聒葛够 硼年f 月f7 日篡篇e l 沙髟年f 蝴，7 。 江苏大学硕士学位论文 1 1 研究背景 第1 章绪论 随着计算机技术和因特网的进一步发展，人们不但对于网络所能实现的诸如 电子邮件、远程登录、文件传输等简单的数据传输功能具有很高的兴趣，更对远 程教育、视频会议、电子商务等多媒体业务表现出了越来越大的热情。应用的多 元化、网络拓扑的异构性和传输物理介质的多样性使得网络变得越来越复杂，对 网络的控制和管理提出了巨大的挑战。对网络应用的要求不断提高，促使在网络 的设计和维护中不仅要考虑单一的数据传输，更要考虑到某些业务传输的实时性 和抖动性等指标，即：保证网络的服务质量q o s ( q u a l i t yo fs e r v i c e ) 。然而，随着 信息技术的迅猛发展，各个领域的网络硬件资源的实际增长速度是无法满足如此 快速的传输需求增长的，于是网络拥塞就产生了。当网络拥塞产生时，将无法使 吞吐量维持在网络固有的传输能力水平，实际上将会使得网络吞吐量急剧下降， 甚至产生网络拥塞崩溃现象。在1 9 8 6 年1 0 月，由于拥塞崩溃的发生，美国l b l 到u cb e r k e l e y 之间的数据吞吐量从3 2 k b p s 跌落到4 0 b p s 1 1 。之后，网络拥塞控 制成为了研究热点。 网络的拥塞控制就是网络节点采取措施来避免拥塞的发生或者对拥塞的发 生作出反应。它实际上包含拥塞避免( 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 仃0 1 ) 两种不同的机制【2 】。拥塞避免是预防策略，它的目的是避免 网络拥塞发生，使得网络运行在高吞吐量、低延迟的状态。拥塞控制是恢复策略， 它用于把网络从拥塞状态中恢复出来，使网络重新进入正常的运行状态。一种理 想的拥塞管理算法要求适应网络的变化、符合网络的特征、把握网络流量的特性、 充分利用好有限的网络资源。传统的观点认为网络流量呈现短程相关性，然而直 到二十世纪九十年代网络流量的长程相关性( l r d ) i 拘观点被逐步证实并得到认 可，打破了原有网络流的短相关( s i m ) 的基础性假设，自然会带来许多与原有假 设不同的特征( 如：流量特征，排队特征) 与操作方法( 缓存大小的选取，拥塞控制 策略) 。例如：传统模型中的缓存中队列大小分布是指数分布，而采用了长相关 的分形模型后，队列大小分布是韦伯分布或双曲线分布【3 】。由于韦伯分布或双曲 江苏大学硕士学位论文 线分布比指数分布具有更重的拖尾( 衰减更慢) ，使得排队延时和丢包率增加。 长相关模型的引入势必会给原本复杂的拥塞控制问题带来新的困难，但它同 时也会带来新的解决方法。在较长时间尺度上，长相关特征的数据流是有规律的 ( 相关性- ) ，例如：t u a n 和p a r k 4 针对网络的自相似性的可预测性提出了 s a c ( s e l e c t i v ea g g r e s s i v e n e s sc o n t r 0 1 ) 。s a c 会在被告知未来网络空闲时收回带 宽，通过与未来网络空闲度及其信赖度的函数调节拥塞的程度。而且这种方法在 网络自相似性越强时越有效。不过文献f 4 1 采用的方法依赖于对网络流量的测量， 虽然有理论上的价值，但在现有网络环境中很难付诸实用。本文同样利用长相关 性带来的网络流的可预测性，通过自相似参数一h u r s t 指数对路由器的队列算法 进行参数优化，从而提高整体网络的性能。 1 2 本领域研究现状 在i n t e m e t 发展初期，拥塞控制主要是通过t c p 协议中端到端基于滑动窗口 的流量控制完成【5 】，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 r n e t 中广泛采用的传输控制协议仍 是t c p 协议，在该协议下，当发送方检测到发送数据有所丢失时会降低并重新 2 江苏大学硕士学位论文 调整发送速率。因此，如果在路由器中增加智能预测环节，使得在路由器缓存被 耗尽之前就有计划的丢弃一部分分组，就可以提前通知发送方降低发送速率，避 免可能出现的危险。主动队列管理就是基于这个思想被提出来的。 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 ) 6 1 算法为候选算法。然而，随后的研 究中发现r e d 仍有一些缺陷。较有影响力的r e d 变种算法有：w r e d t 7 】， s t a b i l i z e dr e d t s i ，s e l fc o n f i g u r a t i o nr e d 9 ，a d a p t i v er e d 1 0 1 ，f r e d t l l 】和b a l a n c e d 砌m 【1 2 】以及虚队列a q m 策略等【1 4 】。目前，主动队列管理算法已经成为了t c p 端到端拥塞控制研究中的技术热点之一。 然而，传统的网络性能分析和控制管理都是建立在泊松分布和马尔可夫过程 理论基础上的，泊松分布模型和马尔可夫过程最初用于电话网的规划和设计，是 2 0 世纪初a k e r l a n g 根据电话业务的特征提出的，它能较为准确的描述电话网 中的业务特征，因而得到了广泛的应用。到六七十年代，a r p a n e t 开始发展， 由于网络测量技术的落后和限制，网络业务模型在很长一段时间内都采用传统的 话务模型或其它改进形式，例如流体流模型、马尔可夫调制的泊松过程等。这些 模型的共同特点是所描述的业务序列具有短程相关性( s h o r tr a n g ed e p e n d e n c e ) ，当 时间尺度增加时，统计意义上单位时间内得到数据包序列分布趋于白噪声过程。 近几年来，随着网络技术的飞速发展和网络应用范围的扩大，网络业务的突发性 和复杂性远远超过传统通信网，同时随着测量技术的发展，研究发现基于传统模 型推导出的网络性能参数与网络的实际情况相差较远，这些都对传统模型的有效 性提出了质疑。1 9 8 9 年到1 9 9 2 年，w e l e l a n d ，m s t a q q u ，w w t l l i n g e r 和 d vw i l s o n 等人测量了b e l l c o r em o r r i s t o w n 研究中心的网络业务流，通过统计分 析发现这些业务呈现出自相似性，完全不同于泊松分布模型所描述的特性【l5 1 。 在之后很多研究者展开了相继的研究：文献 1 6 1 9 1 测量分析了广域网业务数据， 指出w w w 业务具有明显的分形本质；文献【2 0 】【2 1 】测量并分析了a t m 网络中 传输的视频会议业务流，发现v b r 视频业务具有自相似性了；文献2 2 1 收集了 蜂窝数字包数据网络( c d p d ) 中的业务数据并对其o p n e t 建模和仿真分析，发现 业务流呈现长程相关性；文献f 2 3 1 对c d m a 系统下行链路的突发数据通信业务 进行了测量分析，指出c d m a 多址干扰具有自相似性；文献 2 4 1 发现a dh o e 无 3 江苏大学硕士学位论文 线业务也有自相似特征；对8 0 2 1 1 无线局域网业务的测量结果表明无线局域网 业务具有较强的自相似性【2 5 1 。上述大量的实际网络业务流检测结果表明：无论 网络的拓扑结构、传输介质、用户数量、协议类型、业务地点、编码方式、业务 类型如何变化，都存着统计白相似特征。 网络业务的统计自相似性主要是指在不同时间尺度上观测到的业务流量序 列具有相同的统计特性，即长程相关性；而泊松分布和马尔可夫过程理论所描述 的是短程相关性，即业务流量结构在不同时间尺度呈现不同的特征，在统计时间 尺度较大时或连接数目趋于无穷时，业务流量趋于平滑。因此，有必要深入理解 网络业务流的本质，采用更有效的控制策略，为用户提高更好的服务质量。 本文的研究旨在从本质上理解自相似网络业务流的特征规律，结合其特征优 化拥塞控制算法，提高网络性能。 1 3 主要内容 本文在第一章绪论介绍网络拥塞控制及网络自相似特性的研究概况及研究 背景，最后对本文的研究内容进行了概括。 第二章研究了i n t e r a c t 中t c p i p 拥塞控制方法。首先介绍了t c p 基于滑动 窗口的拥塞控制机制的四个核心算法：慢启动、拥塞避免、快速重传和快速恢复， 讨论了当前的各种t c p 拥塞控制改进方案。然后介绍了主动队列管理机制和口 路由器的拥塞控制算法，如尾丢弃算法、随机早检测算法、显示拥塞指示算法、 公平队列算法、b l u e 算法以及随机公平b l u e 算法，并对以上几种算法进行总 结。 第三章首先介绍了自相似过程的相关概念、几种网络自相似模型以及自相似 指数h u r s t 的计算方法，并重点分析了嵌入式分支过程( e b p ) 方法在实时计算 h u r s t 指数方面的原理及优势。然后针对八种技术h u r s t 值的方法进行实验比较， 得出e b p 方法计算精度较高的结论。最后介绍了n s 2 的基本仿真原理，并完成 在n s 2 中仿真产生自相似数据流。 第四章首先探讨了自相似网络环境下路由拥塞控制策略一随机早检澳t j ( r e d l 算法的局限性，并结合r e d 算法自身参数敏感等缺陷进行了改进，提出一种适 应网络自相似特征的新队列算法。然后详细阐述和推导了新算法的理论依据和具 4 江苏大学硕士学位论文 体实现。 第五章是本文的仿真实验部分。本文首先利用n s 2 ( n e t w o r ks i m u l a t i o n v e r s i o i l 2 ) 网络实验平台设计实验确定新队列算法的有关参数，然后对r e d 算法 及改进的算法进行仿真分析，并验证了本文提出的新的队列算法的有效性。 第六章总结本文的工作，指出不足并对网络拥塞控制研究进行了展望。 5 江苏大学硕士学位论文 2 1 引言 第二章拥塞控制策略研究 在网络通信中，拥塞容易造成延迟和抖动等使网络服务质重t ( o o s ) 性能指标 下降，是影响带宽、缓存、吞吐量等网络资源利用率的关键因素，因此有效解决 拥塞问题对于提高网络性能具有重要意义。网络产生拥塞的根本原因是用户提供 给网络的负载大于网络资源容量和处理能力，在i n t e m e t 中，存储空间不足、通 信信道带宽容量不足、处理机处理能力较弱等都是产生拥塞现象的直接原因，但 是无论增加缓存容量或是提高处理器及链路的速度都不能从根本上解决问题，相 反，某些情况下甚至可能会进一步加剧拥塞。网络中发生拥塞后如果不加以控制， 往往会导致恶性循环，这时如果路由器没有空余的缓存空间，它就必须丢掉新到 的数据包，当数据包丢弃时，源端可能会因为超时而重传此包，由于源端在未收 到确认之前不能丢弃数据包，相应的缓存不能释放，使缓存进一步消耗，导致拥 塞加重，在网络流量非常高的情况下，网络甚至会完全瘫痪，几乎没有数据包能 够送达接收方。网络拥塞已经成为制约网络发展和应用的一个瓶颈，如何更好的 预防和控制拥塞一直是近年来网络研究的热点问题。 2 2 拥塞控制策略的研究方向和分类 2 2 1 拥塞控制的主要研究方向 拥塞控制策略包括拥塞避免和拥塞控制这两种不同的机制。拥塞避免是预防 机制，它的目标是避免进入拥塞状态，使得网络运行在高吞吐量、低延迟的状态 下。拥塞控制是恢复机制，它用于把网络从拥塞状态中恢复出来。目前，拥塞控 制的研究主要集中在三个方向： ( 1 ) 改进现有的t c p 拥塞控制算法； ( 2 ) 研究在中间网络设备( 主要是路由器和交换机) 中采取一定策略避免和控 制网络拥塞； 6 江苏大学硕士学位论文 ( 3 ) 研究新的端到端拥塞控制算法。 拥塞控制的主要目标是控制进入网络的数据流量，保证通信子网不会被用户 发送的数据流淹没，合理地使用瓶颈资源。直观上，解决网络拥塞可以从两方面 入手，一是拥塞避免，即尽量避免拥塞的发生，是网络运行的最佳状态；二是在 拥塞发生后采取补救措施消除拥塞。完全避免网络拥塞必然会以牺牲网络的资源 利用率为代价，在追求公平、高效、高利用率的网络环境下，采取这种保守的方 法显然是不适宜的，因此，采用拥塞避免与拥塞控制相结合的方法更为合理 2 2 2 拥塞控制方式的分类 现有的拥塞控制方式可以从一下几个角度进行划分： ( 1 ) 从控制理论角度出发，可以分为开环控制和闭环控制，开环控制又称为 预防式控制，它事先设计一个“好”的网络，确保它不会发生拥塞，而网络一旦 运行起来，就不再采取措施，这类控制机制较适用于音频和活动图像业务。开环 控制比较典型的例子就是资源预留( 如r s v p 协议) 。这种方法虽然是一种很直接 的控制拥塞的方法，但由于事先精确确定业务特性几乎不可能，因此为保证服务 质量、避免拥塞，往往需要预留多余的网络资源，很容易造成网络资源利用率低 下。另外，资源预留的复杂性和可扩展性差也是该方法不能被广泛采用的重要原 因。而且对于复杂的网络系统来说仅仅有开环控制是不够的。 闭环控制，又称为反应式控制，能够使得网络中的拥塞状态信息能及时反馈 至端系统，从而调整端系统的数据传输速率，这样既保证了传输质量又能充分利 用网络资源。对于互联网这种网络业务不断变化的复杂系统，一般采用闭环控制。 依据控制论的观点，闭环控制中发送方接受反馈信息，并从反馈信息中推断网络 状况，确定控制参数，并依据一定的控制算法调整发送速率，完成对网络拥塞的 响应。 ( 2 ) 从实施控制的类型上，拥塞控制可以分为基于窗1 2 ( w i n d o w b a s e d ) 和基于 速率( r a t e b a s e d ) 两种类型。t c p 采用的是典型的基于窗口的控制方式，通过调整 滑动窗口的大小控制发送到网络的数据量。基于窗口的控制易于实现，并且可以 限制注入网络的最大流量。基于速率的控制方式则是通过每秒发送的比特数来控 制数据流的发送。如果传输速率能够匹配网络可用带宽，就可以减少路由器的缓 7 江苏大学硕士学位论文 冲区长度，所以它本质上更适合于多媒体数据流的传输。 ( 3 ) 从推断网络状态的反馈信息类型上，可以分为显示( e x p l i c i t ) 拥塞控制和隐 式( i m p l i c i t ) 拥塞控制：在显示反馈方式中，网络使用显示信号执行流量控制的端 点通告其状态( 有效带宽、缓冲容量等) ；如果控制端使用流量测量或者通过诸如 超时、重复a c k 等隐含信号来推断网络状态，则为隐式控制方式。 ( 4 ) 根据拥塞控制算法的实施位置，可以将拥塞控制算法分为两大类：源算 法( s o u r o e 础g o r i t h m ) 和链路算 法( l i n ka l g o r i t h m ) 。源算法在主机和网络边缘设备 中执行，作用是根据反馈信息调整发送速率。链路算法在网络设备f 如路由器和 交换机) 中执行，作用是检测网络拥塞的发生，产生拥塞反馈信息。 当前的拥塞控制研究主要集中在尽量做好( b e s t e f f o r t ) 型服务，对支持q o s 的拥塞控制新机制的研究还不多，而这种研究对支持多媒体数据流传输是很有价 值的。 源算法中使用最广泛的是t c p 协议中的拥塞控制算法。t c p 是目前i l l t e m e t 中使用最广泛的传输协议。据m c i 统计，总字节数的9 5 和总报文数的9 0 使 用t c p 传输【2 6 1 。近年来，t c p 中采用了很多新的拥塞控制算法，包括慢启动 ( s l o w ) 、拥塞避免、快速重传( f a s tr e t r a n s m i t ) 、快速恢复( f a s tr e c o v e r y ) 、选择性应 答( s a c k ) 等，大大提高了网络传输的性能。t c p 中使用的拥塞控制算法已经称 为保证i n t e r a c t 稳定性的重要因素。 链路算法的研究目前集中在主动队列管t 里( a c t i v eq u e u em a n a g e m e n t ，a q m ) 算法方面。和传统的尾丢弃( d r o p t a i l ) 相比，a q m 在网络设备的缓冲溢出之前就 丢弃或标记报文。 2 3 拥塞控制源算法 2 3 1t c p 拥塞控制 1 9 8 8 年v a nj a c o b s o n 指出了t c p 在控制网络拥塞方面的不足，并提出了“慢 启动 ( s l o ws t a r t ) 、“拥塞避免”( c o n g e s t i o na v o i d a i l c e ) 算法。1 9 9 0 年出现的t c p r e n o 版本增加了“快速重传 ( f a s tr e t r a n s m i t ) 、“快速恢复 ( f a s tr e c o v e r y ) 算法， 避免了网络拥塞不够严重时，采用“慢启动 算法而造成过大地减少发生窗口尺 8 江苏大学硕士学位论文 寸的现象。t c p 的拥塞控制就是由这四个核心算法组成。为了实现算法，必须向 每个t c p 连接状态加入几个参量：拥塞窗口、通知窗口、发送窗口、慢启动阈 值、回路响应时间、超时重传计数器及快速重传阈值。 ( 1 ) 拥塞窗n ( c w n d ) ：描述源端在拥塞控制情况下最多能发生数据包的数量， 是对发送端收到的确认( a c k ) 之前，能向网络传送的最大数据量的一个发送端限 制； ( 2 ) 通知窗n ( a w n d ) 是接收端给源端预设的发送窗口大小，它只在t c p 连 接建立的初始阶段使用； ( 3 ) 发送窗口( w i n ) ：是源端每次实际发送数据的窗口大小； ( 4 ) 慢启动阈值( s s t h r e s h ) ：是拥塞控制中慢启动阶段和拥塞避免阶段的分界 点，初始值通常设为6 5 5 3 5 b y t e s ； ( 5 ) 回路响应时间：一个t c p 数据包从源端发送到接收端，源端收到 接收端确认的时间间隔； 。 ( 6 ) 超时重传计数器( r t o ) ：描述数据包从发送到实效的时间间隔，通常设为 2 r t r 或5 r t r ； ( 7 ) 快速重传阂值( t c p r e x m t t h r e s h ) ：是能触发快速重传的源端收到重复确认包 a c k 的个数。当此个数超过t c p r e x m t t h r e s h 时，网络就进入快速重传阶段，其 缺省值为3 。 t c p 拥塞控制四个主要过程如下： ( 1 ) 慢启动 由于数据包需要在路由器处排队，而端系统不能预测网络资源的使用情况， 如果在建立新的连接时向网络中发送大量的数据包，容易导致耗尽路由器的资 源，使得网络吞吐量急剧下降。为了避免这一现象，t c p 使用了慢启动算法来探 测网络的可用带宽。 慢启动算法为每个连接设置两个参数：拥塞窗口( c w n d ) 和慢启动阈值 ( s t h r e s h ) 。当建立新的t c p 连接时，c w n d 被初始化为一个数据包大小( 一个数据 包缺省值为5 1 2 或5 3 6 b y t e s ) ，实际发送窗口w i n 取拥塞窗口和通知窗口中较小 值，源端按w i n 大小发送数据，每收到一个a c k 确认，c w n d 就增加一个数据包 发送量，结果c w n d 随r t r 呈指数增长：1 个、2 个、4 个、8 个，因此， 9 江苏大学硕士学位论文 源端向网络中发送的数据量将急剧增加。当拥塞窗口达到慢启动阈值( 通常设为 6 4 k 字节) ，就进入拥塞避免阶段。 ( 2 ) 拥塞避免 在拥塞避免阶段，源端每收到一个a c k 确认，c w n d 增加1 c w n d 个数据包， 即每个r r r 内增长一个数据包大小，所以在拥塞避免算法中c w n d 的增长是线性 的。在两种情况下将进入拥塞避免状态：当源端收到三次相同的重复a c k 时， 此时表明网络发送拥塞，慢启动阈值s s t h r e s h 被设置为当前c w n 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 的值，并启动慢启动算法。在r e n o t c p 中，慢启动和拥塞避免算法是一起实现的，算法描述如下： 初始化：c w n d = 1 s s t h r e s h = 6 5 5 3 5 b 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 r i v e dp a c k e s 让c w n d s s t h r e s h c w n d + = 1 e l s ec w n d + = l c w n d 当检测到丢包时，发送方执行以下操作： s s t h r e s h = m a x ( c w n d 2 ，2 ) 如果检测到定时器超时，c w n d = 1 ( 3 ) 快速重传 如果一个t c p 连接由于拥塞而被丢弃了一个数据包，接收端对每个收到的 错序的数据包发送相应的重复确认，知道丢失的数据包收到为止。源端在接收到 重复a c k 时并不能确定是由于分组丢失还是分组乱序造成的，如果假定是分组 乱序，在目的端处理之前源端只可能收到一个或两个重复a c k ；如果收到三个 或更多的重复a c k ，表明网络已经发送拥塞。源端不等到重传定时器超时就重 发这个可能丢失的分组，这就是快速重传。 ( 4 ) 快速恢复 1 0 江苏大学硕士学位论文 当快速重传算法重传了可能丢失的分组之后，如果t c p 重新进入慢启动阶 段，将会使拥塞窗口c w n d 减为1 ，重新开始探测网络带宽，从而严重影响网络 吞吐量，因此快速恢复算法在快速重传之后转去执行拥塞避免算法，避免了过大 地减少发送窗口而导致的网络性能下降。快速恢复和快速重传算法描述如下： s t e p1 ：i f ( d u p a c k s = = 3 ) s s t h r e s h = m a x ( 2 ，e w n 0 2 ) ； c w n d = s s t h r e s h + 3 ； s t e p2 ：重传丢失的分组 s t e p3 ：此后每收到一个重复的a c k 确认时，c w n d = c w n d + 1 s t e p4 ：当收到对新发数据的a c k 确认时，c w n d = s s t h r e s h ，这个a c k 能够 对那些在丢失的分组之后，第一个重复a c k 之前发送的所有包进行确认。 2 3 2t c p 拥塞控制算法的改进现状 ( 1 ) 慢启动过程的改进：慢启动阶段对短数据传输更重要，拥塞避免阶段对 长数据传输更重要。目前i n t e m e t 上的一个主要应用册的流量主要是短 数据。这方面的研究包括：增大拥塞窗口的初始值，文献 2 7 1 推荐将初始值由 1 m s s ( m a x i m u ms e g m e n ts i z e ) 增加到4 m s s ：将慢启动过程分为多段，逐步减小 窗口增长的速度，平滑从慢启动到拥塞避免的过渡；在多个连接或主机间共享网 络状况信息，根据网络的状况决定初始的阈值，如：s p a n d 和t c pf a s ts t a r t 。 ( 2 ) 减少不必要的超时重传和快速重传：当前的t c p 应用主要有两种重传机 制快速重传和超时重传。当这些重传发生时，t c p 都会减小拥塞窗口，从而 降低传输的速率。r t r 测量的准确性和乱序报文都会影响t c p 做出正确的判断。 e i f e l 算法【2 8 j 通过在应答报文中增加特殊信息来解决这个问题。 ( 3 ) 基于速率的控制策略：t c p 使用的窗口控制策略有一些缺陷，容易导致 报文的突发，速率受到窗口大小的限制，一个窗口内多个报文的丢失不容易恢复 等。为此，一些研究者提出r b p ( r a t e - b a s e dp a c i n g ) ，将窗口控制和速率控制结合 起来以克服以上缺陷。 ( 4 ) t c p f r i e n d l y 的拥塞控制：很多多媒体的传输要求速率不能剧烈变化，但 1 1 江苏大学硕士学位论文 是也要对网络中的拥塞做出反应，并和t c p 的传输保持公平。t c p f r i e n d l y 定 义为：长时间的吞吐量不超过相同条件下t c p 连接的吞吐量。针对这个需求提 出了t c p f r i e n d l y 的拥塞控制，它使用基于速率的控制，速率的计算建立在t c p 吞吐量模型的基础上。 ( 5 ) 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 ) 的使用：端系统通过数据包中网关设 定的标志位检测拥塞，而不完全依赖数据包丢失来判断拥塞的发生。在无线网络 环境中，e c n 的使用有利于将数据包损坏和拥塞导致的数据包丢失区分开来。 2 4 拥塞控制链路算法 在i n t e r a c t 技术发展的初期，拥塞控制的绝大多数功能都在主机端实现的， 对网络中间节点所能发挥的作用考虑较少。但随着