面向統(tǒng)計QoS保障的多時間尺度接納控制算法

陳艷平，王慧強，馮光升，高玉龍

(1. 哈爾濱工程大學 計算機科學與技術學院，黑龍江 哈爾濱 150001；2. 哈爾濱工業(yè)大學 通信技術研究所，黑龍江 哈爾濱 150080)

1 引言

接納控制是保障業(yè)務流QoS的有效方法之一，目前主要有2種方法，一種是基于測量的接納控制，一種是基于參數(shù)的接納控制。其中基于參數(shù)的接納控制采用相關模型來預測和計算流的行為特征和估算流量，由于設定了流模型，使用的算法簡單，但基于參數(shù)接納控制算法的控制能力取決于對訪問模式研究的深度以及數(shù)學模型的擬合程度。

各種新興網(wǎng)絡訪問方式的出現(xiàn)導致網(wǎng)絡數(shù)據(jù)流突發(fā)性的變化更加隨機，這種隨機性一方面使得構(gòu)建統(tǒng)一、準確的業(yè)務流模型更加困難，同時也給保障業(yè)務流服務質(zhì)量帶來挑戰(zhàn)。在業(yè)務流建模方面，隨著音頻、視頻數(shù)據(jù)的增加，網(wǎng)絡數(shù)據(jù)流不再滿足泊松過程，而是表現(xiàn)出自相似、多分形等特性，自相似的本質(zhì)是一種單分形結(jié)構(gòu)，大量研究表明業(yè)務流在大時間尺度上表現(xiàn)出單分形，而在小時間尺度上表現(xiàn)出多分形特性[1]，即業(yè)務流具有特征尺度。目前業(yè)務流建模主要針對某個特征進行建模，文獻[2]提出了采用分形布朗運動(FBM, fractional Brownian motion)模型描述自相似過程，但是對于非高斯(即重尾性)的自相似流突發(fā)性刻畫能力有限，文獻[3]提出了基于線性分形α穩(wěn)定自相似過程流模型，引入了傾斜參數(shù)用于表示重尾性。文獻[4]研究表明，vBNS在突發(fā)水平高的業(yè)務流用多分形流模型表示比較準確，而突發(fā)水平低的業(yè)務流并不適合用多分形流模型建模。文獻[5]也表明業(yè)務流的到達快慢影響它的特性。針對多分形流，文獻[6]提出了乘法多分形模型(multiplicative multifractal model)對業(yè)務流的多分形特性建模，文獻[7]提出了基于小波的多分形模型描述業(yè)務流的多分形。針對流的不同特征尺度，目前還沒有一個統(tǒng)一的業(yè)務流模型，采用單一的特征模型影響后續(xù)的業(yè)務流性能分析及QoS保障，特別是于業(yè)務流的突發(fā)性對網(wǎng)絡性能影響很大[8]。

對業(yè)務流模型的研究可以看出，目前還沒有統(tǒng)一模型針對流的所有特征進行建模，因此基于參數(shù)的接納控制大多采用針對單一特征的流模型，這大大影響接納決策的準確性。另外，在QoS保障方面，大多采用確定服務質(zhì)量參數(shù)[9]，然而越來越多的音頻、視頻等數(shù)據(jù)對延遲等性能具有一定的容忍能力，統(tǒng)計QoS保障成為接納控制新的研究方向。其中統(tǒng)計網(wǎng)絡演算是新興的QoS統(tǒng)計分析的理論，以該理論為基礎研究基于參數(shù)的接納控制方法方興未艾。文獻[10，11]提出了基于網(wǎng)絡演算的統(tǒng)計QoS保障接納控制方法，但兩者都基于一個前提，即業(yè)務流符合線性包絡，該方法不能用于自相似、多分形業(yè)務流的接納分析。

