網(wǎng)絡(luò)流量測量的模型與算法研究

劉 剛

(黑龍江省交通信息通信中心)

1 引 言

最近幾年,互聯(lián)網(wǎng)地增長速度驚人,在使用互聯(lián)網(wǎng)過程中,用戶通常會面對網(wǎng)絡(luò)擁堵,網(wǎng)速較慢以及服務(wù)質(zhì)量較低等多方面關(guān)于網(wǎng)絡(luò)性能的問題,改善網(wǎng)絡(luò)性能以及加強網(wǎng)絡(luò)管理已經(jīng)成為日趨嚴峻的問題。如何掌握網(wǎng)絡(luò)行為特性,更好的了解網(wǎng)絡(luò)流量狀況以及盡可能多的網(wǎng)絡(luò)信息,無異成為關(guān)鍵的測量手段之一,因而人們越來越關(guān)注網(wǎng)絡(luò)流量的分析與測量。隨著互聯(lián)網(wǎng)的發(fā)展,我國已躍居為世界上互聯(lián)網(wǎng)網(wǎng)民第二的國家。隨著網(wǎng)絡(luò)流量的成倍增長,同時給網(wǎng)絡(luò)管理者帶來了流量的監(jiān)測、預(yù)測和網(wǎng)絡(luò)規(guī)劃等問題。我國的一些ISP和網(wǎng)絡(luò)規(guī)劃及運營者也越來越重視網(wǎng)絡(luò)行為、網(wǎng)絡(luò)流量測量、性能分析等方面的工作,正在逐步縮小和國外的差距?？v觀互聯(lián)網(wǎng)發(fā)展的三十年,網(wǎng)絡(luò)用戶數(shù)的成倍增長以及 Internet技術(shù)的日新月異,使得下一代Internet的成長和發(fā)展更加的迅猛。

網(wǎng)絡(luò)流量行為的主要有三個特性:方向性、端點性和時間性。論文主要分析了網(wǎng)絡(luò)流量特征,構(gòu)造出接近于真實網(wǎng)絡(luò)流程特性的流量模型,以此作為網(wǎng)絡(luò)行為預(yù)測和網(wǎng)絡(luò)規(guī)劃的依據(jù),將長相關(guān)特性的時間序列分析方法與自相似業(yè)務(wù)建模分析相結(jié)合,提出了基于FARIMA模型地對自相似業(yè)務(wù)進行研究的方法,利用“后向預(yù)報”技術(shù)對序列進行分形反濾波,并通過實驗,對實測數(shù)據(jù)的驗證,論證了模型的有效性和準確性。

2 小波變換與時間序列分析

小波技術(shù)是處理網(wǎng)絡(luò)流量非平穩(wěn)序列的有效工具和方法,可以保持分析對象的尺度不變性。小波變換定義為:

設(shè)f(t),φ(t)是平方可積函數(shù),且φ(t)的傅立葉變換Ψ(t)滿足條件:

內(nèi)積表示兩個函數(shù)的相似程度,小波函數(shù)也可以記作內(nèi)積形式:

小波變換的逆變換為:

利用時頻處理方法,對非平穩(wěn)信號進行分析,具體為將時域信號分解為二維時域—頻域聯(lián)合分布表示。通常情況下,時域信號時非常復(fù)雜的,利用小波變換技術(shù)來處理時域信號,在小波域上可以將時域信號分解為近似非相關(guān)過程,這樣可以使得在時域上非常困難的流量建模工作,在小波域上通常會比較簡單。小波分析處理非平穩(wěn)時間序列的方法為:利用小波分解將多個層的信號層層分解到不同的頻率通道上,分解后的時間序列通常在頻域上比原始信號單一,而且小波分解對時間序列做了平滑,所以分解后的時間序列平穩(wěn)性比原始序列的要大大提升。將非平穩(wěn)時間序列,經(jīng)小波變換后可以作為平穩(wěn)時間序列來處理,得到平穩(wěn)序列后就可以采用傳統(tǒng)的預(yù)測方法來對分解后的時間序列進行預(yù)測。

