1、1,網(wǎng)絡(luò)流量自相似特性,2,提綱,問題提出 自相似的數(shù)學(xué)描述 產(chǎn)生自相似的原因 自相似對(duì)網(wǎng)絡(luò)性能的影響 國內(nèi)相關(guān)工作 可能的研究方向,3,問題提出,什么是自相似？ 為什么研究自相似？ 產(chǎn)生自相似的原因？ 泊松過程隨機(jī)變量(單位時(shí)間呼叫到達(dá)的次數(shù))是獨(dú)立的、且服從相似分布，即 PXknet(t)n/n! (n0) 馬爾可夫模型對(duì)過去具有有限記憶，即在已經(jīng)知道“現(xiàn)在”的條件下，其“將來”不依賴于“過去” 時(shí)間t與過去時(shí)間t-s，若s足夠大，則t與t-s時(shí)的業(yè)務(wù)量是不相關(guān)的，即僅考慮s較小時(shí)業(yè)務(wù)到達(dá)間的相關(guān)性，稱之為短時(shí)相關(guān)Short Range DependenceSRD模型,4,自相似的數(shù)學(xué)描述

2、,網(wǎng)絡(luò)流量模型 時(shí)間序列，表示每單位時(shí)間到達(dá)的字節(jié)數(shù)或數(shù)據(jù)包數(shù)量 自相似的物理描述 網(wǎng)絡(luò)流量在很寬的時(shí)間尺度內(nèi)存在突發(fā)現(xiàn)象，“Burst” 時(shí)間尺度幾十毫秒、秒、分鐘、小時(shí),5,自相似的數(shù)學(xué)描述,數(shù)學(xué)定義 假設(shè)前提平穩(wěn)隨機(jī)過程，即統(tǒng)計(jì)特性（均值、方差、相關(guān)等）不隨時(shí)間推移而變化。一階平穩(wěn)（均值為常數(shù)），二階平穩(wěn)（均值和方差為常數(shù)，任意兩時(shí)間點(diǎn)之間的協(xié)方差只取決于時(shí)間間隔，又稱之為廣義平穩(wěn)） 自相關(guān)函數(shù)定義為： r(k)E(Xt)(Xt+k)/E(Xt)2,6,自相似的數(shù)學(xué)描述,自相似 條件1針對(duì)一個(gè)平穩(wěn)隨機(jī)過程 X(Xt: t0,1,2,3) 條件2其自相關(guān)函數(shù)滿足r(k) kL1(k)，當(dāng)k

3、，其中01，L1是慢變函數(shù)，即對(duì)所有x0，limtL1(tx)/L1(t)1（常見的慢變函數(shù)，如L1(t)常數(shù)，L1(t)(t)） 條件3-對(duì)X進(jìn)行堆疊，堆疊產(chǎn)生的時(shí)間序列為X(m)(Xk(m)：k1,2,3 )，其中 Xk(m) 1/m(Xkm-m+1 Xkm)，k1, 2, 3, ,7,自相似的數(shù)學(xué)描述,自相似(Exactly second order) self-similar X(m)的自相關(guān)函數(shù)r(m)滿足：r(m)(k)r(k)，對(duì)所有m1, 2, (k1, 2, 3, ) 漸進(jìn)自相似(Asymptotically second order) self-similar X(m)的自