針對以上研究問題，本文提出通過在線測量，估計業(yè)務流的突發(fā)水平，進而采用不同的模型對網(wǎng)絡業(yè)務流進行建模；基于選定的流模型有效帶寬推導其有效包絡，采用統(tǒng)計網(wǎng)絡演算對業(yè)務流進行性能分析，根據(jù)獲得的性能參數(shù)進行接納控制決策，以此保障業(yè)務流的統(tǒng)計QoS。內(nèi)容組織如下：第2節(jié)給出用于統(tǒng)計QoS分析的網(wǎng)絡演算基本定義及定理；第3節(jié)介紹本文接納控制的系統(tǒng)模型；第4節(jié)給出自相似、多分形流模型估計方法、有效包絡獲得方法及突發(fā)期的估計，結(jié)合第2節(jié)的相關理論給出接納控制算法；第5節(jié)仿真實驗從統(tǒng)計QoS保障、帶寬利用率方面對算法的性能進行驗證；第6節(jié)是結(jié)束語。

2 統(tǒng)計QoS分析基礎

統(tǒng)計網(wǎng)絡演算為網(wǎng)絡性能分析提供了新的研究方法，為實現(xiàn)統(tǒng)計QoS保障提供了新理論，為接納控制等技術提供基礎。本節(jié)簡要介紹下文用到的統(tǒng)計網(wǎng)絡演算基本理論和表示符號。業(yè)務流的到達過程和離開過程表示為A=(A( t))t≥0和D=(D( t))t≥0，其中，A( t)、D( t)分別表示業(yè)務流在t時刻到達和離開網(wǎng)絡節(jié)點的累積業(yè)務量。很明顯，A, D都是非降左連續(xù)的，并且?t≥0,D( t)≤A( t)。

定義1 (非負廣義遞增函數(shù)集)[12]：F={f(·):?0≤x≤y, f( x)≥0,f( x)≤f( y)}

定義2 (非負廣義遞減函數(shù)集)[12]：={f(·):?0≤x≤y, f( x)≥0,f( y)≤f( x)}

定義3 (統(tǒng)計到達曲線)[12]：給定函數(shù)α∈F,εA∈，如果業(yè)務流的到達過程A滿足P{ A( s, t)-G( t-s)＞x}≤εA(x)，其中，A( s, t)=A( t)-A( s),0≤s≤t, x≥0，則稱業(yè)務流A具有誤差函數(shù)為εA的統(tǒng)計到達包絡G。

定義4 (統(tǒng)計服務曲線)[12]：給定函數(shù)β∈F,εS∈，到達網(wǎng)絡節(jié)點的業(yè)務流，其到達過程為A，如果該業(yè)務流的離開過程滿足P( D( t)＜A?[β-x]+(t +τ0))≤εS(x)，其中，f( u)du＜∞，則稱該網(wǎng)絡節(jié)點為業(yè)務流A提供了誤差為εS的統(tǒng)計服務曲線β。

統(tǒng)計網(wǎng)絡演算利用到達曲線和服務曲線推導出網(wǎng)絡輸出、延遲、積壓等性能指標，這其中用到2類重要的運算，即最小加卷積和最小加去卷積，卷積定義見定義5，有關去卷積及統(tǒng)計網(wǎng)絡演算其他理論詳見文獻[12]。

定義5 (最小加卷積)[12]：f, gF? ∈ ，函數(shù)f, g的最小加卷積運算為其中，t≥0。

定義6 (統(tǒng)計延遲)[12]：?t≥0，統(tǒng)計延遲W( t)定義為

其中延遲上界為

目前網(wǎng)絡演算理論本身還不完善，用于性能分析的流模型主要有3種[12]，文獻[13]將有效帶寬與網(wǎng)絡演算中的統(tǒng)計包絡進行融合，從而擴寬了網(wǎng)絡演算的應用范圍。下面介紹有效帶寬的定義及有效帶寬和有效包絡轉(zhuǎn)換定理。

定理1[13]到達過程A( t)的有效帶寬為α(s, t)，其有效包絡為

其中，εA為業(yè)務流到達曲線的誤差函數(shù)，s為空間參數(shù)，表示業(yè)務流的到達分布特征，t為時間參數(shù)，表示時間間隔長度。

