自相似網(wǎng)絡(luò)流量模型研究

摘要：對(duì)自相似網(wǎng)絡(luò)流量模型進(jìn)行了研究分析。綜述了目前國(guó)內(nèi)外在網(wǎng)絡(luò)流量長(zhǎng)相關(guān)特性和自相似網(wǎng)絡(luò)建模以及基于自相似網(wǎng)絡(luò)環(huán)境的擁塞控制機(jī)制研究方面所獲得的主要成果。分析了各種模型的特點(diǎn)，進(jìn)行了分類和評(píng)價(jià)，并對(duì)模型的意義進(jìn)行了初步的探討，提出了有待進(jìn)一步研究的問(wèn)題，對(duì)自相似業(yè)務(wù)相關(guān)研究具有一定的指導(dǎo)意義。

關(guān)鍵詞：網(wǎng)絡(luò)流量模型； 自相似； 長(zhǎng)相關(guān)； 擁塞控制

中圖分類號(hào)：TP393 文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：2095-2163（2013）02-0034-07

0引言

1994年Leland對(duì)Bellcore局域網(wǎng)的測(cè)試與分析成果問(wèn)世以后，大量的業(yè)務(wù)流（如WAN、LAN、VBR及ISDN等）監(jiān)測(cè)和分析相繼表明，計(jì)算機(jī)網(wǎng)絡(luò)上的各種業(yè)務(wù)，均呈現(xiàn)了統(tǒng)計(jì)自相似性（長(zhǎng)相關(guān)性），即網(wǎng)絡(luò)流量的時(shí)間序列存在著突發(fā)性。而作為計(jì)算機(jī)網(wǎng)絡(luò)基礎(chǔ)理論研究的前沿?zé)狳c(diǎn)問(wèn)題之一，網(wǎng)絡(luò)流量統(tǒng)計(jì)分析、網(wǎng)絡(luò)流量建模及網(wǎng)絡(luò)性能評(píng)價(jià)也是現(xiàn)代通信網(wǎng)絡(luò)規(guī)劃與設(shè)計(jì)的基礎(chǔ)。而與其相適應(yīng)，基于自相似業(yè)務(wù)流的數(shù)學(xué)建模和排隊(duì)分析已經(jīng)成為當(dāng)前網(wǎng)絡(luò)性能評(píng)價(jià)和優(yōu)化、流量控制和網(wǎng)絡(luò)構(gòu)建過(guò)程中不可或缺的方案實(shí)現(xiàn)要素，并且對(duì)網(wǎng)絡(luò)規(guī)劃、網(wǎng)絡(luò)控制以及高質(zhì)量的網(wǎng)絡(luò)服務(wù)等方面的優(yōu)勢(shì)設(shè)置也有著重要的理論意義與現(xiàn)實(shí)應(yīng)用價(jià)值。各種具有突發(fā)特性的業(yè)務(wù)源呈現(xiàn)出的自相似特性顯著影響到網(wǎng)絡(luò)的傳輸性能和流量控制策略，例如對(duì)時(shí)延、丟包率、吞吐量等網(wǎng)絡(luò)性能指標(biāo)的直接影響，正使得網(wǎng)絡(luò)的設(shè)計(jì)、控制、分析和管理變得復(fù)雜。因而，只有對(duì)自相似流量下的網(wǎng)絡(luò)性能進(jìn)行正確的分析與評(píng)價(jià)，才能降低流量自相似性所帶來(lái)的不利影響，使網(wǎng)絡(luò)性能得到優(yōu)化。另外，為了能夠給豐富的新型業(yè)務(wù)提供強(qiáng)力支持，在對(duì)網(wǎng)絡(luò)節(jié)點(diǎn)設(shè)備系統(tǒng)進(jìn)行設(shè)計(jì)時(shí)，基于網(wǎng)絡(luò)流量特性的有效性能評(píng)價(jià)將為整個(gè)系統(tǒng)性能指標(biāo)的設(shè)計(jì)提供科學(xué)合理的計(jì)算方法。對(duì)自相似流量下的網(wǎng)絡(luò)性能開展探索研究，則顯得至關(guān)重要。而這也是本文的研究目標(biāo)。下面將展開詳細(xì)的分析與論述。

1自相似基本理論

分形和自相似 （Self-Similar）[1]的概念最早形成于上世紀(jì)中期，源起于美籍法國(guó)數(shù)學(xué)家Mandelbrot對(duì)諸如海岸線長(zhǎng)度，流體中的湍流、對(duì)流等非線性問(wèn)題的研究。具有自相似規(guī)律的不規(guī)則事物稱為分形（Fractals）。依據(jù)分形的自相似特性，分形主要有三類：由迭代函數(shù)系統(tǒng)定義出的精確自相似分形；由遞推關(guān)系式定義出的半自相似分形；由不同尺度下保持統(tǒng)計(jì)測(cè)度的特性定義的統(tǒng)計(jì)自相似分形。三種分形約束依次遞減。統(tǒng)計(jì)自相似最弱，是對(duì)自然分形對(duì)象進(jìn)行定義分析的最基本約束。本文討論的自相似就是統(tǒng)計(jì)自相似，又稱為隨機(jī)自相似。分形的度量稱為分形維數(shù)D，主要有豪斯多夫維數(shù)（Hausdorff Dimension）、計(jì)盒維數(shù)（Box Dimension）和分配維數(shù)等定義方式，描述了分形空間特征。

作為分形的基本特性，自相似指的是復(fù)雜系統(tǒng)的整體與部分，一部分與其他部分之間在精細(xì)結(jié)構(gòu)或性質(zhì)上所具有的相似性。自相似具有伸縮對(duì)稱性，即線性或非線性變換下的不變性，對(duì)分形對(duì)象進(jìn)行放縮或者剪切等操作，只能改變其外部表現(xiàn)形式，而表征自相似特性的參數(shù)即分形維度則不會(huì)有任何變化。可以是在幾何結(jié)構(gòu)與形態(tài)、過(guò)程、信息、功能、屬性和成分等表現(xiàn)形式上，可以是在時(shí)間、空間和數(shù)量等測(cè)度上，也可以是隨機(jī)的、統(tǒng)計(jì)的、復(fù)雜的，但絕不僅僅是簡(jiǎn)單的按比例縮放后的重合。自相似隨機(jī)過(guò)程是平穩(wěn)過(guò)程。自相似性的數(shù)學(xué)表示為：

