基于測量的QoS參數(shù)估計及其應(yīng)用(

1、基于測量的QoS參數(shù)估計及其應(yīng)用á 收稿日期:2000-10-16; 修改日期: 2001-03-26基金項目:國家863高科技發(fā)展計劃資助項目(863-317-9601-01)作者簡介:趙斌(1970),男,陜西大荔人,博士生,主要研究領(lǐng)域為綜合業(yè)務(wù)網(wǎng),ATM技術(shù);劉增基(1937),男,浙江麗水人,教授,博士生導(dǎo)師,主要研究領(lǐng)域為寬帶通信網(wǎng)絡(luò)技術(shù);李曉濛(1976),女,浙江寧波人,主要研究領(lǐng)域為綜合業(yè)務(wù)網(wǎng),ATM技術(shù). 趙 斌, 劉增基, 李曉濛(西安電子科技大學(xué) 綜合業(yè)務(wù)網(wǎng)國家重點實驗室,陜西 西安 710071)E-mail:zbnew摘要:提出了一種基于測量的QoS參數(shù)估

2、計方法,該方法使得用戶無須事先為業(yè)務(wù)源建立相應(yīng)的業(yè)務(wù)模型并向網(wǎng)絡(luò)提交其業(yè)務(wù)模型參數(shù),而是通過對業(yè)務(wù)流的統(tǒng)計特性進(jìn)行實時測量來動態(tài)估計相應(yīng)的QoS參數(shù),從而克服了基于模型QoS參數(shù)估計方法所固有的缺陷,便于網(wǎng)絡(luò)進(jìn)行連接允許控制和帶寬的動態(tài)分配.關(guān) 鍵 詞:QoS;測量;連接允許控制中圖法分類號:TP393 文獻(xiàn)標(biāo)識碼: A未來寬帶網(wǎng)絡(luò)的成功在很大程度上依賴于其對各種類型業(yè)務(wù)(如語音、視頻和數(shù)據(jù))的統(tǒng)計的復(fù)用性能.由于不同類型的業(yè)務(wù)具有不同的業(yè)務(wù)特性和服務(wù)質(zhì)量(QoS)要求,這就要求網(wǎng)絡(luò)能夠提供相應(yīng)的機(jī)制,以便在高效地提高資源利用率的同時確保不同類型業(yè)務(wù)的QoS,而如何精確地估計QoS參數(shù)則是其中

3、一個十分重要的問題.在傳統(tǒng)的QoS參數(shù)估計方法中,通常要求用戶提供描述其業(yè)務(wù)模型(如ON/OFF模型、馬爾可夫調(diào)制泊松過程和馬爾可夫調(diào)制流體過程等)的參數(shù),網(wǎng)絡(luò)則根據(jù)相應(yīng)鏈路上各業(yè)務(wù)流的模型參數(shù)以及鏈路容量和緩沖區(qū)大小來估計相關(guān)的QoS參數(shù),這種方法通常被稱為基于模型的QoS參數(shù)估計方法.然而,基于模型的QoS參數(shù)估計方法明顯存在著以下一些缺陷:(1) 業(yè)務(wù)源實際的統(tǒng)計特性很難被一種業(yè)務(wù)模型精確地進(jìn)行描述.(2) 受標(biāo)準(zhǔn)化的限制,用戶所能提交的業(yè)務(wù)量描述符不足以用來對其業(yè)務(wù)模型進(jìn)行描述.(3) 在網(wǎng)絡(luò)內(nèi)部,由于排隊的影響,可能會使業(yè)務(wù)流的統(tǒng)計特性發(fā)生變化,從而不再與用戶在連接建立階段所提交的業(yè)

4、務(wù)量描述符相一致.本文利用大數(shù)量業(yè)務(wù)源復(fù)用漸進(jìn)分析理論提出了一種基于測量的QoS參數(shù)估計方法,該方法無須用戶事先為業(yè)務(wù)源建立相應(yīng)的業(yè)務(wù)模型并向網(wǎng)絡(luò)提交其業(yè)務(wù)模型參數(shù),而是通過對業(yè)務(wù)流的統(tǒng)計特性進(jìn)行實時測量來動態(tài)估計相應(yīng)的QoS參數(shù),從而克服了基于模型QoS參數(shù)估計方法所固有的缺陷.本文將針對ATM網(wǎng)絡(luò)進(jìn)行討論,并分析如何將其應(yīng)用于連接允許控制(connection admission control,簡稱CAC)和帶寬的動態(tài)分配.由于信元的最大排隊時延通?？梢杂删彌_區(qū)的大小來限定,因此本文主要討論的是對信元丟失率(cell loss ratio,簡稱CLR)的估計.1 大數(shù)量業(yè)務(wù)源復(fù)用漸進(jìn)分析

5、理論在ATM網(wǎng)絡(luò)中,除非一些非常簡單的業(yè)務(wù)模型,利用傳統(tǒng)的排隊論進(jìn)行排隊性能分析通常是十分困難的,因此人們開始考慮采用漸進(jìn)分析的方法,其中大數(shù)量業(yè)務(wù)源復(fù)用漸進(jìn)分析理論則是近年來提出的一種十分有效的方法13.考慮一個ATM復(fù)用器,其服務(wù)速率為C,緩沖區(qū)容量為無限,被N個相互獨立的業(yè)務(wù)源復(fù)用.這N個業(yè)務(wù)源分成J類,同類業(yè)務(wù)源之間服從獨立同分布原則,且每類業(yè)務(wù)源的個數(shù)為Nj=N*rj,j=1,2,J.令Xj0,t為一個屬于第j類的業(yè)務(wù)源在時間間隔0,t中所產(chǎn)生的信元數(shù),則其log矩母函數(shù)為.(1)而各業(yè)務(wù)源相應(yīng)的累積log矩母函數(shù)可以表示為.(2)令L為系統(tǒng)穩(wěn)態(tài)隊長,且令QNc,Nb,N為系統(tǒng)的溢出

6、概率,即QNc,Nb,N=PrL>B,其中,Nc=C,Nb=B,則利用大數(shù)量業(yè)務(wù)源復(fù)用漸進(jìn)分析理論可得:.(3)因此當(dāng)N較大時,我們可以得到,(4)其中.(5)上式中,稱為函數(shù)f(x)的Legendre-Fenchel變換.式(3)成立的條件是,當(dāng)N趨于無窮大時,式(2)對于任何t均存在.由于業(yè)務(wù)源一般都滿足這一條件,因此大數(shù)量業(yè)務(wù)源復(fù)用漸進(jìn)分析理論具有較強(qiáng)的適用性.2 信元丟失率由于在有限容量緩沖區(qū)系統(tǒng)中CLR的求解通常十分困難,因此許多文獻(xiàn)在分析ATM網(wǎng)中的信元丟失率時,常常用無限容量緩沖區(qū)系統(tǒng)的隊長尾部分布(即溢出概率)來近似有限容量緩沖區(qū)(容量為B)系統(tǒng)中的CLR,本文中即CLR

7、QNc,Nb,N,然而這種近似方法有時卻會導(dǎo)致較大的誤差.這里我們采用了一種更精確的CLR估計方法.考慮一個具有有限容量緩沖區(qū)(容量為B)的排隊系統(tǒng)S和一個具有無限容量緩沖區(qū)的排隊系統(tǒng)S¥,L和L¥分別為S和S¥的系統(tǒng)隊長,則系統(tǒng)S¥的溢出概率為Pr(L¥>B),而系統(tǒng)S中的信元丟失率可以表示為,其中(x)+=max(x,0),l(t)為各業(yè)務(wù)源累積的到達(dá)速率,C為服務(wù)速率.BtSlotQueue lengthLL¥L¥L系統(tǒng)隊長,時隙.Fig.1 Buffer occupancy in S and S¥圖1

8、 S和S的緩沖區(qū)占用過程圖1比較了在同樣的信元到達(dá)情況下,S和S¥緩沖區(qū)的占用過程.如圖1所示,由于在有限容量緩沖區(qū)排隊系統(tǒng)S中存在著當(dāng)緩沖區(qū)滿時便丟棄信元的現(xiàn)象,因此有Pr(L=B)£Pr(L¥>B).我們可以利用下式來對CLR進(jìn)行估計,即 . (6)由式(4)我們可以得到 Pr. (7)在文獻(xiàn)4中,給出了的一種近似解,即,(8)其中,mi和分別為第i個業(yè)務(wù)源的平均到達(dá)速率和速率方差.考慮到在一個無限容量緩沖區(qū)的排隊系統(tǒng)中,為了滿足穩(wěn)態(tài)條件,要求各業(yè)務(wù)源的累積平均到達(dá)速率應(yīng)小于系統(tǒng)的服務(wù)速率,即m<C,此時,(m-C)+=0.因此,利用式(6)式(8

9、)可以得到.(9)若令,則CLR可以表示為.(10)對于VBR(variable bit rate)業(yè)務(wù)源來說,通常情況下K的取值遠(yuǎn)小于1,我們比較式(10)和式(7)可以發(fā)現(xiàn),信元丟失率CLR通常小于溢出概率,因此當(dāng)我們利用式(10)進(jìn)行CLR估計,并將其應(yīng)用到相應(yīng)的流量控制(如連接允許控制CAC)和帶寬分配時,往往能夠獲得更好的統(tǒng)計復(fù)用增益.3 基于測量的QoS參數(shù)估計本文通過對業(yè)務(wù)流的統(tǒng)計特性進(jìn)行測量,并將測得的統(tǒng)計值代入式(9)來估計相應(yīng)的QoS參數(shù).根據(jù)式(9),為了得到相應(yīng)的CLR,需要通過測量確定以下一些統(tǒng)計值,即各業(yè)務(wù)源累積的平均到達(dá)速率m和速率方差s2,以及各自的log矩母函

10、數(shù), j=1,2,J.我們把時間軸用固定的時間間隔t(幾十微秒到幾百毫秒)等分為連續(xù)的時間段,每個時間段為一個測量周期,我們在每個測量周期內(nèi)測量各業(yè)務(wù)源到達(dá)的信元個數(shù),若測量時間為T(通常由幾百個測量周期組成),則一個第j類業(yè)務(wù)源在第i個時間段內(nèi)被測量到的信元到達(dá)個數(shù)可記為Xj(i-1)t,it,i=1,2,T/t.利用這些測量值,我們可以分別求出相應(yīng)的m,s2及,并最終求得該測量時間內(nèi)的CLR.(1) m和s2.令j和分別為第j類業(yè)務(wù)源的平均到達(dá)速率和速率方差,則它們可以利用下式來進(jìn)行估計,.(11).(12)由于各業(yè)務(wù)源是相互獨立的,且同類業(yè)務(wù)源之間服從獨立同分布原則,因此可得, .(13

11、)(2) .由于,為了計算,我們采用時間平均來替代該式中的統(tǒng)計平均(數(shù)學(xué)期望),即, j=1,2,J. (14)(3) CLR.根據(jù)式(9),為了得到CLR,還需要求解I(b).而由式(5)可知,I(b)是一個求解極小值和極大值的表達(dá)式,即.(15)上式的求解包含了兩個優(yōu)化計算的過程,一個是對于固定的t改變q,求的極大值,將其記為f *(t);另一個是改變t,求f *(t)的極小值.4 基于測量的QoS參數(shù)估計在連接允許控制中的應(yīng)用利用上述基于測量的QoS參數(shù)估計方法,我們可以得到一種基于測量的CAC算法.類似地,我們把時間軸用固定的時間間隔T等分為連續(xù)的時間段,每個時間段為一個更新周期.同時

12、,在每個更新周期中又用更小的時間間隔t(幾十微秒到幾百毫秒)進(jìn)行等分,每個小時間段即為一個測量周期,一個更新周期通常由幾百個測量周期組成.在一個更新周期中,我們測量每個測量周期內(nèi)各業(yè)務(wù)源到達(dá)的信元個數(shù),如一個第j類業(yè)務(wù)源在第i個測量周期內(nèi)被測量到的信元到達(dá)個數(shù)可記為Xj(i-1)t,it,i=1,2,T/t.假設(shè)用戶所要求的QoS為CLR<e,根據(jù)式(9),我們可以估計在任一給定的服務(wù)速率C下的信元丟失率,因此在給定的信元丟失率要求下,為了確保QoS所應(yīng)分配的最小帶寬,可定義為Cmes=minC:CLR<e,(16)即.由于該式將利用上述的測量值來進(jìn)行求解,因此我們稱其為測量帶寬.

13、結(jié)合以上分析,我們得到如下一種基于測量的CAC算法,如圖2所示.CnewUpdate periodUpdate periodCService rate服務(wù)速率,分配帶寬,到達(dá)一個新連接(所需帶寬Cnew),判斷,接納,拒絕,更新周期.Fig.2 CAC algorithm based on measurement圖2 基于測量的CAC算法Bandwidth allocatedA new connection arrives (required bandwidth Cnew)CmesDetermine:Cnew<C-CmesAcceptC¢mesA new connection

14、arrives (required bandwidth C¢new)Determine:C¢new<C-C¢mesRejectt(1) 在每一個更新周期的測量周期內(nèi)測量各業(yè)務(wù)源到達(dá)的信元個數(shù),并在每一個更新周期的結(jié)束時刻利用所測量的結(jié)果計算該更新周期的測量帶寬.(2) 在一個更新周期中,當(dāng)?shù)?個新的連接建立請求到達(dá)時,利用其業(yè)務(wù)量描述符計算該連接所需帶寬,記為Cnew(例如可以使Cnew為該新連接的峰值速率).假設(shè)系統(tǒng)的服務(wù)速率為C,上一更新周期的測量帶寬為Cmes,則系統(tǒng)當(dāng)前剩余帶寬C剩余=C-Cmes.此時判斷,若Cnew <C剩余,則接納該連接請

