局域網流量的多重分形譜分析及關聯性研究

 收稿日期：2007-12-23；

修回日期：2008-03-14

基金項目：西北工業大學青年教師創新基金資助項目(W016210)



作者簡介：劉雁(1974-)，女，重慶人，博士，主要研究方向為計算機網絡非線性動力學（分岔、混沌）、生物醫學信息處理（liuyan@nwpu.edu.cn）；

慕德俊(1963-)，男，教授，主要研究方向為控制領域里的并行處理方法、機器人控制.

（西北工業大學 a.機電學院; b.自動化學院 西安710072）

摘要：鑒于網絡流量復雜的奇異特性，采用多重分形譜分析其豐富的結構特征。首先構造出局域網流量的多重分形譜，并分析其特點；然后分析了譜參數與平均流量變化圖的分布特點；進一步研究了多重分形譜參數與平均流量對數的關聯關系。研究結果顯示，多重分形譜寬度的變化與網絡流量的變化十分相似，且最大與最小概率的多重分形譜函數之差的變化在某種程度上比流量的波動要提前一個時段，該結果為采用多重分形譜實現網絡流量預測奠定了理論基礎。

關鍵詞：局域網絡流量; 多重分形譜; Hǒlder指數; 關聯性

中圖分類號：TP393

文獻標志碼：A

文章編號：1001-3695(2008)10-3153-02

Study on multifractal spectrum of LAN traffic and their correlations

LIU Yana，b MU De-junb

(a.School of Mechatronics b.School of Automation Northwestern Polytechnical University Xi’an 710072 China)

Abstract:Due to the singularity in the network traffic this paper used the multifractal spectrums to study the structures of network traffic. At first，constructed and analyzed the multifractal spectrums. Then studied the distributions of spectrum parameter versus the netwok traffic. Further presented the correlations between multifractal spectrum and logarithm of mean traffic. The result shows that the variation of width of multifractal spectrum is similar to that of network traffic. To some degree the difference between maximum and minimum probability of multifractal spectrum is ahead to the wave of network traffic and it is a fundamental route for the network traffic prediction.

Key words：LAN traffic; multifractal spectrum; Hǒlder exponent; correlation

網絡流量序列包含有豐富的非線性特性，隨著對網絡流量特征研究的深入，特別是對TCP數據流的研究以及對廣域網中流量尺度行為的研究發現：網絡流量在較大的時間尺度上表現出單重分形特性；而在較小的時間尺度上表現出明顯的多重分形特性，即網絡流量表現出復雜的變化規律，尤其是局部存在突發流量[1~4]。傳統的網絡流量的分析方法及模型較多的是網絡流量的自相似特性的研究，在相對較大的時間尺度上刻畫流量的自相似特性[5~7]，但這類分析方法無法描述序列的局部細微特征，不足以充分描述其突發特性。因此，還需引入多重分形來描述網絡流量序列中更加豐富的信息。

目前對于廣域網絡流量的研究已經發現網絡流量序列中存在復雜的奇異特性，而對于局域網絡的研究還處于起步階段。基于此，本文以局域網流量序列為研究對象，著重分析其在復雜的分形結構中不同層次的特征。首先分析局域網流量序列的多重分形譜的特性，進而分析多重分形譜參數與流量變化的關聯關系，分析結果為采用多重分形譜進行網絡流量預測奠定了理論基礎。

1多重分形及其譜參數的物理意義

簡單地說，多重分形即為分形對象的分解，分解后每部分均有自己的分形維數。假定一單位區間具有單位質量，將其分成若干子區間，每個區間長度為δ；同時為第k個子區間分配一個非負的質量μk，序列{μk，k≥1}表示一隨機過程，定義μk在時間點t0 處的奇異性指數α(t0)為

α(t0)=limδ→0(ln(μk)/ln δ)

(1)

其中：μk表示包含時間點t0子區間的質量。奇異性指數α(t)也稱做Hǒlder指數，在分形理論中表征分形體某小區域的分維，又稱為局部分維，其值的大小反映了小區域生長幾率的大小。

如果式（1）中的極限不存在，則表示在t0處的奇異性指數沒有定義；如果α(t)為一常數，則說明該序列的奇異性可以僅用一個全局尺度指數來表征，這種分形特征就是單重分形特征；如果α(t)隨時間t的變化而變化，即其尺度行為特征與時間有關，則該序列具有多重分形特性。與單重分形相比，多重分形概念推廣拓展了人們對尺度行為的理解和認識，與時間相關的尺度特性能夠反映出局部時間范圍內的不規則現象[8]。

