论文关键词:流体流法 双速漏桶 突发业务
论文摘要:利用流体流法分析了双速漏桶监管算法的性能,得到信元丢失率、平均排队队长和平均等待时间的理论计算公式,并用matlab语言进行了编程。通过性能分析可望选取合适的漏桶参数,以进行有效的流量控制。①
key words:fluid flow method;dual velocity leaky bucket;bursty traffic
abstract:we analyzed the performance of the dual velocity leaky bucket policing algorithm by use of fluidflow method and obtained the theoretical equations of the cell loss,the average waiting length and the waiting time.by the performance analysis,suitable parameters for efficacious control may be obtained.
0引 言
atm网络能够支持不同种类和不同服务质量要求的业务。对突发业务进行统计复用,可以获得较高的频带利用率,但当大量业务同时进入网络时,有可能引起严重的网络拥塞。为了保证入网业务的服务质量,必须对入网的业务量进行控制。wWW.133229.cOM双速漏桶监管法是进行业务量控制的一种行之有效的方法。
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.
