智能系统：基于智能预测控制的网络拥塞主动队列管理算法研究

第3卷第4期 智能系统学报 Vol 3 Ng 4 2008年8月 CAA I Transactions on Intelligent Systems Aug 2008 基于智能预测控制的网络拥塞主动 队列管理算法研究 陈增强，刘忠信，袁著祉，王繁珍 (南开大学自动化系，天津300071) 摘要：路由队列管理是保证网络性能避免网络拥塞的重要手段，目前采用的主要队列管理方法为被动式队列管 理，同时主动式队列管理已经成为近来的主要研究热点.随机早侦测(RD)作为最早提出的主动队列管理方法，更 获得了普遍的关注.使用严格的数学模型来描述由端系统和网关组成的系统，并进行队列管理性能分析提出一种 采用快速广义预测控制的RD控制器(FGPC-RED控制器)，进行网络拥塞控制的研究.介绍了系统的结构及系统的 辨识，并通过仿真证明了FG℃算法在路由队列管理中应用的可行性，可以有效控制队列长度，避免路由拥塞及减 小往返延迟 关键词：智能预测控制；网络拥塞控制，主动队列管理；网络模拟器；RD算法 中图分类号：TP2732文献标识码：A文章编号：16734785(2008)04031308 An active queue management algor ithm for network congestion based on intelligent prediction control CHEN Zeng-qiang,L IU Zhong-xin,YUAN Zhu-zhi,WANG Fan-zhen (Deparment ofAutmation,NankaiUniversity,Tianjin 300071,China) Abstract:Queue management is an mportant means to mprove the perfomance of a nework and avoid netork congestion At present,passive queue management dom inates the queue management field Recently active queue management (AQM)has been getting more and more attention,alng with the random early detection (RED)al- gorithm,the first proposed AQM algorithm.In order to analyze a system made up of clients and a gateway,a strict mathematical modelwas developed to describe the system.A kind ofRED controllerwith fast generalized prediction control was included to analyze congestion control The system's architecture and identification are discussed in de- tail A series of smulations were made,showing that fuzzy generalized predictive control (FGPC)is feasible in queue management and effective in controlling queue length,avoiding network congestion,and reducing round trip delay Keywords:intelligent predictive control,netork congestion control active queue management netork smula- tor,RED algorithm 计算机网络在过去的十几年中经历了爆炸式的 计算机网络规模和负荷的增加，拥塞问题也越来越 增长，特别是目前迅速发展的多媒体通信业务，进一严重.同时随着科技的发展，网络设备的处理速度 步推动Inte met规模的扩大和业务的增长.但随着 不断加快，网络带宽持续增长.但硬件的发展往往赶 不上实际需求的增长，而且局部网络资源不足，也会 收稿日期：2007-1008 基金项目：国家自然科学基金资助项目(60774088)：；教有部科学技 导致网络拥塞.拥塞导致的直接结果就是分组丢失 术研究重点项目(107024). 通信作者：陈增强.Email:chenz四@nankai edu cn 率提高，端到端时延加大，甚至有可能使整个系统发 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net

