雙速漏桶監管

前言：本站為你精心整理了雙速漏桶監管范文，希望能為你的創作提供參考價值，我們的客服老師可以幫助你提供個性化的參考范文，歡迎咨詢。

論文關鍵詞:流體流法雙速漏桶突發業務

論文摘要:利用流體流法分析了雙速漏桶監管算法的性能,得到信元丟失率、平均排隊隊長和平均等待時間的理論計算公式,并用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.