張冬梅

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

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.

關(guān)鍵詞： 自相似；Hurst參數(shù)；流量模擬

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

中圖分類號：TP393.0 文獻(xiàn)標(biāo)識碼：A 文章編號：1006-4311（2017）34-0226-02

0 引言

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

1 自相似的數(shù)學(xué)定義

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

在統(tǒng)計意義上，自相似過程主要表現(xiàn)為尺度不變性的隨機(jī)過程。基于此，這種過程實際上可以認(rèn)為是在隨機(jī)過程的基礎(chǔ)上引入了分形。對于隨機(jī)過程X（t），（-∞

則可以認(rèn)為該過程是寬自相似。

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

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

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

網(wǎng)絡(luò)自相似性是網(wǎng)絡(luò)流量特有的屬性，網(wǎng)絡(luò)流量在一個很長時間范圍內(nèi)表現(xiàn)出的結(jié)構(gòu)是自相似的，每一組成分在特征上與整體一致。對于網(wǎng)絡(luò)上的流量，不管是現(xiàn)在的時間t，還是過去的時間（t-s），同時不管s取何值，在t與t-s時刻的流量，都會具有相關(guān)性。

2 自相似的度量及Hurst參數(shù)的估算

既然流量是自相似的，如何用數(shù)學(xué)的定義表述自相似性呢？Hurst能夠?qū)r間序列的自相關(guān)性進(jìn)行描述，也能夠反映函數(shù)的衰減速度。用于對網(wǎng)絡(luò)業(yè)務(wù)流量進(jìn)行表示的序列屬于自相似序列，而其中的Hurst參數(shù)，其取值在0.5

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

2.1 方差時間曲線法

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

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

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

2.2 R/S分析法

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

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

2.3 Whittle估計法

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

g（H）=d？棕

取得最大值的H也就是要得到的Hurst系數(shù)。作為量化的估計方法，Whittle估計法一方面可以對H參數(shù)的值進(jìn)行定量估計，另一方面也能夠?qū)λ姆讲钸M(jìn)行估計。

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

網(wǎng)絡(luò)流量模擬就是構(gòu)造與真實網(wǎng)絡(luò)業(yè)務(wù)相類似的數(shù)據(jù)包并發(fā)送到網(wǎng)絡(luò)上，從而為網(wǎng)絡(luò)攻防試驗或網(wǎng)絡(luò)安全產(chǎn)品提供實驗環(huán)境。如何使網(wǎng)絡(luò)流量模擬所產(chǎn)生的流量和實際的網(wǎng)絡(luò)流量相近，是流量模擬所需要考慮的一個重要問題。流量模擬的模型控制是以自相似模型為基礎(chǔ)，按照綁定的模型計算單位時間內(nèi)的發(fā)包數(shù)量或下一個發(fā)包時間來控制流量的產(chǎn)生過程。

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

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

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

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

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

=

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

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

C是正常數(shù)且與n無關(guān)。

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

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

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

4 結(jié)論

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

參考文獻(xiàn)：

[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]王新.自相似網(wǎng)絡(luò)流量的建模與預(yù)測[D].碩士學(xué)位論文，2003，6.

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