自相似網(wǎng)絡業(yè)務的一個FARIMA模型

1、 自相似網(wǎng)絡業(yè)務的一個FARIMA模型* 本文為國家自然科學基金資助項目（批準號69672031） 劉嘉焜 薛飛 王鐳 張連芳 舒炎泰 （天津大學） 摘 要近來發(fā)現(xiàn)，高速網(wǎng)絡業(yè)務具有自相似及長相關特性。分數(shù)噪聲可描述該類業(yè)務，但它僅表現(xiàn)長相關特性。本文給出利用FARIMA（自回歸分數(shù)整合滑動平均）模型擬合自相似網(wǎng)絡業(yè)務的一整套方法。該模型同時刻畫了實際業(yè)務的長相關與短相關特性。通過對實測數(shù)據(jù)的實驗，證明了模型的優(yōu)效性。關鍵詞：自相似性 長相關 網(wǎng)絡業(yè)務模型 自回歸分數(shù)整合滑動平均1. 概述 隨著寬帶網(wǎng)絡服務需求（如多媒體、視頻業(yè)務等）的激增，高速網(wǎng)絡傳輸技術（如ATM等）成為目前網(wǎng)絡研究的熱點

2、。研究人員圍繞高速網(wǎng)絡的業(yè)務擁塞控制、信息監(jiān)測、帶寬分配及網(wǎng)絡性能評價等課題開展了大量工作，其中建立一個能準確描述網(wǎng)絡業(yè)務（traffic）的模型是所有這些研究工作的基礎。最初研究ATM網(wǎng)絡時，常假設業(yè)務到達為Poisson過程。隨著研究的深入逐漸引入了各種推廣的Poisson過程和其它的隨機模型，如Markov調制Poisson過程1，fluid-flow模型2、TES（Transform-Expand-Sample）模型3、packet-train模型4、批到達Markov過程5等等。這些模型的共同特點是所描述的業(yè)務序列具有短相關性（short range dependence），即業(yè)務序

3、列的自相關函數(shù)隨序列間隔增大呈指數(shù)衰減趨勢。當時間標度增加時，統(tǒng)計上單位時間內得到的數(shù)據(jù)包數(shù)將趨于白噪聲，所以這些模型所表示的業(yè)務流在不同的時間標度下具有不同的特性。但是近年來研究結果表明：實際網(wǎng)絡業(yè)務普遍存在統(tǒng)計上的自相似性，該特性與業(yè)務發(fā)生的時間地點或信元編碼方式無關。其中，從1989年到1992年間，Leland和Wilson6等人使用具有很高時間分辨率的以太網(wǎng)監(jiān)視設備在 BellCore Morristown 研究工程中心的幾個以太網(wǎng)段的不同位置上收集了數(shù)百萬個實際傳輸?shù)臄?shù)據(jù)包。通過對大量實際業(yè)務數(shù)據(jù)的分析，他們發(fā)現(xiàn)：這種聚集的網(wǎng)絡業(yè)務所表現(xiàn)的統(tǒng)計自相似性完全不同于傳統(tǒng)的業(yè)務模型。實際

4、網(wǎng)絡業(yè)務序列的自相關函數(shù)隨間隔增大呈雙曲函數(shù)衰減，從而是長相關的（long range dependence）。Basu和Mukherjee等曾利用ARIMA模型，對貝爾實驗室的自相似業(yè)務數(shù)據(jù)進行了分析7。他們假設業(yè)務過程是非平穩(wěn)的，由于ARIMA模型不能描述網(wǎng)絡業(yè)務內在的長相關性，因此該模型對自相似業(yè)務的描述能力是有限的。該研究證明了利用時間序列分析方法研究網(wǎng)絡業(yè)務是可行的。為研究長相關的物理過程，Mandelbrot等將布朗運動推廣到分數(shù)布朗運動FBM。分數(shù)差分噪聲FARIMA(0,d,0)是FBM的離散情形8。FBM或FARIMA(0,d,0)適合于描述長相關過程，但由于FBM或FARI

