论文关键词:流体流法双速漏桶突发业务

论文摘要:利用流体流法分析了双速漏桶监管算法的性能,得到信元丢失率、平均排队队长和平均等待时间的理论计算公式,并用Matlab语言进行了编程。通过性能分析可望选取合适的漏桶参数,以进行有效的流量控制。①

Keywords:fluidflowmethod;dualvelocityleakybucket;burstytraffic

Abstract:Weanalyzedtheperformanceofthedualvelocityleakybucketpolicingalgorithmbyuseoffluidflowmethodandobtainedthetheoreticalequationsofthecellloss,theaveragewaitinglengthandthewaitingtime.Bytheperformanceanalysis,suitableparametersforefficaciouscontrolmaybeobtained.

0引言

ATM网络能够支持不同种类和不同服务质量要求的业务。对突发业务进行统计复用,可以获得较高的频带利用率,但当大量业务同时进入网络时,有可能引起严重的网络拥塞。为了保证入网业务的服务质量,必须对入网的业务量进行控制。双速漏桶监管法是进行业务量控制的一种行之有效的方法。

1业务模型

本文采用突发业务模型作为系统的输入。这种突发业务实际上是N个独立同分布的Orr-Off信源的复合。Orr-Off信源假定信源有两种状态,即On态和Off态。On态时信源以固定速率V发出信元。Off态时无信元发出。On期和Off期的平均持续时间分别为1/β和1/α.信源处于On状态的稳态分布为式中,p=α/(α+β),为信源利用率。

2双速漏桶算法

双速漏桶由一个输入缓存器(可模型化为一个具有门限K1的K容量的FIFO排队),一个令牌生成器及一个丢弃开关组成。令牌池的容量为B.令牌生成有2个速率R1和R2,且R1<R2.若令牌池满,则新生成的令牌丢弃。当突发业务到达输入缓存器,要离开缓存器必须从令牌池中获得令牌,否则在缓存器中排队等候,直到获得令牌为止。若缓存器中排队长度小于K1,则令牌生成速率为R1,而当排队长度大于K1时,令牌生成速率为R2,若缓存器满,则信元发生丢失。

3突发业务的双速漏桶算法分析

下面用流体流法分析双速漏桶监管器的性能。漏桶可用虚排队模型表示。当实队列长度qr(t)≥0时,虚队列长度qf(t)≥B,有下式成立P{qr≤x}=P{qf≤B+x}

因此,可通过分析虚队列的队长分布求出实队列的队长分布。当虚队列的排队长度q(t)≤x≤K1+B时,令牌生成速率为R1,则q(t)的联合概率分布函数Fi(x)=Pr{q(t)≤x,I=i},0≤i≤N,经推导得Fi(x)的排队方程为i)α+iβ]F(x)+(i+1)βFi+1(x),0≤i≤N,其中,γi=i×V-R1,令向量F(x)=[F0(x),F1(x),…,FN(X)]T,则写成矩阵形式为

式中,D=diag(-R1,V-R1,2V-R1,…,NV-R1),R为强度转移矩阵。当q(t)≤x=y+K1+B时,令牌生成速率为R2,则Gi(y)=Pr{q(t)≤y,I=i},0≤i≤N.同理可得到D′×G·(y)=R×G(y),其中D′=diag(-R2,V-R2,2V-R2,…,NV-R2).下面分4种情况讨论。1)当iV≠R1且iV≠R2时,D和D′是非奇异矩阵,它们的逆矩阵存在,故解为

式中,zj,Φj和z′j,Φ′j为D-1R1和(D′)-1R2的特征值及相应的特征向量。令Ω+={i|iV>R1},Ω-={i|iV<R1},Ω+′={i|iV>R2},Ω-′={i|iV<R2},则待定系数kj和kj′可由下列边界条件求出。

Fi(0)=0,i∈Ω+;

Fi(K1+B)=Gi(0),i∈Ω-或i∈Ω+′;

Gi(K-K1)=∏i,i∈Ω-′;

用Matlab语言求出待定系数kj和k′j,可以方便地求出kj和k′j.

2)当iV=R1且iV≠R2时,D不存在逆阵,令n1=R1/V,注意到D(n1,n1)=0,有Fn1(x)=

(x),故可进行降阶处理,求出N个特征值及相应的特征向量。而对于G(y),D′存在逆阵,可求出N+1个特征值及相应的特征向量。求待定系数时,注意到Gn1(K-K1)=∏n1,kn1可由其他向量表示。与第一种情况不同的是,F(x)只有N个特征值,而G(y)有N+1个特征值。

3)当iV≠R1且iV=R2时,此时D′不存在逆阵,用与第二种情况类似的方法求出F(X)和G(y)

4)当iV=R1且iV=R2时,D和D′均不存在逆阵,用类似的方法求出系数。于是虚队列队长的分布如下P{qf(t)≤x}=

则实际漏桶缓冲区排队的队长分布为

则信元丢失率为

式中,E[λ(t)]是输入速率的平均值,

实队列的平均排队长可用斯蒂尔积分表示如下

根据Little公式可得平均排队时延-W=式中,λr=E[λ(t)]/[1-Ploss].

4数值计算结果

用Matlab语言编程得到的数值计算结果曲线如图1所示。

其中N=20,K=200,B=20.可以看出,信元丢失率、平均排队队长和平均等待时间均随着K1接近K而增大,这是和令牌生成速率何时取R2直接相关的。如果把门限设置得很高,必然导致大量信元的丢失以及平均排队队长和平均等待时间的增大。

参考文献

[1]李式巨,莫少军.ATM网络双速漏桶监管算法[J].通信学报,1997,18(10):31-37.

[2]蒋志刚,李乐民.ATM网络中突发业务的漏桶算法分析[J].电子学报,1995,23(1):8-14.