有些自相似過(guò)程具有長(zhǎng)相關(guān)性，LRD反映了自相似過(guò)程中的持續(xù)現(xiàn)象，意味著未來(lái)的統(tǒng)計(jì)信息蘊(yùn)含在過(guò)去和現(xiàn)在的信息之中，這種信息可以通過(guò)預(yù)測(cè)和估計(jì)實(shí)現(xiàn)和獲得，實(shí)際網(wǎng)絡(luò)流量業(yè)務(wù)的到達(dá)就是長(zhǎng)相關(guān)的。在要求不是很嚴(yán)格的情況下（默認(rèn)1/2

赫斯特系數(shù)[5] 用于描述長(zhǎng)相關(guān)時(shí)間序列的自相關(guān)性（Autocorrelation），用于表征時(shí)間序列是回歸、平均還是聚集等相關(guān)趨勢(shì)，而在分形理論中則表征分形的隨機(jī)程度（Randomness）并直接依賴于分形維度，有H=2-D。H的取值如下：第2期王暉，等：自相似網(wǎng)絡(luò)流量模型研究智能計(jì)算機(jī)與應(yīng)用第3卷

（1）0< H <1/2 表示負(fù)相關(guān)，表征時(shí)間序列中的一個(gè)高值之后是一個(gè)低值的可能性很高，低值之后又可能變?yōu)楦咧担@種高低值的交替的趨勢(shì)很可能持續(xù)一段時(shí)間；

（2）1/2< H <1 為正相關(guān)，表征時(shí)間序列中的一個(gè)高值之后是另外一個(gè)高值的可能性很高，這種維持高值的趨勢(shì)將很可能持續(xù)一段時(shí)間；

（3）H=1/2 表征沒(méi)有相關(guān)性的時(shí)間序列，但是在很小的時(shí)間間隔中可以是正相關(guān)或者負(fù)相關(guān)，自相關(guān)數(shù)絕對(duì)值服從指數(shù)式衰減，不同于正負(fù)相關(guān)的冪定律衰減。

正相關(guān)時(shí)，H 越大，自相似程度越高。H越大，分形維度越小，曲線越粗糙；反之，H越小，分形維度越大，曲線越光滑。如圖1所示。

在信號(hào)系統(tǒng)分析中，常常給出自相似的另外一種定義，是基于時(shí)間序列的。該定義在時(shí)間序列分析和預(yù)測(cè)中會(huì)經(jīng)常用到。自相似的這一定義表述如下。圖1 不同H的分?jǐn)?shù)布朗運(yùn)動(dòng)軌跡

Fig.1 Fractional Brownian motion for different values of the Hurst parameter H給定一個(gè)廣義平穩(wěn)隨機(jī)過(guò)程（時(shí)間序列），X={Xn，n =1，2，…}，對(duì)其進(jìn)行非重疊的順序分塊，分塊長(zhǎng)度是m，得到X（m）n=∑nmi=nm-m+1Xi，n=1，2，3，…，稱為X的聚類（過(guò)程）。如果存在聚類使得，當(dāng)m→∞，D[X（m）n]=m2H-2D[Xn]，1/2

由定義可以看出，隨機(jī)時(shí)間序列的聚類方差按照冪定律衰減，且衰減速率是-1<2H-2<0，將其稱為聚類具有慢衰減方差（Slow Decaying Variance）。和泊松過(guò)程相比，該衰減較慢，泊松過(guò)程的聚類方差有D[N（m）n]=m-1D[Nn]。現(xiàn)在已經(jīng)知道方差可以描述時(shí)間序列的波動(dòng)性，也就是可以粗略描述業(yè)務(wù)流的突發(fā)性。因此，可以斷定自相似業(yè)務(wù)流的突發(fā)性比泊松過(guò)程突發(fā)性大。這就解釋了為什么自相似過(guò)程即使在很大的時(shí)間單位下也會(huì)保持震蕩，而泊松過(guò)程卻趨于平滑，也從另一個(gè)角度展現(xiàn)了統(tǒng)計(jì)自相似不隨時(shí)間尺度的變化而變化的獨(dú)有特性。

2網(wǎng)絡(luò)流量模型

分析網(wǎng)絡(luò)流量特征是探索網(wǎng)絡(luò)的第一步，有助于根據(jù)網(wǎng)絡(luò)特征設(shè)計(jì)合理的擁塞控制策略，也有利于完善進(jìn)一步的網(wǎng)絡(luò)仿真實(shí)驗(yàn)。

根據(jù)分析粒度不同，網(wǎng)絡(luò)流量分析可分為以下幾類[6]：

（1）位級(jí)（bit），主要分析網(wǎng)絡(luò)流量的數(shù)據(jù)特征，如鏈路傳輸速率，吞吐量等；

（2）包級(jí)（packet），主要分析IP 分組的到達(dá)、延遲、亂序和丟包等；

（3）流級(jí)（traffic），主要分析流的到達(dá)過(guò)程、到達(dá)間隔及其統(tǒng)計(jì)特征；

（4）應(yīng)用級(jí)（application），主要基于網(wǎng)絡(luò)應(yīng)用提供的服務(wù)使用情況，搜集和分析網(wǎng)民行為和網(wǎng)絡(luò)經(jīng)濟(jì)收益，如網(wǎng)絡(luò)視頻收視、網(wǎng)絡(luò)廣告投放和網(wǎng)絡(luò)搜索等信息，主要用于經(jīng)濟(jì)領(lǐng)域。

在科研領(lǐng)域，流級(jí)流量分析研究為主導(dǎo)。網(wǎng)絡(luò)流量測(cè)量技術(shù)主要有兩種：

（1）被動(dòng)嗅探式，不注入數(shù)據(jù)包、精度高、耗費(fèi)資源，諸如TcpDump、WinDump和WinPCap等；

（2）基于SNMP參數(shù)測(cè)量，主動(dòng)發(fā)送數(shù)據(jù)包、精度低、且可擴(kuò)展性高。

