自相似流量模擬的Hurst參數(shù)實(shí)時(shí)計(jì)算

張冬梅

摘要： Hurst參數(shù)是自相似流量模擬重要參數(shù)。本文采用R/ S法對(duì)Hurst系數(shù)進(jìn)行實(shí)時(shí)計(jì)算，在此基礎(chǔ)上提出通過實(shí)際的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

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

0 引言

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

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

對(duì)于自相似過程的研究始于本世紀(jì)中葉，對(duì)于一個(gè)系統(tǒng)來說，其自相似性主要是從不同的時(shí)空尺度上來看某種過程或結(jié)構(gòu)的特征都具有相似性。此外，各整體之間，或者是部分與部分之間，也會(huì)存在相似性。一般情況下自相似性有比較復(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)計(jì)熱性，這是對(duì)自相似性現(xiàn)象的直觀描述。

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

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

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

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

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

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

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

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

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

2.1 方差時(shí)間曲線法

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

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

這個(gè)式子表述為嚴(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ù)在對(duì)數(shù)圖上畫出來，結(jié)果將得到一條斜率為？茁的直線。斜率在0和1之間就意味著具有自相似性，接下來可以直接估計(jì)H值。這種方法需要預(yù)先獲得大量的觀測(cè)數(shù)據(jù)，并且需要大量運(yùn)算。這種算法的另一個(gè)缺點(diǎn)是必須把所有數(shù)據(jù)都準(zhǔn)備好以后才能進(jìn)行估算。該方法的優(yōu)勢(shì)在于可以對(duì)隨機(jī)過程的自相似性進(jìn)判別。如果生產(chǎn)的曲線，是斜率在0與1之間的直線，可以判斷其具有自相似性。

2.2 R/S分析法

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

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

2.3 Whittle估計(jì)法

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

g（H）=d？棕

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

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

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

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

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

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

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

步驟2：如果數(shù)組data的長度是M，要開始對(duì)當(dāng)前流的Hurst系數(shù)進(jìn)行計(jì)算。令時(shí)間序列是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)，同時(shí)以logn當(dāng)做橫坐標(biāo)進(jìn)行作圖，使用OLS進(jìn)行直線擬合，該直線的斜率即是H。

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

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

4 結(jié)論

對(duì)如何提高網(wǎng)絡(luò)流量模擬與真實(shí)網(wǎng)絡(luò)流量模擬的近似度問題，本文采用流量模擬的模型控制，使流量按照綁定的自相似模型產(chǎn)生流量，利用R/S法對(duì)Hurst系數(shù)的實(shí)時(shí)計(jì)算，從而可以把實(shí)際計(jì)算出的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ù)測(cè)[D].碩士學(xué)位論文，2003，6.

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