一类批处理排队网络的稳定性

一类批处理排队网络的稳定性（精选2篇）

一类批处理排队网络的稳定性 篇1

一类批处理排队网络的稳定性

在标准排队网络稳定性研究的基础上,本文通过引进批长度随机向量,确立了一类批处理排队网络的流体模型和对应的标准排队网络的流体模型.证明了在批优先排队原则下,这两类排队网络的流体模型具有相同的.稳定性,为批处理排队网络的稳定性研究提供了一种有效的方法.

作 者：冯恩民 沈玉波 作者单位：大连理工大学应用数学系,辽宁,大连,116024刊 名：工程数学学报 ISTIC PKU英文刊名：JOURNAL OF ENGINEERING MATHEMATICS年，卷(期)：21(5)分类号：O226关键词：流体极限 率稳定 弱稳定 批处理排队网络 批优先排队原则

一类批处理排队网络的稳定性 篇2

关键词：AIMD,多瓶颈链路,稳定性

1. 引言

就目前而言,在单瓶颈链路条件下研究各种主动队列管理算法的理论性能是可行的,然而现实的网络却是更为复杂的,瓶颈链路之间的相互影响、源端及交叉流量端对瓶颈资源的争夺、交叉流量对网络的影响等等,这些因素是单瓶颈链路所无法模拟的,而这些却正是影响实际网络性能的重要因素。相对于单瓶颈链路拓扑而言,多瓶颈链路拓扑是一种更接近于实际的网络模型,本文通过建立一类具有AIMD参数对的多瓶颈链路AIMD/RED系统模型,然后基于Lyapunov稳定性理论,给出具有复杂多变时滞的多瓶颈网络系统模型渐近稳定的充分条件;并针对一类具有三瓶颈链路的网络系统稳定性进行了分析和研究

2. 系统的稳定性标准

稳定性是系统的一个基本结构特性。稳定性问题是系统控制理论研究的一个重要课题,对大多数情形,稳定是控制系统能够正常运行的前提。系统运动稳定性可分类为基于输入输出描述的外部稳定性和基于状态空间描述的内部稳定性。本文中主要讨论的是系统的内部稳定性,以下简称为稳定性。

1892年,俄国学者Lyapunov在“运动稳定性一般问题”一文中,提出了著名的Lyapunov稳定性理论。Lyapunov引入了一个虚构的能量函数,称为Lyapunov函数,记为V(x,t)或V(x)。由于V(x)是表示能量的函数,所以V(x)>0。这样就可以根据V(x)的定号性来判断系统的稳定性。显然,若V(x)>0,并且V(x)<0,则系统就是渐进稳定的。

3. 多瓶颈网络流体模型

为了更好的模拟网络中的实际情况,我们首先对单瓶颈网络流体力学模型[1]进行了一些改进,选用了AIMD参数对(α,β),即加增过程中每次增加α窗口;在倍减过程中窗口大小不是减半,而是变为当前窗口大小的β倍;其中α>0,β∈[0,1]。则此时的单瓶颈链路的AIMD/RED流模型可以用如下的一组非线性微分方程表示:

其中{a}+=max{a,0},α>0,β∈[0,1]。

如图1所示为一类多瓶颈AIMD/RED系统。在系统中,所有的AIMD流在通过链路时都会产生不止一个的瓶颈路由器。图中带有箭头的粗线表示了每个链路上的网络传输情况,并且每通过一个拥塞路由器后网络传输能力便会下降。假设每个数据包只能被丢弃(标记)一次,按照文献[4]中的建模思想,一个具有组AIMD流和个拥塞链路的多瓶颈AIMD/RED系统的数学模型如下:

在多瓶颈系统模型(2)中,r(i),i=1,…,N代表数据流i所经过的拥塞路由器,f(m),m=1,…,M代表通过拥塞路由器的数据流组。

4. 一般多瓶颈网络系统的稳定性标准

在系统(2)中,其平衡点为

其中Ri=Ri*;i=1,…,N;。

按照对单瓶颈网络的处理办法,对系统(2)也在平衡点附近对其进行线性化处理,我们忽略了时延参数q(t-Ri),i=1,…,N的独立性,并且把时变延迟固定为一个平衡值Ri*,i=1,…,N。

我们所采用的系统形式表示如下:

其中,,Aij,Bi11,Bi12,为已知的具有适当维数和形式的实常数矩阵。通过劳斯判定标准可以检验出A軓是一个赫维茨矩阵,这就意味着对任意给定的正定矩阵Q,存在有正定矩阵P,使得。