網(wǎng)絡(luò)流量模型（Traffic Model）是網(wǎng)絡(luò)流量統(tǒng)計(jì)特征的研究工具。通常，采用時(shí)間序列表示某個(gè)特定時(shí)間或時(shí)間間隔內(nèi)到達(dá)的數(shù)據(jù)包數(shù)量，流量則為該時(shí)間段內(nèi)的平均值。用數(shù)學(xué)語(yǔ)言來(lái)描述即可，在時(shí)間點(diǎn)上的一個(gè)觀測(cè)值序列表示流量，這個(gè)觀測(cè)值序列的時(shí)間尺度可以是毫秒、秒、分鐘、小時(shí)等，流量的單位一般是字節(jié)每秒（B/s）。網(wǎng)絡(luò)流量模型一直以來(lái)就倍受學(xué)者關(guān)注，各類相關(guān)模型都已很多。按照網(wǎng)絡(luò)流量相關(guān)性特點(diǎn)可以分為短相關(guān)流量模型和長(zhǎng)相關(guān)流量模型兩大類。短相關(guān)流量模型的自相關(guān)函數(shù)隨時(shí)間間隔的增加呈指數(shù)衰減。長(zhǎng)相關(guān)流量模型的自相關(guān)函數(shù)則隨時(shí)間間隔的增加呈冪定律收斂，而且比指數(shù)衰減要慢。

近年來(lái)，研究發(fā)現(xiàn)局域網(wǎng)和廣域網(wǎng)的流量都呈現(xiàn)統(tǒng)計(jì)自相似特征。這種特性就決定了自相似業(yè)務(wù)流模型已經(jīng)成為模擬實(shí)際網(wǎng)絡(luò)流量的主要手段，有關(guān)這方面的研究較多，目前主要有兩類[7]：物理模型和統(tǒng)計(jì)模型。物理模型的建立基于自相似過(guò)程的物理意義，對(duì)于自相似的成因和特點(diǎn)有較強(qiáng)的表現(xiàn)力，使用頻度較高的物理模型是流疊加法的ON/OFF模型[8]、TES模型[9]、α-Stable業(yè)務(wù)流模型[10]；統(tǒng)計(jì)模型的建立則基于長(zhǎng)相關(guān)性隨機(jī)過(guò)程，形式靈活，精度較高，常用的統(tǒng)計(jì)模型有FARIMA模型[11]、分形高斯噪聲模型（Fractional Gaussian Noise FGN）[12]、基于小波變換或馬拉特（Mallat）模型、基于混沌映射的確定性模型、散粒噪聲模型等，甚至是多重分形[13]。這類模型能很好地說(shuō)明網(wǎng)絡(luò)通信量中出現(xiàn)的長(zhǎng)相關(guān)和重尾等現(xiàn)象，但對(duì)于瞬時(shí)性能的評(píng)估卻非常困難。除前面介紹的流量模型外，目前已在研究的模型還有，漏桶模型、瀑布模型[14]、季節(jié)性神經(jīng)網(wǎng)絡(luò)流量模型等。其中，漏桶模型比較適合于特定網(wǎng)絡(luò)應(yīng)用流量的分析。例如，VBR的多媒體模型[15]。但是，該模型難以反映網(wǎng)絡(luò)流量實(shí)際變化中的突發(fā)特性，尤其是混合流的特性。

3網(wǎng)絡(luò)自相似流量

因特網(wǎng)業(yè)務(wù)流量由響應(yīng)業(yè)務(wù)流量（即TCP長(zhǎng)流，Long Lived TCP Flows）和非響應(yīng)業(yè)務(wù)流量（即UDP流和TCP短流，Short Lived TCP Flows）構(gòu)成。有研究表明，Internet流量主要由TCP短流（如Web流量，HTTP應(yīng)用）構(gòu)成[17]；TCP短流使得平均隊(duì)列深度都表現(xiàn)出了類指數(shù)的特性。由此可知，應(yīng)將短流的隊(duì)列行為構(gòu)設(shè)進(jìn)入網(wǎng)絡(luò)設(shè)計(jì)時(shí)的決策范疇[18]。2008年，IResearch咨詢公司通過(guò)Cisco System 提供的數(shù)據(jù)統(tǒng)計(jì)結(jié)果表明， P2P和在線視頻服務(wù)流量已經(jīng)超過(guò)了網(wǎng)頁(yè)瀏覽、電子郵件這些傳統(tǒng)的網(wǎng)絡(luò)服務(wù)， 正在占用越來(lái)越多的網(wǎng)絡(luò)帶寬。以2008年為例， 在線視頻（ 包括PC 和電視終端） 和P2P流媒體產(chǎn)生的數(shù)據(jù)流量已經(jīng)占據(jù)全球互聯(lián)網(wǎng)總流量的75. 9%，達(dá)到4 034 PB， 而當(dāng)初預(yù)計(jì)到2012 年，這一數(shù)字將會(huì)繼續(xù)上升至81.2%。另外，對(duì)等網(wǎng)（Peer-to-Peer，P2P）技術(shù)應(yīng)用呈現(xiàn)了空前繁榮，如文件共享、協(xié)同計(jì)算、流媒體、IP-TV、VoIP語(yǔ)音視頻通信及在線游戲等應(yīng)用的陸續(xù)出現(xiàn)。基于實(shí)時(shí)性考慮，這些新興應(yīng)用協(xié)議多選擇UDP作為其底層的傳輸協(xié)議，使得UDP流量呈上升趨勢(shì)[19]。有研究分析可得，大概有30%-70%的網(wǎng)絡(luò)流量產(chǎn)生于這種技術(shù)。而該技術(shù)又無(wú)疑帶來(lái)日益增多的非響應(yīng)業(yè)務(wù)流量（主要是UDP流）。因此則勢(shì)必給網(wǎng)絡(luò)流量的穩(wěn)定性帶來(lái)影響，而且也必將使路由器的排隊(duì)性能面臨嚴(yán)峻挑戰(zhàn)。同時(shí)，文獻(xiàn)[20]中基于對(duì)Internet 城域出口鏈路流量的準(zhǔn)確測(cè)量，又一次提到了網(wǎng)絡(luò)流量的短相關(guān)性不再明確，由此對(duì)于利用控制理論和排隊(duì)理論開展AQM算法的性能分析制造了一定難度。

