（控制理论与控制工程专业论文）新型网络拥塞控制器的设计与研究.pdf

摘要 摘要 随着网络应用的日益普及，数据流量呈现出前所未有的快速增长。与之同时， 网络拥塞的问题也日益凸现，并时时威胁着网络的稳定性。为了有效解决这一 问题，各种主动队列管理( a q m ) 算法相继出现。在一定程度上，其延缓了拥 塞的发生，避免了网络抖动甚至瘫痪的出现。为了更有效地改进既有算法的不 足，本文在a q m 中，分别引入两类控制算法：快速广义预测控制( f g p c ) 和 自抗扰控制( a d r c ) ，设计出相应的新型拥塞控制器。 作为a q m 的代表，r e d 通过不断调整丢包率p ，对控制动作进行指导，以 实现队长的平稳变化。但在具体实现时，其需要借助于参数设定的线性模型。 为了弥补其对参数设置敏感的不足，本文设计的f g p c 控制器，采用递归最小 二乘法对模型进行在线估计。在所得结果基础上，运用f g p c 算法，寻求最佳 控制量，进而实施有效的队列管理。n s 上的仿真表明，在网络高负载情况下， 该控制器具有比其他a q m 更为出色的表现的性能，其在稳定队长的同时，亦能 保持较低的时延和抖动。 本质上说，网络是一个高度复杂的非线性系统，任何确切的数学模型都无法 描述运行中的全部细节。许多基于模型的控制器，常规下性能优良，但在一些 例外情况下却表现很差。抗干扰控制器作为一种无需模型，直接利用反馈改造 原有系统结构的控制算法，为我们提供了一条解决问题的新途径。它采用扩张 状态观测器( e s o ) ，对系统中未建模部分及外界干扰进行统一估算，并利用状 态反馈，对原有系统结构进行简化。其在发挥原有p 长处的基础上，引入了 非线性环节，增强了对网络的特殊控制效果。仿真表明，当网路负载较低时， 其具有良好的性能。 本文通过在n s 上的仿真实验，考察了各参数变化对系统性能的影响。同时 也在相同的运行环境下，对各种a q m 控制器进行了横向对比。综合而言，高负 载情况下采用f g p c ，低负载情况下采用自抗扰控制器是不错的选择。 关键词：主动队列管理，快速广义预测控制，自抗扰控制器，扩张状态观测器 a b s 眦t a b s t 陷c t w t ht h ep o p u l a r i t ) ro f i n t e m 乩d a 诅n o w s 乜妇o nm p i dg r o w t t lt t l a ne v e rm e t h o w e v e l a tm es 锄e 妇em o r ec o n g e s t i o n so fn e t v ，o r kc o m ea l o n gt o o ，w i l i c ho r e n t h r e a o e nm es t a _ b i l i z a t i o no f n 咖o r k t os o l v e 血i s ，a c t i v eq l l c u em 锄a g 锄e n t ( a q m ) l l a sb e e np u tf o r 帆一t o 蛐l e v e l ，i tp o s t p o n e st h eo c c u i r e n c eo fc o n g e s t i o n ，锄d a v o i d s 也eo s c i l l 撕o no re v e np a r a l y s i so fn e t w o r k t oi m p r o v et h ea i r e a d ye x i s t e d a l g o r i t h mm o r ee 丘b c t i v e l y t h ep a p e ri m r o d u c e st w oc l 嬲s e so fc o m r o lt l l e o r y ：f 觞t g e m m t i z e dp r e d i c a 廿v ec o n 仰l ( f g p c )柚da 幽v ed i s t i l r b 锄c e s r e i e c t i o n c o n 廿d l l e ro 蝴r c ) ，a n dd e s i 印sn c wn e 帆o r kc g e s t i o nc o 曲o l l e r a s 也ed c l e g a t eo f a q m s ，r 叻g i l i d e s 也ec o 廿d la c t i o nb yc o n t i n l l a l l y 删璐t 崦 p a c k e 临d r 叩p r o ba _ b i l 时p ，t or e 址i z es m o o t l lv a r i e t ) ro fq u c u el e n g t h h o w e v e r ，i 壬l d e t a i l so f i m p l 锄e n t a t i o n i tr e l i e so nt h el i n e 盯m o d e lr e s 伍c t e db y p a r a m e t e rs e t t i i l g t ol e s s e ni t ss e n s m 、，j t yt om es 砌吨，也ed e s i 驴e df g p cc 0 d n o l l c ri nt h ep 印 a d o p t sr e c u r s i v el e a s ts q u a r e dm 劬o dt oe s t i m a ：t et h eo n l i n em o d e l b 觞e do nt b e r e s l l l to f 恤tr e c o 卿t i o i l ，i t 印p l i e sf g p ca l g o 栅1 i nt oc o m p u 把m e 咖廿o l 血b l e ， 、i t h 州c ht op e 血皿p m p e r 虹o no f q u e i l em a n a g e m e n t s i i n l l l a t i o n so nn ss b o w m a tu n d e rl l i g hl o a do f n e t w o r k ，f g p cc 0 咖l l e rb e h a v e sm o r ee x c e u e n tt h 锄。也e r s nc 趾e 髓c t i v e l ys 乜山i l i z eq u e 鹏l e n g t l l ，锄dm e a l l d m em a k e st h et r a i l s f 锄n gb e a r s m a l ld c l a ya n dd i t l l e 血g a c n 】a l l y ，n e 俩o r ki sa 栅m o r ec o m p l e xs y s t e mt h a i li i n a g i n e d n om a i b e m a t i c m o d e lc a n 舀v ea ne x a c td e s 商埘o no fa l l 岫gd e “1 s m 锄y 舳l l e r sb 鹤e do n m o d e l ，b e l l a v ew e l ll l 玎d c rn o 皿a lc o n d i t i o n ，b u tg i v e sb a dp e r f b m 趾c ei ne x c 印t i o n a l c 鹊e s a d r c ，w o 越n g 嬲a n e ws c h e m et h a tn e v e rr c q i l i 豫sm o d e l ，a i l dl i s e sf e e d b a c k t 0r e c o 咖c to r i g i n a ls y s t e m ，州d e sl l sag o o dw a yt os o l v et h ep r o b l e m n l n i l i z e s 胁e 璐i v es 诅t e0 b s e e r ( e s 0 ) t 0e s t i m a t e st h ee 彘c to fn o n m o d e l 堍p a n a l l do u t s i d ed i s t l j r b 柚c e s ，锄dl l s es t a t l l sf 酰d b a c kt os i m p l i 母s y s t e ms 劬c t u r e c 跚y m gf b r 啪r dm es 叻n gp o m to fp d ，i t m 的d u c e sn o n - l i i l e a r 汹et os 蚰g m e n i t ss p e c i a lc 印a b i l 时f b rm t 、) l ，o r kc o n 仃0 1 s i 瑚m a 廿o n ss h o wt h a tu n d e rl i g b t l o a do f n e t w o f ki tb e l l a v e se x c e l l e n t i a b s n a c t t h cp 印e rc h e c k s 也ei n n u e n c e so fs p e c 垴cp a 删e t e rs 础l l g so np e r f o m 趾c e t l l r d u g hs i n l l l l a 士i 咄o nn s 灿s o ，“d o e sc o m p a r i s o nb e t w e e nd i 旋n ta q m su n d e r 也es 锄em n i n ge n v i 瑚m 即t i nc o n c l l l s i o n ，血ec h o i c eo fa d o p 血gf g p cc o h 昀1 1 e r 腑d e rh 铋v yl o a d ，锄da d o p 血ga d r cc o n 们l h 岫d e rl i g h tl o a d i sab e t 嘧o n e k e ) w o r d s ：a c 石v eq u e u em 锄舭吐f a s tg 曲e r a l i z e dp r e d i c a t i v ec o 曲r o l ，a c t i v e d i s n 曲a n c e sr q e c t i o nc o i l 仃0 1 1 e x t e n s i v es t a 【e0 b s e e r 南开大学学位论文版权使用授权书 本人完全r 解南开大学关于收集、保存、使用学位论文的规定， 同意如下各项内容：按照学校要求提交学位论文的印刷本和电子版 本；学校有权保存学位论文的印刷本和电子版，并采用影印、缩印、 扫描、数字化或其它手段保存论文；学校有权提供目录检索以及提供 本学位论文全文或者部分的阅览服务：学校有权按有关规定向国家有 关部门或者机构送交论文的复印件和电子版；在不以赢利为目的的前 提下，学校可以适当复制论文的部分或全部内容用于学术活动。 学位论文作者签名：复乏海 钞铝年岁月别日 i 经指导教师同意，本学位论文属于保密，在年解密后适用 本授权书。 指导教师签名：学位论文作者签名： 解密时问： 年月 臼 备密级的最长保密年限及书写格式规定如下 黉黧囊懑弩鬃蒸纛豢矮黉鬻 南开大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行 研究工作所取得的成果。除文中已经注明引用的内容外，本学位论文 的研究成果不包含任何他人创作的、己公开发表或者没有公开发表的 作品的内容。对本论文所涉及的研究工作做出贡献的其他个人和集 体，均已在文中以明确方式标明。本学位论文原创性声明的法律责任 由本人承担。 学位论文作者签名：砂乏瑙 “年岁月_ 日 第一章引言 第一章引言 稳定性是现代网络高速可靠运行的必要前提之一。随着网络应用的日益广 泛，形式的不断更新，数据流量出现高速增长，导致拥塞问题日益严重，并时 时威胁着网络的可靠运行。主动队列管理算法( a o m ) 的诞生，就是针对这一 问题的。它采用积极主动的方式，监测网络流量变化，采取适当预防措施，延 缓拥塞的发生。随着网络研究的不断深入，系统化、全局化的分析方法日渐成 为主流。将网络整体视作一个大的系统，运用系统化的控制方法解决拥塞问题 ”j 【2 i 【3 】，就是该思想的一种实践。本文在a q m 中，分别引入f g p c 算法和自抗 扰控制理论，设计出新型拥塞控制器。其在弥补既有算法不足的同时，亦能在 复杂多变条件下，实现网络的安全平稳运行。 第一节互联网拥塞解决途径 互联网的普及很大程度上得益于t c p p 协议的广泛认可，作为网络的“粘合 剂”，它通过统一的地址分配机制和数据包格式，屏蔽不同硬件细节，将采用各 种不同技术标准的局域子网构筑成统一的国际互联网。随着其规模的日益庞大， t c p 佃也在其中扮演着越来越重要的角色。 在流量控制方面，t c p 协议采取了基于窗口的速率调整方法。该方法简单实 用，在一定程度上延缓了拥塞的发生。但是，这并不能彻底解决问题。网络拥 塞的发生，究其本质还是资源分配的不均衡性，这是一个需要协议动态协调的 过程【4 】。只有端节点的源算法与链路上的拥塞控制算法相互配合，才能协调好网 络资源的分配，减缓拥塞的发生。 1 1 1 端节点的源算法 源算法中使用最广泛的是t c p 协议中的拥塞控制策略。早期时，该策略只 具有自时钟特性。即包丢失时，源端必须等待至重发计时器超时，才能重新发 送丢失的数据包。由于缺乏有效预防措施，这种做法会极大的降低网络利用率。 随着研究的不断深入，该策略中又相继加入如下子策略：慢启动( s l o w 啦l r t ) ， 拥塞避免( c o n g e s t i o na v o i d a n c e ) ，快速重传( f ；l s tr e l 瑚s m j t ) 及快速恢复( f b t r e c o v e r y ) 。在具体实现上，不同版本的t c p 略有差异。 第一章引言 i 址o e 是t c p 协议的早期版本，它采用了慢启动、拥塞避免和快速重传3 个 子策略，同时为了更好的设置超时重发计时器，其对往返时间r t t 的计算方法 做了改进。其流程描述如下： ( 1 ) 收到一个新的确认报文： i f ( w s 5 曲m ) w = w + l e l s e w = w + l ，w ( 2 ) 重发计时器超时，或者收到3 个重复的a c k ： s s t l r e s h = w f 2 w = l 其中，w 表示发送窗口大小，砌w 表示慢启动阈值。 该算法的思路就是通过不断增加发送速率，探测网络中潜在的带宽容量，实 现网络资源的充分利用。在此过程中，如检测到数据包丢失，就可认定拥塞已 经发生，网络资源已至极限。此后，其将以指数形式递减发送速率，以减缓链 路上的拥塞。 在慢启动开始时，发送窗口被设置为一个数据包大小。之后，每收到一个新 的a c k 时，就将发送窗口加l 。在此阶段，每经过一个r t t 后，窗口大小一般 都会翻倍。当该值持续增大，超过船f 矗陀嘲时，发送端即进入拥塞避免阶段。此 时，每收到一个新的a c k ，窗口大小都会增加其当前值的倒数。从另一个角度 看，也就是在一个r t t 周期内，只有当发送窗口内的数据包都收到回应时，窗 口大小才会加1 。事实上，此时阈值州矗r 船 代表了网络中当前可用的资源量， 如窗口大小超过此值，那么就应放缓对窗口的调整步伐，以避免拥塞程度的加 重。在传输中，如检测到包丢失，发送方就会将耶脯，嚣 降为当前窗口的一半， 并置当前窗口为l ，重新发送丢失的数据包，回退到慢启动阶段。其中，数据包 丢失的检测，一般通过两种方式进行，一是定时器超时，二是收到3 个重复的 a c k ，也就是常说的“快速重传”。 2 第一章引言 图1 1t c pr e n o 的状态转换图 t c pr e n o 在鼬o e 的基础上增加了“快速恢复”这一策略。图1 1 给出了发送 端采用r e n o 时的状态转换图。其中f 肼r ，代表的就是“快速重传快速恢复” 这一阶段。在r 肋。中，如检测到3 个重复的a c k ，那么它就会进入快速恢复阶 段，而不像在1 址o e 中那样，回退到慢启动。在r c n o 设计中，其做了如下假定： 重复的a c k 通常表明一个数据包已经离开网络，抵达目的端，由于带宽资源总 量守恒，如果此时发送窗口允许发送新包，那么就应当继续发送，以充分利用 闲余的网络资源空间。因此，在每收到一个重复的a c k 时，r e 就会将发送窗 口大小暂时加l 。当窗口内最初丢失的数据包得到确认时，r e n o 就可以退出该 阶段。此时，它会将发送窗口置为刚进入该阶段时窗口大小的一半，并恢复到 拥塞避免阶段。 r e n o 的快速恢复算法在一个发送窗口中只有单个报文丢失的情况下表现良 好，比t a h o e 有很大改进。但不足的是在每个r t t 内，它最多只能重发一个报 文，如存在两个报文丢失，那么发送端就要执行两次快速重传，快速恢复，窗口 调整过于频繁。如有三个或者更多的报文丢失，那么r e n o 就必须依靠定时器的 超时才能恢复常态。这期间窗口大小的持续变化，对传输时延造成了很大的波 动。 n e wr e 在r e n 0 的基础上，改进了上述不足。在快速恢复阶段，其不会轻 易退出该阶段，直到进入该阶段初始时窗口内的所有数据包都收到确认为止。 s a c k 在数据包中增加了选项，使其能够在a c k 中描述那些已被接收到但不是按 序号所期望接收的下一个包的序号。除此以外，这两个版本的t c p 就基本沿用 了r e n o 的做法。 t c pv e g 硒是为了提高源端的数据传输能力而提出的t c p 改进算法。为了纠 正r m o 的扰动性，v e g 蠲提出了一种新的拥塞避免机制。其思想就是由发送端 对路径上缓存的属于该流的包数量进行统计，并通过窗口大小的调节使其保持 第一章引言 在口r z 了二与声r 订1 衄之间。在一个r 1 盯内，窗口是增加还是减少，取决于当前 估计值是否小于口胄乃二，或者大于肚刀二。如果都不是，那么窗口就维持不变。 同r e n o 相比，v e g 嬲对带宽的分配更为公平，不像r 肋。那样易于引起大的时延 波动。其策略描述如下： ( 1 ) 每经过一个r t t ： i f ( w ，r z 瓦。一w r z 7 肚7 了k ) w 一一 ( 2 ) 每次检测到数据包丢失： w = w 2 t c p 的不断发展，策略上的不断改进，增强了其对拥塞局面的处理能力，保 证了蜘m e t 的平稳运行。但是，这还不足以彻底解决问题。随着h 慨m e t 规模 的壮大，更多的流量信息集中在链路上的中间节点，不能为端节点所利用。如 果位处于中间节点的路由器采取更为有效的链路拥塞控制算法，那么拥塞的发 生会得到有效预防。 1 1 2 链路的拥塞控制算法 拥塞控制可分为两部分：源端算法负责动态调整发送速率以缓解其数据所途 经路径上的拥塞程度；链路算法则以隐式或显式的方式，通知源端进行调整。 在当前互联网的实现中，源端算法主要依靠t c p 来执行，而链路算法则要靠主 动队列管理来实现。 从控制角度看，算法可分为开环和闭环两类。采用开环控制时，需要对流量 模型能够进行一定程度的预先估计。如果事先该不能准确描述该模型，那就只 能采取闭环控制。i n t e m e t 的运行具有高度的复杂多变性，事实上多数都是采用 闭环控制。在a q m 中，目前采用的反馈方式有如下几种：丢弃、标记和源抑制。 丢弃是目前多数a q m 采用的反馈方法，t c p 可以通过计时器的超时来断定拥塞 的发生。标记方式可以显示地通知端系统，以避免源端等待进入超时处理程序。 目前，它还只是作为一种选项，尚未得到全面支持。源抑制是指当流量超过路 由器处理能力时，其在丢弃报文的同时向源端发送s q 报文，显式通知源端调整 其发送速率。 4 第一章引言 m t f 推荐在路由器中采用主动队列管理技术。其做法的主要思路就是根据 队长变化对拥塞程度进行检测，预先发送通知给源端，同时采用相应的包丢弃 举措对队列进行管理。这样源端可以在队列溢出之前对其发送速率进行调整， 以免进一步加深拥塞程度。它可以有效降低包丢失率，避免网络运行的长期振 荡。 第二节智能控制算法 智能控制的概念和原理1 5 】主要是针对被控对象、环境、控制目标以及任务的 复杂性而提出来的。随着信息技术的发展，人工智能、信息科学、思维科学、 认知科学和人工神经网络等方面都得到了长足的进步。特别是智能机器人在工 程实践中的广泛应用，为智能控制理论的发展奠定了良好的基础。 1 2 1 预测控制 7 0 年代以来，人们在加强对生产过程的建模、系统辨识、自适应控制、鲁 棒控制、最优控制等研究的同时，开始逐步打破传统思维的束缚，寻找各种对 模型要求低、在线计算方便、成本低，适用于工业过程的新算法。特别是计算 机应用范围的不断扩大，为预测控制的发展及应用创造了有利条件。 预测控制1 6 】i7 】其实是一类的计算机控制算法。最早应用于工业过程的预测控 制算法，有m c h a l e t 、m e h m 提出的建立在非参数模型脉冲基础上的模型预测启 发控制( m p h c ) ，即模型算法控制( m a c ) ，也有c u l t e r 提出的建立在非参数 模型阶跃基础上的动态矩阵控制( d m c ) 等。通常，它们都具有如下特征： ( 1 ) 预测模型建立方便 用来描述过程动态行为的预测模型可以通过简单实验得到，不需深入过 程内部机理，也不需要复杂的系统辨识。 ( 2 ) 滚动优化策略 预测控制不同于通常的离散最优控制，它不是采用一成不变的全局优化 )目标，而是采用滚动式的有限时域优化策略。也就是说，优化过程不是 一次离线进行，而是通过在线计算反复进行，滚动实施，从而使模型失 配、时变、干扰等引起的偏差能得到及时补偿。 ( 3 ) 模型误差反馈校正 由于实际系统中存在着非线性、时变、模型失配、干扰等因素，在预测 第一章引言 算法中，基于不变模型的预测输出，不可能与系统实际输出完全一致。为 此在预测算法中，有必要采用误差反馈的形式，对预测偏差进行校正。这 种利用实时信息对预测模型进行校正的策略，是克服系统中不确定干扰、 提高系统控制精度和鲁棒性的有效措施。 后来，人们在自适应控制理论的研究中发现，为了增强系统的鲁棒性，有必 要在最小方差的基础上，吸取预测控制中多步预测、滚动优化的思想，以便充 分利用反映未来变化趋势的动态信息，提高控制系统的实用性。为此，出现了 一些基于过程参数辨识、带有自校正及在线修正机制的预测控制算法。典型代 表有c l a r k e 的广义预测控制( g p c ) 、l e l i c 的广义预测基点配置控制( g p p ) 等。 特别是c l a r k e 等人提出的广义预测控制g p c ，其可广泛适用于开环不稳定 系统及非最小相位系统，受到了人们的强烈关注。但这些算法都需要求解丢番 图方程或者复杂的矩阵求逆，耗费了大量计算资源。为了弥补不足，快速广义 预测控制f g p c 采用逐步递推的方法，求解最佳控制量。与传统g p c 相比，在 不失控制精度的前提下，其具有更快的计算速度。本文在a q m 中引入了该算法 作为拥塞控制器设计的理论基础。 1 2 2 自扰动控制 p d 控制器目前在工业过程控制中仍占据着主导地位，尽管现代控制论给出 的方法在理论上具有优异的性能，但在实际中仍难有用武之地瞪j 。之所以在实践 中无法得到广泛应用，根本原因还在于实际系统的复杂性、随机性、多变性等 因素，使得理论中的很多边界条件都难以满足，控制效果自然也就难如人意了。 但是，p d 控制在工业实践中的成功应用，还是给予了人们很大启发。如何充分 发扬p d 优点，改进不足，就成了自扰动控制理论不断发展的动力。 图1 2 p d 控制系统结构图 工业控制中广泛使用的p d 采用了依靠目标与实际值的偏差来消除偏差的 策略，正如图1 2 所示，采用偏差的过去、现在和将来变化趋势的加权和来产生 控制量。虽然p d 在实际中应用广泛，但在许多高性能指标要求的运行环境中 6 第一章引言 仍难以胜任。借助于对象模型寻求其它控制方法似乎可行，但实际上却摒弃了 p d 控制的最大优点，即依靠实际行为与控制目标的偏差来消除偏差。只有在充 分发扬现有p d 长处的基础上，改进不足，才能有效解决问题。目前而言，p d 缺陷主要表现在以下几个方面【8 】： ( 1 ) 误差e 的提取 ( 2 ) 由误差e 提取如出 ( 3 ) “加权和”策略 ( 4 ) 积分反馈的副作用 为了弥补上述不足，我们可以引入具有特殊效应的非线性环节，并利用状态 反馈，开发出高性能的控制器。改进措施具体如下【8 】： ( 1 ) 安排过渡过程” ( 2 ) 合理提取“微分”一“跟踪微分器”( 1 h c k i n gd i 位f a m a t o r ，t d ) ( 3 ) 采取合适组合方法一“非线性组合”( 卜口) ( 4 ) 采用“扰动估计”一“扩张状态观测器”( e x t c n d e ds 眦e0 b s e e r ，e s o ) 图1 3a d r c 控制系统结构图 图1 3 所示的就是采取改进措施之后的a d r c 控制系统结构。改进后，其具 有许多优点：首先，采用扩张状态观测器，对系统未建模部分及外界干扰统一 进行了估算，并利用状态反馈抵消其对系统的影响；其次，引入非线性环节， 对偏差的过去、现在和未来变化趋势采用非线性的组合方式来产生控制量，有 效解决了快速性与超调之间的矛盾，增强了其对非线性系统的控制功效；此外， 它还具有较强的鲁棒性，对外界环境具有很强的抗扰动能力。 第一章引言 在本文中，我们以自抗扰控制理论为指导，在充分发扬其不需特定模型的优 点基础上，设计出能够在互联网这样复杂的运行环境内实现流量控制的最新解 决方案。 第三节本文的立意与结构安排 互联网拥塞控制的研究走过了一条漫长的道路，从被动队列管理，到主动队 列管理，到系统化的全面分析方法，控制理论越来越多的融入到这个领域。但 是，互联网本身却是一个涉及诸多因素的复杂系统，许多经典控制方法表现不 甚理想，特别是，很多理论上可行，实践中屡屡受挫的方法。在汲取既有方法 不足的基础上，本文在a q m 中引入了两种新的控制方案，一是f g p c ，二是自 扰动控制。 f g p c 是基于线性模型的，但是该模型是通过实时在线辨识获得的。其能够 在一定程度上克服网络的非线性因素，使短时间内的局部线性化得以准确描述 系统的当前运行状态。自抗扰控制器则不依赖于模型，从而也就避免了复杂的 建模问题。其能够发挥p 控制中偏差反馈及状态干扰估计的长处，有效抑制 网络运行的振荡。本文将在n s 【9 】仿真器上分别对这两种新型拥塞控制器进行测 试，分析其性能表现。 本文共分五章，其结构安排如下： 第一章为引言，首先概要介绍了网络拥塞控制的总体机制，包括两个方面， 即t c p 协议的流量管理和链路上的拥塞控制。随后简要介绍了智能控制算法的 一些发展趋势，主要是与本文相关较密切的预测控制及自扰动控制。 第二章介绍了各种a o m 算法的具体实现机制，如r e d ，p i ，b l u e 等。它 们将作为横向比较的对象，与本文的f g p c 控制器及自扰动控制器进行对比分 析。 第三章介绍f g p c 算法的理论基础，并结合a q m 算法的应用背景，设计出 f g p c 拥塞控制器。同时，阐述了控制器设计中的基本原则及实现上的细节。最 后给出n s 上的仿真结果，并与其他现有a q m 算法进行比较。 第四章介绍了自扰动控制的理论基础，并在a o m 中引入该方法，设计出用 于路由器队列管理的离散自扰动控制器。同样，在n s 上也要进行仿真实验，对 其参数影响，及横向性能比较进行分析。 第一章引言 第五章为总结与展望，总结了本文的工作，指出了创新之处，并对新型拥塞 控制器的优缺点做了评析。对今后工作的方向做了进一步展望。 9 第二章主动队列管理算法 第二章主动队列管理算法 作为对端节点拥塞控制算法的补充，中间节点上的主动队列管理( a q m ) 算法在有效管理路由器缓冲队列的同时，实现了稳定端到端时延，保证o o s ，达 到高吞吐量的目的。d 算法作为a q m 中最具典型性的代表，自问世以来就 一直备受研究者关注，以其为基准衍生出了许多改进版本。与之同时，也为一 些采用其它控制策略的a q m 算法，如p i ，b l u e 等的研究起到了促进积极作用。 鉴于此，本章将从r e d 开始，逐步深入介绍其它a o m 算法。 第一节r 印算法 2 1 1d r o p t a i 算法 d r o p 碱l 是i n l 啪e t 中最初实现的队列管理算法。其简单易行，但性能较差， 极易造成网络运行波动。作为队列管理算法的思想源头，其为a q m 算法的研究 提供了积极借鉴意义。该算法采用先进先出( f i f o ) 原则对入出队列的数据包 进行管理。当队列未满时，数据包将被依次缓存：当队列溢出时，后续进入的 数据包都将被丢弃，直至缓冲队列有闲余空间为止，此种做法常被称为尾部丢 弃，即d m p t a i l 。后来又陆续出现了一些改进，如队列满时，不仅可以采用尾部 丢弃，还可以采取队首丢弃或者随机丢弃方式。但不管怎样，这种做法都是在 缓冲队列溢出时，才被动的采取丢包动作进行处理，而不是事先采取积极主动 的检测手段进行预防，以避免拥塞发生，故d r o p 切_ i l 通常被归入到被动队列管理 一类。 尽管如此，目前d m p t a i l 仍是i n t e m e t 中使用最广泛的队列管理算法。其实 现简单、直观。当然，它也存在着一些缺点。队列溢出时会产生连续丢包，因 而极易造成全局同步，进而降低链路利用率，造成网络资源的浪费。事实上， 在这种情况下，路由器已将拥塞控制的全部责任都推给了源端的t c p 。然而实 践表明，t c p 本身的拥塞控制策略所能达到的范围是有限的。更多的流量信息 集中在路由器上的，不能为t c p 所利用，是网络拥塞控制机制中存在的严重缺 陷。因此，在路由器上采取主动队列管理算法，对拥塞进行检测并预先采取控 制措旌，对于弥补t c p 的不足具有很大意义，d 就是在这种背景下逐步发展 1 0 第二章主动队列管理算法 起来的。 2 1 2r 印算法的基本原理 1 9 9 3 年，s f l o y d 和v j a c o b s o n 提出了随机早期检测( m m d o m e a d y d 曲e c t i o n ， r e d ) 算法【l0 】。其基本思想就是在每个接口维持一个队列，采用指数加权滑动 平均的方法计算队列平均长度口。，并与预先设定的两个阈值m i 矗。、m a ) 【。进行 比较，根据结果的不同采取相应的方法计算丢包概率。 在计算g 一时，为了屏蔽突发数据流的影响，r e d 采取了类似于低通滤波器 的做法。在路由器上，经常会出现这样的情况，发送队列在多数时间内都是空 的，但在某个极短时间内可能被迅速充满，而后又被很快取空。这种情况如被 检测认定为拥塞，则将导致不必要的丢包动作。采用低通滤波器，将计算所得9 一 作为拥塞的衡量标准，可有效避免这一局面。其计算公式如下： = ( 1 一) + g ( 2 1 ) 其中，比为权值，g 为采样所得实际队长。采用滤波器后，由于突发数据流 而导致的实际队长的短时增加不会使平均队长出现大幅增长，从而达到了过滤 短期变化，尽量反映长期变化的目的。 上述公式中，权值比相当于低通滤波器的时间常数，其决定了路由器对当 前输入流量变化跟踪的快慢，其值对性能影响很大。如果过大，砌d 就不能 有效屏蔽短时突发数据流；如果心太小，那么g 。就不能有效跟踪实际队长，从 而也就不能合理估计当前拥塞情况，进而也就不能采取有效的拥塞控制动作。 的选取一般由允许的突发业务流大小及持续时间长短决定，由根据应用场合的 具体要求决定。 计算平均队长是为了反映拥塞程度，并据此指导数据包的丢弃动作，以达到 有效控制队长的目的。每当新包到达时，r e d 就重新计算该值，与m i n 。和n l a ) 【。 进行比较，根据结果的不同采取相应举措。当g 。 m i n 。时，则不丢弃任何新到 达数据包；当m m 。 q 。 m a ) 【m 时，则依线性关系计算丢包概率见；此外，当 g 。m a ) 【。时，则丢弃所有数据包。具体计算公式如下： a 2 o ( o s 吨) 呱差乏盖( 峨c 峨) ( 2 2 ) l ( m s 。) 第二章主动队列管理算法 图2 1 给出了丢包概率岛随平均队长g 。的变化曲线。r e d 使用平均队长g 。 对控制动作进行指导，但在实际中，经常出现实际队长g 远大于平均队长g 。的 情况。有时，虽然平均队长g 还未达最大值，但实际队列已满，如此时有数据包 到达，那么就只能丢弃。这种情况下，r e d 的工作方式就类似于d r 叩t a i l 。 图2 1 丢包概率与平均队长的关系曲线 见并不是最终的丢包概率，还须做进一步修正。最终值见的计算如下： 岛= a “l 一锄) ( 2 3 ) 从( 2 3 ) 中可见，见不仅与g 。有关，还与从上一次丢包开始到现在为止进 入队列的数据包个数c 有关。c 增加时，下一个数据包被丢弃的可能性也增加。 这样做的主要目的是为了实现数据包丢弃的均匀分布，以免出现数据包被连续 丢弃的不利局面。 融的设计目标是尽量使路由器避免在弃尾方式下工作，因此r e d 中的阈 值应根据网络运行的具体要求进行设置。如果经常出现突发性数据流，那么阈 值m i n 。就应足够大，以维持较高的链路利用率。一般情况下，两个阈值之间的 差值应该大于一个r 兀内平均队长的增加值，通常设置m a ) 【。为m m 。的两到三 倍。 2 1 3r 印算法的性能 经大量仿真实践证实，砌d 具有以下优点： ( 1 ) 最小化包丢失率及排队时延。当网路负载变化时，r e d 可以通过检测平 均队长的变化，对当前拥塞程度进行估计，采取相应措施。如果平均队 长g 。超过最大阈值m a 】【。，那么就丢弃所有后继到达数据包。这样做， 第二章主动队列管理算法 既可以抑制g 。的持续增长，又减小了排队时延。反之，如果平均队长 低于下限m i n 。，那么就不丢弃任何数据包，以避免不必要的丢包动作， 使总的包丢失率降至最低。 ( 2 ) r e d 路由器采取了提前丢包及均匀随机丢弃的策略，避免了由于队列溢 出及连续丢包导致的全局同步现象。特别在连续丢包时，大量数据流同 时检测到包丢失，同时减小发送窗口，降低发送速率。宏观上表现为数 据流量时而下降，时而急剧上涨。这种现象周而复始的持续，就表现为 网络运行状态的周期性波动，这在采用d r o p t a i l 算法时经常出现。 ( 3 ) 有效应对网络突发流量。如w e b 流等，经常是突发性质的。r e d 能够屏 蔽短时突发的数据流，避免不必要的丢包动作，从总体上减少数据包的 丢失。 当然，i 也d 算法自身也有不足，体现在以下方面【1 1 】j 【1 2 】f 1 3 】 1 4 】： ( 1 ) 参数设置问题。参数的微小变化往往会给性能带来很大影响。一组r e d 参数在特定环境下表现优良，但在网络负载及其他因素变化时，效果则 大打折扣，甚至相当糟糕。如此一来，在不同应用环境下就需要配置相 应的参数，这给网络管理者带来了诸多不便。 ( 2 ) 有时会出现延时抖动。由于权重很小，平均队长g 。变化缓慢。当网 络负载很重时，口。总是在m a ) 【。附近波动，这会导致网络吞吐量的急剧 下降。 第二节r 印算法的改进 2 2 1 d a p t i v er e d 算法 r e d 算法的显著不足之处在于它对负载的敏感性。随着负载的改变，平均 队长也在相应区域内波动，这对算法稳定性造成了极大负面影响。作为一种 改进机制，a r e d 算法【1 5 】通过检测的变化来判断r e d 的早期检测机制是否 过于积极或保守。如果g 。经常在m i n 。上下波动，则表明早期检测过于积极； 反之，如果g 。总在m 瓤。附近波动，则说明早期检测过于保守。通过g 。的观察， 算法可以实现对m a ) 【。的动态调节。流程如下： 每次计算完平均队长g 。： 城m j h n 2 + 口v g 唧) 0 ( g k 码口v & 屉j 印情弓 1 ) ) j 打嘻蚝+ + ； 丢弃数据包： i f ( 1 1 1 i n ns 盯曙g m a x n ) i f ( g 帆m 剐m i i l g ，“) ) 见= m 戕p ( 口磁一m i i l n ) ( m a x m m i n n ) ； 以概率儿丢弃数据包； e l s ei f ( 口 苫口 m m m ) 不丢弃任何数据包： e l s e 丢弃包； i f ( g 慨不为0 ) 曲。+ + ； 计算平均队长m 砚； 缓存新的数据包： ( 2 ) 当某个数据包离开时： 计算平均队长m 猕； 近g 切一0 ) _ 嘣瞻一一； 从状态表中删除关于数据流f 的信息： 坦7 l 嘲) a 、，g = 嘴q i n m ： e l s e “。g q j 仉苫智= m a 口曙田，1 ) ； i 瑾队列空且数据包离开) g f 拥p = 矗m p ； 其中。为活跃流数量，m i n 。最小队长阈值，m “。最大队长阈值，m a 】( 。：在缓 冲区中允许每条流排队的包数的最大值，m i i l 。：在缓冲区中允许每条流排队的包 第二章主动队列管理算法 数的最小值，g ：当前队列占用大小，砌p ：当前时间，o 舀：平均队长，口v g 。： 每流的平均队长，m ( 即：包p 的流标识，g 慨：队列中来自流i 的包数，s 州砖： 对拥塞通知没有反应的次数。 f m m 的设计初衷是为了解决砌m 的公平性问题。优点主要有： ( 1 ) 对非适应流进行了区分及采取了相应限制措施。 ( 2 ) 丢包率依赖于该流在缓冲区中的占用情况，进而加强了对脆弱流的保护。 ( 3 ) 与r e d 相比，平均传输时间更为公平。 缺点主要在于： ( 1 ) 需要维持每个流的状态信息，计算量大，占用空间多。 ( 2 ) 在平均传输时延上会产生偏见。 2 2 3s 旺d 算法 r e d 算法中存在着负载敏感性的问题，为此，s r e d 采取了从队列中随机 抽取数据包，并与新到数据包进行比较以判断其是否来自同一数据流的办法， 对当前队列中活跃流的数目进行估计，并以此调整丢包率，实现对负载波动的 抗扰动性。 在t c p 流量模型中，丢包概率与发送窗口有如下近似关系： 伽耐p “2 ( 2 4 ) 如果活跃流数目为，那么有 p 。“= q ( 2 5 ) 即 p = ( q ) 2 ( 2 6 ) 式( 2 4 ) 、( 2 5 ) 、( 2 6 ) 给出了算法的总体思路。首先，通过“击中”与否， 对当前活跃流的数目进行估计。其次，根据估计结果，对当前丢包概率进行调 整。此外，还要采取一些其它优化措施。 所谓“击中”与否，就是指当一个新包到达时，s i 冱d 会从队列中随机抽出某 包进行比较，如果同属于一个数据流，则称其为“击中”，可以用来对活跃流数目 进行估计。为了使系统有较长的记忆时间，即能够同已经离开缓冲队列的数据 包进行比较，s r e d 采用了一种称为“僵尸”列表的数据结构。该列表的字段中记 录了最近一段时间内流经该队列的个流的相关信息，如枷f 和“时间戳”等。 运行中，每当新包到达时，s i 通d 就会检查列表中是否还有空余位置。如果 1 6 第二章主动队列管理算法 有，则将该包的流标识加入列表，并置c d 枷f 为0 ，时间戳为该包到达时间。如 果没有，则采用相关方法进行替换。在此种情况下，每逢新包到达，s 砒m 就会 从列表中随机选出