4、相關(guān)函數(shù)r(m)滿足： r(m)(1)211，當(dāng)m r(m)(k)1/22(k2)，當(dāng)m (k2, 3, ) 2表示一個(gè)算子符，其作用于函數(shù)f(k)表示2(f(k)f(k1)2f(k)f(k1),8,自相似的數(shù)學(xué)描述,自相似參數(shù)H H1/2 r(k)k(2-2H)L1(k)，當(dāng)k 漸進(jìn)自相似(asymptotically self-similar) r(k)1/2(k1)2H2k2H(k1)2H 嚴(yán)格自相似 (exactly self-similar) 參數(shù)H滿足0.5H1，參數(shù)H用來表示自相似的程度,9,自相似的數(shù)學(xué)描述,自相似的特性 長(zhǎng)相關(guān)（LRDlong range dependence

5、、large scale correlation、long term correlation ） 長(zhǎng)相關(guān)定義若一個(gè)隨機(jī)過程滿足自相似的條件1和條件2，即其自相關(guān)函數(shù)隨時(shí)滯的增加呈雙曲線衰減（冪律衰減），則該隨機(jī)過程呈現(xiàn)長(zhǎng)相關(guān)性 長(zhǎng)相關(guān)自相似，自相似是長(zhǎng)相關(guān)的特例/簡(jiǎn)單模型 不可和性，即k r(k)。不可和性的物理意義在于高滯后的相關(guān)雖然是個(gè)別的小量，但其累計(jì)的結(jié)果則十分重要 短相關(guān)過程(short-range dependence)自相關(guān)函數(shù)呈指數(shù)衰減，即r(k)k，當(dāng)k(01)，其自相關(guān)函數(shù)是可和的，即0k r(k),10,自相似的數(shù)學(xué)描述,自相似的特性 慢衰減方差 自相似過程的方差滿足va

6、r(X(m)am，當(dāng)m，其中01，a是與m無關(guān)的正常數(shù)，與前條件2中相同 短相關(guān)過程的方差滿足var(X(m)bm1，當(dāng)m，其中b是與m無關(guān)的正常數(shù) 自相似過程的方差衰減要慢于短相關(guān)過程,11,自相似的數(shù)學(xué)描述,自相似的特性 Hurst效應(yīng) H表示Hurst參數(shù)，自相關(guān)程度的度量 重新調(diào)制尺度權(quán)差(R/S)對(duì)于一個(gè)給定的觀察序列X1, X2, X3 .Xn，樣本均值為X(n)，樣本方差為S2(n)，則R(n)/S(n)1/S(n)max(0, W1, W2, , Wn)min(0, W1, W2, , Wn)，其中Wk(X1X2X3.Xk)kX(n)，k1,2,3n，R表示重新調(diào)整尺度的極差

7、R/S: Rescaled adjusted range analysis,12,自相似的數(shù)學(xué)描述,自相似的特性 Hurst效應(yīng) Hurst在1991年和1995年發(fā)現(xiàn)大多數(shù)自然產(chǎn)生的時(shí)間序列滿足ER(n)/S(n)cnH，當(dāng)n，其中Hurst參數(shù)典型為0.73，c是與n無關(guān)的正常數(shù) 若觀察序列取自一個(gè)短相關(guān)模型，曼德博羅等發(fā)現(xiàn)，滿足ER(n)/S(n)dn0.5，當(dāng)n，其中d與n無關(guān)的正常數(shù) 上述兩式的差異通常稱之為赫斯特效應(yīng)或赫斯特現(xiàn)象 Hurst赫斯特英國的水文專家，長(zhǎng)期從事尼羅河水壩工程研究 Mandelbrot曼德博羅分形理論的創(chuàng)始人，美籍法國數(shù)學(xué)家,13,自相似的數(shù)學(xué)描述,自相似

8、r(k) kL1(k)，k(01)，L1是慢變函數(shù) k r(k) var(X(m)am，m(01),短相關(guān) r(k)k，當(dāng)k(01) 0k r(k) var(X(m)bm1，m,14,自相似的數(shù)學(xué)描述,如何測(cè)度自相似 數(shù)學(xué)定義針對(duì)無限長(zhǎng)度的時(shí)間序列 實(shí)際中僅僅一段時(shí)間的取樣，保證取樣點(diǎn)足夠多,15,自相似的數(shù)學(xué)描述,如何測(cè)度自相似 針對(duì)有限的時(shí)間序列來估計(jì)Hurst參數(shù) 方法1分析堆疊過程X(m)的方差，自相似的慢衰減方差特性 var(X(m)am- (m) (var(X(m)(m)(a) (m),0.4 H0.8,16,自相似的數(shù)學(xué)描述,如何測(cè)度自相似 方法2基于R/S統(tǒng)計(jì)的時(shí)域分析 ER(

9、n)/S(n)cnH (n) (ER(n)/S(n)H(n)(c) (n) 原始的時(shí)間序列分為大小為n的塊，對(duì)每個(gè)塊計(jì)算其R(ti,n)/S(ti,n),H0.79,17,自相似的數(shù)學(xué)描述,如何測(cè)度自相似 基于周期圖(Periodogram)的頻域分析 協(xié)方差函數(shù)傅立葉變換功率譜 用周期圖近似估計(jì)功率譜 從譜密度中找到參數(shù)H,18,自相似的數(shù)學(xué)描述,具備自相似的數(shù)學(xué)模型 自相似理論廣泛地應(yīng)用在水文和經(jīng)濟(jì)學(xué)領(lǐng)域 分形(分?jǐn)?shù))高斯噪聲fractional Gaussian noise FGN 分形(分?jǐn)?shù))布朗運(yùn)動(dòng)fractional Brownian motion FBM，是分形高斯噪聲的增量和過

10、程 分形(分?jǐn)?shù))自回歸滑動(dòng)平均過程fractional ARIMA processes AutoRegressive Integrated Moving-Average，漸進(jìn)自相似過程,19,自相似的數(shù)學(xué)描述,網(wǎng)絡(luò)流量的建模 ON/OFF模型疊加大量的ON/OFF源，每個(gè)源有兩個(gè)狀態(tài)，即ON和OFF。在ON狀態(tài)，以連續(xù)速率發(fā)送數(shù)據(jù)包，在OFF狀態(tài)，不發(fā)送數(shù)據(jù)包。每個(gè)發(fā)生源ON或OFF的時(shí)長(zhǎng)獨(dú)立地符合重尾分布（Heavy-tailed distribution） 重尾分布若一隨機(jī)變量滿足重尾分布，則PXx x-，當(dāng)x, 00，xk，分布函數(shù)為F(x)PXx1(k/x)，當(dāng)減小，大量的概率質(zhì)量集中

11、在分布的尾部 H(3)/2 佩瑞多.韋爾福雷多（Pareto Vilfredo）意大利經(jīng)濟(jì)學(xué)家和社會(huì)學(xué)家,20,對(duì)流量自相似研究的三個(gè)方面,分析流量的特征，建模 小波分析（Discrete Wavelet Transform）和分形理論 分形和多重分形(Multifractal)模型 “可信的”網(wǎng)絡(luò)流量生成模型 產(chǎn)生流量自相似的原因 評(píng)估自相似流量對(duì)網(wǎng)絡(luò)的影響,21,產(chǎn)生自相似的原因,是流量?jī)?nèi)在的特性還是網(wǎng)絡(luò)協(xié)議的調(diào)制作用？ Web流量的自相關(guān)性 (Boston University, 1996, 1998,實(shí)際數(shù)據(jù)) Web文件大小的分布（包括用戶請(qǐng)求的文件、實(shí)際傳輸?shù)奈募⑽募膫鬏敃r(shí)間、