1994年，Leland等人發(fā)現(xiàn)了Bellcore的局域網(wǎng)網(wǎng)絡(luò)流量具有自相似特性[21]，開啟了自相似網(wǎng)絡(luò)流量的研究進(jìn)程。此后，Paxson[22] ， Crovella[28]等人分別驗(yàn)證了泊松采樣測(cè)量的失效，表明網(wǎng)絡(luò)流量具有廣泛的統(tǒng)計(jì)自相似特性（Self-similar），從而詮釋了馬爾科夫鏈和泊松過(guò)程等短相關(guān)模型已不具說(shuō)明功效的網(wǎng)絡(luò)現(xiàn)象。其中的廣泛性是指網(wǎng)絡(luò)流量的時(shí)間序列在不同的時(shí)間尺度（毫秒～小時(shí)）上都存在著突發(fā)性。無(wú)論網(wǎng)絡(luò)的規(guī)模、拓?fù)洹?yīng)用、編碼、傳輸介質(zhì)如何變化，這種突發(fā)性始終存在。從某種意義來(lái)說(shuō)，網(wǎng)絡(luò)流量的突發(fā)性就是自相似特性的具體表現(xiàn)。而網(wǎng)絡(luò)流量的自相似性質(zhì)的發(fā)現(xiàn)，則成為網(wǎng)絡(luò)測(cè)量領(lǐng)域和網(wǎng)絡(luò)行為辨識(shí)方面的一個(gè)里程碑似的重大突破。其后，多種自相似模型相繼引入，更新和拓展了人們有關(guān)網(wǎng)絡(luò)流量特征的認(rèn)識(shí)。自Taqqu等人提出實(shí)際網(wǎng)絡(luò)流量呈現(xiàn)復(fù)雜的多重自相似[23]的理論后，基于網(wǎng)絡(luò)多重自相似特征的研究已經(jīng)日漸涌現(xiàn)[24-26]，多重分形（Multifractal）業(yè)務(wù)流可以看成是多個(gè)基于不同網(wǎng)絡(luò)應(yīng)用的單分形業(yè)務(wù)流的合成和疊加。基于時(shí)間尺度對(duì)網(wǎng)絡(luò)流量自相似的分析過(guò)程已變得越來(lái)越復(fù)雜，文獻(xiàn)[27]就提出一種基于行為尺度的自相似，相關(guān)實(shí)驗(yàn)表明，在P2P業(yè)務(wù)流中存在時(shí)間尺度上的多重自相似，雖然簡(jiǎn)單的自相似無(wú)法描述，卻存在較完美的行為自相似，即基于網(wǎng)絡(luò)應(yīng)用角度的網(wǎng)絡(luò)行為（不同數(shù)據(jù)包收發(fā)粒度）的自相似。目前，已將基于多重分形的網(wǎng)絡(luò)流量建模和網(wǎng)絡(luò)性能評(píng)價(jià)確定為自相似網(wǎng)絡(luò)的研究方向。

4網(wǎng)絡(luò)流量自相似性成因

關(guān)于網(wǎng)絡(luò)流量自相似的成因，當(dāng)前的解釋很多。大致可以歸納為兩個(gè)：網(wǎng)絡(luò)文件的重尾分布[8，23，28-29] 和TCP的擁塞控制機(jī)制[30-31]。

Willinger等人認(rèn)為計(jì)算機(jī)網(wǎng)絡(luò)文件大小服從重尾分布是導(dǎo)致網(wǎng)絡(luò)流量自相似性的主要原因。首先，可以把網(wǎng)絡(luò)中端到端的鏈接看做是一個(gè)ON/OFF源，其中，ON對(duì)應(yīng)有數(shù)據(jù)包發(fā)送，為鏈接忙時(shí)間，OFF對(duì)應(yīng)無(wú)數(shù)據(jù)包發(fā)送，為鏈接閑時(shí)間，在網(wǎng)絡(luò)流量足夠大，網(wǎng)絡(luò)鏈接足夠多時(shí)，可認(rèn)為這些ON/OFF源是獨(dú)立同分布的；又由于忙時(shí)間和閑時(shí)間的持續(xù)都可能很長(zhǎng)，且難以忽略，即呈現(xiàn)“Noah”效應(yīng)，從而可以用重尾分布描述這些時(shí)間間隔。其次，Web文件（或者視頻流文件）大小的分布（包括用戶請(qǐng)求的文件、實(shí)際傳輸?shù)奈募⒎?wù)器端存儲(chǔ)的文件等）服從重尾分布，使得網(wǎng)絡(luò)傳輸時(shí)間具有無(wú)限方差，即服從重尾分布，從而導(dǎo)致整個(gè)鏈路層上的自相似；用戶的想時(shí)間（think time）的重尾分布進(jìn)一步導(dǎo)致了網(wǎng)絡(luò)空閑時(shí)間服從重尾分布，并且ON狀態(tài)比OFF狀態(tài)還要重尾。大量重尾分布的ON/OFF源的聚合就產(chǎn)生了自相似性。最后，可靠的傳輸機(jī)制和流量控制機(jī)制又保留了由文件大小重尾分布所引發(fā)的長(zhǎng)相關(guān)性——注意無(wú)流量控制和不可靠的UDP并未使得生成的流量具有長(zhǎng)相關(guān)性。況且對(duì)流量自相似的估計(jì)并不因網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)變化而改變，或者說(shuō)自相似網(wǎng)絡(luò)流量經(jīng)過(guò)網(wǎng)關(guān)路由的轉(zhuǎn)發(fā)處理并不能削弱自相似性。一個(gè)自相似過(guò)程的分支仍然是自相似的，若干個(gè)自相似過(guò)程的聚合也仍然是自相似的。網(wǎng)絡(luò)業(yè)務(wù)流一直存在自相似性，不僅不會(huì)隨著業(yè)務(wù)的聚合和分支而削弱，反而自相似系數(shù)還會(huì)增大，并使得自相似統(tǒng)計(jì)特征變得愈加復(fù)雜，由此產(chǎn)生了多重自相似。