多重分形用于表示分形體中小區域的分維，如果小區域的數目很大，α(t)將單重分形的分形指數(Hurst參數)擴充到多值，這就需要知道α(t)取不同值的概率才能分析網絡流量的特征。于是，得到一個由不同α(t)組成的無窮序列構成的譜f(α)，其物理意義則是表示相同α值的子集的分形維數，即表示α(t)出現的概率，稱為多重分形頻譜，簡稱多重分形譜。f(α)取值應在[0，1]之間，通常是上凸形狀(∩)，可以將多重分形譜理解為指數α(t)的概率分布(密度)[9]。

多重分形譜f(α)可以反映網絡流量在分形結構上不均勻分布的性質，從而給出比簡單分維更加豐富的結構信息。如果一個序列的多重分形譜的α(t)<1，則表示時間序列上某點周圍的小區間內所有尺度上都有較高程度的突發；若α(t)>1，則說明業務量變化較平緩，突發不明顯[8，10]。因此，可以通過判斷α(t)的范圍來判斷網絡流量的突發特性。多重分形譜的寬度Δα=αmax-αmin的大小反映了整個分形結構上概率分布的不均勻程度，從而可以全面地描述分形結構上不同區域、不同層次、不同局域條件的特性。此外，多重分形譜的參數αmax和f(αmax)反映的是概率最小子集的性質，而αmin和f(αmin)反映的是概率最大子集的性質。因此，多重分形譜f(α)是對序列分形結構上的復雜程度、不規則程度以及不均勻程度的一種度量。 

2多重分形譜物理量之間的關系

定義一個配分函數χq(ε)，對概率P(ε)用q次方進行加權求和，其數學表達式為

χq(ε)=∑Pi(ε)q=ετ(q)(2)

其中：τ(q)稱為質量函數（又稱結構函數），如果上式右面的等式成立，即配分函數和ε有冪函數關系，則質量函數為

τ(q)=ln χq(ε)/ln ε(3)

根據多重分形的定義可由τ(q)得到多重分形的廣義維數

Dq=τ(q)/（q-1）=ln χq(ε)/[(q-1)ln ε](4)

根據勒讓德變換，α、 f(α)、τ(q)和Dq存在以下關系：

Dq=[qα-f(α)]/（q-1）(5)

f(α)=qα-τ(q)(6)

α=dτ(q)/dq (7)

由式(5)可知，如果已知α及f(α)則可求出Dq，而α可以通過式(7)τ(q)求導得出。由式(6)(7)可得到多重分形譜為

f(α)=q (dτ(q)/dq)-τ(q)(8)

進一步，根據式(4)(7)有

α=dτ(q)/dq=d[(q-1)Dq]/dq(9)

即如果已知Dq也可求出α。在以上各式中q稱為權重因子，多重分形譜即是通過不同的q取值將分形體分成具有不同層次的區域來研究[9，11]。

3仿真分析

局域網流量序列來自于某集團公司內部網絡中心的網絡監測系統中心交換機的流量數據，測試時間為2005年3月16日~3月28日。此局域網是以太類型的由幾百臺主機組成的中型局域網，流量數據是由網絡嗅探工具在等時間間隔內(1 s)記錄網絡數據包的個數和數據量，所得結果為一非負的時間序列，其傳輸的信息主要包括網頁瀏覽、文件傳輸、網絡業務系統等。

3．1多重分形譜及參數

圖1為以2005年3月16日工作時段為分析對象的多重分形譜，其多重分形譜參數如表1所示。從仿真結果可以看出，圖中多重分形譜的寬度和形狀差別很大。其中：17:00~18:00的多重分形譜寬度Δα最窄而8:00~9:00的Δα最寬，表明后者的流量分布最不均衡；15:00~16:00的αmin和f(αmin)最小，說明在此時段出現最大值的概率最小，但最易發生流量突變；而10:00~11:00時段的αmin和f(αmin)最大，說明在此時段出現最大值的概率最大，但最不易發生流量突變；9:00~10：00的f(αmax) 最大，說明此時段出現最小值的概率最大；而11：00~12：00的f(αmax) 最小，說明此時段出現最小值的概率最小。進一步分析可以看出，Δf有正負，多重分形譜所表現出圖形的形狀不同，如10：00~11：00的多重分形譜左邊呈現鉤狀，而9：00~10：00的多重分形譜右邊呈現鉤狀。這反映了出現流量最大值與最小值概率之比，即當Δf>0時，流量出現最大值的概率大于出現最小值的概率；反之亦然。

表1工作時段流量序列的多重分形譜參數

時段αminf(αmin)αmaxf(αmax)ΔαΔf

8~90.473 10.057 62.713 70.042.240 60.017 6

9~100.374 30.038 11.922 30.521 11.548-0.483