12、服務(wù)器端存儲(chǔ)的文件等）呈重尾分布，客戶端Cache的影響相對(duì)較小Web文件傳輸時(shí)間的重尾分布Web流量的自相似性,22,產(chǎn)生自相似的原因,若文件大小符合重尾分布，則對(duì)應(yīng)的文件傳輸均導(dǎo)致鏈路層的自相似性，Web、NFS、FTP等 (Purdue University, Boston University, 1996, NS模擬) 上述情況似乎都可以從ON/OFF模型找到解釋的理由,23,產(chǎn)生自相似的原因,對(duì)IP流量成分的進(jìn)一步分析 （Hungary, Budapest Uni. Of Tech.&Econo. 實(shí)際數(shù)據(jù),2000） 不同協(xié)議成分如IP、ICMP、TCP、UDP、HTTP、SMTP

13、、FTPdata、FTPcontrol、OSPF、Telnet，是否多重分形(multifractal)和分形(monofractal，即自相似),24,產(chǎn)生自相似的原因,重傳機(jī)制(Retransmission)產(chǎn)生自相似特性(CMU，1997) 模擬條件輸入是泊松到達(dá)（即，新數(shù)據(jù)包（不包括重傳的數(shù)據(jù)包）到達(dá)是一個(gè)簡(jiǎn)單的泊松過程），數(shù)據(jù)包長(zhǎng)度為常數(shù)，一個(gè)隊(duì)列情況，先進(jìn)先服務(wù)，無擁塞控制的重傳機(jī)制 結(jié)論當(dāng)時(shí)間尺度超過10倍的數(shù)據(jù)包傳輸時(shí)間，重傳數(shù)據(jù)包流量的方差在總的流量（新數(shù)據(jù)包、重傳數(shù)據(jù)包和丟失的數(shù)據(jù)包）中占據(jù)絕大多數(shù)成分。 即使改變重傳機(jī)制的參數(shù)，如緩存大小、重傳企圖的次數(shù)和超時(shí)時(shí)限，不能改

