一種網絡流量自相似參數估計方法

2023-05-27 18:14:56

專利名稱：一種網絡流量自相似參數估計方法
技術領域：
本發明屬於計算機網絡技術，涉及自相似網絡流量領域中自相似參數 估計技術，能直接應用於實際網絡中，實時準確估計網絡流量的自相似參數。
背景技術：
現有研究表明，網絡流量具有自相似特性。自相似概念是Bdoit B. Marddbrot首先提出的，用來描述對象的尺度不變特性。嚴格自相似過程 的定義為-
稱一個連續時間過程7 =化(/),^0}是自相似係數為/^0 (H-ss)的過 程，如果它滿足條件^0"—"r^),VQ0，V。0。其中表示有限維分 布皆相等。參數/f被稱為Hurst參數或自相似參數，它是自相似程度的主
要度量。
網絡流量自相似性的發現顛覆了傳統基於Poisson過程的網絡流量模 型。傳統的基於分析網絡流量馬爾可夫性的模型不僅不能體現網絡自相似 這一基本特性，而且很有可能從本質上導致對網絡QoS性能指標，如延時， 阻塞等的低估。於是，分析網絡流量的自相似性並建立網絡流量自相似模 型是目前網絡研究迫切需要解決的問題。網絡流量自相似性研究中的關鍵 步驟就是對網絡流量自相似(Hurst)參數進行有效而準確的估計。而時間 方差圖法是一種自相似參數估計的重要方法，該方法利用自相似過程慢衰 減特性，也就是當樣本數m趨於無窮時，其算術平均的方差衰減速度要慢 於其樣本大小的倒數附-1，而是與附-〃成正比關係(0<〃<1)。對於長度為W 的網絡流量《(i-l,2,…局，時間方差圖法的主要步驟為
(1)將原始時間序列^(i^,2,…,A0劃分為_/個大小為附的數據塊，J、L^/附」，其中符號b」表示對^向下取整。。計算出每個數據塊的均值:
義!附)=(^^,+1+ + ^^)/附，A:-l,2,…^ m = l,D (1) 其中A:為各個數據塊的標記。
(2) 計算I壙)，A-l，2，.々的方差，方差var(義W)由式(2)可得 var(義W卜丄t(X")2 一(丄力X")2 (2)
此方差即為var(^1的估計值。
(3) 按以下子步驟可獲得"或/Z的估計值
".對於每個給定的w，將原始數據《,％2,...,^^，分解為y個數據塊，， 每個數據塊大小為附，計算出^["0， A:=l,2,...，iV/m; 6.對不同的m值，重複步驟a;
c.由於當m — oo時，方差var(X(—) am—"，其中a為獨立於m的有 限正常數，0<"<1.且//=1-々/2以樣本方差logF"W(—為縱軸，logm為橫軸 描點。這些點應該在一條直線附近，且直線的斜率為"=2//-2，-1^^《0。
我們稱由以上步驟計算網絡流量自相似參數的方法為原始的時間方差 圖法。該方法計算複雜度適中，而且直觀，意義明確，但是它最大的缺點 就是計算的準確性和魯棒性較差，不能適應複雜的實際網絡環境。

發明內容
本發明提供了一種網絡流量自相似參數估計方法，該方法提高了計算 的準確性和魯棒性，能夠適應複雜的實際網絡環境。
本發明提供的網絡流量自相似參數估計方法步驟包括
(1) 在網絡的聚合節點上採集一組網絡數據，其長度記為M
(2) 按照下式(I)計算數據塊大小m的取值範圍附min和附maxformula see original document page 5
(I)
其中，符號「xl表示對;c向上取整；
(3) 4*m=mmin;
(4) 將步驟(l)釆集的長度為iV網絡數據劃分為大小為m的數據塊，得
到j個數據塊，_/ = Lw/w」；對每個數據塊依次賦予編號&再根據下式(n)
計算每個數據塊的均值X";
I"-U…+ 4)/w，卜l,2，…，y (II)
(5) 利用步驟(4)計算的_/個數據塊的均值，根據下式(III)求出方差 var(,));
var(,)卜丄力才))2 —(丄^才))2 (III)
_/ 4=1 ;t=l
(6) 令附=附+1，如果m《m臓，轉入步驟(4)，否則進入步驟(7);
(7) 根據下式計算自相似參數7/.'
其中，"為序列log(var(XW))和logm線性擬合得到的直線的斜率。
和原始的時間方差圖法相比，本發明增加了數據塊選擇過程，解決了 時間方差圖數據塊範圍不確定的問題。它通過大量實驗給出了具體的經驗 公式，能在大範圍內根據不同長度的數據量選擇計算區間，剔除了影響參 數估計的不良數據。本發明方法不僅降低了計算量，而且大大增加了算法 的精確度和魯棒性，具有很強的適應性。本發明能適應複雜的網絡環境而 應用於實際網絡中對自相似參數進行準確估計。圖2為H-0.70時，原始方法的估計結果示意圖。 圖3為H-0.70時，本發明方法的估計結果示意圖, 圖4為H-0.75時，原始方法的估計結果示意圖。 圖5為11=0.75時，本發明方法的估計結果示意圖, 圖6為H-0.80時，原始方法的估計結果示意圖。 圖7為H-0.80時，本發明方法的估計結果示意圖, 圖8為H-0.85時，原始方法的估計結果示意圖。 圖9為H-0.85時，本發明方法的估計結果示意圖,
具體實施例方式
下面結合附圖和實例對本發明作進一步詳細的說明。
如