根據(jù)對時間序列的分析可以看出,利用觀測數(shù)據(jù)的特性來對數(shù)據(jù)建立盡可能合理的統(tǒng)計模型,并用該模型的統(tǒng)計特性來表征數(shù)據(jù)的統(tǒng)計規(guī)律,這種方法可以達到對系統(tǒng)的預(yù)測以及對其未來行為的預(yù)測這個目標,以用來對網(wǎng)絡(luò)流量進行控制或預(yù)報。時間序列分析的目的可以用四個方面來概括:描述、推斷、預(yù)報和控制。描述就是通過對數(shù)據(jù)的分析并構(gòu)造適當?shù)臄?shù)學(xué)模型來描述產(chǎn)生數(shù)據(jù)的隨機機制;推斷是根據(jù)某一隨機機制所產(chǎn)生的數(shù)據(jù),分析推斷它是否具有某些指定的屬性,或者由多個不同應(yīng)用的時間序列,分析不同的隨機機制是否具有相同的屬性;預(yù)報是利用時間序列的相關(guān)性,預(yù)報隨機機制在未來時刻的取值;控制是對某一個或多個隨機機制的一段觀測數(shù)據(jù)的分析,尋求對某些量的控制,以達到優(yōu)化的目的。

3 FARIMA模型

FARIMA模型是分數(shù)自回歸求和滑動平均模型,全稱為FractionalAutoregressiveIntegratedMovingAverage,記為FARIMA(p,d,q),數(shù)學(xué)表達式為φ(B)dxt=θ(B)at,其與普通ARIMA(p,d,q)模型的唯一差別在于d的取值。ARIMA模型的d只取0、1、2中的一個整數(shù),而FARIMA模型d∈(-0.5,0.5),可取分數(shù)。除了這點FARIMA(p,d,q)模型的其它處理工程和ARIMA(p,d,q)是一樣的,都是對時間序列進行d次差分后,轉(zhuǎn)換為ARMA(p,q)模型來處理。

通過FARIMA的定義可以看出,當d=0時,它是普通的ARMA(p,q)過程,是相關(guān)的。當d∈(0.0.5)時,FARIMA過程為長相關(guān)過程。另外,如果p=q=0,即FARIMA (0,d,0),它是FARIMA最簡單的形式,一般稱為分數(shù)差分噪聲,分數(shù)差分噪聲FARIMA(0,d,0)是FBM的離散情形,與FGN等價,但是由于FBM或FARIMA(0,d,0)過程僅有3個參數(shù),它們不能很好地表示實際中不可忽略的短相關(guān)結(jié)構(gòu)[6]。差分系數(shù) d表示長相關(guān)的強度,如同F(xiàn)GN過程中的Hurst參數(shù)一樣。事實上,H=d+1/2。

當d∈(0,0.5),p≠0和q≠0時,一個FARIMA(p,d, q)過程可以被看作由一個分數(shù)差分噪聲FARIMA(0,d,0)驅(qū)動的ARMA(p,q)過程,數(shù)學(xué)表達為Xt=φ-1(B)θ(B)Yt,其中Yt=Δ-dat是FARIMA(0,d,0)中的分數(shù)差分噪聲。FARIMA(p,d,q)過程擴展了分數(shù)布朗運動或FARIMA(0,d,0)的描述能力,彌補了他們在描述能力上的不足,從定義不難看出,FARIMA(p,d,q)模型是分數(shù)差分噪聲FARIMA(0,d, 0)為激勵的ARMA模型,該模型在利用參數(shù)d描述觀測樣本中的長相關(guān)結(jié)構(gòu)時,利用p+q+1個參數(shù)來刻畫樣本中的短相關(guān)結(jié)構(gòu)。

6 網(wǎng)絡(luò)流量建模

