（控制理论与控制工程专业论文）大时滞网络的拥塞控制算法研究.pdfVIP

l at h e s i si nc o m t r o lt h e o r ya n dc o n t r o le n g i n e e r i n g t h e c o n g e s t i o nc o n t r o la l g o r i t h m so f l a r g e - - d e l a yn e t w o r k s b yy a n g x i a o l i s u p e r v i s o r ：p r o f e s s o rj i n gy u a n w e i n o r t h e a s t e r nu n i v e r s i t y j u n e2 0 0 8 、f j 独创性声明 学位论文作者签名：船 学位论文版权使用授权书 日 期：c 劬9 、 作者和导师同意网上交流的时间为作者获得学位后： 半年口一年口一年半口两 学位论文作者签名：撕办翻 导师签名 签字日期。 莎和乳7 签字日期 东北大学硕士学位论文摘要 大时滞网络的拥塞控制算法研究 摘要 以t 鲫协议为基础的i n t e r a c t 自9 0 年代产生以来，其网络规模、用户数量及业 务量迅速增长，新型网络应用不断涌现使得网络拥塞的状况愈加严重复杂。拥塞造成了 服务质量性能指标下降，严重影响网络资源的利用率。因此，拥塞控制一直是网络研究 领域的热点问题。 主动队列管理( a q m ) 算法作为端系统拥塞控制的一种补充，在保证高吞吐量的基础 上有效地控制了队列长度。但是大多数a q m 算法在设计及验证过程中都没有充分考虑 大时滞网络对算法性能的影响。因此，研究大时滞网络的a q m 算法就成为一种发展方 向。 本文从控制理论角度对网络拥塞控制机制建模并进行分析的基础上，针对大时滞对 网络拥塞控制系统的影响，主要工作如下： 针对p i ，p i d 控制算法在大时滞网络环境下的控制效果不理想，而s m i t h 预估补偿 器在网络参数变化下又过于依赖网络的精确模型的弱点，提出了基于改进s m i t h 预估补 偿器的a q m 算法。通过改进算法改善了控制系统的动态性能，经过在大时滞动态网络 环境变化下的仿真比较分析，验证了改进s m i t h 算法的有效性。 针对s m i t h 预估补偿机制过分依赖网络模型，而改进s m i t h 预估补偿机制控制效果 不够理想的缺点，提出了将单神经元自适应p i d 算法跟s m i t h 预估补偿器相结合的a q m 算法。这种算法通过单神经元的自适应自学习能力，以及无需被控对象的精确模型即能 实现良好的控制的特性，克服了s m i t h 预估补偿依赖精确模型的缺点，对网络环境变化 有很强的鲁棒性，并通过在大时滞网络环境变化下的仿真比较分析，验证了该算法的优 越性。 最后对全文进行了概括性总结，并提出了下一步研究的方向。 关键词：拥塞控制；主动队列管理；大时滞；参数变化；s m i t h 预估补偿；单神经元 一i i ， ? l i ， j j 东北大学硕士学位论文 a b s t r a c t t h e c o n g e s t i o nc o n t r o la l g o r i t h m so fl a r g e - d e l a yn e t w o r k s a b s t r a c t w i t ht h ee v o l v e m e n to fi n t e r n e tb a s e do nt c p i f , t h es c a l e ，u s e r sa n dt r a f f i c so fi th a v e e x p e r i e n c e da ne x p l o s i v eg r o w t hs i n c e 9 0 s t h en e t w o r kc o n g e s t i o nh a sb e c o m em o r e s e r i o u sa n dc o m p l e xd u et ot h ee v e r - i n c r e a s i n gn e t w o r ka p p l i c a t i o nt y p e s c o n g e s t i o no f t e n r e s u l t si nd e c l i n eo fq u a l i t yo fs e r v i c e ，w h i l et h en e t w o r kr e s o u r c eu t i l i z a t i o ni sa l s oa f f e c t e d s e r i o u s l y t h ec o n g e s t i o nc o n t r o l li sa l w a y sa h o ts p o ti nt h ef i e l do fn e t w o r kr e s e a r c h t h ea c t i v eq u e u em a n a g e m e n t ( a q m ) a c t i n go nt h ei n t e r m e d i a t en o d e si sa b l et oc o n t r o l t h eq u e u el e n g t he f f e c t i v e l yo nt h eb a s i so ft h eh i g ht h r o u g h p u to ft h er o u t e r s h o w e v e r , m o s t a q m a l g o r i t h m si nt h ed e s i g na n dv e r i f i c a t i o np r o c e s sd on o tf u l l yc o n s i d e r t h ei m p a c to ft h e l a r g e d e l a yn e t w o r k s ot h a tt h ea q ma l g o r i t h m so fl a r g e d e l a yn e t w o k sh a sb e c o m ea r e s e a r c hd i r e c t i o n c o n s i d e r i n gl a r g e - d e l a yo fn e t w o r k sa n du n c e r n t yo fn e t w o r k sm o d e l ，b a s e d o nt h e a n a l y s i so fc o n g e s t i o nc o n t r o lm e c h a n i s mo ft c p i pi nc o n t r o lt h e o r y , t h er e s e a r c hw o r k i s s u m m a r i z e da sf o l l o w s ： c o n s i d e r i n gt h ec o n t r o l so fp ia n dp i d c o n t r o l l e ra r en o te f f e c t i v e ，a n dt h ew e a k n e s so f d e p e n d i n go np r e c i s em o d e lo ft h es m i t hc o n t r o l l e r a ni m p r o v e ds m i t hc o n t r o l l e ra sa q m a l g o r i t h mi sp r o p o s e db a s e do nt h es m i t hc o n t r o l l e r t h es i m u l a t i o nr e s u l t so ft h ea l g o r i t h m u n d e rd i f f e r e n ti n s t a n c e ss h o wt h es u p e r i o r i t yo ft h ei m p r o v e ds m i t hc o n t r o l l e r c o n s i d e r i n gt h ew e a k n e s so fd e p e n d i n g o np r e c i s em o d e lo ft h es m i t hc o n t r o l l e r , a n dt h e c o n t r o l so fi m p r o v e ds m i t hc o n t r o l l e ri si m p e r f a c t ，a na c t i v eq u e u em a n a g e m e n ta l g o r i t h mi s p r o p o s e db a s e do nt h ec o m b i n i n go fs e l f - l e a r n i n gs i n g l en e u r o np i dc o n t r o l l e rw i t hs m i t h c o n t r o l l e r t h ed e f e c to fd e p e n d i n go np r e c i s i o nm o d e lo fs m i t hc o n t r o l l e rc a nb eo v e r c a m e b ys e l f - l e a r n i n gs i n g l en e u r o nc o n t r o l l e r , w h i c hm a y w o r kw e l lw i t h o u tt h ep r e c i s em o d e lo f r e a lp r o c e s s t h es i n g l en e u r o np i ds m i t hc o n t r o l l e ri sr o b u s tt od y n a m i cn e t w o r kp a r a m e t e r s a n ds u i t a b l ef o rn e t w o r k sw i t hl a r g e d e l a y t h ec o n c l u s i o ni sd r a w nf o rt h ew h o l et h e s i s ，a n dt h ef u r t h e rr e s e a r c ha s p e c ti sp u t f o r w a r d k e y w o r d s ：c o n g e s t i o nc o n t r o l ；a c t i v eq u e u em a n a g e m e n t ；n e t w o r kp a r a m e t e r s ；l a r g e d e l a y ； s m i t hc o n t r o l l e r ；s i n g l en e u r o n l i l 1 函 v i 东北大学硕士学位论文目录 目录 独创性声明i 摘要i 】【 a b s t r a ( x 1 i l 第一章绪论1 1 1 网络拥塞概念及其产生原因一1 1 2 网络拥塞控制发展历程及其分类4 1 3 大时滞网络拥塞控制系统的研究意义及研究现状6 1 4 本文主要工作8 第二章t c p i p 网络拥塞控制机制分析。9 2 1 基于源端的t c p 拥塞控制算法9 2 1 1t c p 拥塞控制算法1 0 2 1 2t c p 拥塞控制算法存在的主要问题及改进1 1 2 2 基于路由器的主动队列管理算法1 3 2 2 1 随机早期检测算法一1 4 2 2 2 基于优化理论的a q m 算法概况1 6 2 2 3 基于控制理论的a q m 算法概况1 7 2 3 小结。1 9 第三章基于改进的s m i t h 预估补偿机制的a q m 算法研究2 1 3 1 基于a q m 算法的网络拥塞控制系统模型2 1 3 2 经典p i 及p i d 算法性能分析2 6 3 3 改进的s m i t h 预估补偿机制2 8 3 3 1 传统s m i t h 预估补偿结构及原理2 8 3 3 2 传统s m i t h 预估控制的优缺点3 0 3 3 3 改进的s m i t h 预估控制系统结构及原理3 1 3 3 4 基于改进s m i t h 预估补偿机制的网络拥塞控制系统3 2 3 4 仿真分析3 2 3 4 1p i 算法在不同时滞环境下的仿真分析3 3 3 4 2p i d 算法在不同时滞环境下的仿真分析3 4 3 4 3s m i t h p i d 算法在大时滞环境下仿真分析3 6 3 4 4 改进s m i t h 预估控制器在大时滞网络环境变化时仿真效果3 7 3 5 小结3 9 一一 东北大学硕士学位论文 目录 第四章基于单神经元自适应p i ds m i t h 策略的a q m 算法研究4 1 4 1 单神经元模型4 1 4 2 单神经元p i d 控制器设计4 3 4 2 1 单神经元p i d 与常规p i d 的比较4 3 4 2 2 几种典型的学习规则4 4 4 2 3 单神经元自适应p i d 控制器设计及其学习算法4 4 4 2 4 改进的单神经元自适应p i d 控制器4 7 4 3 基于单神经元自适应p i ds m i t h 策略的网络拥塞控制系统4 7 4 4 仿真分析4 8 4 4 1 改进单神经元p i ds m i t h 算法在大时滞网络环境变化时的仿真分析4 8 4 4 2 改进单神经元p i ds m i t h 算法与改进s m i t h 算法的仿真比较分析5 0 4 5d 、结5 1 第五章总结与展望5 3 5 1 主要工作5 3 5 2 进一步工作研究。5 3 参考文献5 5 致谢一5 9 一v i；i jj。 峨，；t，t， 东北大学硕士学位论文 第一章绪论 第一章绪论弟一早珀v 匕 i n t e m e t 从出现以来就一直以惊人的速度飞速发展。近些年来，许多新兴的网络服 务业务，例如p 2 p 及视频会议等大数据传送量业务的出现，已使i n t e r n e t 由以往的单一 数据传送网发展成传送数据、语音、视频等多媒体信息的综合业务网。正是由于网络数 据流量的急剧增加，使i n t e m e t 经常发生拥塞现象，在极端情况下甚至可能导致网络的 崩溃。同时，新业务的出现也对网络服务质量提出了更高的要求。这些新需求的共同特 点是要求有较低的网络延时和抖动、较低的数据包丢失率以及较高的访问带宽。这些严 格的服务质量指标促进了网络技术的发展，接纳控制、流量成形、队列调度以及拥塞控 制等都得到了显著的发展，而这些网络技术最基本最核心的依旧是拥塞控制。因此，在 过去的二十几年中，如何预防和控制拥塞一直是计算机网络界研究的热点。 1 1 网络拥塞概念及其产生原因 当网络中存在过多的数据包时，网络的性能就会下降，这种现象称为拥塞。由于 i n t e m e t 采用的是统计复用技术，大量的数据流共享一条链接，其运行环境在不断发生 变化，基于t c p 佃协议栈的网络通信协议i n t e m e t 中的主流通信协议，这种网络采用的 是尽力而为( b e s t e f 幻m 的服务模型，所有的数据流被不加区分地在网络中传输，网络无 法给用户一个定量的性能指标，如吞吐量、时延、包丢失率等。因此，在目前网络带宽 有限，数据传输的需求量远远超过网络的瓶颈带宽时，必定会产生拥塞。文献【1 】用用图 1 1 来描述拥塞的发生。 吞 吐 e 里 响 应 时 间 网络负载网络负载 图1 1 网络负载与吞吐量及响应时间的关系 f i g 1 1t h er e l a t i o n s h i po fn e t w o r kl o a dw i t ht h r o u g h p u ta n dr e s p o n d i n gt i m e 从图1 1 中可以看出，当网络负载较小时，吞吐量和负载之间基本成线性关系，响 应时间增长缓慢，当负载达到网络容量时，吞吐量的增长开始变得很缓慢，而响应时间 增加较快，这一点称为膝点( k n c e ) 。如果网络负载继续增加，则路由器开始丢包，当负 载超过菜一点数量时，吞吐量开始急剧下降，而响应时间急剧上升，称该点为崖点( o i a 3 。 一1 一 东北大学硕士学位论文第一章绪论 通常将膝点附近称为拥塞避免区间，膝点和崖点之间为拥塞恢复区间，崖点之外为拥塞 崩溃区间。拥塞控制就是网络节点采取措施来避免拥塞的发生或者对拥塞的发生做出反 应，在图1 1 中就是使负载保持在k n e e 附近。 网络产生拥塞的根本原因在于用户对网络资源，包括链路带宽、存储空间和处理器 处理能力等的需求超过了网络本身固有的容量。拥塞导致的后果是数据分组延时增加、 丢弃概率增大、上层应用系统性能下降，甚至可能使整个网络系统崩溃。当网络处于崩 溃状态时，微小的负载增量都将使网络的有效吞吐量急剧下降，端到端的时延急剧增加。 拥塞产生的直接原因有以下三点： ( 1 ) 存储空间不足。几个输入数据流共同需要同一个输出端口，在这个端口就会建 立排队，如果没有足够的存储空间存储，数据包就会被丢弃，对突发数据流更是如此。 增加存储空间在某种程度上可以缓解这一矛盾，但如果路由器有无限存储量时，拥塞只 会变得更坏，而不是更好。因为在网络里数据包经过长时间排队完成转发时，它们早已 超时，源端认为它们已经被丢弃，而这些数据包还会继续向下一路由器转发，从而浪费 网络资源，加重网络拥塞。 ( 2 ) 带宽容量不足。低速链路对高速数据流的输入也会产生拥塞。根据香农信息理 论，任何信道带宽最大值即信道容量为c = b l o g ，0 + s i n ) ( n 为信道白噪声的平均功 率，s 为信源的平均功率，b 为信道带宽) 。如果尺 c ，则在理论上无差错传输就是不 可能的，所以在网络低速链路处就会形成带宽瓶颈，当其满足不了通过它的所有源端带 宽要求时，网络就会发生拥塞。 ( 3 ) 处理器处理速度慢也会引起拥塞。如果路由器的c p u 在执行排队缓存、更新路 由表等功能时，处理速度跟不上高速链路，也会产生拥塞。同样，低速链路对高速c p u 也会产生拥塞。 要避免拥塞的发生，对以上三点原因需综合考虑。例如，提高链路速率而不改变处 理器，只会转移网络瓶颈，而不能避免拥塞，所以拥塞往往也是系统各部分不平衡的结 果。拥塞一旦发生往往会形成一个不断加重的过程。如果路由器没有空余的缓存，它就 必须丢弃新到的数据包。当数据包被丢弃时，源端会超时，重传该数据包。如果没有得 到确认，源端只能保留数据包，结果缓存会进一步消耗，加重拥塞。 拥塞虽然是由于网络资源的稀缺引起的，但单纯增加资源并不能避免拥塞的发生。 例如上面所说到的增加存储空间并不能解决拥塞问题。事实上，缓存空间不足导致的丢 包更多的是拥塞的“症状 而非原因。另外，增加链路带宽及提高处理能力也不能解决 拥塞问题1 2 】，这可以从图1 2 图1 4 中看到。 在图1 2 中，四个节点之间的链路带宽都是1 9 2 k b p s ，传输某个文件需要用时5 分钟。 当第一个节点和第二个节点之间的链路带宽提高至l j l m b p s 时，如图1 3 所示，传输完该文 一2 一 厶 di，lii 。，； o 东北大学硕士学位论文第一章绪论 件所需时间反而大大增加到了7 个小时。这是因为在路由器r 1 中，数据包的到达速率远 远大于转发的速率，从而导致大量数据包被丢弃，源端的发送速率被抑制从而使得传输 时间大大增加。即使所有链路具有同样大的带宽也不能解决拥塞问题，例如图1 4 中，所 有链路带宽都是1 g b p s ，如果a 和b 同时向c 以1 g b p s 的速率发送数据，则路由器的输入速 率为2 g b p s ，而输出速率只能为1 g b p s ，从而产生拥塞。 1 9 2 k b p s l 路由器 i 1叫紫陋 l r 1广 li 图1 2 所有带宽为1 9 2 k b p s f i g 1 2a l lt h eb a n d w i d t h sa r c1 9 2 k b p s 图1 3 带宽不对称的情况 f i g 1 3t h eb a n d w i d t h sa r cu n s y m m e t r i c a l 图1 4 所有链路带宽都为1 g b p s f i g 1 4a l lt h eb a n d w i d t h sa 聆1 g b p s 从以上分析可以看出，就i n t e r n e t 的体系结构而言，拥塞的发生是其固有的属性。 首先，拥塞问题本质上是一个如何资源共享的问题，在包交换网络中，所有激活的 网络终端共享网络资源。这些资源包括节点处理能力、缓存空间和通信链路的带宽等。 这三者中的任何一个都有可能成为潜在的瓶颈，从而导致网络拥塞。网络必须尽可能为 一3 一 东北大学硕士学位论文第一章绪论 所有的请求提供服务，但用户的需求在传输起始时间、需求速率、持续时间上变化很大， 在很多情况下还是突发的。而任何网络的物质资源都有固定的上限能力，因此用有限的 资源去适应波动很大的用户需求，一定会出现网络资源不能满足用户需求的时候。 其次，拥塞总是发生在网络中资源“相对 短缺的位置，拥塞发生位置的不均衡反 映了i n t e r n e t 的不均衡性。第一是资源分配的不均衡，如图1 3 中带宽分布的不均衡； 第二是流量分布的不均衡，如图1 4 所示。i n t e r n e t 中资源和流量的不均衡是广泛存在的， 由此导致的拥塞不能依靠单纯的使用增加资源的方法来解决。 拥塞本身是一个动态问题，它不可能只靠静态的方案来解决，而且需要协议能够在 网络出现拥塞时保护网络的正常运行。目前，网络拥塞己成为制约网络发展和应用的一 个瓶颈，如何更好的预防和控制拥塞一直是近年来网络研究的热点问题。 拥塞控制算法的设计难点体现在【3 j ： ( 1 ) 算法的分布性。拥塞控制算法的实现分布在多个网络的节点上，必须使用不完 全的信息来完成控制，并使各节点协调工作，还必须考虑某些节点工作不正常的情况。 ( 2 ) 网络环境的复杂性。i n t e r n e t 中各处的网络性能有很大的差异，算法必须有很好 的适应性，另外，由于i n t e r n e t 对报文的正确传输不提供保证，算法必须能处理报文丢 失、乱序到达等情况。 ( 3 ) 算法的性能要求。拥塞控制算法对性能有很高的要求，包括算法的公平性、效 率、稳定性和收敛性等，某些性能指标之间存在矛盾，在算法设计时需要进行权衡。 ( 4 ) 算法的开销。拥塞控制算法必须尽量的减小附加的网络流量，特别是在拥塞发 生时。在使用反馈式的控制机制时，这个要求增加了设计的难度。算法还必须尽量降低 在网络节点上设计的复杂性。 1 2 网络拥塞控制发展历程及其分类 拥塞控制问题的研究始于2 0 世纪8 0 年代中期。1 9 8 4 年，n a g e l 首次指出了复杂 t c p i p 网络中存在的拥塞问题，特别是在由路由器连接的带宽差异较大的网络中，容易 发生拥塞崩溃【4 l 。但这一问题在学术界并没有引起足够的重视。直到1 9 8 6 年，a p p a n e t ( 美国国防高级研究计划局网络) 首次出现了一系列的拥塞崩溃现象【5 l ，网络吞吐量急 剧下降，许多分散在各地的网络节点被迫长时间停止使用。 对于a p p a n e t 的拥塞崩溃问题最初所做的反应是增加网络的容量，这使拥塞得到 了短暂的缓解，但之后a p p a n e t 网仍然持续地遭受拥塞崩溃，直到采取一个控制策略 来控制进入网络的分组数量。 1 9 8 8 年j a c k s o n 在其著名的论文【5 】中指出了t c p 协议在拥塞控制上的不足，并增加 了拥塞控制算法( t c pt a h o e ) ，提出了著名的“慢启动 ( s l o ws t a r t ) 、“拥塞避免 一4 一 东北大学硕士学位论文第一章绪论 ( 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 ) 等算法。于1 9 9 0 年在t c pr e n o 6 l 版本中又增加了“快速恢复”( f a s tr e c o v e r y ) 算法，避免了网络拥塞不够严重时采用“慢 启动”而造成大幅度减小发送窗口尺寸的现象。该算法奠定了拥塞控制研究的基础。 从2 0 世纪8 0 年代至今，许多学者进行了更深入和细致的研究，不断改进t c p 拥 塞控制算法存在的缺陷，相应提出了3 个版本的t c p 拥塞控制算法。即：s a c k l 7 1 ，n e w r e n o i 剐，v e g a s l 9 l 。 i n t e m e t 是在a p p a n e t 和n s f n e t ( 美国国家科学基金会网络) 网络互联的基础 上发展起来的，它的体系结构决定了其拥塞存在的必然性。i n t e m e t 采用的是无连接的 端到端数据包交换，提供“尽力而为 ( b e s te f f o r t ) j j 务模型的设计机制。这种机制的最 大优势是设计简单，可扩展性强。然而这种优势并不是没有代价的，随着i n t e m e t 用户 数量的膨胀，网络的拥塞问题也变得越来越严重。例如由于本地缓存溢出，网络路由器 会丢弃约1 0 的数据包【5 1 。如果不在i n t e r n e t 中使用拥塞控制算法，拥塞崩溃的发生会 严重降低网络的性能。 据统计，i n t e m e t 上9 5 的数据流使用的是t c p i p 协议【l ，因此，i n t e m e t 上主要 的互联协议t c p i p 的拥塞控制机制对控制网络拥塞具有特别重要的意义。 然而对于i n t e m e t 这样复杂的异构系统，仅仅依靠t c p 拥塞控制机制是不能确保 q o s ( q u a l i t yo f s e r v i c e ) 的，网络层必须参与资源的控制和分配。在路由器中采用队列调 度算法和缓存管理技术，当路由器处理能力不足时，队列管理算法对来不及处理的数据 包进行丢弃或标记。而调度算法直接管理输出链路的带宽资源。传统的策略采用“去尾 ( d r o p t a i l ) ”的管理策略，即报文到达时，如果缓冲队列已满，路由器则丢弃该报文。“去 尾 策略虽然简单，但很容易产生持续的的满队列状态，甚至导致业务流对缓存的死锁 和业务流的全局同步。 f l o y d 于1 9 9 3 年提出著名的随机早期检钡l j ( r a n d o me a r l yd e t e c t i o n , r e d ) 1 1 2 l 控制策 略，有效地改善了网络路由器常用的“去尾”策略的缺陷，此后许多学者进行了更深入 的研究，提出了一系列基于路由器的主动队列管理( a c t i v eq u e u em a n a g e m e n t ，a q m ) 策 略。t c p 与a q m 的结合是解决目前i n t e m e t 拥塞控制的主要途径。 虽然学术界在拥塞控制领域已经开展了大量的研究工作，但是到目前为止拥塞控制 问题还没有很好的解决。因此关于i n t e r n e t 的拥塞控制问题一直是网络研究的一个热点。 y a n g 提出了拥塞控制的一般分类方法【1 2 1 ： ( 1 ) 从控制理论的角度，拥塞控制算法可以分为开环控制和闭环控制两大类。当流 量特征可以准确规定、性能要求可以事先获得时，适用开环控制；当流量特征不能准确 描述或者当系统不提供资源预留时，适用闭环控制。i n t e r a c t 中主要采取闭环控制方式。 开环控制方法要求在网络运行之前就针对网络的数据流量、拓扑结构、控制方法等 一5 一 东北大学硕士学位论文第一章绪论 设计好拥塞控制方法。它要求所有的路由器均支持在数据传输开始前，根据客户需要预 留资源。开环方法不能简单地用端到端的机制来实现。 闭环方法指发送方能通过反馈信息了解网络当前状态，并动态的调节发送速率以适 应网络负载要求。反馈可以是“显式”或者“隐式”的，“显式”指通过某种标记方法 通知发送源端，通常采用分组丢弃或者e c n 方法，“隐式”指发送通过隐含的信息判断 网络状态( 例如传输超时) 。它的一个缺陷是算法性能受到反馈延迟的严重影响，如果 反馈信息不能及时传到源端，算法会退化1 1 3 】。相比开环，闭环方法更加适应互联网的复 杂环境。闭环的拥塞控制可以分为以下3 个阶段：检测网络中拥塞的发生；将拥塞信息 报告到拥塞控制点；拥塞控制点根据拥塞信息进行调整以消除拥塞。对互联网网络业务 不断变化的复杂系统一般采用闭环控制。 ( 2 ) 根据算法的实现位置，可以将拥塞控制算法分为两大类：路由器算法( 1 i n k a l g o r i t h m ) 和源算法( s o u r c ea l g o r i t h m ) 。链路算法在网络设备中实行，作用是检测网络拥 塞的发生，产生拥塞反馈信息。源算法在主机和网络边缘设备中执行，作用是根据反馈 信息调整发送速率。 源算法中使用最广泛的是t c p 协议中的拥塞控制算法【1 4 1 。t c p 是目前在i n t e m e t 中 使用最广泛的传输协议。根据m c i 的统计，总字节数的9 5 和总报文数的9 0 使用t c p 传输【1 5 l 。近年来，t c p 中采用了很多新的算法，包括慢启动( s l o ws t a r t ) 、拥塞避免、快 速重传( 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 m e t 稳定性的重要因素。 链路算法的研究目前集中在主动队列管理算法( a q m ) 方面。和传统的队尾丢弃算法 ( d r o pt a i l ) 相比，a q m 在网络设备的缓冲溢出之前就丢弃或标记报文。a o m 的一个代表 是r e d ( r a n d o me a r l yd e t e c t i o n ) 1 4 1 。研究表明，r e d 比d r o pt a i l 具有更好的性能。但是， r e d 的性能对算法的参数设置十分敏感，至今没有在i n t e r n e t 中得到广泛的使用。 1 3 大时滞网络拥塞控制系统的研究意义及研究现状 大时滞网络拥塞控制系统研究是基于主动队列管理基础上的研究，针对大的回路延 时而采用了一系列算法研究。因为主机终端和网络中间节点在地理空间上的分散性，路 由器在拥塞控制中产生的任何激励到达源端系统使其做出响应都有一定的滞后。对于几 毫秒到几十毫秒往返时延的t a n 或m a n ，这种忽略有其合理的因素，但在跨州越洋的 t c p 连接中，r 1 盯( 回路延时) 时间往往有几百毫秒，甚至达到秒的数量级。为了证明 这一点，文献 1 9 1 利用p i n g 程序从位于清华大学校内的1 6 6 1 1 1 6 4 2 3 9 测试了去往不同地 址的r t r 的时间，其测试结果如表1 1 所示。 从表1 1 中可见，在同一个l a n 中，r t t 只有1 1 3 m s ；但去往美国东海岸时的r 1 陌却 一6 一 东北大学硕士学位论文 第一章绪论 高达8 8 6 7 m s 。 表1 1 砌厂r 统计值 m l b l e l 1t h es t a t i s t i cv a l u eo fr t t a q m 通过网络中间节点有目的的分组丢弃实现了较低的队列延时和较高的吞吐 量，而已有的大多数a q m 算法在设计过程中都没有综合考虑大时滞以及参数的时变性 对算法性能的影响。 文献 1 9 1 对大时滞a q m 算法性能的影响进行了较详细的分析，并通过仿真试验验 证了几种典型算法( r e d ，p i ，r e m 和p l d ) 的队列在大时滞网络中无一例外地出现出剧烈 的振荡，导致瓶颈链路利用率和延时抖动加剧。其队列长度的统计值如表1 2 所示。 表1 2 队列长度的统计值 t a b l e 4 1t h es t a t i s t i cv a l u e o fq u e u el e n g t h 从表1 2 中可以看出，时延加大后，瓶颈链路的利用率普遍下降1 0 。虽然p i 依旧有 较高的利用率，但队列明显不稳定，r e d 与p i 控制队列的标准偏差增加了4 0 ，而r e m 和 p i d 的情况更差，接近前两者的2 倍，达到7 5 ，由此引入的端到端延时抖动对实现特殊业 务的q o s 保证是极为不利的。 从以上分析可以看到，在网络拥塞控制算法研究中大时滞问题不容忽视，克服纯滞 后是改善网络系统质量的一个关键性问题。在早期的主动队列管理算法的研究中，由于 当时所研究网络的范围和规模都比较小，因此，在进行网络仿真验证算法性能的时候， 在网络环境的设置上，无一例外地认定r 盯往返时延不超过几十毫秒。而此后的学者， 为了进行算法性能的对比方便，也沿用了几十毫秒的础【r 时延。然而，现在的i n t e r n e t 网络覆盖了世界各地，在范围上和规模上都不可与早期的网络相提并论。由上文可以看 出，许多跨洲越洋的t c p 连接，r t r 时延往往有几百毫秒。因此，网络拥塞中的时滞 控制问题就变得很有必要。这也是本文所要研究的内容。 一7 一 东北大学硕士学位论文第一章绪论 已有的对大时滞进行研究的文献中，文献【1 9 】中提出了一种基于内模控制的a q m 算法，m a s c o l o 2 0 】基于经典控制理论和s m i t h 原理设计了一个稳定的拥塞控制算法。用 于解决将时延系统化为无时延系统。但是这两种方法都没有考虑到网络参数对系统的影 响。文献【2 l 】在进行适当模型拟合处理的基础上提出了一种基于s m i t h 预估器的主动队 列管理( a q m ) 算法克服了大时滞给队列稳定性造成的不利影响。但是这种算法控制效果 也不是很理想，调节时间过长。文献【2 2 】提出了一种适应大时滞动态网络环境的预测p l 控制，但是这种算法只适应用于网络环境的小幅变化。因此，本文在大时滞网络环境下， 提出了一种基于改进s m i t h 预估补偿机制及单神经元自适应p i ds m i t h 策略，来应对网 络环境的变化。 1 4 本文主要工作 本文针对网络拥塞中的大时滞问题，采用了改进s m i t h 预估补偿机制以及单神经元 自适应p i ds m i t h 策略，并通过在网络参数变化环境下的仿真验证，得出了比较好的结 论。论文的主要工作及结构安排如下： 第一章介绍了网络拥塞控制的背景，以及大时滞网络拥塞控制的研究意义及研究现 状。 第二章介绍了基于源端的t c p 拥塞控制机制和基于路由器的主动队列管理算法，对 现有的拥塞控制算法进行了分析介绍。着重点出了基于控制理论的主动队列管理算法。 第三章通过对p l 、p l 的仿真分析，验证了大时滞环境下这两种算法的控制效果不理 想。而s m i t h 预估补偿器在网络参数变化环境下又过于依赖网络的精确模型的弱点，提 出了基于改进s m i t h 预估补偿器的a q m 算法。通过改进算法改善了控制系统的动态性能， 经过在大时滞网络参数变化环境下的仿真比较分析，验证了改进s m i t h 算法的有效性。 第四章针对s m i t h 预估补偿机制过分依赖网络模型的缺点，提出了将单神经元自适 应p i d 算法跟s m i t h 预估补偿器相结合的a q m 算法。这种算法通过单神经元的自适应 自学习能力，以及无需被控对象的精确数学模型即能实现良好的控制的特性，克服了 s m i t h 预估补偿依赖精确模型的缺点，对网络参数环境变化有很强的鲁棒性，并通过在 大时滞网络环境变化下与改进s m i t h 算法的仿真比较分析，验证了该算法的优越性。 第五章对本论文的工作作出总结，并提出了下一步工作计划。 一8 一 j，11 东北大学硕士学位论文第二章t c p i p 网络拥塞控制机制分析 第二章t c p i p 网络拥塞控制机制分析 i n t e m e t 上使用最广泛的是t c p i p 协议，这两个协议规定了计算机之间发送的信息应 该怎样分层、分组、怎样进行传输、以及其它许多有关的问题。t c p i p 的拥塞控制是其 成功的关键，近年来一直是一个活跃的研究领域。t c p 是目嘀i h n t e m e t 中使用最广泛的传 输协议。根据m c i 的统计，总字节数的9 5 和总报文数的9 0 使用t c p 传输。端系统中 使用的t c p 拥塞控制算法已经成为保证i n t e r n e t 稳定性的重要因素。而作为端系统拥塞控 制的重要补充，路由器上的a q m 策略能够在保证较高吞吐量的基础上有效地控制队列 长度，从而实现控制端到端的延时、保证q o s 的目的。 2 1 基于源端的t c p 拥塞控制算法 基于源端的拥塞控制策略中，使用最为广泛的是t c p 协议中的拥塞控制策略。目前 在互联网上实际使用的拥塞控制基本上是建立在t c p 的窗口控制基础之上的。由于i p 层 在发生拥塞时不向端系统提供任何显式的反馈信息，因而t c p 拥塞控制采用的是基于窗 口的端到端的闭环控制方式。 t c p 拥塞控制通过控制一些重要参数的改变来实现，t c p 用于拥塞控制的参数主要 有： ( 1 ) 拥塞窗e l ( c w n d ) ：是拥塞控制的关键参数。它描述源端在拥塞控制情况下一次 最多能发送数据包的数量。 ( 2 ) 通告窗h ( a w n d ) ：是接收端给源端预设的发送窗口大小，它只在t c p 连接建立 的初始阶段起作用。 ( 3 ) 发送窗i = 1 ( w i l l ) ：是源端每次实际发送数据的窗口大小。 ( 4 ) 慢启动阈值( s s t h r e s h ) - 是拥塞控制中用来限制发送窗i = 1 大小的门限值，它是慢 启动阶段和拥塞避免阶段的分界点，初始值设为6 5 5 3 5 b y t e s s 戈a w n d 的大小。 ( 5 ) 回路响应时间( g ad ：一个t c p 数据包从源端发送到接收端，直至源端收到接收 确认的时间间隔。 ( 6 ) 超时重传计数器( r t 0 ) ：描述数据包从发送到失效的时间间隔，是判断数据包 丢失与否、网络是否拥塞的重要参数，通常设为2 r t i 或5 r t i 。 ( 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 时，网络就进入快速重传阶段，t c p r e x m t t h r e s h 缺省值为 3 1 2 3 1 。 一9 一 东北大学硕士学位论文第二章t c p d