5、MA(0,d,0)過程僅有三個參數(shù)，它們不能很好地表示實際中不可忽略的短相關結構9,10。本文將長相關特性的時間序列分析方法引入到自相似業(yè)務建模分析中，給出了利用FARIMA模型對自相似業(yè)務進行研究的方法，對模型辨識、參數(shù)估計及生成方法進行了系統(tǒng)的研究，利用“后向預報”技術對序列進行分形反濾波，在模型辯識、參數(shù)估計中利用粗、精估計結合的方法建立模型，并開發(fā)實現(xiàn)了更為有效的算法。最后，通過對實測數(shù)據(jù)的實驗，定義了MSE統(tǒng)計量，證明了模型的優(yōu)效性。2. FARIMA 模型FARIMA(p,d,q)過程擴展了FBM或FARIMA(0,d,0)的描述能力，彌補了它們在描述能力上的不足11。從定義不難看

6、出，F(xiàn)ARIMA(p,d,q)模型是由分數(shù)差分噪聲FARIMA(0,d,0)為激勵的ARMA模型。該模型在利用參數(shù)d描述觀測樣本中的長相關結構時，利用p+q+ 1個參數(shù)來刻畫樣本中的短相關結構。定義2.1 隨機過程稱為服從(-0.5,0.5)的FARIMA()模型，如果是平穩(wěn)（零均值）的，且滿足差分方程 ， (2.1)其中為白噪聲序列,和分別是p階和階多項式，,這里B是延遲算子，即 。顯然，是(-0.5,0.5)的FARIMA()過程當且僅當是一個ARMA()過程。如果對，有，那么滿足和 ，因此，可看成由FARIMA(0,d,0)驅動的ARMA(p,q)過程。定理2.2 設是(-0.5,0.5

7、)的FARIMA()過程，且(2.1)式中多項式與無公共根，則 (1) 如果，則(2.1)式有唯一的平穩(wěn)解，形如 ， (2.2) 其中 ； (2) 具有物理可實現(xiàn)的單邊滑動平均表示的充分必要條件是； (3) 可逆的充分必要條件是；(4) 如果具有物理可實現(xiàn)的單邊滑動平均表示且可逆，則對，其自相關函數(shù)和譜密度有 ， (2.3)其中為常數(shù)； , ()。 (2.4) 因此，在極限狀態(tài)下，F(xiàn)ARIMA()過程的自相關函數(shù)和譜密度函數(shù)有同F(xiàn)ARIMA (0,d,0)類似的結構。即當時，F(xiàn)ARIMA(p,d,q)是長相關的。定理2.3 12 當時，F(xiàn)ARIMA(p,d,q)過程是漸進二階自相似過程，且其H

8、urst參數(shù)H=d+1/2。 不難看出，的FARIMA(0,d,0)和FARIMA()過程可以描述自相似業(yè)務所具有的長相關特性。3. 網(wǎng)流的FARIMA建模與傳統(tǒng)ARMA過程相比，F(xiàn)ARIMA模型的結構辨識和參數(shù)估計要困難和復雜得多。當數(shù)據(jù)同時呈現(xiàn)長短相關時，它們的行為將很難區(qū)分，使得模型選擇變得困難。在利用似然函數(shù)估計自協(xié)方差時，精確似然估計方法遇到了計算上的問題。而其它“半?yún)?shù)（semi-parametric）”技術導致明顯的有限樣本偏置和較大的樣本方差13。相對于FARIMA建模中的困難，傳統(tǒng)的ARMA模型已經(jīng)建立了一套成熟的理論和方法14。如前所述，分數(shù)差分噪聲FARIMA(0,d,0

9、)被定義為高斯白噪聲的-d階分數(shù)差分，這一運算又被稱為分形濾波。利用FARIMA(p,d,q)模型時，在獲取參數(shù)d（等價地，Hurst參數(shù)H）的有效估計后，可以通過分形反濾波來消弱數(shù)據(jù)中的長期間相關結構，以達到增強短相關結構的目的。這是因為當我們將傳遞函數(shù)為的分形反濾波器作用于動態(tài)數(shù)據(jù)時，所得到的過程將是一個ARMA過程?；谏鲜鲇懻?，我們可把FARIMA(p,d,q)分離成“分數(shù)差分”和“ARMA”兩部分，而實現(xiàn)這種分離的關鍵是分數(shù)差分算子（即分形反濾波）的實現(xiàn)。 通過以上討論，我們提出以下FARIMA的模型建立步驟：(1) 動態(tài)數(shù)據(jù)的預處理；(2) 動態(tài)數(shù)據(jù)的長相關結構分析；(3) 動態(tài)數(shù)

