局域網(wǎng)流量的多重分形譜分析及關(guān)聯(lián)性研究

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

修回日期：2008-03-14

基金項目：西北工業(yè)大學(xué)青年教師創(chuàng)新基金資助項目(W016210)



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

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

（西北工業(yè)大學(xué) a.機(jī)電學(xué)院; b.自動化學(xué)院 西安710072）

摘要：鑒于網(wǎng)絡(luò)流量復(fù)雜的奇異特性，采用多重分形譜分析其豐富的結(jié)構(gòu)特征。首先構(gòu)造出局域網(wǎng)流量的多重分形譜，并分析其特點(diǎn)；然后分析了譜參數(shù)與平均流量變化圖的分布特點(diǎn)；進(jìn)一步研究了多重分形譜參數(shù)與平均流量對數(shù)的關(guān)聯(lián)關(guān)系。研究結(jié)果顯示，多重分形譜寬度的變化與網(wǎng)絡(luò)流量的變化十分相似，且最大與最小概率的多重分形譜函數(shù)之差的變化在某種程度上比流量的波動要提前一個時段，該結(jié)果為采用多重分形譜實(shí)現(xiàn)網(wǎng)絡(luò)流量預(yù)測奠定了理論基礎(chǔ)。

關(guān)鍵詞：局域網(wǎng)絡(luò)流量; 多重分形譜; Hǒlder指數(shù); 關(guān)聯(lián)性

中圖分類號：TP393

文獻(xiàn)標(biāo)志碼：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

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

目前對于廣域網(wǎng)絡(luò)流量的研究已經(jīng)發(fā)現(xiàn)網(wǎng)絡(luò)流量序列中存在復(fù)雜的奇異特性，而對于局域網(wǎng)絡(luò)的研究還處于起步階段。基于此，本文以局域網(wǎng)流量序列為研究對象，著重分析其在復(fù)雜的分形結(jié)構(gòu)中不同層次的特征。首先分析局域網(wǎng)流量序列的多重分形譜的特性，進(jìn)而分析多重分形譜參數(shù)與流量變化的關(guān)聯(lián)關(guān)系，分析結(jié)果為采用多重分形譜進(jìn)行網(wǎng)絡(luò)流量預(yù)測奠定了理論基礎(chǔ)。

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

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

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

(1)

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

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

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

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

2多重分形譜物理量之間的關(guān)系

定義一個配分函數(shù)χq(ε)，對概率P(ε)用q次方進(jìn)行加權(quán)求和，其數(shù)學(xué)表達(dá)式為

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

其中：τ(q)稱為質(zhì)量函數(shù)（又稱結(jié)構(gòu)函數(shù)），如果上式右面的等式成立，即配分函數(shù)和ε有冪函數(shù)關(guān)系，則質(zhì)量函數(shù)為

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

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

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

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

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

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

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

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

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

進(jìn)一步，根據(jù)式(4)(7)有

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

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

3仿真分析

局域網(wǎng)流量序列來自于某集團(tuán)公司內(nèi)部網(wǎng)絡(luò)中心的網(wǎng)絡(luò)監(jiān)測系統(tǒng)中心交換機(jī)的流量數(shù)據(jù)，測試時間為2005年3月16日~3月28日。此局域網(wǎng)是以太類型的由幾百臺主機(jī)組成的中型局域網(wǎng)，流量數(shù)據(jù)是由網(wǎng)絡(luò)嗅探工具在等時間間隔內(nèi)(1 s)記錄網(wǎng)絡(luò)數(shù)據(jù)包的個數(shù)和數(shù)據(jù)量，所得結(jié)果為一非負(fù)的時間序列，其傳輸?shù)男畔⒅饕ňW(wǎng)頁瀏覽、文件傳輸、網(wǎng)絡(luò)業(yè)務(wù)系統(tǒng)等。

3．1多重分形譜及參數(shù)

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

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

時段α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多重分形譜參數(shù)與流量變化量的關(guān)系

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

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

時間標(biāo)度Δ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偏離原點(diǎn)越遠(yuǎn)Δαi越大，即流量的變化越大Δαi越大；同時，｜Zi｜較小時，｜Δfi｜較大的概率大。這說明多重分形譜參數(shù)與平均流量的變化存在一定的相關(guān)性。

進(jìn)一步，圖3為2005年3月16日以小時為分析單元、分辨率為分鐘時流量序列的方差對數(shù)、Δα、平均流量對數(shù)及Δf的序列圖。從圖3可以明顯看出，Δα的分布與方差的變化驚人地相似。而從24 h平均流量的對數(shù)圖可以看出，其共有五個低谷，分別是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的波谷出現(xiàn)時間比平均流量對數(shù)波谷要早1 h。如果這種現(xiàn)象是普遍的，則Δf就可以用來預(yù)測流量的變化趨勢。它們之間進(jìn)一步的關(guān)聯(lián)關(guān)系及采用多重分形譜實(shí)現(xiàn)網(wǎng)絡(luò)流量序列的預(yù)測是筆者后續(xù)研究的內(nèi)容。

4結(jié)束語

由于多重分形譜在某些情況下可以描述系統(tǒng)中豐富的突發(fā)信息，是一種描述復(fù)雜系統(tǒng)突發(fā)特性的數(shù)學(xué)方法。本文研究了局域網(wǎng)流量序列的多重分形特征，證實(shí)了在網(wǎng)絡(luò)流量序列中存在局部奇異特性，并進(jìn)一步分析了多重分形譜參數(shù)與網(wǎng)絡(luò)流量序列變化量之間的關(guān)聯(lián)關(guān)系。為進(jìn)一步實(shí)現(xiàn)網(wǎng)絡(luò)流量預(yù)測奠定了理論基礎(chǔ)，對網(wǎng)絡(luò)設(shè)計、性能估計和網(wǎng)絡(luò)協(xié)議的制定等都具有十分重要的意義。

參考文獻(xiàn)：

[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]叢鎖 韓良秀 劉巖 等. 基于離散小波變換的網(wǎng)絡(luò)流量多重分形模型[J]. 通信學(xué)報 2003，24(5):43-48.

[9]孫霞 吳自勤 黃畇. 分形原理及應(yīng)用[M].合肥:中國科學(xué)技術(shù)大學(xué)出版社 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]張濟(jì)忠. 分形[M]. 北京: 清華大學(xué)出版社 1995.