Veres等人認(rèn)為，TCP的擁塞控制機(jī)制亦是流量自相似特性的可能成因。文件的可靠性傳輸，也就是重傳機(jī)制（Retransmission），即使改變其參數(shù)，如緩存大小、重傳預(yù)定的次數(shù)和超時(shí)時(shí)限，也不能改變重傳負(fù)載的自相似特性；同時(shí)，也并不隨著網(wǎng)絡(luò)源、拓?fù)洹I(yè)務(wù)流匯聚和到達(dá)間隔時(shí)間分布的變化而變化；此外，還存在著傳輸層流量控制機(jī)制和可靠傳輸對(duì)網(wǎng)絡(luò)流量的整形。當(dāng)時(shí)間尺度超過(guò)10倍的數(shù)據(jù)包傳輸時(shí)間，重傳數(shù)據(jù)包流量的方差將在總的流量（新數(shù)據(jù)包、重傳數(shù)據(jù)包和丟失的數(shù)據(jù)包）中占據(jù)絕對(duì)優(yōu)勢(shì)成分，這就意味著極大的突發(fā)性，從而在某種程度上使得單個(gè)的TCP流量符合漸進(jìn)自相似（H>0.5）。雖然在瓶頸緩存處堆疊的TCP流量是短時(shí)相關(guān)的（H≈0.5），但TCP擁塞控制可使瓶頸緩存占用率最大來(lái)平滑流量，堆疊的流量得到平滑，并在TCP擁塞控制和具有重尾特性的上層協(xié)議的共同作用下，使得堆疊的網(wǎng)絡(luò)流量仍然顯現(xiàn)了長(zhǎng)相關(guān)性。TCP擁塞控制中包括著混沌特性，諸如：非線性（Nonlinearity）、確定性（Determinism）、混亂中的有序（Order in disorder）、對(duì)初始狀態(tài)的敏感性（蝴蝶效應(yīng)）（Sensitivity to initial conditions or the “butterfly effect”）、不可預(yù)見(jiàn)性（Unpredictability）。系統(tǒng)在特定的參數(shù)下產(chǎn)生自相似時(shí)間序列，從周期性到產(chǎn)生明顯的混沌現(xiàn)象：對(duì)初值敏感，流量在廣泛范圍內(nèi)具有自相似性，甚至是多重分形。周期性是由于流量數(shù)據(jù)的周期采集而引起，或者是由人們上網(wǎng)的行為習(xí)慣所引起。混沌性完全從網(wǎng)絡(luò)流量自相似的頻譜角度而進(jìn)行更為完全的解釋。由此得出，TCP本身就是一個(gè)產(chǎn)生自相似結(jié)果的確定性過(guò)程。

5自相似網(wǎng)絡(luò)流量的仿真和生成

5.1赫斯特指數(shù)估計(jì)

Hurst指數(shù)估算有很多方法，可分為時(shí)域和頻域兩類，較為常用的有重標(biāo)極差（Rescaled Range，R/S）分析法[32-33]、方差時(shí)間圖（Variance Time Graph，VT-G）法[34]、留數(shù)法（Variance of Residuals，Res）[35]和絕對(duì)值法（Absolute Moment，Abs）[36]等時(shí)域算法；以及Whittle法[37]、小波基（Wavelet-transform Based，WB）法[38]和周期圖法（Pariodogram Graph，PG）[39]等頻域算法。其中，各算法的時(shí)間復(fù)雜度分別是： R/S法、Res法和Whittle法的結(jié)果為O（N2），WB法和PG法為O（Nlog（N）），而VT-G法和Abs法則為O（N2）[36]。文獻(xiàn)[40]對(duì)這幾種常見(jiàn)的算法進(jìn)行了分析比較，并給出了各算法的時(shí)間復(fù)雜度；同時(shí)，進(jìn)一步指出VT-G法、Abs法等聚類方差法（Aggregated Variance）[41]，計(jì)算速度較快，結(jié)果相近；PG法在實(shí)現(xiàn)時(shí)可借助快速傅利葉變換來(lái)提高算法的速度；Res法和R/S法的速度相對(duì)較慢，但結(jié)果精度則相對(duì)較高；小波法雖然速度較快，實(shí)現(xiàn)過(guò)程卻相當(dāng)復(fù)雜。當(dāng)H>0. 80以后，對(duì)FGN序列的時(shí)域方法估計(jì)值將失準(zhǔn)且偏低，但頻域方法估計(jì)值卻仍能保持較高精度。文獻(xiàn)[42]中，通過(guò)一系列實(shí)驗(yàn)也指出，時(shí)域類的方法性能全部都要低于頻域類算法。而在頻域類算法中，Whittle法的精度最高。文獻(xiàn)[43]還指出，在人工合成數(shù)據(jù)序列下，各估算算法均表現(xiàn)良好，但在真實(shí)數(shù)據(jù)流的情況下，算法準(zhǔn)確度卻集體下降，這可能和真實(shí)數(shù)據(jù)的多重分形特性有關(guān)；另外，在突發(fā)噪聲干擾下，對(duì)時(shí)域類算法的精度影響較大，而對(duì)頻域類則具有較好的魯棒性，加入現(xiàn)有濾波器技術(shù)也不能有效改進(jìn)算法的精確度；建議研究者們避免采用單一算法，導(dǎo)出相應(yīng)結(jié)論。目前，國(guó)內(nèi)提出的最新計(jì)算方法主要有滑窗時(shí)變方差之差法[44]、局部Whittle法[45]、基于混合FBM的二次變差矩估計(jì)法，而國(guó)外提出的最新計(jì)算方法則有最大似然估計(jì)法（Maximum Likelihood）[46]、基于小波的變方差（Time-Varying）法[47]和基于FBM的錐多元自適應(yīng)回歸曲線法（Conic Multivariate Adaptive Regression Splines，CMARS）[48]。綜上所述，時(shí)域算法大部分是通過(guò)作圖估計(jì)H，精確度普遍不高，且需要較大樣本空間（一般大于10 000）；頻域算法則只需要很小的采樣序列即可，而且精度較高。

限于篇幅，此處僅粗略描述兩個(gè)算法，以供諸位研究同仁參詳與考量所用。具體內(nèi)容如下。

