（信号与信息处理专业论文）网络拥塞控制的red改进算法研究.pdf

g ji ：? xf ! 0 独创性声明 1 1 1 1 1 11 1 11 1 1i i i l l l l l l li i iiliii y 1713 4 7 9 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 论文使用授权 口年s 玛 ；1 日 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：童j 望：叠导师签名： 日期： 如卜年歹月习日 t j 卜 摘要 摘要 由于现有网络业务中自相似性的普遍存在，因此在现代高速技术的研究中， 采用自相似模型比传统的m a r k o v 模型更能准确的描述实际业务特性。并且业务的 自相似性对队列系统和网络性能都产生了一些意想不到的影响，而基于传统模型 下的网络性能结论和网络设计策略不能完全适用于具有自相似业务的高速网络。 随着网络的迅速发展，自相似业务对网络的设计、控制、分析和管理都提出了更 为严峻的挑战。因此，在自相似业务流量下，开展拥塞控制策略的研究对满足 i n t e m e t 网络的发展有着十分重要的意义。 随机早丢弃算法( r a n d o me a r l yd e t e c t i o n ，r e d ) 是f l o y d 在9 0 年代早期提出 的，它是基于传统的泊松分布模型的，其基本思想就是要对到达的分组在拥塞发 生之前，按照某个计算出来的概率进行丢弃，避免拥塞的发生。如何检测拥塞是 算法的关键，其次就是怎样计算分组的分组丢失率。基于传统的网络模型是这种 算法的最大缺点，它往往不能够满足现代网络业务流量普遍呈现自相似特性的要 求。 本文在总结了已有的研究成果基础上，对相关的问题进行细致地分析，研究 如何在自相似业务流量模型下对路由器缓冲区中队列进行管理，改进r e d 算法， 从而更好地避免拥塞发生，提高网络性能，然后提出了一种自相似业务流下的r e d 改进算法。本文所做工作主要体现在以下几个方面： 1 深入学习r e d 算法及其改进算法。 2 深入学习自相似模型的定义、特性、估算、模型、预测及产生原因。利 用n s 2 下基于p a r e t o 分布的o n o f f 模型产生自相似业务流，该模型可以较真实 地反映网络实际环境，生成具有自相似性质的网络业务流量。 3 分析自相似性对网络性能的影响，结合性能评价标准，对经典r e d 算法 进行改进，提出了在任意时刻，每个输入自相似业务流的最大、最小阈值与当前 未使用缓冲区的缓冲区大小成比例，与h u r s t 系数成反比。动态的调整r e d 算法， 使之适应自相似网络业务流量。 4 通过在n s 2 平台上的仿真，对给出算法的平均队列长度、吞吐量、时延 等参数进行对比分析，结果表明，所提出的在自相似业务流下的r e d 改进算法能 够在维持吞吐量的情况下，有效地降低平均队列长度、分组丢失率和端对端时延， 摘要 从而提高网络利用率。 关键词：随机早丢弃算法，自相似，缓冲区分配，平均队列长度，吞吐量，时延 a b s t a r c t a bs t r a c t t h es e l f - s i m i l a rm o d e lt e n d st ob em o r es u i t a b l et h a nt h et r a d i t i o n a lm a r k o vm o d e l i nt h er e s e a r c ho fm o d e mh i g l l - s p e e dt e c h n o l o g y 诵t he x i s t i n go ft h eq u a l i t yo f s e l f - s i m i l a r i t yi nt o d a y sn e t w o r kb u s i n e s s ，勰t h ef o r m e rc a l lp r e s e n tt h ec h a r a c t e r i s t i c o ft h ea c t u a ln e t w o r kb u s i n e s sm o r ea c c u r a t e l y a n dt h eq u a l i t yo fs e l f - s i m i l a r i t yw i l l b r i n gs o m ek i n d so fu n e x p e c t e di n f l u e n c et ot h eb u s i n e s so ft h eq u e u es y s t e ma n dt h e p e r f o r m a n c eo ft h en e t w o r k , w h e r e a st h ec o n c l u s i o n sa n dn e t w o r kd e s i g ns t r a t e g i e s b a s e do nt h et r a d i t i o n a lm o d e lc a nn o tb ee q u a l l ya p p l i c a b l et ot h es e l f - s i m i l a r l l i g h - s p e e dn e t w o r k w i t ht h er a p i dd e v e l o p m e n to fn e t w o r k , s e l f - s i m i l a rn e t w o r k d e s i g n , t r a f f i cc o n t r o l ，a n a l y s i sa n dm a n a g e m e n th a v ep u tf o r w a r dam o r es e r i o u s c h a l l e n g e t h e r e f o r e ，s e l f - s i m i l a rt r a f f i c ，t h ec o n g e s t i o nc o n t r o ls t r a t e g yt oc a r r yo u t r e s e a r c ha c c o r d i n gt ot h ed e v e l o p m e n to fi n t e m e tn e t w o r k 、析t l lg r e a ts i g n i f i c a n c e f l o y dp r o p o s e dt h ef i r s tr a n d o me a r l yd e t e c t i o n ( r e d ) a l g o r i t h m , i ti sb a s e do n t h et r a d i t i o n a lp o i s s o nm o d e l a n di t sb a s i ci d e ai st i l a td i s c a r d i n gt h ed a t ag r o u p a c c o r d i n gt oac e r t a i np r o b a b i l i t ym e c h a n i s md u r i n gt h ep e r i o do fc o n g e s t i o no c c u r so f t h ee a r l yg r o u pa r r i v a l ，i no r d e rt oa v o i dc o n g e s t i o n t h ek e yp o i n ti sh o wt od e t e c t c o n g e s t i o n , a n dh o wt oc a l c u l a t et h ep a c k e td r o pp r o b a b i l i t y b u ti t i sb a s e do nt h e t r a d i t i o n a lp o i s s o nm o d e l ，s oi ti sn o ts u i t e df o rn e t w o r kt r a f f i c 谢ms e l f - s i m i l a r i t y c h a r a c t e r i s t i c s t l l i sp a p e rs u m m a r i z e st h er e s e a r c hr e s u l t sh a v eb e e nb a s e do nt h er e l e v a n ti s s u e s a n dc a r e f u la n a l y s i so fh o wt om o d e ls e l f - s i m i l a rt r a f f i cq u e u eo nt h er o u t e rb u f f e r m a n a g e m e n t , i m p r o v e dr e da l g o r i t h m ，t ob e t t e ra v o i dt h ec o n g e s t i o no c c u r sa n d i m p r o v en e t w o r kp e r f o r m a n c e ，a n dt h e np r e s e n t sas e l f - s i m i l a rt r a f f i cr e da l g o r i t h m n l e p r i m a r ys t u d i e sa r el i s tb e l l o w 1 r e s e a r c ht h er e da l g o r i t h ma n di m p r o v e da l g o r i t h m 2 r e s e a r c ht h ec a b s e so fs e l f - s i m i l a rc h a r a c t e r i s t i c s ，p r o p e r t i e s ，e s t i m a t i o n ， m o d e l i n g ，p r e d i c t i o n u s i n gt h eo n o f fm o d e lb a s e do np a r e t od i s t r i b u t i o nu n d e rt h e n s 2 ，g e n e r a t e ds e l f - s i m i l a rt r a f f i c 1 1 1 i sm o d e lc a l lt r u l yr e f l e c tt h e a c t u a ln e t w o r k e n v i r o n m e n t , g e n e r a t eas e l f - s i m i l a rn a t u r en e t w o r kt r a f f i c i i i a b s t a c t 3 a n a l y s i so fs e l f - s i m i l a r i t yo nn e t w o r kp e r f o r m a n c e ，c o m b i n e d 、) ，i t ha q m p e r f o r m a n c ee v a l u a t i o nc r i t e r i a , t oi m p r o v eo nt h ec l a s s i cr e da l g o r i t h mi sp r o p o s e d a t a n yt i m e ，e a c hi n p u to ft h el a r g e s ts e l f - s i m i l a rt r a f f i c ，t h em i i l i m u mt h r e s h o l da n dt h e c u r r e n tb u f f e ri sn o tu s e dp r o p o r t i o n a lt ot h es i z eo ft h eb u f f e rz o n e ，a n dt h eh u r s t c o e f f i c i e n ti si n v e r s e l yp r o p o r t i o n a l d y n a m i ca d j u s t m e n to fr e da l g o r i t h mt oa d a p t s e l f - s i m i l a rn e t w o r kt r a f f i c 4 f i n a l l y , c o m p a r et h ep a r a m e t e ro f t h en e t w o r ks u c ha st h ea v e r a g eq u e u el e n g t h , n e t w o r kt h r o u g h o u t ，n e t w o r kd e l a y e t ct h r o u g ht h es i m u l a t i o nb a s e do nt h en s 2 s i m u l a t i o np l a t f o r m t h er e s u l t ss h o wt h a tt h ep r o p o s e ds e l f - s i m i l a rt r a f f i co fn e wr e d a l g o r i t h mc a ni m p r o v en e t w o r ku t i l i z a t i o n ，s t a b i l i t yt h ea v e r a g eq u e u el e n g t hn e t w o r k t h r o u g h p u ta n ds o m eo t h e rn e t w o r kp e r f o r m a n c e k e y w o r d s ：r a n d o me a r l yd e t e c t i o n ，s e l f - s i m i l a r , c a c h ea l l o c a t i o n , t h ea v e r a g eq u e u e l e n g t h , t h r o u g h p u t , d e l a y i v 目录 目录 第一章引言_ 1 1 1 课题的提出和意义1 1 2 网络拥塞控制研究现状和趋势2 1 3 本文的主要研究工作3 第二章拥塞控制及主动队列管理5 2 1 拥塞与拥塞控制5 2 2 队列管理技术6 2 3 随机早丢弃算法r e d 及其改进算法。8 2 3 1 随机早丢弃算法r e d 8 2 3 2r e d 改进算法a r e d 1 l 2 3 3r e d 改进算法b l u e 一13 2 4a q m 研究成果和下一步研究方向14 2 5 本章小结1 4 第三章长相关及自相似介绍。16 3 1 自相似概念产生背景。1 6 3 2 长相关和自相似的相关定义及定理。1 7 3 3 自相似过程的性质18 3 4 自相似性对网络性能的影响2 0 3 5 本章小结2 1 第四章自相似模型下基于路由器缓冲区的r e d 算法改进2 2 4 1 几种r e d 改进算法2 2 4 2 自相似业务流下的r e d 算法改进2 3 4 2 1 算法设计要求和性能评价标准2 3 4 2 2 缓冲区溢出公式2 4 4 2 3 缓冲区大小的影响。2 5 4 2 4 一种基于自相似业务流的动态缓冲区管理r e d 算法b h r e d 2 6 4 2 5 路由器缓冲区剩余大小和h u r s t 系数与最大、最小阈值关系2 9 4 3 本章小结31 v 目录 第五章r e d 改进算法仿真试验及分析。3 2 5 1 试验环境及工具。3 2 5 1 1n s 2 及其仿真过程3 2 1 ；1 2g a w k 3 3 1 ；1 3g n u p l o t 3 4 5 2 建立自相似流量模型3 4 5 2 1 生成自相似业务流的方法3 4 5 2 2n s 2 仿真中生成自相似业务流的方法3 5 5 2 3 建立自相似流量网络仿真模型3 6 5 3 仿真算法的具体实现。3 7 5 4 仿真结果及性能分析。3 9 5 4 1 轻负载下仿真结果及性能分析3 9 5 4 2 重负载下仿真结果及性能分析4 5 5 5 本章小结5l 第六章结论及展望5 2 6 1 本文的主要工作5 2 6 2 进一步的工作5 3 致谢5 4 参考文献5 5 作者攻硕期间取得的成果5 9 v i 第一章引言 1 1 课题的提出和意义 第一章引言 随着互联网上的应用和用户在不断快速地增长，互联网的规模也在不断扩大， 如果不在网络中使用拥塞控制算法，如果发生拥塞崩溃，将会导致网络性能的急 剧下降。因此拥塞已经成为了一个十分重要的问题 1 1 。在互联网中使用合适的拥塞 控制算法对于互联网的稳定具有十分重要的意义。根据算法的实现位置，可以将 拥塞控制算法分为两大类：源算法( s o u r c ea l g o r i t h m ) 和链路算法( l i n k a l g o r i t h r a ) 闭。链路算法的研究目前集中在“主动队列管理”( 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 pt a i l ，d t ) 相比，a q m 在网络设备的缓冲 溢出之前就标记分组并丢弃。a q m 的一个代表是r e d 算法。 随机早丢弃算法【3 】是f l o y d 在9 0 年代早期提出的，它是基于传统的泊松分布 模型的，其基本思想就是要对到达的分组在拥塞发生之前，按照某个计算出来的 概率进行标记，然后丢弃，来避免拥塞的发生。如何检测拥塞是算法的关键，其 次就是怎样计算分组的分组丢失率。基于传统的网络模型是这种算法的最大缺点， 它往往不能够满足现代网络业务流量普遍呈现自相似特性的要求。 d v w i l s o n 、w e l e l a n d 等人的一系列研究成果【4 j 表明：网络业务在长的时间 尺度下具有正的自相关特性，也就是业务流在前一时期处于什么状态，在接下来 的一段时间将仍然处于这种状态的概率会很大。也就是说分组在到达缓冲区时进 行排队，如果已等待则下一时见仍处于等待的概率将大于非等待的概率。这种特 性叫做“长期记忆”，它对业务流特别是突发性业务流的传输将造成严重影响。原有 模型对于排队性能的估计、拥塞控制、网络流量控制、分组丢失率的预测等方面 过于乐观，导致理论与实际的巨大偏差。经过大量的实验研究和分析，自相似模 型能够较好地解决上述的问题，但由于自相似问题数学上固有的难度，仿真测量 和数值方法仍然是目前的主要研究方向。 自相似性对网络性能有很大的负面影响【5 1 。一般来说，当输入业务流是自相似 业务流时，分组丢失率和排队时延都会高于短相关业务流的情况，增加缓冲区容 量和链路带宽可以一定程度上减小分组丢失率和排队时延。而且自相似程度越高， 分组丢失率和排队时延就增加越明显。如果增大缓冲区容量，能够减小分组丢失 电子科技大学硕士学位论文 率，但是同时也让排队时延增大；相反地，如果提高网络带宽，则可以同时减小 分组丢失率和排队时延，但会让成本增加。研究表明，自相似性越大，如果采取 相应的措施来改善网络性能，所得到的收益也会成倍增加。在网络的规划设计中， 可以根据网络规划成本、收益等需求，结合对最大时延、分组丢失率地限制等网 络性能要求，建立合适的网络排队模型和使用计算机网络仿真的形式去确定最好 的缓冲区大小和瓶颈链路带宽等网络配置参数。 由于与传统模型的结论相比，自相似业务流模型下的网络性能会有较大差异， 特别是分组丢失率、时延和吞吐量等网络参数，使得自相似业务流模型下的网络 管理、拥塞控制、协议设计、业务监督等需要进行深入研究【6 j 。系统根据服务所需 的系统资源进行分配，并满足各种约束条件，如时延时间约束、缓冲区空间约束， 以及保证数据传输吞吐量的带宽约束等。另一方面，网络用户希望能有服务质量 ( q u a l i t yo fs e r v i c e ，q o s ) 保障，如能提供较大的带宽、较低的分组丢失率、满 足端到端时延和抖动限制。要达到最佳的利用网络资源，需要根据业务流的特点 确定所需的各种资源。 随着网络的不断发展和进步，自相似业务流下对网络的理论分析、算法设计 和管理控制等都提出了更高地要求。因此，研究在自相似业务流量下的主动队列 管理算法改进有着非常重要的意义。 1 2 网络拥塞控制研究现状和趋势 近年来，随着对网络通信量的研究，人们发现传统的m a r k o v 模型或者b e r n o u l l i 过程并不能正确描述互联网的通信量，实验的测量数据表明实际的网络业务流在 很长的时间范围内都具有自相似性，即业务到达是长时相关的 7 1 。自从1 9 9 3 年以 来，许多研究成果已经表明：在多种实际网络中数据传输的模式可由自相似过程 很好的描述。所有这些测量分析研究都揭示了当前网络业务具有统计上的自相似 特性，不论网络的拓扑结构、用户数量、服务类型如何变化，这种自相似性始终 存在。 由于现有网络业务中自相似性的普遍存在，因此在现代高速技术的研究中， 采用自相似模型比传统的马尔科夫模型更能准确的描述实际业务特性【8 j 。并且业务 的自相似性对队列系统和网络性能都产生了一些意想不到的影响，而基于传统模 型下的网络性能结论和网络设计策略不能完全适用于具有自相似业务的高速网 2 第一章引言 络；随着网络的迅速发展，自相似业务对网络的设计、控制、分析和管理都提出 了更为严峻的挑战。因此，在自相似业务流量下，开展拥塞控制策略的研究对满 足l n t e m e t 网络的发展有着十分重要的意义。 目前已有的主动队列管理算法都是以经典的短相关流量为研究背景，最近十 多年的大量研究结果表明，现代网络流量的一个关键特性是自相似或分形，即网 络流量在绝大部分时间尺度范围内具有统计的自相似性和重尾特性。自相似的普 遍存在给目前的主动队列管理算法带来新的困难，引起研究人员的高度重视。 无论是r e d 还是a r e d ，只要算法参数设定，输入业务流不管是泊松流，还 是自相似流，其队列长度的波动规律基本相同。而自相似业务流与传统泊松流对 网络性能的影响大不相同，即便是自相似流，当h u r s t 系数不同时，其占用链路容 量、队列长度、队列溢出概率也不同，因此，r e d 算法需要考虑网络流量的自相 似性。对于r e d 各种改进算法的学习，其中绝大多数算法的研究在很大程度上是 依赖于直觉的、针对局部的，缺乏系统的理论体系作为指导 9 1 。通过对网络系统建 模，应用控制理论实现算法的分析和设计，这将是值得进一步探索的一个研究方 向。 由于现代网络的复杂性使得现代的控制算法的研究不应该仅局限在源端的 t c p 拥塞控制或链路中的口拥塞控制，随着人们对网络研究的深入，实现各种算 法有机融合，才能获得最佳的网络性能。例如e c n 和r e d 算法的有效结合。 1 3 本文的主要研究工作 论文的研究目的正是基于如上考虑提出，在总结已有的研究成果的基础上， 对相关问题进行分析，研究如何在自相似业务流量下对缓冲区的队列进行管理， 改进r e d 算法，更好的避免拥塞的发生，提高网络传输性能。具体研究内容如下： ( 1 ) 深入学习现有的r e d 算法及其改进算法，分析现有算法的优点及不足； ( 2 ) 网络自相似性的理论学习，从自相似性的发现入手，深入学习自相似特性 的定义、特性、估算、模型、预测及产生原因。利用n s 2 下基于p a r e t o 分布的o n o f f 模型产生自相似业务流，该模型可以较真实地反映网络实际环境，生成具有自相 似性质的网络业务流量： ( 3 ) 分析自相似性对网络性能的影响，结合a q m 性能评价标准，对经典r e d 算法进行改进，使之适应自相似网络业务流量。 3 电子科技大学硕士学位论文 ( 4 ) 通过仿真说明理论分析的正确性，并与原有算法进行比较。 4 第二章拥塞控制及主动队列管理 第二章拥塞控制及主动队列管理 2 1 拥塞与拥塞控制 网络拥塞的一般定义是指当路由器缓冲区内排队的分组超过某个限度时，缓 冲区的分组溢出，造成路由器丢弃分组【l o 】。从另一个角度去看网络拥塞，是指网 络中存在的分组超过一定数量，网络负载过大使网络性能下降。网络拥塞产生最 主要是因为没有足够大的可使用网络资源，其中包括缓冲区容量、内存、处理器 处理效率、链路带宽大小等，其中的一个或几个方面的资源不足都可能引起拥塞。 如果只针对一个具体的数据流，在一定时间内，如果对其控制不够，当需求的资 源超过了可使用的网络资源，就会造成拥塞。所以拥塞发生的直接原因是相对不 足的网络资源造成的，而网络拥塞会发生在不同的位置，这也反应了互联网网络 资源分配的不均衡性。互联网的不均衡性如图2 1 所示。 图2 - 1 互联网的不均衡性 ( b ) 图2 1 体现了网络资源分配的不均衡。图2 1 ( a ) 中，某一时刻s 源端以1 m s 的速率发送数据，d 是数据接收端，r 是网关，由于瓶颈链路的出现，在r 处会 出现网络拥塞，由于带宽分布的不均衡性造成了网络拥塞。图2 1 ( b ) 中虽然带 宽是一样的。但是如果发送端a 和b 同时向c 发送数据，发送速率都是1 m s ， 在r 处也会出现拥塞。上图可以得出，网络中广泛存在的流量分布和资源分配不 均衡造成了网络拥塞，而要解决网络拥塞问题，不能只通过单独的增加资源来实 5 电子科技大学硕士学位论文 现。 拥塞控制的含义【l l 】是，当拥塞发生时网络结点做出判断并响应或者采取必要 的措施来避免拥塞的发生。由定义知道拥塞控制包括拥塞控制和拥塞避免两个方 面。其中拥塞控制是一种响应机制，主要是在拥塞发生后采取合适的方法将其恢 复；而拥塞避免则是一种主动机制，与拥塞控制不同的是，拥塞避免能在拥塞发 生之前，提前进行控制，避免网络进入拥塞。现在的最典型的拥塞控制机制是传 输控制协议，它主要实现在网络传输层。其实，早期的传输控制协议只有流控制 机制，而没有拥塞控制机制，接收端通过应答分组通知发送端，它能够接收的分 组数量，以此来限制发送窗口的变大。它只考虑了接收端的接收能力却没用考虑 网络中的传输能力是否能够应对过大的数据流，由此造成了拥塞崩溃的发生。在 1 9 8 6 年1 0 月的一天，l b l 和b e r k e l e y 分校之间的网络数据吞吐量【1 2 j 从3 0 多k b p s 下降到了仅仅3 0 b p s ，这也是网络中的第一次拥塞崩溃。在这以后，拥塞控制越来 越受到网络研究领域的重视。 拥塞控制需要网络应用提供满足较小时延和分组丢失率要求的应用，这就是 服务质量的要求。衡量拥塞控制机制性能主要用以下几个指标：分组丢失率、吞 吐量、链路利用率、时延、时延抖动。 传输控制协议( t r a n s m i s s i o nc o n t r o lp r o t o c o l ，t c p ) 中的拥塞控制机制是使用 率最多的拥塞控制源算法1 1 3 1 。而依靠节点之间执行拥塞控制的机制被称为端到端 拥塞控制，它与t c p 协议类似。队列管理算法是链路算法中最主要的，其中尾部 丢弃队列管理算法是其中最简单的，它只需要在缓冲区中分组满时全部丢弃随后 到达的分组。但是这些拥塞控制算法容易导致很多问题，诸如高分组丢失率、全 局同步、长时延等，链路算法需要进一步加强，必须修正尾部丢弃算法的性能不 足，改进端到端拥塞控制性能。 2 2 队列管理技术 拥塞避免和拥塞恢复是队列管理技术的两大分类。传统的尾部丢弃算法由于 实现简单，只是在缓冲区分组满时丢弃后来到达的分组，所以在互联网上应用十 分广泛，但是这种算法存在很多严重的不足，以下将一一分析。 首先是死锁问题【1 4 】：尾部丢弃算法在某些时候，会让某个或几个流占据全部 队列空间，使其他的流的分组不能进入队列，造成死锁。 6 第二章拥塞控制及主动队列管理 其次是满队列问题【1 5 j ：尾部丢弃算法，会造成队列长度在某个时间段内完全 充满，导致突发数据流的全部丢弃，还会由于队列中排队等待的数据过多让端到 端时延急剧上升，这与队列管理最重要的要求之一降低稳定状态时的队列长度相 违背。这些都是由于尾部丢弃算法只在队列满时才发拥塞信号造成的，如果遇到 突发数据流，很容易长时间满队列。 最后是全局同步问趔1 6 j ：因为互联网上数据流具有突发性，到达路由器的分 组也具有突发性，当队列满的时候，在短时间内，会有大量的包连续的被丢弃， 受此影响，发送端会同时收到拥塞信号从而减小数据的发送，下一段时间内，网 络负载又将急剧下降，导致网络利用率的降低，而随后发送端又会加大数据的发 生，造成又一次的网络拥塞，这种现象循环下去，严重的影响了网络资源的利用 和效率。 有人又提出了一种新的队列管理算法前端丢弃【1 7 1 ( d r o pf r o mf r o n t ) ，从字面 意义理解这种算法与尾部丢弃算法类似，它也是在缓冲区中分组满时进行丢弃， 与尾部丢弃不同的是，它是从队列前端开始丢弃分组，因此它可以防止死锁和一 定程度上改善公平性。还有一种算法随机丢弃【l 引( r a n d o md r o p ) ，这种算法在缓 冲区中分组满时，如果有新的分组到达，它会在队列中随机丢弃一个分组。但是 这些拥塞控制算法都是在拥塞出现之后才采取措施，因此属于拥塞恢复算法，也 就是被动队列管理( p a s s i v eq u e u em a n a g e m e n t , p q m ) 。 因为被动队列管理的这些不足，端到端控制研究的重点逐步转移到主动队列 管理【1 9 j 。与被动队列管理不同，主动队列管理能在拥塞发生之前作出反应，防止 拥塞的发生。预见到拥塞可能发生，它一般是采用分组标记来通知发送端降低发 送速率。这种算法可以在拥塞避免的同时消除对突发业务的歧视，也能很好的避 免全局同步现象的发生，即使存在非协作流，也可以减小队列分组丢失率和时延。 目前a q m 主要的目标是在保证高吞吐量的同时减小排队时延。a q m 需要解 决的主要问题主要包括以下几个方面【2 0 】： ( 1 ) 怎样在提高吞吐量和降低时延之间做出最好的平衡，同时维持缓冲区中较 小的队列长度。 ( 2 ) 怎样避免多个t c p 连接中队列溢出而造成同时进入慢启动状态。 ( 3 ) 对于多种业务流，如间隙性、突发性和持久性等业务流，怎样公平的对待。 ( 4 ) 怎样做到提前预测路由器会发生拥塞，然后再通过随机丢弃或者标记分组 的形式来通知发送端采取降低发送速率等措施，避免可能会出现的拥塞。 1 9 9 3 年6 月，f l o y d 提出了随机早丢弃算法，当时这种算法是为了解决互联网 7 电子科技大学硕士学位论文 中网关对突发性业务流的偏见而产生不公平现象提出来的。由于r e d 工作得很有 效，i e t f 将其推荐为互联网中路由器的唯一候选算、法【2 1 1 。 2 3 随机早丢弃算法r e d 及其改进算法 2 3 1 随机早丢弃算法r e d r e d 算法是f l o y d 2 1 在1 9 9 3 年提出来的，它是在路由器出实现的拥塞避免算 法。此算法通过检查路由器缓存内分组的平均队列长度，在检测到网络拥塞的早 期征兆时，也就是路由器的平均队列长度超过一定门限之后，根据一定的概率丢 弃某些到达路由器的分组，而不是等到已经发生网络拥塞后才将所有在队列尾部 的分组全部丢弃，这样就就能在拥塞发生之前及时通知发送端进行合适的调整， 降低发送速率等，避免发生拥塞而丢弃更多的分组。此算法的实现比较简单。 平均队列长度主要采用了和计算平均往返时延r t t 类似的加权平均的计算方 法，这样可以有效避免全局同步问题，并支持突发性业务流。r e d 算法现今已成 为路由器中默认的拥塞避免算法。与尾部丢弃算法相比，r e d 在队列管理上增加 了两种新机制【捌： ( 1 ) 利用合适的概率判断可能发生的拥塞，从而丢弃部分分组来预防，而不是 像尾部丢弃一样等队列全满时再丢弃到达的分组。 ( 2 ) 通过加权平均的方法计算平均队列长度而不是瞬时队列长度来调整分组 丢失率，有效吸收突发性业务流。 随机早期丢弃算法的设计尽可能达到以下标准【2 3 】： ( 1 ) 避免全局同步现象的发生； ( 2 ) 即使在传输层缺乏有效配合的协议时，也能控制平均队列长度来避免拥塞 发生。 ( 3 ) 避免对突发性业务流的偏见，吸收尽可能多的短暂突发性业务流； ( 4 ) 尽量减小排队时延和分组丢失率； 为了达到以上几点标准，r e d 算法采用了基于时间的平均队列长度计算分组 丢失率，并在分组进入路由器之前随机进行丢弃。算法不需要在路由器中维持每 个流的状态信息。 根据前文论述，r e d 算法可以分为两个部分来计算，首先是平均队列长度地 计算，根据平均队列长度的大小来估计拥塞的程度，其次就是对分组丢失率地计 8 第二章拥塞控制及主动队列管理 算。 ( 1 ) 平均队列长度地计算 互联网的数据流具有突发性的特点，因此路由器中的队列长度经常会出现很 快的起伏变化。如果按照瞬时队列长度来计算分组丢失率，很可能出现一些不合 理的情况。因此，r e d 算法计算平均队列长度a v g q 时，采用了和计算平均往返时 延r 1 盯类似的加权平均的计算方法，式( 2 1 ) 给出了平均队列长度a v g q 的计算方 法： a v g q = 1 - w ) 牛a v g q + q 奉w ( 2 - 1 ) 公式( 2 1 ) 中，权值用w 表示，且0 w 1 ，采样时的瞬时队列长度用q 表示。 瞬时队列长度和平均队列长度随时间变化的关系如图2 1 所示，可以看出短暂拥塞 使实际队列长度暂时增加，数据的突发性将不会使平均队列长度有很大的变化， 这样做的好处是过滤短期的队长变化，反映长期的网络状态【2 4 j 。 平均队列长度的计算公式中，权值w 对应低通滤波器的时间常数，w 的大小 会影响路由器对于输入流变化的反应程度。所以，w 值的大小非常重要，当权值w 过大，平均队列长度就会对瞬时队列长度地变化相当敏感，从而不能有效的过滤 短期拥塞；相反，权值w 过小，平均队列长度就会对瞬时队列长度地变化反应过 慢，不能及时合理地反映拥塞状态，这样，路由器就不能很好的发现将会发生的 拥塞。所以，权值w 的设定，应该根据具体情况的不同而不同，一般情况下，大 小是根据路由器中允许发生的突发性业务流持续时间和大小来设置的。 畏 母 器 公 图2 1r e d 算法的平均队列长度和队列长度变化曲线 9 电子科技大学硕士学位论文 ( 2 ) 分组丢失率地计算 平均队列长度地计算目的是为了反映合理的拥塞状态，然后根据拥塞的状态 计算分组丢失率，进行标记丢弃分组，来有效地将平均队列长度稳定在合适的值 附近。因为平均队列长度的计算是基于时间的，某些时候，瞬时队列长度可能大 于平均队列长度，当队列满时，丢弃到达的分组。 m i l l 瞒和m a x ，。分别是r e d 算法中和队列长度有关的最小、最大阈值。当路由 器中有分组到达时，r e d 算法根据前面的计算公式计算出平均队列长度a v g q 。设 平均队列长度达到最大阂值时的分组丢失率为m a x 。，0 m a x 。 n l a x 曲时，丢弃所有到达的分组，分组丢失率只等于1 ；当 a v g q m i n 曲时，不需要丢弃分组，分组丢失率等于o ；当m i n 埔a v g q m a x 曲时， 计算概率只，用概率只标记分组【2 5 1 。 按照下列公式计算概率： 忍= m a x p * ( a v g q m i n 曲) ( m a x , h - m i n 晴) ( 2 - 2 ) e o = 只( 1 - c o u n t 幸只) ( 2 3 ) p r o b m a x p o 1 1 i m a x 胁 嘲 图2 - 2r e d 平均队列长度和分组丢失率关系 根据在互联网上的实践经验，分组丢失率只的计算方法又有了一些改变，目 的是为了使丢包的间隔更加均匀，尽量避免连续地丢包【2 6 】。因此引入c o u n t 表示新 到达的分组有多少个已经进入了队列而没有被丢弃，由公式( 2 3 ) 5 - 丁知，随着c o u n t 的增大，下一个分组可能被丢弃的概率也会缓慢变大。 l o 第二章拥塞控制及主动队列管理 对队列管理而言，网络吞吐量和排队时延始终是一对矛盾的关系【2 7 】。当平均 队列长度能在时延和网络吞吐量之间做出合理的选择，使得总体性能最优化，成 为理想平均队列长度。为了尽量达到理想的平均队列长度，可以通过调整最大、 最小阈值来实现。一般情况下，m a ) 【。一r a i n 咖的值应该不小于一个回路响应时间内 的平均队列长度增加值，这么设置可以有效避免路由器因为丢弃过量的分组而导 致全局同步现象的产生。根据目前互联网上业务流的特点，一般可以将最大阈值 m a x 晴设置成3 倍最小阈值m a n ，。大小。 r e d 算法使得路由器可以更好的管理其队列长度，但多长的队列是最佳长度 仍然有待于进一步研究讨论。 2 3 2r e d 改进算法a r e d 由于互联网中业务流的突发性，r e d 的参数设置对算法性能的影响相当大， 特别是权值w 的影响。权值w 大小的设置，关系着r e d 算法在能及时响应拥塞 来减小长时间的拥塞同时也可以忽略掉一些瞬时业务流，也就是影响平均队列长 度m , g q 对瞬时队列长度变化而做出变化的敏捷程度。但是，在同一队列中t c p 流 的个数会影响长时间拥塞的增加速度，在t c p 流个数很少的情况下，权值w 设置 得比较小，可以让拥塞的出现相对缓慢；但是，如果权值w 过大，使r e d 算法能 响应足够多的t c p 流，在只有少数t c p 流通过链路的时候，会让分组丢失变得过 于主动。 基于以上考虑，f l o y d 等提出了r e d 的改进算法：a r e d 算法，此算法可以 根据网络流量的变化来配置适当的参数。a i l e d 算法能根据最近的拥塞记录适当 的调整算法中的参数。a r e d 算法中，如果在同一队列中有n 个活动的连接，当 n 增加时，r e d 需要变得更积极，于是根据a v g q 最近的变化动态的改变m a x 。 如果删下降到低于m a n 曲，需要计算一个更保守的m a x ， 直m a x ，= m a x p 木a 。如 果铡蛔增加到大于m a ) ( 埔，则需要计算一个更加积极的m a x p n m a x p = m a x p * 卢。 a 、卢分别为减少因子和增大因子，其算法如图2 2 所示。 电子科技大学硕士学位论文 m a x ， o 图2 2a r e d 队列长度和分组丢失率关系 a r e d 相对于r e d 来说改动很小，它在保留了r e d