14、變重傳負(fù)載的自相似特性,25,產(chǎn)生自相似的原因,TCP擁塞控制的渾沌特性(Ericsson，Traffic Analysis and Network Performance Lab. 2000) 渾沌系統(tǒng)的特征：非線性(Nonlinearity)、確定性(Determinism)、混亂中的有序(Order in disorder)、對(duì)初始狀態(tài)的敏感性(蝴蝶效應(yīng))(Sensitivity to initial conditions or the “butterfly effect”)、不可預(yù)見性(Unpredictability) 模型(NS模擬)：TCP Tahoe（Slow-Start、Co

15、ngestion Avoidance、Fast Retransmit） 參數(shù)設(shè)置：link rate-C、delay-D、buffer size-B以及TCP流的數(shù)量-N,26,產(chǎn)生自相似的原因,TCP擁塞控制的渾沌特性(Ericsson，Traffic Analysis and Network Performance Lab. 2000) 結(jié)論：B/N的比率控制著系統(tǒng)的相位遷移，即從周期性到渾沌，并在特定的參數(shù)下產(chǎn)生自相似時(shí)間序列；單個(gè)的TCP流量符合漸進(jìn)自相似，H0.5；在瓶頸緩存處堆疊的TCP流量是短時(shí)相關(guān)的，H0.5，其物理解釋是TCP擁塞控制使瓶頸緩存占用率最大來平滑流量，堆疊的流量

16、得到平滑，單個(gè)TCP流仍保持長(zhǎng)相關(guān)性。 為什么堆疊的網(wǎng)絡(luò)流量仍具有長(zhǎng)相關(guān)性(H0.5)？TCP擁塞控制和具有重尾特性的上層協(xié)議共同作用。 TCP本身是一個(gè)產(chǎn)生自相似特性的確定性過程,27,產(chǎn)生自相似的原因,針對(duì)傳輸層(TCP和UDP)更進(jìn)一步的研究(Purdue University, Boston University, 1996, NS模擬) TCP(Tahoe、Reno或Vegas)可靠的傳輸機(jī)制和流量控制機(jī)制保留了由文件大小重尾分布所引發(fā)的長(zhǎng)相關(guān)性 無流量控制和不可靠的UDP并不使生成的流量具有長(zhǎng)相關(guān)性,28,產(chǎn)生自相似的原因,網(wǎng)絡(luò)拓?fù)涞挠绊?(Purdue University, B

17、oston University, 1996, NS模擬) 對(duì)流量自相似的估計(jì)并不因網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)變化而改變,29,產(chǎn)生自相似的原因,重尾分布的ON/OFF和渾沌的TCP導(dǎo)致Internet流量的分形特性(自相似),Application Layer,Transport/Network Layer,Application Layer,Transport/Network Layer,Heavy-Tailed File Size Distribution ,Congest Control and Reliability,Self-Similarity Link Traffic H,30,自相似流量對(duì)