首先，介紹一下最簡(jiǎn)單的算法VT-G法。給定一個(gè)時(shí)間序列X={Xn，n =1，2，…}， VT-G法主要是利用公式D[Xmn]～m-βD[Xn]，m→∞計(jì)算聚類方差，以此描繪得到方差的log坐標(biāo)系圖線，其擬合直線斜率即為-β，0<β<1，進(jìn)而求得H=1-β/2。有時(shí)候也可用β來(lái)描述自相似程度。

然后，是應(yīng)用最為廣泛的R/S法。給定一個(gè)時(shí)間序列X={Xn，n =1，2，…}計(jì)算重標(biāo)極差序列如（4）所示，并計(jì)算重標(biāo)極差期望E[R（n）/S（n）]。Wallis已證明當(dāng)t趨于無(wú)窮大時(shí)，E[（R/S）t]～C*tH。依據(jù)冪定律擬合數(shù)據(jù)估算Hurst系數(shù)。實(shí)際操作時(shí)，可以在log-log象限中作出重標(biāo)極差期望的時(shí)間曲線，其擬合直線的斜率即是H。

5.2分形高斯噪聲

在已有的流量模型中，分形布朗運(yùn)動(dòng)（FBM）模型是最簡(jiǎn)單、最易于求解的自相似業(yè)務(wù)流模型。由于分形高斯噪聲（FGN）是FBM的增量過(guò)程，故常常使用FGN生成FBM流量[49]。通過(guò)利用分形高斯噪聲合成近似分形布朗運(yùn)動(dòng)網(wǎng)絡(luò)業(yè)務(wù)流的快速技術(shù)主要有[50]：隨機(jī)中點(diǎn)置位法（Random Midpoint Displacement），連續(xù)隨機(jī)添加法（Successive Random Additions）和浮動(dòng)比例法（Floating Proportionality）。更多關(guān)于分形的生成算法可參見(jiàn)文獻(xiàn)[51]。近年來(lái)，還有一些其他生成自相似網(wǎng)絡(luò)業(yè)務(wù)流的方法，諸如基于一般化柯西過(guò)程（Generalized Cauchy Process）的模型[52]。

當(dāng)今，采用一種基于循環(huán)嵌入法（Circulant Embedding Approach，CEA）[53]的快速傅里葉變換（Fast Fourier Transform，F(xiàn)FT）[54]方法來(lái)生成FBM業(yè)務(wù)流，則是一種最快的算法。Perrin在文獻(xiàn)[55]中已經(jīng)驗(yàn)證了CEA算法生成分形高斯噪聲是一種最優(yōu)方案。考察不同的H生成的FBM，可知H越大，分形維度越小，生成曲線越光滑。生成曲線效果如圖1所示。

6展望

目前，自相似網(wǎng)絡(luò)流量研究主要有三個(gè)方面：分析網(wǎng)絡(luò)流量的統(tǒng)計(jì)特征并實(shí)現(xiàn)建模，包括“可信的”網(wǎng)絡(luò)流量生成模型[56-57]和“可靠的”網(wǎng)絡(luò)流量預(yù)測(cè)模型的構(gòu)建[58-59]。其中，小波基（Wavelet Based）分形理論[60-61]和多重分形（Multifractal）模型[62-63，]成為難點(diǎn)和趨勢(shì)；基于自相似網(wǎng)絡(luò)模型評(píng)估自相似流量對(duì)不同網(wǎng)絡(luò)的各種性能影響[64-65]；網(wǎng)絡(luò)自相似或者長(zhǎng)相關(guān)的成因[66-67]。自相似網(wǎng)絡(luò)諸多問(wèn)題還末得到徹底解決，很多問(wèn)題尚處于討論階段，研究成果分散繁雜，也沒(méi)有形成較為一致、清晰、且完整的體系，亟需進(jìn)一步投入，加大研究發(fā)展力度。到目前為止，也還沒(méi)有取得一個(gè)統(tǒng)一的、公認(rèn)的數(shù)學(xué)模型來(lái)描述自相似網(wǎng)絡(luò)流量。

7結(jié)束語(yǔ)

本文從分形和自相似理論基礎(chǔ)引入，主要介紹了網(wǎng)絡(luò)流量的自相似特征以及形成原因；為了更深刻地認(rèn)識(shí)網(wǎng)絡(luò)流量特征，進(jìn)一步介紹了常用的網(wǎng)絡(luò)流量模型；最后對(duì)自相似業(yè)務(wù)流量的合成在Matlab中進(jìn)行了仿真實(shí)現(xiàn)。借助本文，相信能對(duì)網(wǎng)絡(luò)自相似形成了一個(gè)較為系統(tǒng)的認(rèn)識(shí)。

參考文獻(xiàn)：

[1]MANDELBROT B. How long is the coast of Britain？ statistical self-similarity and fractional dimension [J]. Science， 1967， 156（3775）： 636-638.

[2]KARAGIANNIS T， MOLLE M， FALOUTSOS M. Long-range dependence： ten years of Internet traffi c modeling. IEEE Internet Computing， 2004， 8： 57-64.

[3]SAMORODNISKY G. Long range dependence [J]. Foundations and Trendsr in Stochastic Systems， 2007， 1（3）： 163-257.

[4]SAMORODNITSKY G. Long range dependence， heavy tails and rare events [M]. Mathematical Physics and Stochastics， 2002.

[5]HURST H E. Long-term storage of reservoirs： an experimental study [J]. Transactions of the American Society of Civil Engineers， 1951， 116： 770-799.

[6]熊剛， 孟姣， 方濱興，等. 網(wǎng)絡(luò)流量分類研究進(jìn)展與展望[J]. 集成技術(shù)， 2012， 1（1）： 32-42.

[7]吳援明， 寧正容， 梁恩志. 網(wǎng)絡(luò)自相似模型業(yè)務(wù)進(jìn)展[J]. 通信學(xué)報(bào)，2004， 25（3）： 97-104.

[8]WILLINGER W， TAQQU M S， SHERMAN R， et al. Self-similarity through high-variability： statistical analysis of Ethernet LAN traffic at the source level[J]. Networking， IEEE/ACM Transactions on， 1997， 5（1）： 71-86.