第 3卷第 4期 智 能 系 统 学 报 Vol. 3 №. 4 2008年 8月 CAA I Transactions on Intelligent System s Aug. 2008 基于智能预测控制的网络拥塞主动 队列管理算法研究 陈增强 ,刘忠信 ,袁著祉 ,王繁珍 (南开大学 自动化系 ,天津 300071) 摘 要 :路由队列管理是保证网络性能、避免网络拥塞的重要手段 ,目前采用的主要队列管理方法为被动式队列管 理 ,同时主动式队列管理已经成为近来的主要研究热点. 随机早侦测 (RED)作为最早提出的主动队列管理方法 ,更 获得了普遍的关注. 使用严格的数学模型来描述由端系统和网关组成的系统 ,并进行队列管理性能分析. 提出一种 采用快速广义预测控制的 RED控制器 ( FGPC2RED控制器 ) ,进行网络拥塞控制的研究. 介绍了系统的结构及系统的 辨识 , 并通过仿真证明了 FGPC算法在路由队列管理中应用的可行性 ,可以有效控制队列长度 ,避免路由拥塞及减 小往返延迟. 关键词 :智能预测控制 ;网络拥塞控制 ;主动队列管理 ;网络模拟器 ; RED算法 中图分类号 : TP273. 2 文献标识码 : A 文章编号 : 167324785 (2008) 0420313208 An active queue management algor ithm for network congestion based on intelligent prediction control CHEN Zeng2qiang, L IU Zhong2xin, YUAN Zhu2zhi, WANG Fan2zhen (Department of Automation, Nankai University, Tianjin 300071, China) Abstract:Queue management is an important means to imp rove the performance of a network and avoid network congestion. A t p resent, passive queue management dom inates the queue management field. Recently active queue management (AQM) has been getting more and more attention, along with the random early detection (RED) al2 gorithm, the first p roposed AQM algorithm. In order to analyze a system made up of clients and a gateway, a strict mathematical modelwas developed to describe the system. A kind of RED controllerwith fast generalized p rediction control was included to analyze congestion control. The system’s architecture and identification are discussed in de2 tail. A series of simulations were made, showing that fuzzy generalized p redictive control (FGPC) is feasible in queue management and effective in controlling queue length, avoiding network congestion, and reducing round trip delay. Keywords: intelligent p redictive control; network congestion control; active queue management; network simula2 tor; RED algorithm 计算机网络在过去的十几年中经历了爆炸式的 增长 ,特别是目前迅速发展的多媒体通信业务 ,进一 步推动 Internet规模的扩大和业务的增长. 但随 通信作者 :陈增强. E2 收稿日期 : 2007210208. 基金项目 :国家自然科学基金资助项目 (60774088) ;教育部科学技 术研究重点项目 (107024). mail: chenzq@ nankai. edu. cn. 着 计算机网络规模和负荷的增加 ,拥塞问题也越来越 严重. 同时随着科技的发展 ,网络设备的处理速度 不断加快 ,网络带宽持续增长. 但硬件的发展往往赶 不上实际需求的增长 ,而且局部网络资源不足 ,也会 导致网络拥塞. 拥塞导致的直接结果就是分组丢失 率提高 ,端到端时延加大 ,甚至有可能使整个系统发