3 系統(tǒng)模型

為了突出本文提出的思想及說明問題的便利性，僅考慮單個節(jié)點的接納控制，系統(tǒng)模型如圖1所示。在該模型中，業(yè)務流是一組具有相同包頭屬性的包列，當數(shù)據(jù)分組到達時，流模型估計模塊首先分析流的突發(fā)水平，通過在線測量決定其流模型，在線測量過程并不在業(yè)務流的接納控制中，因此減少接納控制本身對業(yè)務流性能的影響。流模型采用定義3表示，根據(jù)流模型推導流的有效包絡及突發(fā)期。參數(shù)估計模塊估計服務節(jié)點當前剩余的服務能力，采用定義4的服務曲線表示。接納控制算法模塊首先根據(jù)流的有效包絡和當前節(jié)點的剩余服務能力利用網(wǎng)絡演算理論推導流的統(tǒng)計延遲，基于統(tǒng)計延遲及突發(fā)期來進行接納決策。

圖1 系統(tǒng)模型

對于業(yè)務流的QoS要求，本文主要考量延遲參數(shù)，統(tǒng)計延遲采用定義6表示，其通過業(yè)務流模型和網(wǎng)絡節(jié)點的服務能力推導而來，而節(jié)點動態(tài)提供的服務能力也與當前網(wǎng)絡節(jié)點中的業(yè)務流有關，因此，業(yè)務流模型的選擇將在很大程度上影響接納控制的性能。本文根據(jù)不同業(yè)務流在不同時間尺度上表現(xiàn)出不同的特性，進而采用不同的業(yè)務流模型，以提高接納控制的性能，并采用網(wǎng)絡演算理論對流進行性能分析，實現(xiàn)統(tǒng)計QoS保障。

4 多時間尺度接納控制算法

根據(jù)文獻[1,14]，業(yè)務流在小的時間尺度上表現(xiàn)出多分形特性，而在大的時間尺度上表現(xiàn)出自相似性。然而目前的業(yè)務流建模大多數(shù)是對流的自相似性和多分形分別建模，沒有統(tǒng)一的模型描述多特征尺度的業(yè)務流。研究表明在突發(fā)水平較高時采用自相似模型刻畫流較準確，而在突發(fā)性較低時采用多分形流建模較準確，因此如果接納控制算法僅采用一種流模型，對接納控制的性能產(chǎn)生很大的影響，例如，假設網(wǎng)絡業(yè)務流目前的突發(fā)水平較低，如果采用自相似模型，使得對業(yè)務流的估計過高，如果業(yè)務流的突發(fā)水平較高而采用多分形流模型，則對的業(yè)務流實際業(yè)務量估計不夠。本文提出多尺度接納控制算法，通過預測網(wǎng)絡業(yè)務流采用哪種模型建模更加準確，進而決定選擇相應的流模型用于接納控制。另外，由于在流的突發(fā)期網(wǎng)絡性能波動較大，為了保障業(yè)務流的統(tǒng)計QoS，并不是所有的流在所有的時間都需要接納控制，本文提出在突發(fā)期推導業(yè)務流的性能，并據(jù)此對業(yè)務流進行接納控制。

4.1 流模型估計

考慮2類流模型：自相似流和多分形流模型。首先給出，多分形和自相似的定義。

定義7(多分形)：如果一個隨機過程X( t)滿足以下條件，則稱該過程為多分形：

t表示時間，q表示q階距。其中，c( q)和τ(q)分別表示多分形過程的尺度參數(shù)和距參數(shù)。如果τ(q)與q呈線性關系，則該過程為單分形，否則，呈多分形。

定義8(自相似)：如果連續(xù)過程Y( t)滿足以下條件，則稱該過程為自相似：

根據(jù)以上定義及文獻[15]的分析，對于網(wǎng)絡流非負時間序列X=X( t1),…,X( tN)，采用式(5)估計X的q階距μ(m)(q)：

4.2 有效帶寬和包絡估計