[9]JAGERMAN D L， MELAMED B. The transition and autocorrelation structure of TES processes[J]. Stochastic Models， 1992， 8（2）： 193-219.

[10]潘明， 季曉飛， 范戈. 基于α-Stable自相似隨機(jī)過(guò)程的通信網(wǎng)業(yè)務(wù)量建模[J]. 上海交通大學(xué)學(xué)報(bào)， 2004， 38（2）： 200-202， 206.

[11]張連芳， 薛飛，王雷，等. 自相似網(wǎng)絡(luò)業(yè)務(wù)的一個(gè) FARIMA 模型[J]. 計(jì)算機(jī)研究與發(fā)展， 2000， 37（9）： 1138-1144.

[12]LAU W C， ERRAMILLI A， WANG J L， et al. Self-similar traffic generation： The random midpoint displacement algorithm and its properties[C]//Communications， 1995. ICC'95 Seattle，'Gateway to Globalization'， 1995 IEEE International Conference on. IEEE， 1995， 1： 466-472.

[13]TAQQU M S， TEVEROVSKY V， WILLINGER W. Is network traffic self-similar or multifractal？[J]. Fractals， 1997， 5（1）： 63-73.

[14]GAO J， RUBIN I. Multiplicative multifractal modelling of long‐range‐dependent network traffic[J]. International Journal of Communication Systems， 2001， 14（8）： 783-801.

[15]GARRETT M W， WILLINGER W. Analysis， modeling and generation of self-similar VBR video traffic[C]//ACM SIGCOMM Computer Communication Review. ACM， 1994， 24（4）： 269-280.

[16]NORROS I. On the use of fractional Brownian motion in the theory of connectionless networks[J]. Selected Areas in Communications， IEEE Journal on， 1995， 13（6）： 953-962.

[17]BROWNLEE N. Understanding Internet traffic streams： dragonflies and tortoises[J]. IEEE Communications Magazine， 2002， 40（10）： 110-117.

[18]周林， 孫衛(wèi)強(qiáng)， 胡衛(wèi)生. TCP 短流對(duì)擁塞點(diǎn)隊(duì)列深度影響的分析[J]. 廣西大學(xué)學(xué)報(bào)： 自然科學(xué)版，2012， 37（6）： 1177-1180.

[19]張藝瀕， 張志斌， 趙詠， 等. TCP與UDP網(wǎng)絡(luò)流量對(duì)比分析研究[J]. 計(jì)算機(jī)應(yīng)用研究， 2010， 6： 2192-2197.

[20]張廣興 ， 張大方 ， 謝高崗 ， 等. Internet 城域出口鏈路流量測(cè)量與特征分析[J]. 電子學(xué)報(bào)，2007（11） ： 2092-2097.

[21]LELAND W E， TAQQU M S， BELLCORE W W. On the self-similar nature of ethernet traffic [J]. IEEE/ACM Transaction on Networking，1994， 2（1）： 1-15.

[22]PAXSON V， FLOYD S. Wide-Area Traffic： the failure of poisson modeling [J]. IEEE/ACM Transactions on Networking， 1995， 3（3）： 226-244.

[23]TAQQU M S， WILLINGER W， SHERMAN R. Proof of a fundamental result in self-similar traffic modeling[J]. ACM SIGCOMM Computer Communication Review， 1997， 27（2）： 5-23.

[24]MATSUDA T， YAMAMOTO M. Influences of TCP congestion control mechanisms to multi-fractal nature of generated traffic[C]//Global Telecommunications Conference， 2003. GLOBECOM'03. IEEE. IEEE， 2003， 7： 3658-3662.

[25]FIEDLER M， CARLSSON P， NILSSON A. Voice and mufti-fractal data in the Internet[C]//Local Computer Networks 2001 Proceedings. 26th Annual IEEE Conference on Local Computer Networks， 2001：426-431.

[26]HIROKI D， MATSUDA T. YAMAMOTO M. Performance evaluation of mufti-fractal nature of TCP traffic with RED gateway[C]//Local Computer Networks 2004 Proceedings. 29th Annual IEEE International Conference on Local Computer Networks， 2004： 400-401.

[27]李銳. IP網(wǎng)業(yè)務(wù)識(shí)別關(guān)鍵技術(shù)研究[D]. 北京：北京郵電大學(xué)， 2010.

[28]CROVELLA M E， BESTAVROS A. Self-similarity in World Wide Web traffic： evidence and possible causes[J]. Networking， IEEE/ACM Transactions on， 1997， 5（6）： 835-846.

[29]SHI J， ZHU H.. Merging and splitting self-similar traffic[C]//5th Aisa-Pacific Conference on Conmmunications， 1999， （1）： 110-114.

[30]VERES A， BODA M. The chaotic nature of TCP congestion control[C]//INFOCOM 2000. Nineteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings. IEEE. IEEE，Tel Aviv， Israel， 2000， 3： 1715-1723.

[31]PARK K， KIM G， CROVELLA M. On the relationship between file sizes， transport protocols， and self-similar network traffic[C]//Network Protocols， 1996. Proceedings.， 1996 International Conference on. IEEE， 1996： 171-180.

[32]MANDELBROT B B， WALLIS J R. Computer experiments with fractional Gaussian noises： Part 2， rescaled ranges and spectra[J]. Water resources research， 1969， 5（1）： 242-259.

[33]QIAN B， RASHEED K. Hurst exponent and financial market predictability [C]//IASTED Conference on Financial Engineering and Applications （FEA） 2004， Cambridge， Massachusetts， USA， 2004：203-209.

[34]COX D， LEWIS P. The statistical analysis of series of events [M]. Sottiswoode， BallantyneCo. Ltd.， UK，1966.

[35]PENG C K， BULDYREV S V， HAVLIN S， et al. Mosaic organization of DNA nucleotides[J]. Physical Review E， 1994， 49（2）： 1685.

[36]TAQQU M S， TEVEROVSKY V， WILLINGER W. Estimators for long-range dependence： an empirical study[J]. Fractals， 1995， 3（4）： 785-798.