圖1所示，本發明提供的網絡流量自相似參數估計方法具體包括如
下幾個步驟
步驟l.在網絡的聚合節點上採集網絡流量，得到一組長度為W的網絡 數據。
網絡流量是自相似參數估計的對象。網絡流量的採集方法採用普通的 數據採集方法即可。需要指出的是，這裡採集的流量是聚合節點上的流量，
也就是路由器上的流量。在聚合節點上的流量的自相似參數在0.5以上，表 現出長程相關的強自相似特徵，對其進行自相似參數估計才有實際的意義。 網絡流量的量度可以是單位時間內到達包的總大小，其單位一般為
^^/S;也可以測量兩個包之間或相距"個包之間到達的時間間隔，單位為 S。本發明採用第一種測量方式，因為第一種方式包含了網絡流量更多的信 息，能準確地反映網絡流量特性，而且第一種測量方式得到的數據的自相 似特徵穩定，自相似參數估計準確性更高。為了達到對網絡流量自相似參
數的實時估計的目的，我們固定網絡流量的長度為W，其大小選取在50000 到500000左右可以保證計算的實時性以及自相似參數估計的準確性。 步驟2.確定數據塊大小m的範圍mmin和
6uL^。,腿」，附_=「10'。，歸，(I) 根據網絡流量數據大小，對數據塊大小m進行選擇，確定數據塊大小
m的具體範圍，達到簡化計算，增加精度的目的。在本發明中，為得到精
確的估計值，體現出統計特性，則必須保證分解後的數據塊大小和數據塊
個數都要足夠大。也就是說，m和W兩個參數都必須較大，且滿足附<<^。
若w取值太大，則數據塊個數太小，不足以體現出統計特性，應捨棄。權
衡兩者之間的關係，通過大量實驗結果，w的經驗選擇範圍由 n+o,扁」，附腿=「101。，謂〕，且^^^鵬確定。
步驟3.初始化數據塊大小m值，令附=附曲。
步驟4.根據數據塊大小m，將網絡數據iV劃分為大小為m的數據塊，
得到j個數據塊，y:L^/附」，對每個數據塊按採樣時間賦予編號A， yt-l，2，.,v'。根據下式(II)計算每一數據塊的均值，得到_/個值。
才)-(U…+ D/附，*=1,2"..J (II)
步驟5.對於步驟4計算的j'個數據塊的均值，根據下式(III)求出方
var(,))-丄t(才))2 -(丄t才))2 (III)
步驟6.令附二附+1，如果m《附薩，轉入步驟4，否則進入步驟(7)。 步驟7.根據下式計算自相似參數//.-"=2// - 2
其中，/ 為序列log(var(^1)和logm進行線性擬合得到的直線的斜率。
於是對應不同的附值，得到了(附max-附mhTH)個^"^"0。由於網絡流量
具有自相似性，於是log(var^—D)與log附成正比，所以對序列 1og(var(義—^和logm進行線性擬合，得到的直線的斜率就是々值。
線性擬合具體的方法可採用最小二乘法擬合，在該方法下"的具體計
算公式為Zlog(var(X("")))logw —1/(m證-mmin +l)Zlog(var(%(w)))Zlogw
一 、 ， ,■ 、 ， \ 2
根據上述步驟對網絡流量的自相似參數進行估計，經過大量實驗驗證， 完全可以精確估計，並且對於不同類型的網絡流量該方法均能適應，能廣
泛應用於LAN和WAN中。 實例
為了驗證以上自相似參數估計方法的有效性，我們用自相似參數固定 的分數高斯噪聲(FGN Fractional Gaussian Noise)模型產生模擬網絡流量數 據，得到自相似參數分別為0.7， 0.75， 0.8， 0.85的數據序列。每組數據集
有100000個數據，由數據塊選擇公式(I)，得到mmin為100， Wmax為lOOO。
我們對原始的時間方差圖法與本發明方法進行比較，實驗結果如下圖2~圖 9，實驗結果總結如表l所示。
由表1可見，使用經驗公式來選擇數據塊大小的變化範圍，可以明顯 地提高自相似參數估計的準確度，並且也能極大地降低計算複雜度，減少 運算時間。本發明能有效應用於網絡流量自相似參數的實時測量中。
表1原始的時間方差圖法與本發明方法精度對比
實際值H原始時間方差圖法的 自相似估計值及其誤差本發明方法的 自相似估計值及其誤差
0.7000.5826 (16.77%;)0.7093 (1.33%)
0.7500.6191 (17.45%)0,7513 (0.17%)
0.8000.6538 (18.28%)0.7902 (1.23%)
0.8500.6866 (19.22%)0.8255 (2.880/0)
權利要求
1、一種網絡流量自相似參數估計方法，其步驟包括(1)在網絡的聚合節點上採集一組網絡數據，其長度記為N；(2)按照下式(I)計算數據塊大小m的取值範圍mmin和mmax其中，符號表示對x向上取整；(3)令m＝mmin；(4)將步驟(1)採集的長度為N網絡數據劃分為大小為m的數據塊，得到j個數據塊，對每個數據塊依次賦予編號k，再根據下式(II)計算每個數據塊的均值(5)利用步驟(4)計算的j個數據塊的均值，根據下式(III)求出方差var(X(m))；(6)令m＝m+1，如果m≤mmax，轉入步驟(4)，否則進入步驟(7)；(7)根據下式計算自相似參數Hβ＝2H-2其中，β為序列log(var(X(m)))和logm線性擬合得到的直線的斜率。
全文摘要
本發明涉及一種網絡流量自相似參數估計方法，包括在網絡的聚合節點上採集一組網絡數據；計算數據塊大小m的取值範圍；在數據塊大小取值範圍內對網絡流量進行時間方差圖自相似參數估計。該方法給出了數據塊選擇的經驗公式，解決了時間方差圖法中數據塊大小範圍不確定而不能實際應用的問題。經過大量的實驗驗證，該方法不僅有效克服了原有時間方差圖法估計自相似參數的精度低，穩定性差的缺點，而且降低了其計算量，能應用於實際網絡流量的自相似參數估計，對自相似網絡流量模型的研究和應用有重要作用。
文檔編號H04L12/26GK101478457SQ200910060559
公開日2009年7月8日 申請日期2009年1月16日 優先權日2009年1月16日
發明者劉祖浩, 莉 喻, 李兆婧, 雲 白, 博 趙 申請人:華中科技大學