網(wǎng)絡演算是QoS分析的新興理論，理論本身還不完善，可用于QoS分析的流模型有限，特別是統(tǒng)計QoS分析。有效帶寬是另外一個重要的性能分析工具，更多類型的流都可以獲得其有效帶寬。文獻[13]提出了有效帶寬和有效包絡的轉(zhuǎn)換定理，根據(jù)此定理，更多類型的流可用于網(wǎng)絡演算的統(tǒng)計QoS分析，進而保障業(yè)務流的統(tǒng)計QoS。對于分形流模型和自相似流模型，本文分別采用 AWMM (adaptive wavelet-based multifractal model)和FBM (fractional Brownian motion)，并根據(jù)定理1給出2類模型對應的有效包絡，獲得這2類流模型的有效包絡就可以利用網(wǎng)絡演算推導流的延遲等性能參數(shù)，為接納控制提供決策基礎。

根據(jù)文獻[7]提出的分形流模型 AWMM，其到達過程X( k)的有效帶寬為

自相似過程采用FBM流模型，其有效帶寬為[16]

其中，ρ表示流的平均速率，β表示標準差，H表示hurst參數(shù)。

根據(jù)定理1，分形流的有效包絡為

自相似流的有效包絡為

推導過程極為簡單，這里不贅述。

4.3 突發(fā)時間估計

引理1[13]假設服務節(jié)點的服務速率為常數(shù)C,調(diào)度算法為 workconserving，如果聚集流的到達過程Ac滿足

對于給定的 ε ∈ ( 0,1)，T為突發(fā)時間的上界，選擇最大T使得：

根據(jù)引理 1，為了獲得突發(fā)期上界，首先要驗證流模型是否符合引理的假設條件。根據(jù)切比諾夫不等式(Chernoff bound)，有

對于多分析流模型，將有效帶寬式(7)代入式(13)，則式(13)的右側(cè)為設，根據(jù)阿貝爾定理有

同理,FBM流的突發(fā)期為

4.4 接納控制算法

算法思路：一個新流向網(wǎng)絡節(jié)點請求服務，延遲要求滿足式(1)，為實現(xiàn)流的統(tǒng)計QoS要求，算法采用統(tǒng)計網(wǎng)絡演算對流進行性能分析，基于分析結(jié)果進行接納控制。由于流在不同時間尺度上表現(xiàn)出不同特性，因而有不同的流模型，本文考慮自相似和多分形2類主要流模型，算法首先通過在線測量，選取適當?shù)臅r間尺度t，判斷流的突發(fā)水平，據(jù)此選定流模型。根據(jù)網(wǎng)絡數(shù)據(jù)量變化的統(tǒng)計結(jié)果，即數(shù)據(jù)量發(fā)生突發(fā)性變化是與特定時間段相關的，因此，在這樣的時間段內(nèi)能夠反映業(yè)務流特征的最短時間作為時間尺度t；另外，多分形流模型還不能直接用于統(tǒng)計網(wǎng)絡演算分析，算法通過有效帶寬和有效包絡轉(zhuǎn)換定理，獲得多分形流模型的有效包絡，使得多分形流模型能夠用于統(tǒng)計網(wǎng)絡演算分析；由于接納算法本身會對流的性能產(chǎn)生影響，因此接納決策時機的選擇對滿足流的性能也至關重要，算法通過推導估計流的突發(fā)期，在流的突發(fā)期內(nèi)對流進行接納控制。

算法具體描述如下：

1) 初始參數(shù)設置。設節(jié)點的服務速率為C，到達曲線、服務曲線和延遲的誤差參數(shù)分別設為εa,εs, εd；

2) 選取時間尺度t，根據(jù)式(5)和式(6)判斷當前流的突發(fā)水平，確定流模型。若采用自相似流模型，轉(zhuǎn)入3)，若采用多分形模型，轉(zhuǎn)入4)；

3) 計算流的均值和方差，根據(jù)式(8)得到流的有效帶寬，根據(jù)式(10)計算流的有效包絡，根據(jù)式(17)得到流的突發(fā)期上界；