18、網(wǎng)絡(luò)性能的影響,網(wǎng)絡(luò)性能的度量吞吐量(throughout)、延時(shí)(delay)、數(shù)據(jù)包丟失(packet loss) 從排隊(duì)論的視角，網(wǎng)絡(luò)是隊(duì)列的集合，每個(gè)隊(duì)列有一個(gè)緩存(buffer)臨時(shí)保存到達(dá)的數(shù)據(jù)包。數(shù)據(jù)包到達(dá)緩存等候轉(zhuǎn)發(fā)，則會(huì)產(chǎn)生延時(shí)。若達(dá)到數(shù)據(jù)包的數(shù)量超過緩存大小，則產(chǎn)生丟棄數(shù)據(jù)包的現(xiàn)象，同時(shí)需要對(duì)丟棄的數(shù)據(jù)包進(jìn)行重發(fā)，導(dǎo)致吞吐量降低。實(shí)際上，網(wǎng)絡(luò)的緩存通常保持很大以避免數(shù)據(jù)包丟失，維護(hù)高的吞吐量,31,自相似流量對(duì)網(wǎng)絡(luò)性能的影響,自相似流量對(duì)網(wǎng)絡(luò)性能產(chǎn)生負(fù)面影響 緩存占用比傳統(tǒng)排隊(duì)論的分析結(jié)果要大，結(jié)果導(dǎo)致更大的延時(shí)（也即隊(duì)列長(zhǎng)度分布在自相似流量作用下的衰減比短時(shí)相關(guān)源（泊松到

19、達(dá)過程）作用下要慢），由長(zhǎng)相關(guān)特性決定,32,自相似流量對(duì)網(wǎng)絡(luò)性能的影響,自相似流量對(duì)網(wǎng)絡(luò)性能產(chǎn)生負(fù)面影響 緩存的線性增長(zhǎng)導(dǎo)致指數(shù)規(guī)律減少的數(shù)據(jù)包丟失，以及成比例增長(zhǎng)的傳輸帶寬利用率。該理論對(duì)自相關(guān)流量不適用,33,自相似流量對(duì)網(wǎng)絡(luò)性能的影響,自相似流量對(duì)網(wǎng)絡(luò)性能產(chǎn)生負(fù)面影響 數(shù)據(jù)包丟失率與緩存大小和自相似之間的關(guān)系當(dāng)趨近于1，自相似程度增大(H(3)/2)，數(shù)據(jù)包丟失率增大,34,自相似流量對(duì)網(wǎng)絡(luò)性能的影響,自相似流量對(duì)網(wǎng)絡(luò)性能產(chǎn)生負(fù)面影響 文件大小的重尾分布與吞吐量的關(guān)系,平均緩存 占用(字節(jié)) 與 數(shù)據(jù)包 平均延時(shí) 成比例,35,國內(nèi)相關(guān)工作,“自相似業(yè)務(wù)量的多重分形分析”，電子學(xué)報(bào)，2

20、000年，第28卷，第1期，P.96-98； “CERNET網(wǎng)絡(luò)業(yè)務(wù)的自相似性及性能分析”，天津大學(xué)學(xué)報(bào)（自然科學(xué)與工程技術(shù)版），2000年，第33卷，第3期，P.367-370； “突發(fā)業(yè)務(wù)的多重分形建模及其參數(shù)估計(jì)”，電子學(xué)報(bào)，1999年，第4期，第27卷； “網(wǎng)絡(luò)中業(yè)務(wù)流的自相似性與線性AR1模型”，電子學(xué)報(bào)，1999年，第4期，第27卷； “自相似業(yè)務(wù)模型下的隊(duì)列分析大偏差技術(shù)”，通信學(xué)報(bào)，1999年，第20卷，第4期；,36,國內(nèi)相關(guān)工作,“自相似業(yè)務(wù)合成流的建模及排隊(duì)性能分析”，通信學(xué)報(bào)，1999年，第20卷，第8期； “自相似業(yè)務(wù)：基于多分辨率采樣和小波分析的Hurst系數(shù)估計(jì)方法”，電子學(xué)報(bào)，1998年，第7期； “A New Multifractal Traffic Model Based on the Wavelet Transform”、“Measurement and Analysis of IP Network Traffi