·314· 智能系统学报 第3卷 生崩溃)当网络处于拥塞崩溃状态时，微小的负 在延迟时间与模型时间不一致时仍具有良好的鲁棒稳 载增量都将使网络的有效吞吐量急剧下降.当负载 定性.另外，这种控制算法基于传统的参数模型，其模 减小时，拥塞可以自动恢复 型参数少，并采用多步预测、滚动优化和反馈校正等策 单纯地增加网络资源之所以不能解决拥塞问 略控制效果好)基于以上的因素，文献[6提出了一 题，是因为拥塞本身是一个动态问题，它不可能只靠 种快速广义预测控制算法(fast generalized predictive 静态的方案来解决，而是需要协议在网络出现拥塞 control,.FGPC),与传统GPC相比，具有更快的运算速 时保护网络的正常运行.目前对互联网进行的拥塞 度，满足控制实时性的要求.本文基于文献[6的FGPC 控制主要是依靠在源端执行的基于窗口的TCP拥 算法提出了一种网络拥塞控制主动队列管理算法(FG 塞控制2机制.TCP拥塞控制是一种端到端的控制 PC-RD算法).FGPC-RE控制方法可有效地减少拥 机制，它是通过改变一些参数实现的.TCP基于窗口 塞现象的发生，降低往返延迟，改善网络的性能 的端到端的拥塞控制对于Inte met的鲁棒性起到了 1 RED算法 关键作用.然而，随着Intemet本身的迅速发展，其 网络规模越来越庞大结构日趋复杂.仅仅依靠端到 在当前的互联网上，丢包是对端节点进行拥塞通 端的拥塞控制是不够的，网络也需要参与资源的控 知的主要机制，解决路由器满队列问题的方法便是 制工作.路由器直接掌握着互联网上各种网络传输 在队列满之前丢包，这样端节点便能在队列溢出前对 信息，能够有效地监控队列的长度，从而尽早检测到 拥塞做出反应这种方法便称为“生动式队列管理” 早期的拥塞(incip ient congestion).另外，路由器能 RD7算法是最常用的一种AQM技术，其基 够全面地审视各个流对拥塞造成的影响，从而决定 本思想是通过监控路由器输出端口队列的平均长度 将拥塞信息通知哪个源端，使其降低数据发送速度. 来探测拥塞.一旦发现拥塞逼近，就随机地选择源端 因此采用基于路由器的拥塞控制和TCP端到端拥 来通知拥塞，使它们在队列溢出导致丢包之前降低 塞控制相结合的方法，是解决目前互联网拥塞控制 发送数据速率，从而缓解网络拥塞.这样对面向连接 问题的一个主要途径) 的TCP数据流来说，RED就有可能避免丢弃属于同 基于路由器的拥塞控制主要是通过对其队列进行 一连接的连续数据包，从而提高连接的吞吐量.图1 管理来实现的，目前的队列管理主要还是被动式队列 显示了平均队长与丢包率的关系 管理(passive queue management,PQM).本质上PQM 并没有参与到网络拥塞管理中去，只是在队列溢出的 情况下被动地丢包.互联网工程工作小组(intemet en~ gineering task force,ETF)推荐在路由器上使用主动式 队列管理(active queue management,.AQM)I4机制来控 Min_th Max_th 4ive 制在什么时候丢多少包，从而有效地管理队长度，以支 图1平均队长与丢包率的关系 持端到端的拥塞控制！ Fig I The relation beween average queue 从控制的观点看，可以将端系统和网关组成的系 length and packet bss ratio 统看成是一个反馈控制系统考虑到其复杂性及时延 RD有2个阈值：和4hax.当一个数据包到 性，为实现对系统的高精度、高可靠以及高鲁棒性的控 达路由器时，RED将当前a和这2个阈值按以下 制效果，需使用具有鲁棒性的预测控制器.Clak等人 原则比较：如果4e≤g时，将此包排队；如果m< 提出的广义预测控制(generalized predictive control, a<x,计算丢弃概率P,并以P丢弃此包；如果 GPC)是一种基于模型参数的自适应预测控制算法，其 4x≤g4e,则丢弃此包 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net

生崩溃 [ 1 ] . 当网络处于拥塞崩溃状态时 ,微小的负 载增量都将使网络的有效吞吐量急剧下降. 当负载 减小时 ,拥塞可以自动恢复. 单纯地增加网络资源之所以不能解决拥塞问 题 ,是因为拥塞本身是一个动态问题 ,它不可能只靠 静态的方案来解决 ,而是需要协议在网络出现拥塞 时保护网络的正常运行. 目前对互联网进行的拥塞 控制主要是依靠在源端执行的基于窗口的 TCP拥 塞控制 [ 2 ]机制. TCP拥塞控制是一种端到端的控制 机制 ,它是通过改变一些参数实现的. TCP基于窗口 的端到端的拥塞控制对于 Internet的鲁棒性起到了 关键作用. 然而 ,随着 Internet本身的迅速发展 ,其 网络规模越来越庞大 ,结构日趋复杂. 仅仅依靠端到 端的拥塞控制是不够的 ,网络也需要参与资源的控 制工作. 路由器直接掌握着互联网上各种网络传输 信息 ,能够有效地监控队列的长度 ,从而尽早检测到 早期的拥塞 ( incip ient congestion). 另外 ,路由器能 够全面地审视各个流对拥塞造成的影响 ,从而决定 将拥塞信息通知哪个源端 ,使其降低数据发送速度. 因此采用基于路由器的拥塞控制和 TCP端到端拥 塞控制相结合的方法 ,是解决目前互联网拥塞控制 问题的一个主要途径 [ 3 ] . 基于路由器的拥塞控制主要是通过对其队列进行 管理来实现的 ,目前的队列管理主要还是被动式队列 管理 (passive queue management, PQM ). 本质上 PQM 并没有参与到网络拥塞管理中去 ,只是在队列溢出的 情况下被动地丢包. 互联网工程工作小组 ( internet en2 gineering task force, IETF)推荐在路由器上使用主动式 队列管理 (active queue management, AQM) [4 ]机制来控 制在什么时候丢多少包 ,从而有效地管理队长度 ,以支 持端到端的拥塞控制. 从控制的观点看 ,可以将端系统和网关组成的系 统看成是一个反馈控制系统. 考虑到其复杂性及时延 性 ,为实现对系统的高精度、高可靠以及高鲁棒性的控 制效果 ,需使用具有鲁棒性的预测控制器. Clark等人 提出的广义预测控制 ( generalized predictive control, GPC)是一种基于模型参数的自适应预测控制算法 ,其 在延迟时间与模型时间不一致时仍具有良好的鲁棒稳 定性.另外 ,这种控制算法基于传统的参数模型 ,其模 型参数少 ,并采用多步预测、滚动优化和反馈校正等策 略 ,控制效果好 [5 ] .基于以上的因素 ,文献 [6 ]提出了一 种快速广义预测控制算法 (fast generalized predictive control, FGPC) ,与传统 GPC相比 ,具有更快的运算速 度 ,满足控制实时性的要求.本文基于文献 [6 ]的 FGPC 算法提出了一种网络拥塞控制主动队列管理算法 (FG2 PC2RED算法 ). FGPC2RED控制方法可有效地减少拥 塞现象的发生 ,降低往返延迟 ,改善网络的性能. 1 RED算法 在当前的互联网上 ,丢包是对端节点进行拥塞通 知的主要机制 ,解决路由器“满队列 ”问题的方法便是 在队列满之前丢包 ,这样端节点便能在队列溢出前对 拥塞做出反应.这种方法便称为“主动式队列管理 ”. RED [ 7 ]算法是最常用的一种 AQM 技术 ,其基 本思想是通过监控路由器输出端口队列的平均长度 来探测拥塞. 一旦发现拥塞逼近 ,就随机地选择源端 来通知拥塞 ,使它们在队列溢出导致丢包之前降低 发送数据速率 ,从而缓解网络拥塞. 这样对面向连接 的 TCP数据流来说 , RED就有可能避免丢弃属于同 一连接的连续数据包 ,从而提高连接的吞吐量. 图 1 显示了平均队长与丢包率的关系. 图 1 平均队长与丢包率的关系 Fig. 1 The relation between average queue length and packet loss ratio RED有 2个阈值 : qm in和 qmax . 当一个数据包到 达路由器时 , RED将当前 qave和这 2个阈值按以下 原则比较 :如果 qave ≤qm in时 ,将此包排队 ;如果 qm in < qave < qmax ,计算丢弃概率 P,并以 P丢弃此包 ;如果 qmax ≤qave ,则丢弃此包. · 413 · 智 能 系 统 学 报 第 3卷

第4期 陈增强，等：基于智能预测控制的网络拥塞主动队列管理算法研究 ·315 RD的目的是控制拥塞结点的队列长度在最 更快的运算速度.正适合了网络流量变化的特点. 大和最小之间，保持对资源的高利用率，RD的有 算法实现如下： 效性经过了一些实践的验证，但依旧存在一些缺陷. 1)初始化：令Pw=pRv=pK=0,Lw=0 1)RD算法的性能敏感于设计参数和网络状况， S=0,Qx=入 在特定的网络负载状况下依然会导致多个TCP的同 2)取k=N,N-1),1,计算： 步造成队列震荡，吞吐量降低和时延抖动加剧 F,)=中(P,A:K,B) 2)RED算法的公平性和稳定性也存在问题.在 -aA 网络严重拥塞时，RD往往失去对队列的控制能 即 ,从而 K K.+aB 力，带来的问题甚至比尾部丢弃严重 3)自RED被首次提出来之后，它的参数配置就 q(P:-aA) a=P0)A0),(K.1,Qs.1:P.1 是一个没有彻底解决的问题， K.+aB 正是由于RED存在着上面所述诸多问题，导致 Lk.1:R.1,Sk.1=中，（区，Q:E,Lk:R,S, 了其他几种AQM技术的产生.这些AQM技术有些 R.] 是在RD基础上的扩充，弥补了RD的一些缺点， 即 Ok.1 Lk.1 St. 比如FRED、ARED等；另外一些AQM算法则是利 -7「 K P.Ra 用链路状态、队列占用状况等信息来管理队列，比如 Y S BLUE、SRED等. K.1 P.1 Rk. 2快速广义预测控制(FGPC)算法 从而 0k.1 Li.1 St. 基于文献[6]中的快速广义预测控制方法，对 g(BK-YQ) BP:-YL BR:YSA 端系统和网关组成的系统采用下面具有随机扰动的 YK +BOs YP:+BLs YRs +BS. 离散差分方程来描述： 式中：B=Q(0)/尽0)+g10),Y=K(0)/ A(E)y(=B(E)u(k-1)+ξ(E)△ N尼o)+00 (1) 3)计算最优控制增量△=(Sw,-Lo)/Qo 式中：A(E)=1+41+…+aa0;B()= 4)计算最优控制量0=u.1+△场转2)， 1+1+…+4。w,△=1-2为差分算子， 是后向移位算子，(k-1)是系统输入信号，y()是 3 FGPC-RED控制器的结构 系统输出信号，ξ（是噪声信号 31 FGPC-RED控制器的结构 将式(1)两边乘△并整理，推导出基于式(2)综 该控制系统的目标为稳定并控制路由器缓冲区队 合加权的目标函数的GPC算法： 列长度的大小在一个合适的目标值，来提高链路的利 用率及减小队列延迟.由于FGC控制算法在各个方 Jlp(n).(2 面的广泛成功应用1，因此在此采用FGC作为主要 式中：M为控制步长，w为t+k时刻的期望输出，输 的手段来对系统进行控制.系统控制框图如图2所示」 出加权p和控制加权入分别是的多项式 在该系统中，Q,为期望的队列长度，是系统的 为避免求解D iophantine方程，FGPC利用反向 输入设定值，g为采样时刻的队列长度，为通过 递推对GP℃进行变换，算法复杂度仅为ON·n), 滤波之后得到的平均队列长度，为预测所得的丢 N与n为求解矩阵的维数.与传统GPC相比，具有 包率，是被控对象的输出，w=()公为输入系统 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net