5) 在突發(fā)期內(nèi)，一個新流到達，根據(jù)式(2)推導延遲界，如果滿足流的延遲要求則接納，否則丟棄。對于非突發(fā)期內(nèi)的流則全部接納。

該算法以業(yè)務流QoS參數(shù)作為接納決策的依據(jù)，只有滿足業(yè)務流QoS參數(shù)要求的流才被接納，通過這樣的方式來實現(xiàn)對業(yè)務流QoS保障。

5 仿真實驗

采用2個數(shù)據(jù)集對算法的性能進行驗證，分別是LBL-TCP-3和pAug。研究表明，LBL-TCP-3具有多分形屬性，而pAug具有自相似性[1]，AWMM流模型較適合前者數(shù)據(jù)的建模，而FBM模型較適合后者。首先，考察針對相同的數(shù)據(jù)采用AWMM和FBM流模型對接納性能的影響。

LBL-TCP-3和pAug數(shù)據(jù)流的統(tǒng)計參數(shù)如表1所示。采用單個服務節(jié)點，服務模式為workconserving，網(wǎng)絡節(jié)點帶寬為1Mbit/s。

表1 數(shù)據(jù)流的統(tǒng)計參數(shù)

首先，針對LBL-TCP-3數(shù)據(jù)，分別采用2種模型進行建模，獲得的有效包絡如圖2所示。從圖2中可以看出，采用FBM模型推得的有效包絡要高于多分形流模型的有效包絡，這一結(jié)果將直接增加向服務節(jié)點申請的帶寬，如果數(shù)據(jù)流的突發(fā)水平并沒有這么高，將導致資源的浪費，資源利用水平低。圖3給出了LBL-TCP-3數(shù)據(jù)流在滿足統(tǒng)計延遲要求的情況下接納流的數(shù)量，從圖中可以看出，對比AWMM模型，F(xiàn)BM流接納的流數(shù)較少。而對于pAug突發(fā)水平較高的數(shù)據(jù)流，采用FBM流模型和多分形流模型進行接納的對比如圖4所示，pAug適合采用FBM流進行建模，采用多分形流建模，由于計算所需的有效帶寬較小，過多的接納了數(shù)據(jù)流，致使產(chǎn)生擁塞，使得很多分組丟棄，導致帶寬利用率下降，且業(yè)務流的延遲加大。采用本文算法通過在線測量，能夠識別出流的類型因而解決流模型對接納性能的影響。

圖2 流的有效包絡

圖3 AWMM和FBM流模型接納數(shù)對比(LBL-TCP-3)

圖4 AWMM和FBM流模型接納數(shù)對比(pAug)

其次，針對LBL-TCP-3數(shù)據(jù)流，考察2種情況：

方法 1 判斷流的突發(fā)期，只有在流的突發(fā)期內(nèi)進行流的接納決策；

方法2 只要新的數(shù)據(jù)流到達就進行接納決策。

圖5給出了二者的對比。從圖中可以看出，在流的突發(fā)水平較低，在非接納控制情況下，大部分流的延遲要求能夠滿足，然而如果進行接納控制，盡管流的統(tǒng)計延遲要求仍能夠滿足，但流經(jīng)歷的延遲增加了。

圖5 流的延遲分布(LBL-TCP-3)

綜上所述，針對不同的特征尺度選擇不同的業(yè)務流模型使得對流模型的描述更加準確，為后續(xù)準確的接納控制提供了基礎；另外，接納控制的目的是保障或提高服務質(zhì)量，但不是控制越多越能提高性能，因此控制時間的選擇對業(yè)務流QoS保障也至關重要。

6 結(jié)束語

