自相似流量模擬的Hurst參數實時計算

張冬梅

摘要： Hurst參數是自相似流量模擬重要參數。本文采用R/ S法對Hurst系數進行實時計算，在此基礎上提出通過實際的Hurst系數與理論Hurst系數的比較來衡量模擬流量與理論模型的差別。

Abstract： Hurst parameter is an important parameter of self-similar flow simulation. In this paper， the R/S method is used to calculate the Hurst coefficient in real time. On this basis， this paper proposes to measure the difference between the simulated flow and the theoretical model by comparing the actual Hurst coefficient with the theoretical Hurst coefficient.

關鍵詞： 自相似；Hurst參數；流量模擬

Key words： self-similar；Hurst parameter；flow simulation

中圖分類號：TP393.0 文獻標識碼：A 文章編號：1006-4311（2017）34-0226-02

0 引言

在網絡信息及通信技術發展的過程中，網絡流量模型一直是研究的重點，二十世紀七八十年代，人們主要采用PSTN模型對網絡流量的到達過程進行研究，由泊松模型的基本假定條件可知，伴隨時間的延續和數據的累積，累計流量應該趨近平均值，然而取得的結果卻與此有很大差異。Leland和Willinger等人收集了Bellcore實驗室在1989到1992年之間的各種Ethernet LAN的數據，證明了傳統用泊松到達傳輸來分析流量的假定是不充分的，需要新的信源模型。Berkeley實驗室的Vern等，在長期的研究中發現絕大部分的TCP過程，具有時間尺度上的非常明顯的自相似性特點，這并不同于泊松過程，主要表現為流量的突發性。因此，對網絡流量數據包的到達過程來建立模型時，應當結合自相似的過程進行建立。基于各種測試的統計，他們得到Ethernet的信源是自相似的，并測得自相似的重要參數Hurst的值是0.9。

1 自相似的數學定義

對于自相似過程的研究始于本世紀中葉，對于一個系統來說，其自相似性主要是從不同的時空尺度上來看某種過程或結構的特征都具有相似性。此外，各整體之間，或者是部分與部分之間，也會存在相似性。一般情況下自相似性有比較復雜的表現形式而不是局域放大倍數以后簡單地和整體完全重合。自相似性應用領域非常廣泛，包括天文學、地理學、電子學、化學以及環境科學等眾多領域。自相似性是跨尺度重復性，它可以產生出具有結構和規則的統計熱性，這是對自相似性現象的直觀描述。

在統計意義上，自相似過程主要表現為尺度不變性的隨機過程?；诖?，這種過程實際上可以認為是在隨機過程的基礎上引入了分形。對于隨機過程X（t），（-∞

則可以認為該過程是寬自相似。

對于離散的自相似過程，通常采用這個過程的聚合過程來進行定義。

對于一個平穩的時間序列X={X（i），i>0}，取X（m）（K）=1/mX（i）。

如果對于任意m，滿足XD=m1-HX（m），則稱序列是嚴格自相似的；如果只有當m→∞時，上面的式子才成立，則稱序列是漸進自相似的。

網絡自相似性是網絡流量特有的屬性，網絡流量在一個很長時間范圍內表現出的結構是自相似的，每一組成分在特征上與整體一致。對于網絡上的流量，不管是現在的時間t，還是過去的時間（t-s），同時不管s取何值，在t與t-s時刻的流量，都會具有相關性。

2 自相似的度量及Hurst參數的估算

既然流量是自相似的，如何用數學的定義表述自相似性呢？Hurst能夠對時間序列的自相關性進行描述，也能夠反映函數的衰減速度。用于對網絡業務流量進行表示的序列屬于自相似序列，而其中的Hurst參數，其取值在0.5

對于Hurst系數進行測量的方法有多種，主要有方差-時間圖法、R/S圖法、周期圖法； Whittle估計方法、小波分析估計方。

2.1 方差時間曲線法

對于一個自相似過程的到達時間序列Xm，當m取值較大時，其方差服從：Var（Xm）～Var（X）/m？茁

其中Hurst參數H=1-（？茁/2）。

這個式子表述為嚴格的數學公式是：log[Var（Xm）]～log[Var（X）]*？茁log（m），其中log[Var（X）]是常數，其值與m的大小無關，如果將Var（X）m作為m的函數在對數圖上畫出來，結果將得到一條斜率為？茁的直線。斜率在0和1之間就意味著具有自相似性，接下來可以直接估計H值。這種方法需要預先獲得大量的觀測數據，并且需要大量運算。這種算法的另一個缺點是必須把所有數據都準備好以后才能進行估算。該方法的優勢在于可以對隨機過程的自相似性進判別。如果生產的曲線，是斜率在0與1之間的直線，可以判斷其具有自相似性。

2.2 R/S分析法

R/S分析是經典的Hurst參數統計方法，它的算法原理是對于長度為k樣本序列{X（k），k=1…n}，劃分該序列為d個長度為n的不相交子序列，每一個子序列有樣本均值和樣本方差S（n），令Wk=[Xi-（n）]，則R/S的統計值為：R（n）/S（n）=[max（0，W（1），W（2），…，W（n）-min（0，W（1），W（2），…，W（n）]/S（n）

