劉 剛

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

1 引 言

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

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

2 小波變換與時(shí)間序列分析

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

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

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

小波變換的逆變換為:

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

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

3 FARIMA模型

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

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

當(dāng)d∈(0,0.5),p≠0和q≠0時(shí),一個(gè)FARIMA(p,d, q)過(guò)程可以被看作由一個(gè)分?jǐn)?shù)差分噪聲FARIMA(0,d,0)驅(qū)動(dòng)的ARMA(p,q)過(guò)程,數(shù)學(xué)表達(dá)為Xt=φ-1(B)θ(B)Yt,其中Yt=Δ-dat是FARIMA(0,d,0)中的分?jǐn)?shù)差分噪聲。FARIMA(p,d,q)過(guò)程擴(kuò)展了分?jǐn)?shù)布朗運(yùn)動(dòng)或FARIMA(0,d,0)的描述能力,彌補(bǔ)了他們?cè)诿枋瞿芰ι系牟蛔?從定義不難看出,FARIMA(p,d,q)模型是分?jǐn)?shù)差分噪聲FARIMA(0,d, 0)為激勵(lì)的ARMA模型,該模型在利用參數(shù)d描述觀測(cè)樣本中的長(zhǎng)相關(guān)結(jié)構(gòu)時(shí),利用p+q+1個(gè)參數(shù)來(lái)刻畫樣本中的短相關(guān)結(jié)構(gòu)。

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

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

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

圖1 流量預(yù)測(cè)過(guò)程圖

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

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

(2)對(duì)參數(shù)d進(jìn)行估計(jì);

(3)對(duì)f(t)進(jìn)行分?jǐn)?shù)差分;

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

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

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

圖2 實(shí)驗(yàn)預(yù)測(cè)算法流程圖

5 實(shí) 驗(yàn)

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

圖3 原始流量軌跡圖

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

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

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

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

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

進(jìn)一步,我們可以計(jì)算該模型的均方誤差,基于均方誤差來(lái)定量的評(píng)估預(yù)測(cè)效果,誤差計(jì)算公式如下:

圖5 預(yù)測(cè)流量

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

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

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

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

6 小 結(jié)

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

[1] 鄭守琪,楊新宇,曾明.兩種網(wǎng)絡(luò)業(yè)務(wù)流分析方法的應(yīng)用與實(shí)現(xiàn)[J].小型微型計(jì)算機(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ò)流量測(cè)量模型[J].計(jì)算機(jī)學(xué)報(bào),2006,29(1):166-170.

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

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