10、據(jù)的分形反濾波；(4) ARMA的結構辨識與模型檢測；(5) FARIMA的參數(shù)估計與評估。3.1 分數(shù)差分算子的實現(xiàn)在對動態(tài)數(shù)據(jù)進行零均值化之后，得到。我們可以在FARIMA(p,d,q)模型p、q均未知的情況下，利用Hurst參數(shù)的有關分析方法，如聚集過程的方差分析法(variance-time)、基于周期圖(Periodogram)的頻域分析法、R/S分析法等得到動態(tài)數(shù)據(jù)Hurst參數(shù)的近似估計H，由關系d=H-0.5得到d的近似估計6。這就完成了步驟（1），（2）。作用于序列的分數(shù)差分算子Ñd的精確形式為： （3.1）其中。對于d<1/2，(3.1)式均方收斂，因此算子

11、Ñd是一個完備的定義。從(3.1)式可看出，分數(shù)差分的計算過程需要用到首個觀測點之前的數(shù)據(jù)W0，W-1，W-2，而且其表達形式為無窮求和，因此在實際應用中必須采取近似形式方能計算。我們的具體策略為只當時，用均值0來替代Wt ，這里M的選擇應足夠大以使得這種替代合理。從而得到算子： 。 (3.2)為了實現(xiàn)(3.2)中定義的差分算子，我們采用“后向預報”技術估計非觀測樣本W(wǎng)t ，的值。假設我們已知過程 (3.3) 的一個樣本，現(xiàn)在我們需要估計觀測點之前的數(shù)據(jù)w0，w-1，w-2，w-n?？梢宰C明由式(3.3)所給出的wt的概率結構與中所描述的一樣，這里F為前置算子即。因此，w-n和序列w

12、1，w2，wt之間的概率關系，等同于wt+n+1和序列w1，w2，wt之間的概率關系。所以，為了估計首個觀測點之前n+1步的數(shù)據(jù)，我們可以首先考慮觀測序列結束之后n+1步數(shù)據(jù)的最優(yōu)預報和估計，然后將這個過程運用于wt的反轉序列。我們稱這種技術為“后向預報”。為了實現(xiàn)后向預報，需要建立一個能基本反映序列變化的模型。我們采用高階AR模型來描述實際的數(shù)據(jù)序列，在我們的實驗中就采用AR(8)模型來建立所需的輔助模型。在得到輔助長自回歸模型后，我們可以利用后向預報技術，利用式(3.2)定義的算子對序列進行分形反濾波，消弱數(shù)據(jù)中的長相關結構，得到序列。根據(jù)式(3.2)，我們在Sun SPARC20工作站上