由于非平穩(wěn)序列經(jīng)過小波變換后,在頻率成分上比較單一,而且小波分解對其進行了平滑,從而小波分解后的序列可以看作是平穩(wěn)的序列。本節(jié)中利用FARIMA模型來對經(jīng)小波分解后的平穩(wěn)時間序列分量進行預(yù)測,由于該模型可以有效地考察長、短相關(guān)特性的不同作用,所生成的數(shù)據(jù)的相關(guān)特性也與真實網(wǎng)絡(luò)業(yè)務(wù)較為一致。

本文所采用的流量預(yù)測的算法原理就是將網(wǎng)絡(luò)流量構(gòu)成的時間序列f(t),先通過Mallat快速分解算法逐層分解為近似分量aj和細節(jié)分量dj,對各層分量時間序列使用FARIMA模型進行預(yù)測,最后通過Mallat分量重構(gòu)算法。由表達式:

圖1 流量預(yù)測過程圖

FARIMA模型算法可以如下描述:

(1)預(yù)處理已知的網(wǎng)絡(luò)業(yè)務(wù)分量,獲得一個零均值的時間序列;

(2)對參數(shù)d進行估計;

(3)對f(t)進行分數(shù)差分;

(4)對p和q定階,根據(jù)擬合FARIMA模型的經(jīng)驗,取p =2,q=1;

(5)估計參數(shù) φj和θj,在對擬合的模型定階后,可以通過參數(shù)估計得到所有的參數(shù)φj和θj以及精確的差分系數(shù)d,最后得到FARIMA(p,d,q)擬合流量。

其算法的基本流程如下圖:

圖2 實驗預(yù)測算法流程圖

5 實 驗

本實驗中我們對網(wǎng)絡(luò)流量進行建模和預(yù)測。下圖是原始網(wǎng)絡(luò)流量時間序列{f(t),t=1,2,...,1008},總計1008個數(shù)據(jù),其流量軌跡如下圖所示:

圖3 原始流量軌跡圖

從圖 3中可以看出,網(wǎng)絡(luò)的流量軌跡不斷出現(xiàn)一個個突發(fā)的流量高峰,整個軌跡呈現(xiàn)出自相似的現(xiàn)象,網(wǎng)絡(luò)流程具有長相關(guān)性和周期性。流量序列是非平穩(wěn)隨機過程。

在實驗中,使用 Db3小波系對采集的數(shù)據(jù)進行分解和重構(gòu),分解層數(shù) N=3。首先對原始流量進行 3層分解,圖 5是對原始流量的時間序列進行二進小波變換得到各層的近似分量a3和細節(jié)分量d3,d2,d1。

從圖 4可以看出,近似信號保持了與原始流量(圖 5)完全相同的變化趨勢,而且數(shù)值很接近。同時,隨著分解層數(shù)的不斷增大,細節(jié)信號也會變得越來越平滑。

圖4 小波分解形成的近似分量和細節(jié)分量

將算法仿真出的數(shù)據(jù)和實際流量數(shù)據(jù)進行比較,對網(wǎng)絡(luò)流量行為進行預(yù)測。圖 5表示的是網(wǎng)絡(luò)的實際流量軌跡,其中平均流量為505.4MB/hour,最大流量為1228.8MB/hour,最小為284.2MB/hour,兩者相差很大,說明了網(wǎng)絡(luò)流量確實是不平穩(wěn)的時間序列;圖 5是利用預(yù)測算法得到的擬合流量,其中,x軸為時間段,y軸為網(wǎng)絡(luò)流量。可以看出預(yù)測流量的變化趨勢、變化快慢和分散程度上都較好的反映了實際流量,從而驗證了算法的有效性。

進一步,我們可以計算該模型的均方誤差,基于均方誤差來定量的評估預(yù)測效果,誤差計算公式如下:

圖5 預(yù)測流量

其中,f(t)為流量真實值,f(t)′為擬合的預(yù)測值,M為數(shù)據(jù)量。通過對預(yù)測量和真是值進行比較,我們計算得到預(yù)測的均方誤差為 53.186,誤差比(平均誤差/平均流量)為10.52%。

