（计算机应用技术专业论文）red拥塞控制算法的分析研究及改进.pdf

南京邮电大学锁。t ：t i t f 究生学位论文 摘螫 摘要 随着l ) 嘲规模的扩大，i n t e r n e t 用户和应用在快速增长，网络拥塞已经成为一个 十分重要的问题，有效的拥塞避免控制机制对于网络的发展应用十分重要。为了减轻当 前i p 网的阻塞现象，主干网路由器必须采取有效的策略来避免和控制网络拥塞，从丽保 证整个网络的稳定性。 目骑，许多路由器采剧随机早期检测( r e dr a n d o me a r l yd e t e c t i o l l ) 的力法束进 行阻塞控制。r e d 是一种广泛应用于包交换网络的主动队列管理技术，它通过监视路由 器的平均队列长度，在缓冲区满之前主动丢包，降低路由器的丢包率，维持较小的队列 长度，并公平地处理包括突发性、持久性和间隙性的各种t c p 业务流，避免多个t c p 连 接出予队列溢n ；两造成嗣步进入“慢启动”状态，在高吞吐量和低时延之恻进行合理平 衡，因而提高了网络的利用率，较好地解决了全局同步问题和对突发性业务的服务特别 差的问题。 传统r e d 的性能很大程度上依赖于其参数是否适合于当前的流量特征，在网络流量 发夸大规模变化时容易引起网络不稳定，同时，系统的最优队长也由各种数揍：流的特性 决定。沦义根撕、自i 嘲络负载的特征，系统地探讨了当r e d 算法的参数发，j ! 变化时， r e d 算法对网络性能的具体影响，给如了在特定的网络环境下选择和调整r e d 参数的 方法，提高r e d 的适应性；在此基础上，根据排队论，利用随机过程的方法对r e d 算 法进行了优化改进，提出了p r e d ( p r o m o 联dr e d ) 算法，在p r e d 算法中增加一 个平均队长参数m i d t h 和与它对应的丢包率p m i d ，使r e d 算法的丢包率曲线从三段变 为扩鸳段，平滑。了丢包性能并在相同负载下减小了丢包率，使r e d 算法的参数选择具有更 加合理的依掘，同时改进了平均队长的计算方法，减少了平均队长的抖动，提高了算法 的性能。这一部分的工作是作者创新性的研究结果，改变了以往按照经验启发式地选择 参数的模式；最后，运用o p n e t 仿真工具对r e d 及其改进算法进行建模分析，比较了改 进后的p r e d 算法和传统r e d 算法的平均队长和丢包率性能曲线，证明了侔肯对r e d 算法改进的j f 确性和改进算法的先进性。 1 i 题b d ：捌采控制，随机早期检测，性能，平均队长，丢包率 耱塞酾氇入学酸i + i o l f u l - 学僦沦文 a b s t r a c t a b s t r a c t w i t ht h ee x p a n s i o no ft h et c p i pn e t w o r k ，b o t ht h en u m b e ro ft h eu s e r so ft h ei n t e r n e t m dt h ea p p li c a t i o no ni ta r ee x p e r i c i n gar a p i di n c r e a s e 。s i n c et h ep r o b l e mo ft h en e t w o r k m n g e s t i o nb e c o m e si n c r e a s i n g l ys e r i o u s ，i th a sb e e nm u c hi m p o r t a n tf o r t h en e t w o r kt o d e v e l o pa m o r ee f f i c i e n tc o n g e s t i o na v o i d e n c e c o n t r o lm e c h a n i s m i no r d e rt oa l l e v i a t et h e c o n g e s t i o no nt h ei n t e r n e t ，t h er o u t e rm u s tt a k ea ne f f i c i e n tm e a s u r e t oa v o i da n dc o n t r o lt h e c o n g e s t i o n ，o nt h eb a s i so fw h i c ht h en e t w o r kc a nm a i n t a i nt h es t a b i l i t y m a n yr o u t e r st a k eac o n g e s t i o nc o n t r o lp l i c yw i t ht h er e d ( r a n d o me a r l yd e t e c t i o n ) a l g o r i t h m 。r e di sak i n do ft h ea q m ( a c t i v eq u e u em a n a g e m e n t ) t e c h n o l o g y t h a th a sb e e n w i d e l ya p p l i c a t e di nt h ep a c k e ts w i t c hn e t w o k i tm o n i t o r st h eq u e u el e n g t ha tt h eg a t e w a y , d r o pt h ea r r i v e dp a c k e tr a n d o m l yb e f o r et h ec a c h e so v e r f l o w t h r o u g ht h i sw a y t h er e d a l g o r i t h mr e d u c et h ep a c k e tl o s sp r o b a b i l i t ya tt h er o u t e ra n dm a i n t a i naf a i r l ys m a l la v e r a g e q u e u el e n g t h 。w h a t s m o r e ，i tp r o c e e d sw i t hav a r i e t yo f t h et c pc o n n e c t i o n sf a i r l y , i n c l u d i n g t h eb u r s t yt r a f f i c ，t h ep e r s i s t a n ta n dt h et i m e dp e r i o dt r a f f i c i tc a na l s oe s c a p et h e “g l o b l e s y n c h r o n i z a t i o n o ft h en e t w o r kc a u s e db yt h ep a c k e 招t h a tb e l o n g st om a n yt c p c o n n e c t i o n s b ed r o p p e da tt h es a m et i m e ，r e s u l t i n gi nm o s to ft h e s ec o n n c t i o n sg e tb a c kt ot h es l o ws t a r t s t a t u si n s t a n t a n e o u s l y t h er e da l g o r i t h mc a ng i v eu saw a yt os h i f tb e t w e e nt h eh i g h t h r o u p u ta n dt h el o wa v e r a g eq u e u i n gd e l a y ，t h e r e f o r ei ti m p r o v et h en e t w o r ku s i n gr a t i o ，a n d s o l v et h ep r o b l e mo fg l o b l es y n c h r o n i z a t i o na n dt h ep r o b l e mo ft h et h eb i a sa g a i n s tt h eb u r s t y l r a m c t h ep e r f o r m a n c eo ft h ec u s t o mr e da l g o r i t h md e p e n d st oag r e a te x t e n to nt h ep a r a m e t e r s s e t t i n gu n d e rt h ec o n t e m p r a r yt r a f f i cl o a d 。i ft h el o a d v a r i e sal o t ，t h ep e r f o r m a n c ew il l e x p e r i e n c ea ，m e a n w h i l e ，t h eo p t i m a lq u e u el e n g t ho ft h es y s t e mi s a l s od e t e r m i n e db yt h e f e a t u r e so ft h et r a f f i cl o a d s 。i nt h i sp a p e r , t h ea u t h o ri n v e s t i g a t e di nt h ea c t u a li m p a c tt h a tt h ep a r a m e t e r sc h a n g i n gh a so nt h e n e t w o r kp e r f o r m a n c eu n d e rt h en e t w o r kl o a d s ，a n dp r o p o s e dt h ew a yo ft h er e dp a r a m e t e r s t u n i n ga c c o r d i n gt ot h el o a d ，i m p r o v et h ea d a p t i v e n e s so ft h er e da l g o r i t h m 。f u r t h e rm o r e ， a c c o r d i n gt ot h eq u e u i n gt h e o r y , t h ea u t h o ri m p r o v e st h er e da l g o r i t h mw i t ht h er a n d o m p r o c e s st h e o r y , p r o p o s e st w op a r a m e t e r sn a m e dm i d t ha san e w t h r e s h o l do ft h ea v e r a g eq u e u e 珏 南泉邮l 乜人学坝1 j 研t 生学位论义 a b s t r a c t s i z ea n di t sp a c k e td r o pp r o b a b i l i t yp m i d i nt h i sw a yt h ep a c k e td r o pp r o b a b i l i t yf u n c t i o n c o n s t r u c t sf o u rp h a s e sr a t h e rt h a nt h r e e ，t h u ss m o o t h e n st h ev a l u eo ft h ef u n c t i o na n dg i v ean e w w a y o f c h o o s i n gt h ep a r a m e t e r st h a ti sm o r er e a s o n a b l e 。w h a t s m o r e ，t h ea u t h o ra l s oi m p r o v e s t h ew a yo ft h ea v e r a g eq u e u el e n g t hc a l c u l a t i n gt h a tr e i n f o r c e st h es t a b i l i t yo fi t ，c o n s e q u e n t l y p r o m o t e dt h ep e r f o r m a n c eo f t h er e d a l g o r i t h m t h e r e f o r et h ei m p r o v e da l g o r i t h mi sn a m e da s t h ep r o m o t e dr e d a l g o r i t h m ，t h a ti st h ep r e d t h i sp r o m o t i o ni sac r e a t i v er e s e a r c hp r o d u c t ，i t a l t e r st h ew a yo ft h ep a r a m e t e rc h o o s i n g w h i c hi nt h ec a s eo fc u s t o mr e di sa c c o r d i n gt ot h e e x p e r i e n c e ，a n di nt h ec a s eo fp r e di sa c c o r d i n gt oac e r t a i nc h a r t t h e r e a f t e r , as i m u l a t i o ni s b u i l tw i t ht h eo p n e tf o rt h ec o m p a r i s i o no ft h ec u s t o mr e da n dt h ep r e da l g o r i t h m ， a n y l i z i n gt h ea v e r a g eq u e u el e n g t ha n dt h ep a c k e tl o s sp r o b a b i l i t yo ft h e m ，a n dp r o v e dt h e c o r r e c t n e s sa n dp r i v i l e d g eo ft h ep r e da l g o r i t h m k e y w o r d s ：c o n g e s t i o nc o n t r o l ，r a n d o me a r l yd e t e c t i o n ，p e r f o r m a n c e ， a v e r a g eq u e u el e n g t h ，p a c k e tl o s sp r o b a b i l i t y 南京邮电大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的 地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包 含为获得南京邮电大学或其它教育机构的学位或证书而使用过的材 料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了 明确的说明并表示了谢意。 研究生签名：西! 进拿日期：姐 南京邮电大学学位论文使用授权声明 南京邮电大学、中国科学技术信息研究所、国家图书馆有权保留 本人所送交学位论文的复印件和电子文档，可以采用影印、缩印或其 他复制手段保存论文。本人电子文档的内容和纸质论文的内容相一 致。除在保密期内的保密论文外，允许论文被查阅和借阅，可以公布 ( 包括刊登) 论文的全部或部分内容。论文的公布( 包括刊登) 授权 南京邮电大学研究生部办理。 研究生签名：。噬避 导师签名： 呼魄蝉 南糸邮电人学倾上研究生学位论文 绪论 绪论 在因特网上，当一个子网或者其中的一部分出现太多分组时，网络的性能丌始下降， 诸如网络延时加大、丢包率上升、吞吐量下降等，这种情况即称为搁塞( c o n g e s t i o n ) 。 导致捌塞出现的原因通常是当前的负载( 临时性地) 超过了( 网络中的某一部分) 资源 的处理能力，或者激用户提供给网络的负载大于网络赘源的容量和处理能力，如网络相 对予负载需求表现为节点存储空浏不足、链路带宽不足、处理器处理速度慢，以及系统 各部分性能不匹配等等，从而导致网络上的包时延增加，丢包率上升，吞吐量下降，直 接使服务质量下降。在处理网络的搠塞问题时一般采用两种方法：一是采取措施预防网 络拥塞，也就是采取流量控制技术：二是采取措施减少已拥塞时的拥塞程度，鼓| 】减少捅 塞时州以及防止捌塞扩散，越至捌塞的消失，也就是采取捌塞控制技术i 博1 。 拥塞控制是一种协调发送端的发送速率和接收端的接收速率一致性的数据传输同步 技术。搠塞控制的任务是确保子网能够处理承载所到达的流量，这是全局性的问题，涉及 各方面的行为，包括所有的主机、路由器及内部的存储转发过程等。在数据传输中，若发 送速率丈予接收速率，接收站就会泉不及处理接收到的数据帧丽产生接收缓冲区溢出，造 成数掘帧的丢失，这种现象称为同步失调，也就是发生了拥塞。若发送速率远小于接收速 率，接收站就会一童处于等待状态，造成介质空闲，介质利用率过低。通过拥塞控制技术 可以有效地解决同步失调和高效利用介质问题。 i n t e r n e t 主要互联协议t c p f l p 的拥塞控制机制( c o n g e s t i o nc o n t r 0 1 ) 对于控制搠塞具 有特别重餮的意义。在t c p 协议中，每个源结点缓慢地增加数掘传输的速率， i 上发现 搠塞就减小速率。曼缓冲区溢出藤出现丢包时可探知搠塞已经发生。此时，目的结点负 责通知源络点发生丢包，并告知中间结点不要再直接给源结点提供任何反馈信息。i p 拥 塞控制是在路由器中实现的，在每个数据包到达路由器时使用排队策略和丢包算法进行 控制，主动队列管理( a q m ) 方案币是为了解决i p 拥塞控制问题所提出的。目前在i n t e r n e t l ：实际使爿j 的捌塞控制机制基本上是建立在t c p 的窗翻控制基础土的。然巍，在i n t e r n e t 如此复杂的异构网络中，让所有用户在i n t e r n e t 应用中都能兼容这种端到端的拥塞控制 是很困难的。因此，网络必须参与资源控制工作。撙层的捐塞控制研究也就成为冒前研 究的热点。r e d ( 随机早期检测) 算法是由f l o y d 等人提出的，作为r f c 2 3 0 9 推荐的 a q m 唯候选算法，也是蹬酶路由器中普遍使爝的q o s 搠塞控铡算法。q 久毓通信楚 3 南京邮电人学顾i ：研究生学位论文绪论 f i 通j 衄形时( 如t c p 流) ，r e d 是一种非常有效的i p 捌塞控制算法。评伊i 算法的t 婴 性能指标包括算法的鲁棒性、稳定性和有效性，具体到拥塞控制算法则表现为丢包率、 排队延时、吞吐量等。本文主要在对r e d 算法的深入研究基础上，论文根据当前网络负 载的特征，系统地探讨了当r e d 算法的参数发生变化时，r e d 算法对网络性能的具体 影响，给f = ；了存特定的网络环境下选择和调整r e d 参数的方法，提高r e d 的适应性： 在此基础l ：，根据排队论，利用随机过程的方法对r e d 算法进 了了优化改进提厂 p r e d ( p r o m o t e dr e d ) 算法，在p r e d 算法中增加一个平均队长参数m i d t h 和与它 对应的丢包率p m i d ，使r e d 算法的丢包率曲线从三段变为四段，平滑了丢包性能并在 相同负载下减小了丢包率，使r e d 算法的参数选择具有更加合理的依据，同时改进了平 均队长的计算方法，减少了平均队长的抖动，提高了算法的性能。这喑b 分的l ：作足作 者创新性的研究结果，改变了以往按照经验启发式地选择参数的模式。然后使用网络仿 真软件o p n e t 对r e d 算法及其改进算法进行了一系列的仿真，并基于仿真实验对两种 算法进行性能比较和分析。 本文共分5 章，第一章综述网络中的拥塞控制，拥塞控制的通用原则、t c p 的捌塞 控制机制。第二章介绍了主动队列管理a q m 算法的相关理论，包括a q m 算法的基本 思想、各种a q m 算法的具体实现，分析讨论了不同的实现算法的性能。第三章介绍了 r e d 算法的提出，详细描述了r e d 算法的实现和参数设置原则，并讨论了各种对r e d 的改进算法。第四章利用随机过程理论分析了传统r e d 算法的性能，提出了适当调整 r e d 算法参数的方法，并基于随机过程理论和排队论对r e d 算法进行改进，推导了改 进r e d 算法的公式。第五章使用网络仿真软件o p n e t 对r e d 算法及其改进算法进行 仿真实验，并对仿真结果进行了比较和分析，得出改进算法的稳定性和效用优于r e d 算法的结论。总结与展望总结全文，展望今后的工作和前景。 4 南京邮i u 人学颂i ：研究生学位论文 第一帝网络拥采拧制综述 第一章网络拥塞控制综述 1 1 拥塞控制的通用原则 在计算机网络这样复杂的系统中可以用控制论的角度来看待拥塞控制的解决方案： 丌环的和闭环的。开环的解决方案试图用良好的设计来解决问题，其本质是从一丌始就 保证问题不会发生，手段包括：确定何时接受新的流量、确定何时丢弃分组及丢弃那些 分组，以及在网络的不同点上执行调度策略，这些手段在作出决定的时候不考虑当自，j 的 网络状念；闭环的解决方案则恰恰建立在反馈环路的基础上，这种方法可以分为曼个部 分，即监视系统检测到何时何地发生了拥塞，将该信息传递到能够采取行动的地方，调 整系统的运行以改正问题。监视子网的拥塞状况时可以采用多种度量标准，包括因缺少 缓存而丢包的百分比、平均队列长度、平均分组延迟等；闭环方案的第二部分可以有多 种实现方法，一种方法是检测到拥塞的路由器给流量源发送一个分组以通告拥塞的发生， 另外也叮以往每个分组中保留一位或一个域用以标志拥塞。为了使收到拥塞信息的土机 能采取适当的行动，必须谨慎地选择时间尺度，选取一个合理的平均值。 当前存在很多拥塞控制算法，总体可以分为开环算法和闭环算法两大类。丌环算法 中类在源端采取行动，另一类在目标端采取行动；闭环算法分为显式反馈和隐式反馈， 其- + - h 参式反馈从拥摩点向源端发送分组以警示源端，隐式反馈中源端利川本地观察到的 现象如分组往返时问来推断拥塞的发生。目前在i n t e r n e t 上实际使用的拥塞控制基本上 是建立在t c p 层的窗口控制基础之上的，即基于窗口的端到端的闭环控制方式，i p 层的 拥塞控制主要在网络中间节点如路由器上及链路上实施资源控制，i p 层所起的作用相对 较小。按照拥摩时包丢弃的方式，又可以将拥塞控制策略分成3 种类型：一是混合式，即 住路由器中1 i 管是哪种数据流，其优先级如何，均共同排队处理，共享同一路由器资源， 如f i f o ，r e d 等；二是分离式，各数据流在路由器中单独排队，如f q ；三是基于部分缓 存共享方式，根据缓存大小设置一个阂值来控制包丢失率。当缓存达到或超过给定阈值 时，只有高优先级数据包才能进行缓存，低优先级数据包则被丢弃，当缓存满时，高优先 级数掘包也被丢弃。 1 2t c p 拥塞控制机制 南京邮电大学颂士研究生学位论文 第一章网络拥臻挖制综矮 t c p 的摊塞控铡f 豫j 采用的是基予窗口的端到端的闭环控制方式。目的节点蒂确地接 收到也历将向信源发确认( a c k ) 信息。每个信源有一个大小可变的窗【1 ，使用窗| i 大小来确定还没有收剐确认信息的龟的数量。当窗口已满，信源在发送个新包静必须 等待个确认信息。t c p 算法有两个重要特征：一个是“自定时特征，当网络出现拥 塞且确认信息出现延迟时自动放慢信源的发送速率；另一个是使用窗翻大小来控制信源 速率，大约每个往返时间发送一个窗口的数据包。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 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 ) 删个核心部分组成。t c p 使用的是加式增加积式减少( a i m d ) 的基于窗u 的端到端的 拥塞控制机制，即如果一个数据包丢失，发送窗口就要减半；否则就简单的增加一个数 据包的发送量。大量的实践证明，这种拥塞控制机制对i n t e m e t 上大批量文件传输等尽 力型( b e s t - e f f e c t ) 服务具有较好的适应性。 以下介绍三种t c p 搠塞控制算法。 1 2 。薹t c p 飘h o e t c p t a h o e 1 】算法主要分为两个阶段：慢扇动和拥塞避免，在t c p 建立连接时，为发 送方增加个拥塞窗i z i ( c w n d c o n g e s t i o nw i n d o w ) 用以控制发送包的数量，并设置一个慢启 动阂值( s s t h r e s h s l o ws t a r tt h r e s h h o l d ) 用以梦f | 定跌慢窟动状态切换到搠塞避免状态。4 开 始，拥塞窗门设置为l ，发方发送一个报文段，并启动定时器，在超时之前收到一个收方应 答响应a c k ，则e w 髓d 相应增加一个报文段大小变成2 ，以此类推c w n d 按照l ，2 ，4 ，8 的指 数规律增长。如果出现响应超时或连续收到3 个以上的重复a c k ，则停止继续增匀h c w n d ， 将s s t h r e s h 设为当l 囊j c w n d 的半( 最小为2 ) ，如采是超时的情况则将c w n d 重新饕为l ，否则 c w n d , 1 4 变。算法f | 1 比较c w n d 弓s s t h r e s h ，当c w n d l b s s t h r e s h 大时将迸入移h 塞避免阶段，即每 收到相应a c k 时对c w n d 只按照线性规律增鸯i 1 c w n d ，直到c w n d 过大，发包数量稿对测终当 前承载能力过多，重新导致超时或重复a c k 。当c w n d 不大于s s t h r e s h 时，则进入慢启动状态。 1 z 2 。i c pr e n o r e n o | 2 l 算法对t a h o e 算法作了改进，增加了快速重传快速恢复机制，即在接连收 到3 个重复a c k 时就断定丢包，进入快速重传阶段，而无需等待定时器超时，接下来 执行的是拥塞避免算法而非慢启动，这就是快速恢复。当收到第3 个重复的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 加上3 倍的报文段大小，此后每收到另+ 个苇复的a c k ， 6 南京邮r 乜人学颂i ：研究生学位论文第常州络拥壤挡制综述 就将c w n d 增加1 个擐文段大小并发送1 个分组 如果新c w n d 允许发送) 。当f 一个确 认新数抛的a c k 到达时，设置c w n d 为s s t h r e s h 。这个a c k 是进行重传后的一个往返时 瓣内对丢失撤文段重传的确认，也是对丢失的分组和收到的第1 个重复的a c k 之闻的 所有中间报文段的确认。这步采用的是拥塞避免，因为当分组丢失时，将当前的速率 减半纛不是鬣为慢感动专露僮。 薹2 3t c p v e g a s v e g a s 3 1 对r e n o 进行了三项改进：首先采用新的重传触发机制，即只要收到一个重复的 a c k 就断定超时，以便及时检测到拥塞：而在慢启动阶段则采用了更加谨慎的方式来增加 c w n d ，以减少不必要的分组丢失；改进“捎 塞避免”阶段的窗口调整算法，通过观察以自u 的t c p 连接中r t t 值改变情况来控制拥塞窗口c w n d ，当r t t 变大时就认为发生拥塞，玎始 减d x c w n d ，如果r t t 变小，就增) 狐l c w n d ，解除拥塞，理想情况下c w n d 就会稳定在一个合适的 值上。这样使拥塞机制的触发不再依靠包的具体传输时延，丽只与r t t 的改变有关。 1 3 本章小结 以上对当翦i n t c m e t 上实行的各种拥塞和流量控制算法原理进行了总体概述，分析、 比较了这些算法的基本性能的优劣。t c p 协议通过窗口机制，以丢包率或排队时延作为 捌塞的度量，进行期塞控制；在整个因特网上，通过分布式的对单个信源传输速率进霉亍 调整，进行流量控制；而流量控制是搠塞控制的一种有效手段，目的是避免链路容量过 载，保涯服务质量，并使网络资源褥到充分的利用。拥塞流量控制算法的鱼相似问题、 稳定性、效率问题以及公平性问题都是有待进一步研究和改进的问题。下一章将对主动 队列管理a q m 算法进行介绍。 7 翻糸邮i 【1 入学倾i ? l l j 究，学位论文第二帝土动队列管胖a o m 箅法办案 第二章主动队列管理a q m 算法方案 2 1a q m 算法概述 主动队列管理a c t i v eq u e u em a n a g e m e n t ( a q m ) 1 4 1 策略是一种拥塞避免机制，它通过 预先主动丢包来向数据源提供早期拥塞通知。数据源可以掘此减小窗口大小( 或者数据 速率) ，以避免进一步的拥塞和丢包。相对于使用丢尾策略的网关路由器只有当缓存满了 之后才进行丢包，a q m 策略为在低的排队时延和高的链接性能之间提供了更多选择的 町能性。仔何以满足某些性能尺度为目的的r e d 参数的设定，都应该建：立在这监参数设 定如何影响特定的性能尺度的研究基础之上。主要思路是根据网络1 1 l 负载的情况刈标记 丢失概率进行动态调整。t c p 拥塞控制机制本质上是端到端的控制机制，它默认为i p 层对拥塞的发生和拥塞的控制不进行任何支持。当前随着i n t e m e t 业务的迅猛发展，仅 依靠单一的端到端的拥塞控制机制不可能有效地解决拥塞问题，另外期望所有用户在 i n t e r n e tj 近川1 一邻遵0 ：这种端到端的拥褒控制也是不现实的，这要求网络本身也必须参j 对资源的管理与控制。基于此，提出了在路由器中采用排队算法和数据包丢弃的策略， 即i p 拥塞控制机制。 2 2a q m 实现算法 2 2 1 先入先出( f i f o ) f i f 0 1 即“先到先服务，意指先到达路由器的数据包就先被传输，如果缓存己满则 丢包。优先级排队对基本f i f o 排队进行了简单改进，它为每个数据包分配一个优先级标志， 在路由器按照不同优先级进行多个f i f o 排队，非空的最高优先级队列优先发送，同一优先 级队列内仍然是f i f o 方式。由于高优先级队列会“抢占 所有其它的队列，因此用户不能 用不受控的方式为自己的数据包指定高的优先级。一些重要的报文如路由更新包往往采用 优先级排队的方式，其优先级由i p 包头的t o s 域定义并由一个特殊的队列保存，这其实是 区分服务思想的一种实现。 2 2 2 随机早检测算法( r e d ) r e d 4 1 算法在路由器监控队列长度，一旦发现拥塞迫近，就通知源端调整捌塞窗口。 它也是通过丢包的方式使源端发现超时或重复应答，隐式通知源端拥塞情况。r e d 算法包 8 南京邮电人学硕：t ：研究生学位论文 第二章主动队列管理a q m 算法方案 含两部分：如何监控队列长度和何时丢弃数据包。首先，r e d 使用类似t c p 计算超时时使用 的杖值w q 束计算平均排队长度a v g = ( 1 一w q ) xa v g + w q q ，其中，o w q l ，q 足采样测 矗时 的排队队长。使用平均队长比使用瞬时值更能精确“捕捉”拥塞情况。r e d 丢弃数引流t - 一 包的概率与这个流在路由器中所获得的带宽成比例，因为一个发送数量相对较大的数据流 可供随机丢弃的数据包的数量也相对较多。因此在r e d 算法中需要考虑公平性。 2 2 3 显式拥塞指示( e c n ) e c n 算法【l 】在源端数据包中嵌入e c n ，由路由器根据网络情况设置c e ( c o n g e s t i o n e x p e r i e n c e d ) 比特位，源端从网络中接收反馈回来的已被c e 置位的数据包，再将随后发出 的数据包标记为“可丢弃 的数据包。改进算法n e w e c n 可通过调整拥塞窗i s l c w n d 大小，纠 证了有长时f n j r t t 的t c p 连接的偏差，改进了共享瓶颈处带宽的公平性。 2 2 4 公平排队算法( f q ) 在f q 【4 】算法中，路由器的每个输出链路( o u t p u t l i n e ) 都对应一个排队队列，对它们按 “轮询”( r o u n dr o b i n ) 方式处理。当有某条输出链路空闲时，路由器就顺次扫描所有队列， 将每队第一个包发出。当某个流的数据包到达过快时，其队列就会很快占满，属于这个 流的新到的包就会被丢弃。采用这种方式，每个数据流就不可能牺牲其它数据流而额外 占用资源。f q 算法并没有告知源端路由器状态的机制，也就是说，f q 仍然要依赖于端到 端的拥塞控制机制。它只是将数据流分隔，使不遵守拥塞控制机制的数据流不至于影响 其它流。所以它在没有牺牲统计复用的情况下提供了公平性，与端到端的拥塞摔制机制 也i j j 。以较好地队川。由于数据包是变长的，所以为了在输出链路上公平分配宽，必须考 虑包的大小。 2 2 5 加权公平排队算法( w f q ) 它足f q 的改进算法。w f q l 4 l 对每个流即每个排队分配一个权值。这个杖值决定了 路由器每次转发该队列的比特数量，从而控制数据流得到的带宽。将所有权值看成1 ，那 么f q 也是一种特殊的w f q 。权值的分配往往对应不同优先级的数据流，例如用i p 包头 中t o s 域指定流的优先级，排队时再按优先级分配权值。这也是区分服务的思想。权值 可以由路器自己决定，也叮以卜h 源端通过某种信令通知路由器柬决定。总之w f q 根 9 南求1 1 1 i f 电人学颁l ：研究生学位论文第。章主动队列管理a q m 算法方案 掘小嗣数据流应用的不同带宽要求，对每个排队队列采用加权方法分配缓存资源，欤丽 增加了f q 对不同应用的适应性。 2 。3a q m 算法性能分析比较 f f f 0 的t 要问题足无法隧分不同的数据流，它对拥塞控制不起作用， ：要“l1 、c p 进 行搠塞的检测和峨应。r e d 设讨。的出发点是怎样与t c p 拥塞控制有效配合。对翻向连接 的t c p 数据流来说，r e d 有可能避免丢弃属于同一连接的连续数据包，从而提高连接的 吞吐量。在路由器上运行r e d 可以更精确地管理队长，其最优队长取决于各种数据流的 特性。e c n 不依赖于重传超时和粗粒度的t c p 定时，对有一定时延要求的应用效果较好。 7 院p 在源端进行拥寒控制，传统的f i f o 排队不提供约束所有数据源遵守搠塞控制的机制， 这就有可能让行为不良的数据流强占大量带宽。针对此提出了f q 算法即公平排队法，可 以解决这个问题。 2 4 本章小结 本章介绍了a q m 主动队列管理的原理和优点，详细描述了各种具体的a q m 算法的提 出和实现，并对不同的a q m 安现算法进行了分析比较。下一章将对a q m 算法中魄随机早 检测算法r e d 进行详细介绍。 l o 南京邮i 【1 人学坝i ：i j f 究生学位论义销三乖r e d 算法训究 第三章r e d 算法研究 3 1r e d 算法概述 r e d 算法的主要思想是为路由器上的t c p 流提供拥塞控制。r e d 算法的基本目的是通 过控制路由器的平均队长使得路由器保持在较低时延和高的吞吐量的工作状态。同时，避 免由于各个t c p 链接在同一时间进入慢启动状态，将拥塞窗口减为1 而引起的全局同步现 象。控制不规范行为的用户，寻求对突发业务流没有偏差的机制。我们希望当平均队长大 于最小阈值时，r e d 丢弃小百分比的数掘包，使得一些t c p 链接减少发送窗l 1 人小，从而 减少在一段时f 日j 内进入路由器的数据量，这样就减小了平均队长，避免了捌塞的发生并能 够维持较高的吞吐量。r e d 算法使路由器能够更加精确地管理队长。而最优的队长则取决 于各种数据流的不同特性。 r e d 的任务之一是检测早期的拥塞，任务之二是选择一个链接以通知拥塞。r e d 网关 的原理非常通用，即便在不可靠的传输层协议下也能有效控制平均队长。r e d 网关的捌塞 控制机制简化了传输层协议的工作，它也适用于当前t c p 协议以外的传输层协议，包括基 于比特速率的传输层协议以及基于窗口的传输层协议。但是，r e d 网关的某些方面是针对 t c p i p 协议的。r e d 所在的网络应该是传输层协议只需要一个丢包信息就能够检测到捌 塞。r e d 适用于使用包调度和包丢弃算法的网关， r e d 算法监视每个输出队列的平均队长，并且随机选取队列中的一个链接米通知拥 塞。瞬时的拥塞可以通过队列长度的短时增加来容纳，而长时间的拥塞则通过计算平均队 长反映。r e d 并不一定通过丢包来预告拥塞，它也可以在包头设定一个b i t 来通知传输层拥 塞发生。如果r e d 通过丢包而不是设定b i t 位来标记包，那么它在传输层不合作的情况下也 能控制甲均队长。并且r e d 算法有一个优点，就是它可以在不改变当f i i j t c p i p 网络的传输 层协议的状况下被直接简单地植入网络。 早在r e d 算法之前有一系列的相关算法机制【l 】，首先是传统的d r o p t a i l 算法，它 采用先进先出的排队机制，当队列满时固定在队尾的位置进行确定的丢包，这种方法容 易同时丢弃柬( i 数个链接的包从而引起全局同步。然后是r a n d o md r o p 算法，这种算法 在队列满时，从队列中随机选取一个包进行丢弃。相应地还有e a r l yr a n d o md r o p 算法， 该算法在队列长度达到并超过一个丢弃水平时，路由器以一定的概率丢弃每个到达的包， 这样就减少了全局同步的发生，但是不能控制不规范行为的用户。另外还有一种源抑制 信息的算法，路由器在队列到达限度之前向源端发送源抑制信息，但是这样比较复杂因 l l 南京邮电大学硕士研究生学位论文 第三章r e d 算法研究 为它使路由器参与到端到端的协议中。此外还可以采用d e c b i t 机制，通过在数据包头 没胃个洲摩指示比特位来向源端提供关于拥塞的反馈信息。丽r e d 算法则足矗：队列中 刁i 固定丢弃位置并且彳i 固定丢弃概率的一种算法。 3 2r e d 算法实现及参数设置 算法的具体描述如下【l i ： 初始化 c o u n t = 1 a v g = 0 每个数扔：包到达时 计算新的平均队长大d , a v g i f 队列非空 a v g = ( 1 一w q ) a v g + w q q e l s e m = ( t i m e q _ t i m e ) s ； a v g = ( 1 - w ) m 宰a v g ； i f m i n t h = a v g m a x t h c o u n t + + 计算丢包率p a ) q - j p a 的概率标也( 或丢弁) 数据包 c o u n t = o e l s e i f m a x t h = a v g 标址( 或三弃) 数据包 c o u n t = 0 e l s e c o u n t = 1 当队列为宁时： q _ t im e 2 t i m e 1 2 南京邮电人学顾i ：弧j f 究生学位论文第三帝r e d 算法研究 r e d 五卉概牢p a 的计算方法 p b = p m a x ( a v g m i n t h ) ( m a x t h m i n t h ) 【1 】 p a = p b ( 1 一c o u n t p b ) 2 】 a v g 为平均队列长度，q 为新测得的瞬时队长，指数加权平均w q 。这样r e d 算法i ，j 以 分为两个独：矗：的算法，计算平均队长的算法决定了在网关队列中能够容纳的突发私度：计 算丢包概率的算法决定了在当前的拥塞状况下队列丢包的频度。其目的使保证使网关以一 定平稳的间隔标记包，避免各种偏差和全局同步，并及时丢弃足够多的包以控制平均队长。 传统的r e d 参数设置遵循以下一些规则：r e d 网关的目的之一是检测早期的拥塞， 但应陔是持续了很长一段时| 日j ( 几个r t t 的时i 日j ) 的拥塞，所以它调控用于计算i f 均队 长的低通滤波时间常数w q 来调节平均队长的变化，使平均队长能够容纳瞬时的突发业 务流和暂时拥塞而不会出现典型的增大，故w q 的上限由队列所允许的瞬时突发业务量 决定，下限应该使平均队长及时反映瞬时队长的变化，而不至于太拖后。在实际中，要 求w q 应该“过滤”掉l o o m s 时问段内发生的瞬时队长变化值，因为路l l 器存拥塞发乍 即平均队长大于阂值时，随机丢弃一个包，然后接着转发其他包，这样被丢包的链 接源端将收到目的端