13、利用C語言實現(xiàn)了分數(shù)差分算子，用于采樣數(shù)據(jù)的分形反濾波。為了考察分形反濾波的實際效果，我們選取某隨機數(shù)種子值和不同的差分階數(shù)d，利用定義生成分數(shù)差分噪音FARIMA(0,d,0)序列，每個序列的樣本個數(shù)為20000個。利用生成的分數(shù)差分算子進行分形反濾波，對各序列進行Hurst參數(shù)估計，得到表1。表1 FARIMA(0,d,0)序列的分形反濾波效果 目標參數(shù)dFARIMA(0,d,0)序列特性分形反濾波后序列的特性0.10.6260.1260.5110.0110.20.7270.2270.5250.0250.30.8250.3250.5360.036從表1分形反濾波后數(shù)據(jù)可以看出，分形反濾波達

14、到了預期效果。3.2 FARIMA的結構辨識ARMA模型的結構辨識與模型檢測我們知道，經(jīng)分形反濾波后所得到的序列是一個ARMA模型，因此FARIMA結構辨識的等價問題就是序列的ARMA分析與定階。我們采用 ARMA模型參數(shù)的近似極大似然估計14 。應用于辨識ARMA模型階數(shù),我們采用最小信息準則或最小AIC(Akaike Information Criterion)準則，和BIC準則15。我們在0,1,2,3,4,5中選擇p、q，在35種有效組合中，綜合利用AIC和BIC準則選擇使準則函數(shù)最小的p、q組合。對每個p、q組合的分析利用ARMA的極大似然估計方法。我們在統(tǒng)計軟件S-plus的基礎上

15、，利用S語言編制了通過近似極大似然估計和定階準則進行模型辨識的程序，使用 BellCore Morristown 研究中心的實際業(yè)務數(shù)據(jù)pAug.TL進行了實驗。3.3 模型的統(tǒng)計檢驗與診斷 時間序列建模的統(tǒng)計檢驗對于保證模型的應用效果具有重要的意義。通過模型的統(tǒng)計檢驗，可以對得到的候選模型進行評估。序列被估計為ARMA(p,q)模型后 ， 應為白噪聲序列。因此，我們可以利用模型ARMA(p, q)，從序列的一段樣本求得模型殘量的一段樣本值。這時我們便可以對命題“是白噪聲序列”進行統(tǒng)計檢驗14。我們利用以下的模型檢驗與診斷方法：1 標準化模型殘量序列圖；2 模型殘量的自相關函數(shù)檢驗；3 por

16、tmanteau檢驗。 因篇幅所限僅給出ARMA(1,0)模型診斷（圖1）。該圖有標準化殘差圖、殘差自相關函數(shù)圖及portmanteau檢驗圖。需要說明的是portmanteau檢驗，圖中的虛線表示顯著性水平0.05，分析點代表在當前自由度（即橫坐標取值）下，檢驗值所對應的顯著性水平；若分析點在該虛線之下，則表示分析點所對應的顯著性水平小于0.05，表示擬合情況較好；否則，就認為擬合不理想。 圖1 ARMA(1,0)模型診斷圖3.4 FARIMA模型的參數(shù)估計近似極大似然方法完成FARIMA(p,d,q)的模型辨識后，我們就可以利用FARIMA模型的最大似然方法對p+q+1個未知參數(shù)進行估計，

17、從而得到我們所需要的模型。設是FARIMA(p,d,q)過程，關于的條件分布是正態(tài)分布，、可以用Durbin-Levinson算法求得14。利用極大似然方法作參數(shù)估計時，似然函數(shù)的計算量相當大。由于我們所研究的序列是一個樣本數(shù)較大的序列(N=2,000)，我們利用一種近似極大似然方法來實現(xiàn)FARIMA的參數(shù)估計。該算法設計的基本出發(fā)點是僅利用FARIMA(0,d,0)過程的偏相關系數(shù)來計算上述的條件均值和條件方差，而不用FARIMA(p,d,q)過程的偏相關系數(shù)，這是因為FARIMA(p,d,q)過程的偏相關系數(shù)相當復雜。這樣即可得到全部估計17。 我們在利用AIC、BIC準則判定最優(yōu)模型的同

