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

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

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

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

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

5、理論在ATM網(wǎng)絡(luò)中,除非一些非常簡(jiǎn)單的業(yè)務(wù)模型,利用傳統(tǒng)的排隊(duì)論進(jìn)行排隊(duì)性能分析通常是十分困難的,因此人們開(kāi)始考慮采用漸進(jìn)分析的方法,其中大數(shù)量業(yè)務(wù)源復(fù)用漸進(jìn)分析理論則是近年來(lái)提出的一種十分有效的方法13.考慮一個(gè)ATM復(fù)用器,其服務(wù)速率為C,緩沖區(qū)容量為無(wú)限,被N個(gè)相互獨(dú)立的業(yè)務(wù)源復(fù)用.這N個(gè)業(yè)務(wù)源分成J類,同類業(yè)務(wù)源之間服從獨(dú)立同分布原則,且每類業(yè)務(wù)源的個(gè)數(shù)為Nj=N*rj,j=1,2,J.令Xj0,t為一個(gè)屬于第j類的業(yè)務(wù)源在時(shí)間間隔0,t中所產(chǎn)生的信元數(shù),則其log矩母函數(shù)為.(1)而各業(yè)務(wù)源相應(yīng)的累積log矩母函數(shù)可以表示為.(2)令L為系統(tǒng)穩(wěn)態(tài)隊(duì)長(zhǎng),且令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較大時(shí),我們可以得到,(4)其中.(5)上式中,稱為函數(shù)f(x)的Legendre-Fenchel變換.式(3)成立的條件是,當(dāng)N趨于無(wú)窮大時(shí),式(2)對(duì)于任何t均存在.由于業(yè)務(wù)源一般都滿足這一條件,因此大數(shù)量業(yè)務(wù)源復(fù)用漸進(jìn)分析理論具有較強(qiáng)的適用性.2 信元丟失率由于在有限容量緩沖區(qū)系統(tǒng)中CLR的求解通常十分困難,因此許多文獻(xiàn)在分析ATM網(wǎng)中的信元丟失率時(shí),常常用無(wú)限容量緩沖區(qū)系統(tǒng)的隊(duì)長(zhǎng)尾部分布(即溢出概率)來(lái)近似有限容量緩沖區(qū)(容量為B)系統(tǒng)中的CLR,本文中即CLR

7、QNc,Nb,N,然而這種近似方法有時(shí)卻會(huì)導(dǎo)致較大的誤差.這里我們采用了一種更精確的CLR估計(jì)方法.考慮一個(gè)具有有限容量緩沖區(qū)(容量為B)的排隊(duì)系統(tǒng)S和一個(gè)具有無(wú)限容量緩沖區(qū)的排隊(duì)系統(tǒng)S¥,L和L¥分別為S和S¥的系統(tǒng)隊(duì)長(zhǎ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)隊(duì)長(zhǎng),時(shí)隙.Fig.1 Buffer occupancy in S and S¥圖1

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

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

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

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

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

13、結(jié)合以上分析,我們得到如下一種基于測(cè)量的CAC算法,如圖2所示.CnewUpdate periodUpdate periodCService rate服務(wù)速率,分配帶寬,到達(dá)一個(gè)新連接(所需帶寬Cnew),判斷,接納,拒絕,更新周期.Fig.2 CAC algorithm based on measurement圖2 基于測(cè)量的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) 在每一個(gè)更新周期的測(cè)量周期內(nèi)測(cè)量各業(yè)務(wù)源到達(dá)的信元個(gè)數(shù),并在每一個(gè)更新周期的結(jié)束時(shí)刻利用所測(cè)量的結(jié)果計(jì)算該更新周期的測(cè)量帶寬.(2) 在一個(gè)更新周期中,當(dāng)?shù)?個(gè)新的連接建立請(qǐng)求到達(dá)時(shí),利用其業(yè)務(wù)量描述符計(jì)算該連接所需帶寬,記為Cnew(例如可以使Cnew為該新連接的峰值速率).假設(shè)系統(tǒng)的服務(wù)速率為C,上一更新周期的測(cè)量帶寬為Cmes,則系統(tǒng)當(dāng)前剩余帶寬C剩余=C-Cmes.此時(shí)判斷,若Cnew <C剩余,則接納該連接請(qǐng)

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

16、如何利用測(cè)量值來(lái)計(jì)算更新周期的測(cè)量帶寬.利用第4節(jié)的方法,我們可以估計(jì)在任一給定C下的信元丟失率,因此根據(jù)式(16),我們可以調(diào)節(jié)式中的C,直到恰好滿足CLR<e,則此時(shí)的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ù)用多個(gè)VBR業(yè)務(wù)源時(shí),利用我們的方法(式(9)得到的緩沖區(qū)容量與信元丟失率CLR之間的對(duì)應(yīng)關(guān)系,并將其與溢出概率(式(7)及

17、CLR仿真結(jié)果進(jìn)行了比較,對(duì)式(9)中CLR和式(7)中溢出概率的求解均采用了我們上面所描述的測(cè)量方法來(lái)進(jìn)行,兩者的區(qū)別是相差了一個(gè)系數(shù)K.我們采用的業(yè)務(wù)源是一種在ATM網(wǎng)絡(luò)性能分析中被廣泛采用的真實(shí)的業(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 概率,溢出概率(測(cè)量),仿真,緩沖區(qū)容量.(a) C=34Mbps,r= 0.85 (b) C=155Mbps,r= 0.85Fig.3圖3從圖3可以看出,測(cè)量的溢出概率與實(shí)際的CLR相比高出了23個(gè)數(shù)量級(jí),而測(cè)量的CLR則與實(shí)際的CLR十分接近,兩者相差不超過(guò)一個(gè)數(shù)量級(jí),因此與溢出概率相比,采用式(9)進(jìn)行CLR估計(jì)可以得到更為精確的結(jié)果.此外,從圖中還可以看出,當(dāng)緩沖區(qū)容量較小時(shí),測(cè)量的CLR值隨著緩沖區(qū)的增加而快速下降,但當(dāng)緩沖區(qū)容量增加到一定量之后,進(jìn)一步增加緩沖區(qū)容量只對(duì)CLR的改善產(chǎn)生較小的影響,這一現(xiàn)象表明,本文的方法能夠用來(lái)描述信元級(jí)和突發(fā)級(jí)

19、兩級(jí)的排隊(duì)行為,便于網(wǎng)絡(luò)進(jìn)行相應(yīng)的流量控制.我們針對(duì)鏈路利用率比較了兩種基于測(cè)量的CAC算法的性能,一種是本文的CAC算法;另一種是利用溢出概率(式(7)來(lái)近似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(見(jiàn)表1)和155Mbps(見(jiàn)表2).表1和表2給出了在不同的緩沖區(qū)容量下,各

20、CAC算法的鏈路利用率.本文的CAC算法的性能與仿真結(jié)果十分接近,它明顯優(yōu)于溢出概率近似法,這是因?yàn)楸疚牡腃AC算法采用了更為精確的信元丟失率的估計(jì)方法(式(9),從而能夠獲得更好的統(tǒng)計(jì)復(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