15、求,并更新C剩余=C剩余-Cnew;否則,則拒絕該連接請求.(3) 在該更新周期中,當(dāng)又有新的連接建立請求到達(dá)時(其所需帶寬為),判斷若<C剩余,則接納該連接請求,并更新C剩余=C剩余-;否則,拒絕該連接請求.(4) 在該更新周期的結(jié)束時刻,利用該更新周期的相應(yīng)測量值計算其測量帶寬,在下一個更新周期中,令系統(tǒng)剩余帶寬C剩余=C-.如圖2所示,在上述基于測量的CAC算法中,帶寬的分配是一種動態(tài)的過程,這種動態(tài)過程表現(xiàn)為在每一個更新周期的結(jié)束時刻,測量帶寬被重新計算并用于下一個更新周期的接納控制,以便獲得更好的統(tǒng)計復(fù)用增益,提高網(wǎng)絡(luò)資源利用率.在上述基于測量的CAC算法中,一個關(guān)鍵的問題在于

16、如何利用測量值來計算更新周期的測量帶寬.利用第4節(jié)的方法,我們可以估計在任一給定C下的信元丟失率,因此根據(jù)式(16),我們可以調(diào)節(jié)式中的C,直到恰好滿足CLR<e,則此時的C即為Cmes.5 數(shù)值結(jié)果Buffer size B (ms)Log (probability)0-1-2-3-4-5-6510152025303540Overflow probability (measurement)CLR(measurement)CLR(simulation)圖3給出了在復(fù)用多個VBR業(yè)務(wù)源時,利用我們的方法(式(9)得到的緩沖區(qū)容量與信元丟失率CLR之間的對應(yīng)關(guān)系,并將其與溢出概率(式(7)及

17、CLR仿真結(jié)果進(jìn)行了比較,對式(9)中CLR和式(7)中溢出概率的求解均采用了我們上面所描述的測量方法來進(jìn)行,兩者的區(qū)別是相差了一個系數(shù)K.我們采用的業(yè)務(wù)源是一種在ATM網(wǎng)絡(luò)性能分析中被廣泛采用的真實的業(yè)務(wù)源,即星球大戰(zhàn)MPEG-1視頻壓縮流序列5.在圖3(a)中,鏈路容量C=34Mbps,業(yè)務(wù)強(qiáng)度r=0.85;圖3(b)中,鏈路容量C=155Mbps,業(yè)務(wù)強(qiáng)度r=0.95.Overflow probability (measurement)Buffer size B (ms)CLR(measurement)CLR(simulation)Log (probability)51015202530

18、3540-6-5-4-3-2-10 概率,溢出概率(測量),仿真,緩沖區(qū)容量.(a) C=34Mbps,r= 0.85 (b) C=155Mbps,r= 0.85Fig.3圖3從圖3可以看出,測量的溢出概率與實際的CLR相比高出了23個數(shù)量級,而測量的CLR則與實際的CLR十分接近,兩者相差不超過一個數(shù)量級,因此與溢出概率相比,采用式(9)進(jìn)行CLR估計可以得到更為精確的結(jié)果.此外,從圖中還可以看出,當(dāng)緩沖區(qū)容量較小時,測量的CLR值隨著緩沖區(qū)的增加而快速下降,但當(dāng)緩沖區(qū)容量增加到一定量之后,進(jìn)一步增加緩沖區(qū)容量只對CLR的改善產(chǎn)生較小的影響,這一現(xiàn)象表明,本文的方法能夠用來描述信元級和突發(fā)級

19、兩級的排隊行為,便于網(wǎng)絡(luò)進(jìn)行相應(yīng)的流量控制.我們針對鏈路利用率比較了兩種基于測量的CAC算法的性能,一種是本文的CAC算法;另一種是利用溢出概率(式(7)來近似CLR的CAC算法,我們稱其為溢出概率近似法.該算法與本文CAC算法的不同之處在于,將式(16)中的CLR替換為溢出概率,其余不變.在這里,我們使用的VBR業(yè)務(wù)源仍是星球大戰(zhàn)MPEG-1視頻壓縮流序列,我們定義鏈路利用率,其中C為服務(wù)速率,m為業(yè)務(wù)源平均速率,N為CAC所允許的最大連接數(shù).假設(shè)所要求的QoS為CLR<10-6,服務(wù)速率C分別為34Mbps(見表1)和155Mbps(見表2).表1和表2給出了在不同的緩沖區(qū)容量下,各

20、CAC算法的鏈路利用率.本文的CAC算法的性能與仿真結(jié)果十分接近,它明顯優(yōu)于溢出概率近似法,這是因為本文的CAC算法采用了更為精確的信元丟失率的估計方法(式(9),從而能夠獲得更好的統(tǒng)計復(fù)用增益,提高網(wǎng)絡(luò)資源的利用率.Table 1 Link utilization (CLR<10-6,C=34M)表1 鏈路利用率(CLR<10-6,C=34M)Buffer size B(ms) 48101520Overflow probability approximation0.5170.5880.6250.7080.760CAS in this paper0.6160.6890.7550.8

21、050.808Simulation0.6350.7040.7630.8100.813緩沖區(qū)容量,溢出概率近似法,本文CAC,仿真.Table 2 Link Utilization (CLR<10-6,C=155M)表2 鏈路利用率(CLR<10-6,C=155M)Buffer size B(ms) 48101520Overflow probability approximation0.8000.8800.8840.8890.892CAS in this paper0.8620.9010.9080.9140.914Simulation0.8830.9190.9200.9210.921

22、References:1 Botvich, D.D., Duffield, N.G. Large deviations, economies of scale, and the shape of the loss curve in large multiplexers. Queueing Systems, 1995,20(3):293320.2 Duffield, N.G. Economies of scale in queues with sources having power-law large deviation scalings. Journal of Applied Probabi

23、lity, 1996,33(3):840857.3 Courcoubetis, C., Weber, R. Buffer overflow asymptotics for a switch handling many traffic sources. Journal of Applied Probability, 1996,33(3):886903.4 Song, J., Boorstyn, R. Efficient loss estimation in high speed networks. In: Proceedings of the IEEE ATM Workshop98. 1998.

24、 360367.5 Rose, O. Traffic modeling of variable bit rate MPEG video and its impacts on ATM networks Ph.D. Thesis. Institute of Computer Science, Wuerzburg University, 1997.Estimation of QoS Parameters Based on Measurement and Its Application áReceived October 16, 2000; accepted March 26, 2001Supported by the National High Technology Development 863 Program o