18、時，也考察差分系數(shù)d的合理性。若經(jīng)近似極大似然方法估計所得的d與前面所述的d的近似估計相差甚遠，或并不處于區(qū)間(0,0.5)內，我們則認為該模型是不準確的。4. 性能分析我們對同一序列分別建立FGN、AR、ARIMA和FARIMA四種不同的模型。如前所述，F(xiàn)GN模型有三個參數(shù)：均值、方差和Hurst參數(shù)；ARIMA模型是美國Georgia理工學院的研究小組所采用的時間序列模型7；而AR模型是用傳統(tǒng)方法給出的AR(8)自回歸模型（這里不詳述了）。網(wǎng)絡自相似業(yè)務的基本特性可用其自相關函數(shù)來反映。我們定義自相關函數(shù)均方誤差量MSE(Mean Squared Errors)如下： (4.1)其中MSE

19、(m)表示模型m的自相關函數(shù)均方誤差量，ACFmi表示模型m的第i階自相關函數(shù)，ACFSi表示樣本序列的第i階自相關函數(shù)。該統(tǒng)計量反映了模型對序列自相關函數(shù)的描述效果，值越小，效果越好。表2 各模型的MSE統(tǒng)計量模型MSE統(tǒng)計量FARIMA(1,d,1)0.0006031FGN0.0398209AR(8)0.0026151ARIMA(10,1,0)0.0011448從表2中MSE統(tǒng)計量來看，F(xiàn)ARIMA的描述效果仍被證明是最有效的，ARIMA次之，F(xiàn)GN的效果最差。為了比較FARIMA與其它模型在描述能力的優(yōu)劣，我們給出：FGN模型為： mean=3.8995，Var= 7.357078，H=

20、0.80；AR模型為AR(8)；ARIMA(10,1,0)：參數(shù)() =（-0.47360296,-0.48794950,-0.39297214, -0.28920862, -0.20433070, -0.23897851, -0.17016975, -0.10837808, -0.06937427,-0.03941886），=5.24312。利用仿真技術，分別產(chǎn)生四種模型的樣本，并與原始序列進行比較。圖2圖5是各模型與原始序列自相關函數(shù)的比較?？梢钥闯觯陂g隔較?。╨ag<15）時，F(xiàn)GN模型的自相關函數(shù)與原始序列的自相關函數(shù)有一定差異，而其它模型則較為準確地描述了這種短相關特性。考察

21、模型對長相關特性的描述效果，當間隔較大(lag>40)時，F(xiàn)GN和AR模型對長期間相關特性的描述誤差較大，而FARIMA和ARIMA要好得多，而FARIMA對長期間相關特性的描述偏大，ARIMA則偏小，顯然這與模型自身的特性有關：前者是把原序列看成平穩(wěn)的長相關序列來處理，而后者把原序列看成是非平穩(wěn)的短相關序列。 圖2 FARIMA模型與樣本數(shù)據(jù)自相關函數(shù)的比較 圖4 AR模型與樣本數(shù)據(jù)自相關函數(shù)的比較圖3 FGN模型與樣本數(shù)據(jù)自相關函數(shù)的比較 圖5 ARIMA模型與樣本數(shù)據(jù)自相關函數(shù)的比較 比較四個模型FGN、AR(8)、 ARIMA(10,1,0)、FARIMA(1,d,1)可以發(fā)現(xiàn)，

22、FGN模型適于描述長相關特性，模型參數(shù)較少，但描述能力有限；AR和ARIMA模型用較多的參數(shù)描述了樣本中復雜的相關特性，但模型較為復雜。FARIMA過程引入分數(shù)差分階數(shù)d這一個參數(shù)就有效地描述了樣本中的長相關特性，從而使得模型變得很簡潔。另外，通過將FARIMA(p,d,q)分離成“分數(shù)差分噪音”和“ARMA(p,q)”兩個組成部分，利用分數(shù)差分階數(shù)d反映了樣本中的長相關特性，而ARMA(p,q)中p+q+1個參數(shù)描述了樣本中的短相關特性，故模型本身還具有一定的物理意義，使得我們在利用該模型進行深入研究時可以有效地考察長、短相關特性的不同作用。這是AR、ARIMA模型所不具備的。5. 結論本文