令,其中λ(P)代表正定矩阵P的特征值,下面我们运用Lyapunov第二方法给出带有反馈时延的多瓶颈系统(2)局部渐近稳定的一些充分条件。

定理1如果存在正定矩阵P,Q且满足是正定的,从而系统(2)的平衡点是局部渐近稳定的。

证明:选用Lyapunov函数形式为

则

使R*=max{R1*,…,RN*},运用Lyapunov-Razumikhin条件,对于t-R*≤ξ≤t,当μ>1时,则有V(ξ)≤μ2V(t),从而‖x(ξ)‖≤M·μ·‖x(t)‖。

因此可得到:

从而系统(2)在其平衡点的渐近稳定成立。

5. 一类具有三条瓶颈链路拓朴结构网络系统的稳定性分析

我们考虑了一个简单的多瓶颈链路情况,图2所示为具有三条瓶颈的链路网络。在网络中有四组数据流共享四个路由器,其中有三条瓶颈链路L1、L2和L3;组Ⅰ和组Ⅱ中的数据流在链路L1上的共享带宽,并且组Ⅰ中的数据流还分别和组Ⅲ与组Ⅳ中的数据流在链路L2与L3上共享带宽。假设所有的路由器都使用RED协议,并且在非瓶颈链路上没有丢包和时延抖动。瓶颈链路L1、L2和L3的链路带宽分别为C1,C2,和C3,四组数据流的往返时延分别记为R1,R2,R3和R4。

在上面的三瓶颈链路拓扑结构中,令链路L1、L2和L3上的包丢失概率分别记为Kp1、Kp2和Kp3,四组AIMD流的参数对分别记为(α1,β1),(α2,β2)、(α3,β3)和(α4,β4)。这就表明,对于组Ⅰ来说,其数据流在链路L1、L2和L3上的包丢失概率分别为p1(t-R1)=Kp1q1(t-R1)、p2(t-R1)=Kp2q2(t-R1)和p3(t-R1)=Kp3q3(t-R1)。假设一个数据包最多被丢弃(标记)一次,则数据流I可能被丢失的概率为p1(t-R1)+p2(t-R1)+p3(t-R1)-p1(t-R1)p2(t-R1)p3(t-R1),如果p1、p2和p3非常小时,包丢弃概率可以近似等于p1(t-R1)+p2(t-R1)+p3(t-R1)。

下面我们给出一个具体的数值例子来说明基于定理1的具有反馈时延的AIMD/RED系统的局部渐近稳定的充分条件。令N1=N2=N3=N4=8,C1=3×103packet/sec,C2=5×103packet/sec,C3=4×103packet/sec,Kp1=Kp1=Kp3=0.0005。选择(α1,β1)=(1,0.5),Tp1=0.020s;(α2,β2)=0.2,0.875),Tp2=0.013s;(α3,β3)=(1,0.5),Tp1=0.007s;(α4,β4)=(0.3,0.75),Tp2=0.018s。

利用Matlab中的LMI控制工具箱来对定理1求解,我们采用的一个解决方法如下:

选取正定矩阵

我们可以检验矩阵Q-2M(‖PB1‖+‖PB2‖+‖PB3‖+‖PB4‖)I的特征值为

1.0e+003[9.3704 7.8061 4.5396 2.0973 0.8614 0.00510.0003],

这说明Q-2M(‖PB1‖+‖PB2‖+‖PB3‖+‖PB4‖)I是正定的。因此,定理1的条件得到证明并且系统是局部渐近稳定的。

6. 总结

具有多瓶颈链路的TCP/RED系统是不稳定的,尽管其参数设置和稳定的单瓶颈链路系统参数设置一样。通过在多瓶颈链路条件下对各种主动队列管理算法进行研究,更能揭露算法在实际网络中可能遇到的问题,因而对多瓶颈链路网络进行深入研究对于推动主动队列管理算法与实际网络的融合具有重要意义。

参考文献

[1]V.Misra,W.B.Gong,D.Towsley.Fluid-based analysis of a networkof AQM routers supporting TCP flows,in:Proc.of ACM/SIGCOMM,2000,pp.151～160.

[2]D.Bauso,L.Giarre and G.Neglia.Active Queue ManagementStability in Multiple Bottleneck Networks,in:Proc.of IEEE ICC’04,vol4,2004,pp.2267～2271.

[3]Y.Xiao,M.Lee.Nonlinear control of active queue management formultiple bottleneck network,IEICE Trans.on Communications.2006(11):3108～3113.

[4]L.Wang,L.Cai,X.Liu,X.Shen.Stability and TCP-friendliness ofAIMD/RED systems with feed-back delays,Computer Networks,2007,51(15):4475～4491.