[37]WILLINGER W， TAQQU M S， LELAND W E， et al. Self-similarity in high-speed packet traffic： analysis and modeling of Ethernet traffic measurements[J]. Statistical science， 1995， 10（1）： 67-85.

[38]VEITCH D， ABRY P. A wavelet-based joint estimator of the parameters of long-range dependence[J]. Information Theory， IEEE Transactions on， 1999， 45（3）： 878-897.

[39]GEWEKE J， PORTER-HUDAK S. The estimation and application of long memory time series models[J]. Journal of time series analysis， 1983， 4（4）： 221-238.

[40]陳建， 譚獻(xiàn)海， 賈真. 7種 Hurst系數(shù)估計(jì)算法的性能分析[J]. 計(jì)算機(jī)應(yīng)用， 2006， 26（4）： 945-950.

[41]BERAN J. Statistics for long-memory processes[M]. Chapman and Hall， NewYork， 1994.

[42]JEONG H， MCNICKLE D， PAWLIKOWSKI K. Comparison of various estimators of Hurst parameter in simulated FGN[R]. Department of Computer Science and Software Engineering， University of Canterbury， 2006.

[43]CLEGG R G. A practical guide to measuring the Hurst parameter[J]. arXiv preprint math/0610756， 2006.

[44]張 博， 汪斌強(qiáng)， 智英建. 長(zhǎng)相關(guān)網(wǎng)絡(luò)流量 Hurst 指數(shù)估計(jì)算法[J]. 計(jì)算機(jī)工程， 2009， 35（2）：83-85.

[45]胡宏偉， 徐海燕. 基于局部 Whittle法的長(zhǎng)記憶參數(shù)及變點(diǎn)估計(jì)[J]. 合肥學(xué)院學(xué)報(bào)， 2011， 21（2）：1-5.

[46]CLAUSET A， SHALIZI C R， NEWMAN M E J. Power-law distributions in empirical data[J]. SIAM review， 2009， 51（4）： 661-703.

[47]ZHIPING L， QINYING T. Time-varying long memory parameter estimation based on Wavelets[J]. 應(yīng)用概率統(tǒng)計(jì)， 2012， 28（5）.

[48]OZKURT F Y， ACAR C V， OKUR Y Y， et al. Estimation of Hurst parameter of fractional Brownian motion using CMARS method[J]. arXiv preprint arXiv：1302.3438， 2013.

[49]PAXSON V. Fast， approximate synthesis of fractional Gaussian noise for generating self-similar network traffic [J]. ACM SIGCOMM Computer Communication Review， 1997， 27（5）： 5-18.

[50]GEIST R， WESTALL J， SPICER K. Simulation modeling of self-similarity in network traffic[J]. Proceedings of CMG’99， 1999.

[51]SAUPE D. Algorithms for random fractals [J]. The science of fractal images， 1988： 71-136.

[52]LI MING. Generation of teletraffic of generalized Cauchy type [J]. Physica Scripta， 2010， 81（2）：1-10.

[53]DIETRICH C R， NEWSAM G N. Fast and exact simulation of stationary Gaussian processes through circulant embedding of the covariance matrix [J]. SIAM Journal on Scientific Computing， 1997， 18（4）： 1088-1107.

[54]KROESE D P， BOTEV Z I. Spatial process generation. SCHIMIDT V （Ed.）. Lectures on stochastic geometry， spatial statistics and random fields， Volume II： Analysis， Modeling and Simulation of Complex Structures， Springer-Verlag， Berlin. 2012： 1-41. Weblink：http：//www.maths.uq.edu.au/～kroese/ps/MCSpatial.pdf

[55]PERRIN E， HARBA R， JENNANE R， et al. Fast and exact synthesis for 1-D fractional Brownian motion and fractional Gaussian noises[J]. Signal Processing Letters， IEEE， 2002， 9（11）： 382-384.

[56]CHA′VEZ H I L， MONROY M A A. Generation of LRD traffic traces with given sample statistics[C]//Engineering Applications （WEA）， 2012 Workshop on. IEEE， 2012： 1-6.

[57]HASHEMIAN R， KRISHNAMURTHY D， ARLITT M. Web workload generation challenges–an empirical investigation[J]. Software： Practice and Experience， 2012， 42（5）： 629-647.

[58]ZHOU D， CHEN S， DONG S. Network traffic prediction based on ARFIMA model[J]. arXiv preprint arXiv：1302.6324， 2013.

[59]VAUGHAN J， STOEV S， MICHAILIDIS G. Network–wide statistical modeling， prediction and monitoring of computer traffic[J]. Technometrics， 2012.

[60]ZHAO H， ANSARI N. Wavelet transform-based network traffic prediction： a fast on-line approach[J]. Journal of Computing and Information Technology， 2012， 20（1）： 15-25.

[61]LI M X， MENG X R， YUAN R K， et al. Online prediction of network traffic by integrating lifting wavelet de-noising and LSSVM[J]. Journal of Computer Applications， 2012， 2： 10.

[62]GOSPODINOVA E， GOSPODINOV M. Fractal and multifractal analysis of network teletraffic[C]//Proceedings of the 13th International Conference on Computer Systems and Technologies. ACM， 2012： 224-231.

[63]DE GODOY STE^NICO J W， LING L L. Multifractal nature of wireless network traffic[C]//Proceedings of the 2012 SpringSim Poster Work-In-Progress Track. Society for Computer Simulation International， 2012： 6.

[64]RIZK A， FIDLER M. Non-asymptotic end-to-end performance bounds for networks with long range dependent fBm cross traffic[J]. Computer Networks， 2012， 56（1）： 127-141.

[65]JIN X， MIN G， VELENTZAS S， et al. Quality-of-service analysis of queuing systems with long-range-ependent network traffic and variable service capacity[J]. Wireless Communications， IEEE Transactions on， 2012， 11（2）： 562-570.

[66]BREGNI S， GIACOMAZZI P， SADDEMI G. Long-range dependence of traffic across schedulers with multiple service classes[J]. Computer Communications， 2012， 35（7）： 842-848.

[67]1 LI V O K， LI V O K. Reconsidering network traffic modeling[J]. 2013. http：//www.eee.hku.hk/research/doc/tr/TR2012006_Reconsidering_Network_Traffic_Modeling.pdf