23、討論了FARIMA(p,d,q)模型的概念和特性，發(fā)現(xiàn)時該模型可以描述自相似業(yè)務的長相關特性。并比較了FARIMA()模型與其它模型的描述能力，提出了一種基于FARIMA過程進行自相似業(yè)務建模分析的方法,系統(tǒng)地將具有長相關特性的時間序列分析方法應用在網(wǎng)絡業(yè)務的數(shù)據(jù)分析與建模中。通過對樣本數(shù)據(jù)進行分形反濾波，利用傳統(tǒng)的ARMA建模分析和統(tǒng)計檢驗技術解決了業(yè)務建模中的模型辯識問題。我們利用一種近似極大似然估計方法實現(xiàn)了業(yè)務建模中的參數(shù)估計。通過將所建的FARIMA模型同其它業(yè)務模型相比較，證實了FARIMA模型的優(yōu)效性。參考文獻1H.Heffes and D.M. Lucantoni. “A Ma

24、rkov modulated characterization of packetized voice and data traffic and related statistical multiplexer performance” IEEE Journal on Selected Areas in communications,4:856-868,19862D.Anick, et al., “Stochastic theory of a data-handling system with multiple sources” Bell System Technical Journal,61:

25、1871-1894,19823B.Melamed “An overview of TES processes and modeling methodology” In L.Donatielo and R.Nelson, eidtors, Models and techniques for Performance Evaluation of computer and communications system, pp 359-393. Springer-Verlag, New York,19934 R.Jain and S.A.Routhier, ”Packet trains: Measurem

26、ents and a new model for computer network traffic” IEEE Journal on Selected Areas in Communications, 4:986-995,19865D.M.Lucantoni “The BMAP/G/1 queue” In L.Donatielo and R.Nelson ,eidtors, Models and techniques for Performance Evaluation of computer and communications system, pp 335-358. Springer-Ve

27、rlag, New York,19936W.E. Leland, M.S.Taqqu, W. Willinger and D.V. Wilson, "On the self-similar nature of Ethernet traffic", In Proceedings of the ACM/SIGCOMM'93, San Francisco, CA, 183-193,1993.7S.Basu, A. Mukherjee “Time series models for Internet Traffic”, In: Proceedings of IEEE INF

28、OCOM96 pp 611-620,19968 J.R.M.Hosking, “Fractional differencing,” Biometrika, 68: 165-176, 1981.9I. Norros, “On the use of Fractional Brownian Motion in the theory of connectionless networks,” , IEEE Journal on Selected Areas in Commununication, 1995, 13(6):953-96210N.Duffield, “Economies of scale i

29、n long and short buffers of large multiplexers” in: Proceedings of 12th IEE UK Teletraffic Symposium, Windsor, 15-17 March 1995, 11 C.W.J.Granger and R.Joyeux, “An introduction to long-memory time series models and fractional differencing”, Journal of .Time Series Analysis. 1: 159-29, 1980.12 W.Lela

30、nd, et al., “On the self-similar nature of Ethernet traffic (extended version),” IEEE/ACM Transactions on Networking ,1994, 2(1):1-1513C.Agiakloglou, P.Newbold and M.Whohar, “Bias in an estimator of the fractional difference parameter”, Journal of Time Series Analysis, 14: 235-46, 199314Brockwell, P.J.and Davis, R.A., Time Series: Theory and Methods, 2nd edition, New York, Springer verlag, 1991.15H.Akaike, “Time series analysis and control through parametric models” ,Applied Time Series Analysis,