由于數(shù)據(jù)模型對實際業(yè)務流的擬合程度存在誤差，特別是當前對流的自相似、多分形等特性還沒有統(tǒng)一的數(shù)學模型，而業(yè)務流呈現(xiàn)多樣性，目前采用一種模型對流建模的誤差較大，本文通過在線測量業(yè)務流的突發(fā)水平，選取對應的業(yè)務流模型，實現(xiàn)了對業(yè)務流更加準確的建模，減小流建模中的誤差，為后續(xù)的接納控制提供更可靠基礎。另外，由于音頻、視頻等數(shù)據(jù)逐漸成為網(wǎng)絡中的主要數(shù)據(jù)形式，這類數(shù)據(jù)對服務質(zhì)量有一定的容忍能力，因此QoS保障由確定性轉(zhuǎn)向統(tǒng)計性，統(tǒng)計網(wǎng)絡演算作為統(tǒng)計QoS分析理論，本身需要完善，在具體應用中需要結(jié)合相關理論拓展理論的應用范圍，本文通過有效帶寬和有效包絡的轉(zhuǎn)換定理，實現(xiàn)了多分形模型用于網(wǎng)絡演算統(tǒng)計QoS分析；最后，通過接納時機的選擇盡量減小接納控制本身對業(yè)務流性能的影響。

[1] ABRY P, BARANIUK R, FLANDRIN P, et al. Multiscale nature of network traffic[J]. IEEE Signal Processing Magazine, 2002, 19(3):28-46.

[2] NORROS I. On the use of fractional brownian motion in the theory of connectionless networks[J]. IEEE Journal on Selected Areas in Communications, 1995, 13(6):953-962.

[3] KARASARIDIS A, HATZINAKOS D. Network heavy traffic modeling using α-stable self-similar processes[J]. IEEE Transactions on Communications, 2001, 49(7):1203-1214.

[4] GAO J, RITKE R. Long-range-dependence and multifractal modeling of vBNS traffic[A]. Proceedings of the 2001 Applied Telecommunications Symposium[C]. Seattle, Washington, 2001.167-173.

[5] MAULIK K, RESNICK S. The self-similar and multifractal nature of a network traffic model[J]. Stochastic Models, 2003, 19(4):549-577.

[6] GAO J, RUBIN I. Multiplicative multifractal modeling of longrange-dependent traffic in computer communications networks[J].Nonlinear Analysis, Theory, Methods and Applications, 2001, 47(9):5765-5774.

[7] VIEIRA F H T, LEE L L. Adaptive wavelet-based multifractal model applied to the effective bandwidth estimation of network traffic flows[J]. IET Communications, 2009, 3(6): 906-919.

[8] ERRAMILLI A, NARAYAN O, NEIDHARDT A, et al. Performance impacts of multi-scaling in wide area TCP/IP traffic[A]. IEEE INFOCOM[C]. Tel Aviv, Israel, 2000.352-359.

[9] MENTH M, LEHREIDER F, BRISCOE B, et al. A survey of PCN-based admission control and flow termination[J]. IEEE Communications Surveys & Tutorials, 2010, 12(3):357-375.

[10] PAOLO G, GABRIELLA S. Resource allocation and admission control for the provisioning of quality of service in networks of static priority schedulers[J]. Computer Networks,2009, 53(2):231-243.

[11] WANG S Q, XUAN D, BETTATI B, et al. Toward statistical QoS guarantees in a differentiated services network[J]. TeleCommunication,2010,43(3-4):253-263.

[12] JIANG Y. A basic stochastic network calculus[A] ACM SIGCOMM Conference on Network Architectures and Protocols[C]. Pisa, Italy,2006.123-134.

[13] CHENG Z L, BURCHARD A, LIEBEHERR J. A network calculus with effective bandwidth[J]. IEEE/ACM Transactions on Networking,2007, 15(6):1442-1453.

[14] GONG W B, LIU Y, MISRA V, et al. Self-similarity and long range dependence on the internet:a second look at the evidence, origins and implications[J]. Computer Networks, 2005, 48(3):377-399.

[15] TAQQU M S, TEVEROVSKY V, WILLINGER W. Is network traffic self-similar or multifractal[J]. Fractals, 1997, 5(1):63-73.

[16] KELLY F. Notes on Effective Bandwidths[M]. USA: Oxford University Press, 1996.