RED的目的是控制拥塞结点的队列长度在最 大和最小之间 ,保持对资源的高利用率. RED 的有 效性经过了一些实践的验证 ,但依旧存在一些缺陷. 1) RED算法的性能敏感于设计参数和网络状况 , 在特定的网络负载状况下依然会导致多个 TCP的同 步 ,造成队列震荡 ,吞吐量降低和时延抖动加剧. 2) RED算法的公平性和稳定性也存在问题. 在 网络严重拥塞时 , RED 往往失去对队列的控制能 力 ,带来的问题甚至比尾部丢弃严重. 3)自 RED被首次提出来之后 ,它的参数配置就 是一个没有彻底解决的问题. 正是由于 RED存在着上面所述诸多问题 ,导致 了其他几种 AQM技术的产生. 这些 AQM技术有些 是在 RED基础上的扩充 ,弥补了 RED的一些缺点 , 比如 FRED、ARED 等 ;另外一些 AQM 算法则是利 用链路状态、队列占用状况等信息来管理队列 ,比如 BLUE、SRED等. 2 快速广义预测控制 ( FGPC)算法 基于文献 [ 6 ]中的快速广义预测控制方法 ,对 端系统和网关组成的系统采用下面具有随机扰动的 离散差分方程来描述 : A (z - 1 ) y ( k) = B (z - 1 ) u ( k - 1) +ξ(z - 1 ) /Δ. (1) 式中 : A (z - 1 ) = 1 + a1 z - 1 + … + aN a z - N a ; B ( z - 1 ) = 1 + b1 z - 1 + … + bN b z - N b ,Δ = 1 - z - 1为差分算子 , z - 1 是后向移位算子 , u ( k - 1)是系统输入信号 , y ( k)是 系统输出信号 ,ξ( k)是噪声信号. 将式 (1)两边乘Δ并整理 ,推导出基于式 (2)综 合加权的目标函数的 GPC算法 : J = ∑ N k =1 [ p ( yk - wk ) ] 2 + ∑ M - 1 k =0 (λΔuk ) 2 . (2) 式中 :M 为控制步长 , wk 为 t + k时刻的期望输出 ,输 出加权 p和控制加权 λ分别是 z - 1的多项式. 为避免求解 D iophantine方程 , FGPC利用反向 递推对 GPC进行变换 ,算法复杂度仅为 O (N ·n) , N 与 n为求解矩阵的维数. 与传统 GPC相比 ,具有 更快的运算速度. 正适合了网络流量变化的特点. 算法实现如下 : 1) 初始化 :令 PN = p, RN = p, KN = 0, LN = 0, SN = 0, QN =λ. 2) 取 k = N, (N - 1) , …, 1,计算 : ( P…k , K…k ) =φ+ ( PK , A ^ ; KK , B ). 即 q - 1 P…k K…k = Pk -αA ^ Kk +αB ,从而 P…k K…k = q ( Pk -αA ^ ) Kk +αB ,α= Pk (0) /A ^ ( 0) , ( Kk - 1 , Qk - 1 ; Pk - 1 , Lk - 1 ; Rk - 1 , Sk - 1 ) =φ+ ( K…k , Qk ; P…k , Lk ; Rk , Sk ) , 即 q - 1 Kk - 1 Pk - 1 Rk - 1 Qk - 1 Lk - 1 Sk - 1 = β -γ γ β K…k P…k Rk Qk Lk Sk . 从而 Kk - 1 Pk - 1 Rk - 1 Qk - 1 Lk - 1 Sk - 1 = q (βK…k -γQk ) βP…k -γLk βRk -γSk γK…k +βQk γP…k +βLk γRk +βSk . 式中 :β = Qk ( 0 ) / K… 2 k (0) +Q 2 k (0) , γ = K…k ( 0 ) / K… 2 k (0) +Q 2 k (0). 3) 计算最优控制增量Δu0 = (S0wr - L0 y0 ) /Q0 . 4) 计算最优控制量 u0 = u - 1 +Δu0 转 2). 3 FGPC2RED控制器的结构 3. 1 FGPC2RED控制器的结构 该控制系统的目标为稳定并控制路由器缓冲区队 列长度的大小在一个合适的目标值 ,来提高链路的利 用率及减小队列延迟. 由于 FGPC控制算法在各个方 面的广泛成功应用 [ 8210 ] ,因此在此采用 FGPC作为主要 的手段来对系统进行控制.系统控制框图如图 2所示. 在该系统中 , QT 为期望的队列长度 ,是系统的 输入设定值 , q为采样时刻的队列长度 , qave为通过 滤波之后得到的平均队列长度 , p为预测所得的丢 包率 ,是被控对象的输出 , w =ξ(z - 1 ) /Δ为输入系统 第 4期 陈增强 ,等 :基于智能预测控制的网络拥塞主动队列管理算法研究 · 513 ·

