基于非线性主动队列管理的网络输出反馈控制

基于非线性主动队列管理的网络输出反馈控制

随着网络规模的扩大和网络服务质量的要求的提高，网络过载的预防和控制已成为一个重要的研究主题。路由器中的主动队列管理(Activequeuemanagement,AQM)机制可以通过提前检测拥塞来提高网络的吞吐量,同时有效地控制缓存队列的长度,从而为要求时延保证的Internet业务提供一种良好的保障机制,是作用在网络中间节点上的一种有效的拥塞控制策略。由于网络拥塞控制模型可以看作是1个反馈控制系统,所以从控制理论的角度来研究网络拥塞控制可以取得有效的控制性能,例如参考文献对现有经典的AQM算法的鲁棒稳定性、公平性等性能进行了分析,从而改进了一些经典算法,同时一些基于现代控制理论的新的AQM算法也相继被提出。KSFC算法基于鲁棒控制理论,利用线性矩阵不等式(Linearmatrixinequality,LMI)方法设计了AQM系统的状态反馈控制率,但是由于这类算法要获取TCP窗口值,因此其实用性受到很大限制;α-robustAQM简化了系统控制率,但是在变时滞条件下的控制性能较差;参考文献根据基于规则的预测控制理论(Rule-basedpredictivecontrol,RBPC)设计了一类新的AQM算法,用来稳定瓶颈路由器中的队列扰动。然而这些新的AQM算法均基于简单的线性控制,是在小信号线性化的基础上设计的,所以存在局部稳定性的问题。参考文献设计了一种具有全局稳定性的非线性拥塞控制模型,但是其仅针对单链路和单TCP源,具有一定的局限性;参考文献设计了一种非线性输出反馈控制算法(Nonlinearoutputfeedbackcontrol,NOFC),可以使瓶颈路由器的队列长度稳定在期望值,但是把往返时间(Roundtriptime,RTT)设为固定值,与实际的网络情况不相符合。因为RTT可以表示为队列长度的函数,本文根据这一条件设计了基于变化RTT的网络模型,通过反步设计法设计了非线性AQM算法。由于在实际网络中,路由器无法得到TCP窗口值,为了使设计的非线性AQM算法仅与队列长度相关,提出了TCP窗口值的观测器设计,并证明了当丢包率的取值范围为0～1时,TCP窗口观测值收敛到实际值。ns仿真表明,本文设计的基于反步设计法的非线性主动队列管理算法(NonlinearAQMalgorithm-backsteppingtechnique,NAQM-bt)在变化的网络环境下具有较好的鲁棒稳定性,并保证了网络具有较高的吞吐量和较低的丢包率。1多线程窗口大小估计Misra等人于2000年基于流体理论提出的网络模型,描述了瓶颈路由器和TCP窗口的动态特性,在忽略超时重传机制下,可用非线性微分方程组(1)来描述˙W(t)=1R(t)-W2(t)2R(t)p(t)˙q(t)=-C+ΝR(t)W(t)(1)式中:状态变量W(t)和q(t)分别为平均TCP窗口大小和平均队列长度,控制输入p(t)为数据包的标注概率,R(t)、C和N分别是RTT、链路容量和TCP连接数。在实际网络环境下N应该是时间t的函数,为了计算简便,设为已知的常数。设Tp是整个网络的传输延迟,则R(t)可以表示为R(t)=q(t)/C+Tp,代入方程组(1)得˙W(t)=Cq(t)+ΤpC-CW2(t)2(q(t)+ΤpC)p(t)˙q(t)=ΝCq(t)+ΤpCW(t)-C(2)设ˉq=1/(q+ΤpC),代入方程组(2)得˙W=Cˉq-(C/2)W2ˉqp(t)˙ˉq=-ΝCWˉq3+Cˉq2(3)由于在实际路由器中,无法得到TCP窗口的大小,所以设计开环观测器的动态方程如下˙ˆW=Cˉq-(C/2)ˆW2ˉqp(t)(4)式中:ˆW是TCP窗口大小观测值,定义ε=W-ˆW为实际窗口值和观测值之间的估计误差。假设1存在常量t0>0以及正常量T0和α,使得∀t≥t0,丢包率p(t)满足1Τ0∫tt+T0p(s)ds≥α(5)假设2limsupt→∞p(t)<ˉpˉp∈(0,1)根据网络的物理特性,对于丢包率p(t)做出了上述的2个假设。假设1意味着在一定长的时间间隔T0里,路由器缓存中标注或丢弃的数据包总数应该达到一定的数量级。因为在TCP网络中,发送端以线形增加的方式发送数据包,一定长时间内过多数据包的积累必然会造成网络拥塞。在拥塞控制中,并不希望由于过多的数据包丢弃造成链路利用率偏低,假设2意味着当系统趋于稳定时丢包率p(t)稳定在某一个小于1的值附近。引理1假设丢包率p(t)满足假设2,则TCP窗口大小观测值满足liminft→∞ˆW(t)>0。证明由假设2可以得到,对于足够大的t‚˙ˆW≥Cˉq-(C/2)ˆW2ˉqˉp。考虑微分方程˙y1=Cˉq-(C/2)y21ˉqˉp有1个稳定平衡点√2/ˉp>0,根据比较引理,有liminft→∞ˆW(t)>0。定理1如果p(t)∈[0,1]满足假设1和假设2,则窗口大小估计误差ε渐近收敛到0。证明因为ε=W-ˆW‚所以˙ε=˙W-˙ˆW=(C/2)(ˆW2-W2)ˉq⋅p(t)=-(C/2)(W+ˆW)ˉq⋅p⋅ε(6)解微分方程(6)得ε(t)=ε(t0)e-C/2∫t0t(W(s)+W^(s))⋅q¯(s)⋅p(s)ds(7)式中:t0>0为一个足够大的常量。对任意t>t0,有t=t0+kΤ0+Τ˜‚其中T0的定义与假设1相同,k为自然数,Τ0≥Τ˜≥0,代入∫t0tp(s)ds得∫t0tp(s)ds=∫t0t0+kΤ0+Τ˜p(s)ds=∫t0t0+T0p(s)ds+∫t0+Τ0t0+2Τ0p(s)ds+…+∫t0+(k-1)Τ0t0+kΤ0p(s)ds+∫t0+kΤ0t0+kΤ0+Τ˜≥p(s)dskαT0+∫t0+kΤ0t0+kΤ0+Τ˜p(s)ds≥kαT0(8)式(8)中第1个不等式由不等式(5)推导,第2个不等式是由于p(t)是非负的。由于W(t)是实际的TCP窗口值,所以W(t)≥0,∀t≥0;同理q¯(t)≥0,∀t≥0,且拥塞控制的目标是使路由器中的队列长度维持在1个理想值附近,所以liminft→∞q¯(t)>0。根据引理1得(W(t)+W^(t))q¯(t)≥W^(t)⋅q¯(t)≥liminft→∞W^(t)⋅liminft→∞q¯(t)>0(9)根据不等式(8)和(9)有∫t0t(W(s)+W^(s))⋅q¯(s)⋅p(s)ds≥βkαΤ0≥βα(t-t0-Τ0)(10)式中:β=liminft→∞W^(t)⋅liminft→∞q¯(t)。将不等式(10)代入式(7)得ε(t)≤ε(t0)eCβΤ02⋅e-C2β(t-t0)(11)在图1中,取W(0)=10,W^(0)=0.1,标注概率p(t)=0.1sint+0.1满足假设1和假设2,如图1所示,窗口大小估计误差ε(t)渐近收敛到0。2控制体系的设计与分析2.1计算模型与控制函数由于窗口大小估计误差ε渐近收敛到0,考虑如下系统状态方程W^˙=Cq¯-(C/2)W^2q¯p(t)q¯˙=-ΝCW^q¯3+Cq¯2(12)通过变换得x1=-ΝCW^q¯3+Cq¯2x2=q¯(13)改变状态方程组(12),则x1、x2满足x¯1=-ΝC2q¯4+ΝC22W^2q¯4u(t)+3Ν2C2W^2q¯5-5ΝC2W^q¯4+2C2q¯3x¯2=x1(14)显然当u=2(q¯4-3ΝW^2q¯5+5W^q¯4-2Νq¯3+1ΝC2v)/(W^2q¯4)时,可以得到1组线性的系统状态方程组x˙1=vx˙2=x1(15)下文通过反步设计法设计控制率v,使得队列长度q收敛到一个期望的理想长度q*。队列长度q收敛于q*,相当于x2收敛于x2=1/(q*+TpC)。基于这个目标,取z2=x2-x*2,设函数V(z2)=z22/2,则V˙(z2)=z2x˙2=z2x1(16)首先考虑标量系统x˙2=x1,把x1看作是输入,设计反馈控制x1=φ(z2),以稳定原点z2=0。取x1=φ(z2)=-k1z2,k1>0,代入式(16)得V˙(z2)=z2x1=-k1z22≤0为运用反步法,应用变量代换z1=x1-φ(z2)=x1+k1z2,系统的形式转化为z˙1=v-k12z2z˙2=-k1z2(17)取Vc(z)=z12/2+z22/2作为复合Lyapunov函数,得V˙c=z1(v-k12z2)-k1z22(18)取v=k12z2-k2z1,k1>0,k2>0,代入式(18)得V˙c=-k2z12-k1z22≤0。所以u(t)=2(q¯4-3ΝW^2q¯5+5W^q¯4-2/Νq¯3+(k12z2-k2z1)/(ΝC2))/(W^2q¯4)(19)式中:k1、k2>0,z2=q¯-q¯*,z1=-ΝCW^q¯3+Cq¯2+k1z2。显然控制率u(t)即丢包率p(t)。根据定理1对丢包率p(t)的限制条件,有以下对控制参数k1,k2的限制条件{0≤q¯min4-3ΝW^2q¯min5+5W^q¯min4-2Νq¯min3+k2CW^q¯min3-k2ΝCq¯min2+k1(k1-k2)ΝC2(q¯min-q¯*)≤W^2q¯min420≤q¯max4-3ΝW^2q¯max5+5W^q¯max4-2Νq¯max3+k2CW^q¯max3-k2ΝCq¯max2+k1(k1-k2)ΝC2(q¯max-q¯*)≤W^2q¯max42(20)式中:q¯max=1/(ΤpC),q¯min=1/(qmax+ΤpC),qmax是路由器缓存的最大容量。2.2种参考文献的计算当丢包率p(t)如表达式(19)所示时,z1、z2收敛于原点。根据上文有z1=x1+k1z2=-ΝCWq¯3+Cq¯2+k1(q¯-q¯*),所以W收敛于1/(Νq¯*)=(q*+ΤpC)/Ν,又因为往返时间r=q/C+Tp,所以W收敛于r*C/N,r*=q*/C+Tp,即TCP端发送数据的速率与其往返时间r成正比。参考文献提出了一种拥塞算法公平性的判断依据。定义1设有n个数据源发送端,其数据发送量分别为(x1,x2,…,xn),定义公平系数为f(x1,x2,⋯,xn)=(∑i=1nxi)2/(n∑i=1nxi2)并把f(x1,x2,…,xn)称之为Jain公平系数。f(x1,x2,…,xn)的值在0到1之间,越大的Jain公平系数值代表了各数据流之间的公平性越好。下文根据Jain公平系数的定义研究本文算法的公平性,设有n个数据源发送端,其往返时延分别为ri,i=1,2,…,n。在时间T内发送的数据源分别为(x1,x2,…,xn),为了计算简便,设T=m1r1=m2r2=…=mnrn,显然有xi=(T/ri)Wi,又因为W收敛于r*iC/N,所以在一段较长的时间内近似的有xi=TC/N,有f(x1,x2,…,xn)=(∑i=1nΤC/Ν)2n∑i=1n(ΤC/Ν)2=1显然本文算法具有较好的公平性。3仿真实验与结果分析网络试验采用网络仿真软件ns-2,网络拓扑结构如图2所示。图2中,si(i=1～N)为TCP应用发送端,N=30,其分组长度为500byte,sd为UDP应用发送端,其速率为0.5Mbps。结点nn1和nn2之间为瓶颈链路,其带宽C=2500packet/s,即10Mbps。任意两结点之间的传播延时都为1.25ms,则Tp=0.01s。各个队列缓存均为800packet,即qmax=800packet,期望的队列长度q*=200packet。仿真实验的采样频率为160Hz。在瓶颈链路采用本文的NAQM-bt算法,其他链路的队列管理算法均采用尾丢弃(Droptail)算法。根据不等式组(20),取k1=1.15,k2=166.7。下面验证NAQM-bt控制算法的鲁棒稳定性。图3(a)为初始网络参数下瓶颈路由器中的队列长度曲线;在图3(b)中,在数据发送端加入1个UDP/CBR源作为噪声干扰,发送带宽为0.5Mb,在80s时开始发送数据,在240s时停止发送数据;在图3(c)中Tp由0.01s变为0.1s;在图3(d)中,在实验进行到80s时,有15个新的FTP源加入开始发送数据,在180s的时候这15个FTP源停止发送数据并离去。由图3可知,当网络参数发生一些变化时,输出反馈控制依然能得到较好的控制效果,这说明NAQM-bt算法具有较好的鲁棒性,能适应一定网络环境的变化。下面对本文的NAQM-bt算法以及KSFC算法、RBPC算法和NOFC算法的性能进行比较。图4给出了在相同网络环境下,这4种算法在瓶颈路由器中的队列曲线对比。图5、图6分别是这4种算法在不同传播延时下的链路利用率和丢包率。显然,本文的NAQM-bt和RBPC能够较好地抑制路由器中的队列扰动,但是RBPC算法牺牲了一定的链路利用率,而本文的NAQM-bt算法保证了较好的网络性能(链路利用率和丢包率)。下文验证NAQM-bt控制算法的鲁棒稳定性。表1为在不同参数条件下本文NAQM-bt算法的性能。显然,对于满足不等式组(20)的参数k1和k2,NAQM-bt算法都维持了较好的网络性能,具有较高的鲁棒