求出每個子序列的R/S統計值，再以算術平均值代替數學期望值，求出這些子序列的平均值E[R（n）/S（n）]，當序列是自相似序列時，E[R（n）/S（n）～cnH]，H就是Hurst系數，c為與d無關的常數。如果序列是短相關序列，則當n→∞時， H=0.5。已知序列X，把它分割成以n為大小的互不相交的塊，每塊中求R（n）/S（n）的值；在對數坐標上選擇合適的n的值，求得所有R/S值；在這些數據中擬合一條直線，其斜率就是Hurst參數的值。R/S分析法要能先活動該隨機過程的所有的觀察值，因此對于H參數的預測并不適合。

2.3 Whittle估計法

Whittle估計法屬于定量估計方法的一種，主要是在周期圖的基礎上進行的，并以周期圖的頻域為基礎進行分析。假設序列X屬于高斯隨機序列，并且周期圖是I（），f（x，H）是X的功率譜密度。根據最大似然，能夠使

g（H）=d？棕

取得最大值的H也就是要得到的Hurst系數。作為量化的估計方法，Whittle估計法一方面可以對H參數的值進行定量估計，另一方面也能夠對它的方差進行估計。

3 自相似流量模型模擬的Hurst系數的實時計算

網絡流量模擬就是構造與真實網絡業務相類似的數據包并發送到網絡上，從而為網絡攻防試驗或網絡安全產品提供實驗環境。如何使網絡流量模擬所產生的流量和實際的網絡流量相近，是流量模擬所需要考慮的一個重要問題。流量模擬的模型控制是以自相似模型為基礎，按照綁定的模型計算單位時間內的發包數量或下一個發包時間來控制流量的產生過程。

在對流量的模型控制中，針對不同的流量模型，采用一系列內置的流量速率過程數據來描述流量模型。流量生成源的實現算法流程如圖1所示，首先發送一個數據包，然后根據綁定的自相似模型來讀取下一單位時間內的發包數量或下一次發包時間。

由于網絡軟件及硬件的影響，網絡流量模擬所產生的流量與系統設置的理論模型是有一定差別的，差別的衡量用描述網絡流量自相似性的重要參數——Hurst系數。網絡流量模擬系統采用Hurst系數的實時計算方式對Hurst系數進行計算，通過實際的Hurst系數與理論Hurst系數的比較來衡量模擬流量與理論模型的差別。

當時間序列的樣本數目太少時，其它計算Hurst參數的方法誤差比較大，而R/S方法計算的結果相對來說更加穩定，為了實時的監測與計算H系數，可以把算法分為兩個部分，分別是數據收集與Hurst系數計算。在該算法體系中，對時間序列X進行記錄時，使用數組data。

步驟1：在第一個分組到達以后，再開始進行數據的收集，同時進行時間的計數。如果到達第一個分組時，時間記錄是tN，在這之后每次到達一個分組以后，對其到達時間與開始計數時間的時間之差？駐t進行記錄并且對到達的分組數total_number進行累計，在第n個分組（n>1）到達之后，如果tN+n-tN

步驟2：如果數組data的長度是M，要開始對當前流的Hurst系數進行計算。令時間序列是X，均值是，S（n）為標準差，而部分和是Y（n）=Xi，可以得到

=

？駐k=Y（k）-k，k=1，2，…，n。

由于自相似特性，n→∞，因此：E[]～cnH

C是正常數且與n無關。

以log{E[R/S（n）]}當做縱坐標，同時以logn當做橫坐標進行作圖，使用OLS進行直線擬合，該直線的斜率即是H。

步驟3：歸零時間與數據的計數器，并將Hurst系數值輸出，重復步驟1和2至試驗終止。

M的選擇非常重要，M選擇的太大反映不出Hurst系數的變化，M選擇的太小，Hurst系數變化過于頻繁，無法準確反映其實際的值。在試驗中我們選擇M在800-1200之間。另外，研究表明，網絡流量的自相似程度與流量的負載有關，網絡流量呈現自相似程度是在負載15%到70%之間，所以流量模擬環境在負載范圍內計算Hurst的值才是有意義的。

4 結論

對如何提高網絡流量模擬與真實網絡流量模擬的近似度問題，本文采用流量模擬的模型控制，使流量按照綁定的自相似模型產生流量，利用R/S法對Hurst系數的實時計算，從而可以把實際計算出的Hurst值與理論Hurst的值進行比較來衡量流量模擬與理論模型的差距。

參考文獻：

[1]W.E.Leland， M.S.Taqqu， W.Willinger， and .V.Wilson. On the Self-Similar Nature of Ethernet Traffic （extend version）. IEEE/ACM Transactions on Networking.

[2]王新.自相似網絡流量的建模與預測[D].碩士學位論文，2003，6.

[3]魏恒義，程竹林，劉偉娜，曹雪.基于小波分析的網絡流量的隨機模擬[J].西安交通大學學報，2003，2（2）：37-38.