·316· 智能系统学报 第3卷 的辨识步数counts 0, FGPC-RED TCP 2)随机产生一个丢包率p为辨识需要，p在 控制器 处理过程 0.03~0.06之间取值： 滤波器 3)将p赋值给RD系统的丢包率： 模型 4)调用最小二乘法的辨识程序对整个系统进 行辨识： 图2FGPC-RD控制系统 5)辨识步数n加1 Fig 2 FGPC-RED control system 32FGPC-RED系统的运算流程及参数配置 的噪声信号 FGPC-RED控制系统在时刻n的运行流程为 将运行时间分成许多个大小固定时间段，即采 1)对当前的队长进行采样，即g(n: 样间隔为8().时间标志为n第n个时间段用 2)用式(3)计算平均队列长度ge(n: T(n)来表示.g(n)为在第n个时间段的真实队列 3)采用递推最小二乘法的式(4)与(5)对系统 长度.系统的目标就是找到一个恰当的丢包率使系 的模型进行辨识，并将辨识所得的系统传递给 统的队列长度保持在目标队长，而不受网络的流量 FGPC-RED控制器； 及扰动如UDP流的影响 4)通过FGPC算法对丢包率pn进行预测： 从图2可以看出，该系统主要包括3个部分：式 5)在时刻n使用p(m)作为系统的丢包率： (3)所给的低通滤波器：辨识模块，在该部分采用递 推最小二乘法V进行系统辨识，FGPC-RED控制 6)存储ae(n)及p(n,这些将在n+1时刻计 算时被使用 器，根据Q对p进行预测. 在该部分可以看出，FGPC-RED控制器主要有 由于网络流量的突变及其他扰动如UDP流2) 以下参数： 的存在，实际的队列长度可能会产生强烈的波动，因 采样间隔δ()：该参数决定了p的更新时间间 此低通滤波器被采用.经过滤波的队列长度为 隔.8（减小时，计算量将会增加.另一方面，较小的 qave (n)=(1-B)gove (n-1)+Bg(n).(3) 8()将提高系统的性能.因此，应该合理选取采样间 式中：β为滤波因子，在表现上看来，是平均队列的 隔，在仿真中8()取为01s 权.因此，该控制器的主要目标为调整来控制队 目标队列长度Q:该参数直接决定了系统稳定 列长度到给定的值。 状态时的队列长度，队列长度将影响使用率及队列 在运行时，应对系统模型进行实时的辨识，此处 采用了递推最小二乘法来对系统进行辨识.8，为 延迟.较高的Q,将提高系统的利用率，但会增大队 N+次采样数据得到的最小二乘估计量，第 列延迟.该参数应该根据路由器的性能来确定 n+N+次采样后，得到的估计量为8+1 滤波因子阝：该参数影响滤波器的反应速度.B 卫ΦxL 较大时，实时的队列长度的变化将较快地影响平均 g=9+oR中+d 队列长度.常采用的β为0002 [y(n+N+1)-ΦN,8, 4) 4算法仿真与性能评估 EΦΦN1P PN+1 Px (5) Φ1Pw④x+1+1 对仿真工作的评价，一个重要的标准就是仿真工 各符号和含义请参考文献111 具的准确性).在综合比较了多种通信网仿真工具 在t()时刻，辨识过程为 以后，选定了著名的仿真软件NS作为仿真平台.NS 1)如果当前辨识的步数n小于系统初始设置 为美国国防部远景规划署(Ddefense Advanced Re 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net

图 2 FGPC2RED控制系统 Fig. 2 FGPC2RED control system 的噪声信号. 将运行时间分成许多个大小固定时间段 ,即采 样间隔为 δ( t). 时间标志为 n, 第 n 个时间段用 T ( n)来表示. q ( n) 为在第 n个时间段的真实队列 长度. 系统的目标就是找到一个恰当的丢包率使系 统的队列长度保持在目标队长 ,而不受网络的流量 及扰动如 UDP流的影响. 从图 2可以看出 ,该系统主要包括 3个部分 :式 (3)所给的低通滤波器;辨识模块 ,在该部分采用递 推最小二乘法 [ 11 ]进行系统辨识; FGPC2RED 控制 器 ,根据 QT 对 p进行预测. 由于网络流量的突变及其他扰动如 UDP流 [ 12 ] 的存在 ,实际的队列长度可能会产生强烈的波动 ,因 此低通滤波器被采用. 经过滤波的队列长度为 qave ( n) = (1 - β) qave ( n - 1) +βq ( n). (3) 式中 :β为滤波因子 ,在表现上看来 ,是平均队列的 权. 因此 ,该控制器的主要目标为调整 p,来控制队 列长度到给定的值. 在运行时 ,应对系统模型进行实时的辨识 ,此处 采用了递推最小二乘法来对系统进行辨识. θ^N 为 N + K次 采 样 数 据 得 到 的 最 小 二 乘 估 计 量 , 第 n +N + 1次采样后 ,得到的估计量为 θ^N + 1 : θ^N +1 =θ^N + PNΦN +1 ΦT N +1 PNΦN +1 +w - 1 N +1 · [ y ( n +N + 1) - ΦT N +1θ^N ], (4) PN +1 = PN - PNΦN +1ΦT N +1 PN ΦT N +1 PNΦN +1 + 1 . (5) 各符号和含义请参考文献 [11 ]. 在 t( n)时刻 ,辨识过程为 1)如果当前辨识的步数 n小于系统初始设置 的辨识步数 counts; 2)随机产生一个丢包率 p, 为辨识需要 , p在 0103～0106之间取值; 3)将 p赋值给 RED系统的丢包率; 4)调用最小二乘法的辨识程序对整个系统进 行辨识; 5)辨识步数 n加 1. 3. 2 FGPC2RED系统的运算流程及参数配置 FGPC2RED控制系统在时刻 n的运行流程为 1)对当前的队长进行采样 ,即 q ( n) ; 2)用式 (3)计算平均队列长度 qave ( n) ; 3)采用递推最小二乘法的式 ( 4)与 ( 5)对系统 的模型进行辨识 , 并将辨识所得的系统传递给 FGPC2RED控制器; 4) 通过 FGPC算法对丢包率 p ( n)进行预测; 5) 在时刻 n使用 p ( n)作为系统的丢包率; 6) 存储 qave ( n)及 p ( n) ,这些将在 n + 1时刻计 算时被使用. 在该部分可以看出 , FGPC2RED 控制器主要有 以下参数 : 采样间隔 δ( t) :该参数决定了 p的更新时间间 隔.δ( t)减小时 ,计算量将会增加. 另一方面 ,较小的 δ( t)将提高系统的性能. 因此 ,应该合理选取采样间 隔 ,在仿真中 δ( t)取为 0. 1 s. 目标队列长度 QT :该参数直接决定了系统稳定 状态时的队列长度 ,队列长度将影响使用率及队列 延迟. 较高的 QT 将提高系统的利用率 ,但会增大队 列延迟. 该参数应该根据路由器的性能来确定. 滤波因子 β:该参数影响滤波器的反应速度. β 较大时 ,实时的队列长度的变化将较快地影响平均 队列长度. 常采用的 β为 0. 002. 4 算法仿真与性能评估 对仿真工作的评价 ,一个重要的标准就是仿真工 具的准确性 [ 12 ] . 在综合比较了多种通信网仿真工具 以后 ,选定了著名的仿真软件 NS作为仿真平台. NS 为美国国防部远景规划署 (Ddefense Advanced Re2 · 613 · 智 能 系 统 学 报 第 3卷

第4期 陈增强，等：基于智能预测控制的网络拥塞主动队列管理算法研究 ·317 search Projects Agency,DARPA)资助，由Berkelay国 800m 家实验室开发的网络模拟器(netork smulator) 700 600 FGPC-RED控制器的主要目的是将队列长度控 500 制在一个目标值Q,并使之具有较快的收敛速度，克 400%称 300 服RD存在的对参数和网络状况过于敏感，从而造 200 成队列震荡，吞吐量降低和时延抖动加剧现象 100 采用如图3所示的哑铃状(dumbbell)网络拓扑 406080100 t/s 结构，包含2个路由器以及多个源节点和目的节点， (b)400个CP连接时的情形 0 图4Q,为400时，100和400个CP连接时候的队列 源节点 目的节点 长度 Fig 4 The queue length when O,is 400 and TCP link is 100and400 为了更充分地观察FGPC-RED控制器的性能 图3仿真网络拓扑图 在400个连接时，设置了Q,为200与600 Fig 3 The smulation network topobgy 1000 如图3所示：节点m与h为路由器，m与历间 900 800 链路的带宽(capacity)为45Mbps,传输延迟为5ms, 700 600 队列缓存管理模块的)类型为FGPC-RED.缓冲区的 500 大小为1000个包，采样间隔6（为100ms目标队列 400 300 长度Q,为400，滤波因子B为Q002 200 100 41基于TCP连接的仿真 04 20 4060 80100 1/s 在该部分主要测试是在只有CP连接时， FGPC-RED控制器是否能达到预期的设计目标】 (aQ,为200的情形 图4显示了FGPC-RED控制器在100~400个 连接时候的实时队列长度.可以看到FGPC-RED控 1w酬 800 制器可以比较快地将对列长度控制到并且稳定在 700 Q,同时可以看出，400个连接时平均队长的波动要 600 500 小于100个连接的平均队长的波动. 400 300 800m 200 700 100 600 0 20 406080100 t/s 500 ✉400 树 b)Q,为600的情形 300 200 图5400个1CP连接时，Q,为200与 100 600时的队列长度 0 20 4060 80100 1/s Fig 5 The queue length when TCP link is 400. and r is 200 and 600 (a)100个TCP连接时的情形 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net