10~110.620 10.473 92.618 30.041 51.998 20.432 4

11~120.412 10.065 92.434 802.022 70.065 9

14~150.615 30.237 11.783 50.267 51.168 2-0.030 4

15~160.148 101.794 70.195 71.646 6-0.195 7

16~170.303 101.655 60.0771.352 5-0.077

17~180.551 50.159 51.561 40.291 31.01-0.131 8

注:Δf＝f(αmin)-f(αmax)。

3．2多重分形譜參數與流量變化量的關系

通過前面的仿真分析可知，多重分形譜的參數Δα和Δf可以在一定程度上反映流量波動幅度的變化。為進一步分析多重分形譜與流量變化量之間的關系，定義Zi為描述一定時間間隔Δt下的平均流量I(ti)的變化為

Zi=ln [I(ti)/I(ti-1)](11)

時間標度Δt選為1 h，則I(ti)表示為第i h的平均流量，I(ti-1)表示為第(i-1) h的平均流量，這樣每小時分別都有一個Zi、Δαi和Δfi[9]。

這里選取2006年3月15日的15:00至3月28日10:00共307 h流量序列分析Δαi和Δfi隨Zi變化的分布圖，如圖2所示。可以看出，Zi偏離原點越遠Δαi越大，即流量的變化越大Δαi越大；同時，｜Zi｜較小時，｜Δfi｜較大的概率大。這說明多重分形譜參數與平均流量的變化存在一定的相關性。

進一步，圖3為2005年3月16日以小時為分析單元、分辨率為分鐘時流量序列的方差對數、Δα、平均流量對數及Δf的序列圖。從圖3可以明顯看出，Δα的分布與方差的變化驚人地相似。而從24 h平均流量的對數圖可以看出，其共有五個低谷，分別是3:00~4:00、7:00~8:00、13:00~14:00、16:00~17：00及19:00~17:00。而Δf的低谷共有七個，分別是2:00~

3:00、6:00~7:00、9:00~10:00、12:00~13:00、15:00~16:00、18:00~19:00及21:00~22:00。除了兩個時段外，其他時段Δf的波谷出現時間比平均流量對數波谷要早1 h。如果這種現象是普遍的，則Δf就可以用來預測流量的變化趨勢。它們之間進一步的關聯關系及采用多重分形譜實現網絡流量序列的預測是筆者后續研究的內容。

4結束語

由于多重分形譜在某些情況下可以描述系統中豐富的突發信息，是一種描述復雜系統突發特性的數學方法。本文研究了局域網流量序列的多重分形特征，證實了在網絡流量序列中存在局部奇異特性，并進一步分析了多重分形譜參數與網絡流量序列變化量之間的關聯關系。為進一步實現網絡流量預測奠定了理論基礎，對網絡設計、性能估計和網絡協議的制定等都具有十分重要的意義。

參考文獻：

[1]LEVY V J SIKDAR B. A multiplicative multifractal model for TCP traffic[C]//Proc of the 6th IEEE Symposium on Computers and Communications. Washington DC: IEEE Computer Society 2001:714-719.

[2]FELDMANN A GILBERT A C WILLINGER W. Data networks as cascades: investigating the multifractal nature of Internet WAN traffic[J].Computer Communication Review，1998，28(4):42-55.

[3]LACOVONI G MANCE V VERQNI D. Single source TCP-beha-viour: a multifractal analysis[C]//Proc of IEEE Global Telecommunications Conference. 2000:323-328.

[4]FELDMANN A GILBERT A C WILLINGER W， et al. The changing nature of networ traffic: scaling phenomena[J].ACM SIGCOMM Computer Communication Review，1998，28(2):5-29.

[5]JACKSON J K. Network of waiting lines[J].Operation Research，1957，5(4):518-521.

[6]BERAN J SHERMAN R TAQQU M S， et al. Long-range-depen-dence in variable-bit-rate video traffic[J].IEEE Trans on Communications 1995，43(2):1566-1579.

[7]RAO Yun-hua XU Zhong-yang LIU Zheng-lin. Length requirement of self-similar network traffic[J].Chinese Journal of Electronics，2004，13(1):175-178.

[8]叢鎖 韓良秀 劉巖 等. 基于離散小波變換的網絡流量多重分形模型[J]. 通信學報 2003，24(5):43-48.

[9]孫霞 吳自勤 黃畇. 分形原理及應用[M].合肥:中國科學技術大學出版社 2003.

[10]RIEDI R.An improved multifractal formalism and self-similar-mea-sures[J].Journal of Math Analysis and Applications，1995，189(2):462-490.

[11]張濟忠. 分形[M]. 北京: 清華大學出版社 1995.