圖6給出了預(yù)測誤差圖,x軸是時間軸,y軸是誤差值。從圖中可以看到預(yù)測的誤差值區(qū)間基本集中在數(shù)值區(qū)間(-100,100)。通過誤差分析得出結(jié)論,此預(yù)測算法能夠很好的對網(wǎng)絡(luò)流量進行測量分析。綜上所述,該算法可以有效地對流量趨勢進行預(yù)測。

圖6 流量預(yù)測誤差

通過上面的分析,基于FARIMA模型的流量預(yù)測算法可以準確地描述網(wǎng)絡(luò)業(yè)務(wù)流的變化趨勢,預(yù)測的流量和實際流量的趨勢大致相同。實驗結(jié)果表明該預(yù)測模型能有效的描述業(yè)務(wù)流量的未來趨勢,預(yù)測誤差較低而且在允許的范圍內(nèi)。

6 小 結(jié)

本文通過對網(wǎng)絡(luò)實際業(yè)務(wù)流量的各種統(tǒng)計和分析,驗證了業(yè)務(wù)流量具有自相似特性;并在此基礎(chǔ)上提出了一個基于FARIMA模型并結(jié)合小波分析技術(shù)實現(xiàn)的混合流量模型,而且驗證了預(yù)測模型的有效性。在實際網(wǎng)絡(luò)環(huán)境中,通常需要巨量的實驗數(shù)據(jù)和性能開銷,如何實現(xiàn)網(wǎng)絡(luò)流量的有效測量代表了今后研究的方向。完善本實驗?zāi)Ｐ汀；陔S機過程分析的網(wǎng)絡(luò)測量技術(shù)的建模與分析是今后該領(lǐng)域研究的重點。深入研究此類模型對于提高網(wǎng)絡(luò)測量技術(shù)有著積極的意義。隨著網(wǎng)絡(luò)技術(shù)的進步,網(wǎng)絡(luò)動態(tài)信息逐漸增多,這些都是對測量技術(shù)的新的挑戰(zhàn)。研究流量預(yù)測模型是今后發(fā)展的方向和難點,也是提高網(wǎng)絡(luò)測量技術(shù)研究工作的重要方向。

[1] 鄭守琪,楊新宇,曾明.兩種網(wǎng)絡(luò)業(yè)務(wù)流分析方法的應(yīng)用與實現(xiàn)[J].小型微型計算機系統(tǒng).2003,23(1):70-73.

[2] BHuffaker,JJung,ENemeth,etal.Visualizationofthegrowth andtopologyoftheNLANRcachinghierarchy.ComputerNetworksandISDNSystems,1998,30:2131-2139.

[3] ClaffyK,MonkTE,McRobbD.Internettomography.Nature. 1999-01-07.

[4] W.E.Leand,M.S.Taqqu,W.Willinger,andD.V.Wilson.On theself-similarnatureofEthernettraffic(extendedversion). IEEE/ACMTransactionsonNetworking,1994,2:1-15.

[5] HoskingJRM.Fractionaldifferencing[J].Biometrika,1981;68 (1):165-176.

[6] NorrosI.OntheuseoffractionalBrownianmotioninthetheoryofconnectionlessnetworks[J].IEEEJournalonSelectedAreasinCommunications,1995;13(6):953-962.

[7] WELeland,MSTaqqu,W.Willingeretal.Ontheself-similarnatureofEthernettraffic(extendedversion)[J].IEEE/ACM TransactionsonNetworking,1994;2(1).

[8] 洪飛,吳志美.基于小波的多尺度網(wǎng)絡(luò)流量測量模型[J].計算機學(xué)報,2006,29(1):166-170.

[9] 李捷,劉瑞新,劉先省,韓志杰.一種基于混合模型的實時網(wǎng)絡(luò)流量算法[J].計算機研究與發(fā)展,2006,43(5):806-812.

[10]紀其新,董永強.基于小波域混合高斯模型的自相似流量合成算法[J].計算機研究與發(fā)展,2006,43(3):389-394.