search Projects Agency, DARPA)资助 ,由 Berkelay国 家实验室开发的网络模拟器 ( network simulator). FGPC2RED控制器的主要目的是将队列长度控 制在一个目标值 QT ,并使之具有较快的收敛速度 ,克 服 RED存在的对参数和网络状况过于敏感,从而造 成队列震荡,吞吐量降低和时延抖动加剧现象. 采用如图 3所示的哑铃状 ( dumbbell)网络拓扑 结构 ,包含 2个路由器以及多个源节点和目的节点. 图 3 仿真网络拓扑图 Fig. 3 The simulation network topology 如图 3所示:节点 n1 与 n2 为路由器, n1 与 n2 间 链路的带宽 ( capacity)为 45 Mbp s,传输延迟为 5 ms, 队列 (缓存管理模块的 )类型为 FGPC2RED. 缓冲区的 大小为 1 000个包 ,采样间隔δ( t)为 100 ms,目标队列 长度 QT 为 400,滤波因子β为 0. 002. 4. 1 基于 TCP连接的仿真 在该部分主要测试是在只有 TCP 连接时 , FGPC2RED控制器是否能达到预期的设计目标. 图 4显示了 FGPC2RED控制器在 100～400个 连接时候的实时队列长度. 可以看到 FGPC2RED控 制器可以比较快地将对列长度控制到并且稳定在 QT ,同时可以看出 , 400个连接时平均队长的波动要 小于 100个连接的平均队长的波动. ( a) 100个 TCP连接时的情形 ( b) 400个 TCP连接时的情形 图 4 QT 为 400时 , 100和 400个 TCP连接时候的队列 长度 Fig. 4 The queue length when QT is 400 and TCP link is 100 and 400 为了更充分地观察 FGPC2RED控制器的性能 , 在 400个连接时 ,设置了 QT 为 200与 600. ( a) QT 为 200的情形 ( b) QT 为 600的情形 图 5 400个 TCP连接时 , QT 为 200与 600时的队列长度 Fig. 5 The queue length when TCP link is 400, and QT is 200 and 600 第 4期 陈增强 ,等 :基于智能预测控制的网络拥塞主动队列管理算法研究 · 713 ·