網絡流量測量的模型與算法研究

劉 剛

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

1 引 言

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

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

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

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

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

內積表示兩個函數的相似程度,小波函數也可以記作內積形式:

小波變換的逆變換為:

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

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

3 FARIMA模型

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

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

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

6 網絡流量建模

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

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

圖1 流量預測過程圖

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

(1)預處理已知的網絡業務分量,獲得一個零均值的時間序列;

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

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

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

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

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

圖2 實驗預測算法流程圖

5 實 驗

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

圖3 原始流量軌跡圖

從圖 3中可以看出,網絡的流量軌跡不斷出現一個個突發的流量高峰,整個軌跡呈現出自相似的現象,網絡流程具有長相關性和周期性。流量序列是非平穩隨機過程。

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

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

圖4 小波分解形成的近似分量和細節分量

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

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

圖5 預測流量

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

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

圖6 流量預測誤差

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

6 小 結

本文通過對網絡實際業務流量的各種統計和分析,驗證了業務流量具有自相似特性;并在此基礎上提出了一個基于FARIMA模型并結合小波分析技術實現的混合流量模型,而且驗證了預測模型的有效性。在實際網絡環境中,通常需要巨量的實驗數據和性能開銷,如何實現網絡流量的有效測量代表了今后研究的方向。完善本實驗模型。基于隨機過程分析的網絡測量技術的建模與分析是今后該領域研究的重點。深入研究此類模型對于提高網絡測量技術有著積極的意義。隨著網絡技術的進步,網絡動態信息逐漸增多,這些都是對測量技術的新的挑戰。研究流量預測模型是今后發展的方向和難點,也是提高網絡測量技術研究工作的重要方向。

[1] 鄭守琪,楊新宇,曾明.兩種網絡業務流分析方法的應用與實現[J].小型微型計算機系統.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] 洪飛,吳志美.基于小波的多尺度網絡流量測量模型[J].計算機學報,2006,29(1):166-170.

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

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