基于測(cè)量的自相似網(wǎng)絡(luò)流量預(yù)測(cè)研究

基于測(cè)量的自相似網(wǎng)絡(luò)流量預(yù)測(cè)研究

通過(guò)首次提出網(wǎng)絡(luò)自相似過(guò)程的概念，對(duì)網(wǎng)絡(luò)的自相似特征進(jìn)行了大量研究。在文獻(xiàn)[2、3、4、5、6、7、8、9、10、11和12]中，不同的網(wǎng)絡(luò)環(huán)境在不同的域中傳輸網(wǎng)絡(luò)時(shí)，網(wǎng)絡(luò)具有普遍不同的自相似現(xiàn)象。這種相似性的長(zhǎng)度增加，緩沖區(qū)需求能力降低，端部延遲率和傳輸率降低。這些測(cè)量參數(shù)的惡化程度與湖值測(cè)量的自相似度成正比。在文獻(xiàn)中，我們研究了降低hurst參數(shù)，改進(jìn)網(wǎng)絡(luò)性能指標(biāo)的方法。在web中，為了提高網(wǎng)絡(luò)響應(yīng)能力，預(yù)測(cè)了humst參數(shù)。在基于自相似特性的網(wǎng)絡(luò)流量預(yù)測(cè)時(shí),往往由于自相似計(jì)算過(guò)程復(fù)雜,計(jì)算量大而導(dǎo)致其在實(shí)際過(guò)程中無(wú)法滿(mǎn)足實(shí)時(shí)預(yù)測(cè)應(yīng)用的要求.本文在對(duì)當(dāng)前自相似網(wǎng)絡(luò)流量預(yù)測(cè)進(jìn)行綜述和研究的基礎(chǔ)上,根據(jù)網(wǎng)絡(luò)自相似流量特性提出了一種自相似網(wǎng)絡(luò)流量預(yù)測(cè)算法.分析表明,該算法在不明顯降低預(yù)測(cè)效果的情況下,可顯著減少計(jì)算量.1網(wǎng)絡(luò)搜索模型1.1隨機(jī)變量的i獨(dú)立同分布設(shè)m個(gè)同類(lèi)的業(yè)務(wù)源,單個(gè)業(yè)務(wù)源ON狀態(tài)持續(xù)時(shí)間為τ(i),OFF狀態(tài)持續(xù)時(shí)間為θ(i).隨機(jī)變量τ(i),θ(i)獨(dú)立同分布,其分布函數(shù)為p(τ>t):t-αt→∞,1<α<2.(1)即τ(i),θ(i)均服從Pareto分布,具有有限均值E(X)<∞和無(wú)限方差.可以證明,當(dāng)m→∞時(shí),總的業(yè)務(wù)是漸近自相似的,且滿(mǎn)足H=(3-α)/2.1.2jbm法假設(shè)分形高斯噪聲{Xn}n=1,2,…為一平穩(wěn)高斯噪聲,均值為μ=E(Xn),方差為σ2=E[(Xn-μ)2],則r(k):H(2H-1)k2H-2,k→∞,0.5<H<1.(2)At為FBM,它滿(mǎn)足At=mt+√amBΗt,t∈(0,∞).(3)其中,m為業(yè)務(wù)的平均到達(dá)速率,a>0為方差系數(shù),BΗt為標(biāo)準(zhǔn)的FBM且滿(mǎn)足0.5<H<1.1.3屬性bp型隨機(jī)過(guò)程{X0}n=1,2,…為FARIMA過(guò)程,如果它具有如下形式:Φ(B)=ΔdXn=Θ(B)ωn.(4)式中Φ(B)=1-Φ1(B)-…-Φp(B)p為AR項(xiàng);Θ(B)=1-Θ1(B)-…-Θq(B)q為MA項(xiàng);后向算子BXn=Xn-1;Δ=1-B為差分算子,Δd=(1-B)d=Γ(-d+n)/(Γ(-d)Γ(n+1))為差分分形算子,Γ(·)表示Γ函數(shù).式中FARIMA(p,d,q)模型需要三個(gè)參數(shù),其中p,q為整數(shù),d為實(shí)數(shù).對(duì)于d∈(-1/2,1/2),X為一平穩(wěn)可逆過(guò)程,當(dāng)k→∞時(shí)相關(guān)系數(shù)r(k):ak2d-1,a為有限正值且與k無(wú)關(guān).X是漸近自相似的,且H=d+1/2.1.4功率譜的基本概念設(shè)隨機(jī)過(guò)程x(t)的正交小波變換為x(t)=∞∑m=-∞∞∑n=-∞cmnφmn(t)?cmn=∫∞-∞x(t)φmn(t)dt?φmn(t)=2m/2φ(2mt-n).(5)若母小波φ(t)具有R(R>1)階消失矩,即∫∞-∞trφ(t)dt,r=0,1,…,R-1,且小波系數(shù){cmn}是零均值互不相關(guān)的隨機(jī)變量,方差為varxmn=σ22-γm,0<γ<2R,則x(t)的功率譜為Sx(ω)=σ2∞∑-∞2-γm|Ψ(2-mω)|2,(6)且Sx(ω)是近似1/f的或稱(chēng)廣義1/f的,即σ2L/|ω|γ≤Sx(ω)≤σ2n/|ω|γ.(7)式中σ2L,σ2n是滿(mǎn)足0<σ2L<σ2n<∞的參數(shù).1.5響應(yīng)面模型若參數(shù)0<α≤2,σ>0,-1≤β≤1,而且μ∈R,則α穩(wěn)定過(guò)程的特征函數(shù)表達(dá)式如下:Eexp(iθX)={exp{-σα|θ|α[1-iβ(signθ)tanπα2]+iμθ}?α≠1；exp{-σ|θ|[1+iβ(signθ)ln|θ|]+iμθ}?α=1.(8)式中:signθ={1?θ＞0；0?θ=0；-1,θ＜0.α為特征指數(shù),表征突發(fā)程度;β為偏斜參數(shù)(-1<β<1),α和β聯(lián)合決定概率密度函數(shù)的形狀;σ為尺度參數(shù);μ為位稱(chēng)參數(shù).若X服從上述參數(shù)決定的α穩(wěn)定分布,則記為X～Sα(σ,β,μ).(9)1.6尺度系數(shù)法k合成網(wǎng)絡(luò)流量多分形小波模型合成網(wǎng)絡(luò)數(shù)據(jù)的方法與小波域獨(dú)立高斯模型方法相似.首先,生成根尺度系數(shù)U0,0和Aj,k,然后運(yùn)用公式{Uj,2k=2-1/2(1+Aj-1,k)Uj-1,k?Uj,2k+1=2-1/2(1-Aj-1,k)Uj-1,k?(10)遞歸計(jì)算得到尺度系數(shù)序列{U0,k},從而合成相應(yīng)的網(wǎng)絡(luò)流量.多分形小波模型是一個(gè)乘法模型,合成信號(hào)可以用累乘公式C(n)[k]=2-nU0?0n-1∏j=0[1+(-1)kAi,k](11)表達(dá),上式得到的數(shù)據(jù)是非負(fù)且長(zhǎng)相關(guān)的.1.7比較模型的自相模型各種自相似網(wǎng)絡(luò)流量模型的優(yōu)缺點(diǎn)見(jiàn)表1.2時(shí)域方法和頻域方法Hurst參數(shù)估計(jì)的方法分為時(shí)域和頻域兩類(lèi).常用的時(shí)域方法包括方差時(shí)間法(VT)、絕對(duì)值法(Abs)、留數(shù)法(Res)和R/S法.頻域方法有周期圖法、Whittle法和小波法.2.1xn.12的n/m算法描述序列X的m階聚集序列X(m)的n階中心矩為:AΜ(m)n=1Ν/mΝ/m∑k=1|X(m)k-ˉX|n.(12)如果序列X是高斯的或方差有限的,那么對(duì)于大的N/m和m,滿(mǎn)足:AM(m)n∝Cmn(H-1).(13)在對(duì)數(shù)坐標(biāo)圖得到的直線(xiàn)的分辨率為n(H-1).當(dāng)n=1時(shí),對(duì)應(yīng)算法是絕對(duì)值法(Abs);當(dāng)n=2時(shí),對(duì)應(yīng)算法為方差的時(shí)間法(VT).2.2最小均方線(xiàn)a+bt將原始序列X分為大小為m的子塊,每子塊的部分和Y(t),最小均方線(xiàn)a+bt,其余數(shù)的樣本方差為1mm∑t=1(Y(t)-a-bt)2.(14)該方差正比于m2H.2.3rse表達(dá)對(duì)于時(shí)間序列X,部分和Y(n)及樣本方差S2(n),R/S方法統(tǒng)計(jì)量為:RS(n)=1S(n)[max0≤i≤n(Y(t)-tnY(n))-min0≤i≤n(Y(t)-tnY(n))].(15)對(duì)于FGN有:E[RSn]∝CΗnΗ.(16)2.4譜密度的確定對(duì)于長(zhǎng)度為N的時(shí)間序列X,其周期圖定義為:Ι(v)=12πΝ|Ν∑j=1X(j)eijv|2.(17)在方差有限的情況下,考慮低頻部分,譜密度為I(v)∝|v|1-2H.3.5功率譜密度的選擇已知X為高斯隨機(jī)序列,其周期圖為I(ω),功率譜密度為f(ω,H),由最大似然原理,使g(Η)=∫π-πΙ(ω)f(ω,Η)dω?(18)取最大值的H即為Hurst參數(shù).2.6般估算參數(shù)的估算對(duì)一個(gè)信號(hào)x(t),利用小波分解法可分解為以下形式:x(t)=approxj+j=J∑j=1detailj(t)=∑kax(J,k)?J,k(t)+j=J∑j=1∑kdx(j,k)Ψj,k(t).(19)其中ax(J,k)=<x,?J,k(t)>dx(J,k)=<x,ΨJ,k(t)>.H的估計(jì)值為:Η(j1?j2)=12[j2∑j=j1Sjjηj-j2∑j=j1Sjjj2∑j=j1Sjηjj2∑j=j1Sjj2∑j=j1Sjj2-(j2∑j=j1Sjj)2+1].(20)其中ηj=log2(1n∑k|dx(j,k)|2)?sj=(nln22)/2j+1?ηj為漸近方差倒數(shù),j為分解級(jí)數(shù),nj=2-j,n為原始數(shù)據(jù)長(zhǎng)度,nj為j尺度小波分解下的小波函數(shù)系數(shù)的個(gè)數(shù).2.7多種檢測(cè)法聯(lián)合使用的穩(wěn)定性分析方差時(shí)間法、絕對(duì)值法都屬于聚類(lèi)方差法,計(jì)算速度較快,結(jié)果一般相同;周期圖法實(shí)際使用時(shí)可使用快速傅利葉變換來(lái)提高算法的速度;R/S法是最普遍使用的方法,但速度較慢;小波法雖然速度較快,實(shí)現(xiàn)卻相當(dāng)復(fù)雜.用時(shí)間方差法、絕對(duì)值法估計(jì)H參數(shù)的時(shí)間復(fù)雜度為O(n),用留數(shù)法、R/S法和Whittle法估計(jì)H參數(shù)的時(shí)間復(fù)雜度為O(n2),其余方法的時(shí)間復(fù)雜度為O(NlogN).文獻(xiàn)等指出在已有H參數(shù)估計(jì)方法中,Whittle估計(jì)量方法是最精確的,小波估計(jì)方法與之相近.方差時(shí)間圖和R/S分析屬于時(shí)域分析方法,只能統(tǒng)計(jì)得到Hurst系數(shù).Whittle估計(jì)法是一種頻域分析法,能得到Hurst系數(shù)的置信區(qū)間等精細(xì)結(jié)構(gòu),使自相似性更具可信性.一般來(lái)說(shuō),多種檢測(cè)法應(yīng)該聯(lián)合使用,首先用時(shí)域法判斷序列是否具有自相似性,再用頻域法對(duì)Hurst系數(shù)估值,并得到Hurst系數(shù)的性能指標(biāo).3業(yè)務(wù)流的到達(dá)率分形布朗業(yè)務(wù)能較好地解釋網(wǎng)絡(luò)中的自相似現(xiàn)象,所以假設(shè)網(wǎng)絡(luò)中的業(yè)務(wù)流(假設(shè)均為聚集流)是分形布朗業(yè)務(wù):At=mt+√amΖ(t).(21)式中:m為業(yè)務(wù)流的平均到達(dá)率;a>0為方差系數(shù)(即單位時(shí)間內(nèi)的方差均值比σ2/m);Z(t)為正態(tài)分形布朗業(yè)務(wù),是嚴(yán)格的自相似過(guò)程.H為自相似參數(shù).假設(shè)P(X>B)=ε,有效帶寬CE的近似解為(Norros公式):CE=m+(κ(Η)-2ln(ε))1Ηa12ΗB-(1-Η)Ηm12Η.(22)式中κ(H)=HH(1-H)(1-H);ε是業(yè)務(wù)流信元丟失率.4基于測(cè)量的流量自類(lèi)似于平等的帶寬算法4.1通過(guò)h參數(shù)進(jìn)行帶寬波動(dòng)的可行性自相似網(wǎng)絡(luò)模型相關(guān)計(jì)算與H參數(shù)有著直接的聯(lián)系,通過(guò)各種方法計(jì)算和求H值是進(jìn)行流量自相似預(yù)測(cè)的第一步.網(wǎng)絡(luò)流量的平均值和方差總處于不斷的變化中,總流量的變化以自相似H參數(shù)進(jìn)行波動(dòng).而平均流量和流量的突發(fā)性和長(zhǎng)相關(guān)性帶來(lái)了方差的波動(dòng),H參數(shù)是這種波動(dòng)和長(zhǎng)相關(guān)的直接體現(xiàn),通過(guò)H參數(shù)可以動(dòng)態(tài)地表征流量的波動(dòng).因此用平均流量作為等價(jià)帶寬計(jì)算的均值,用H參數(shù)來(lái)計(jì)算流量波動(dòng)對(duì)帶寬的影響可以比較近似地求得網(wǎng)絡(luò)實(shí)際流量.通過(guò)不斷測(cè)量和計(jì)算網(wǎng)絡(luò)流量的變化,包括均值和H參數(shù),從而近似地預(yù)測(cè)出網(wǎng)絡(luò)流量.由于H參數(shù)計(jì)算量大,復(fù)雜度高,因此通過(guò)減少計(jì)算量,降低計(jì)算復(fù)雜度,使網(wǎng)絡(luò)流量預(yù)測(cè)接近實(shí)時(shí)性能,是基于測(cè)量的流量自相似帶寬預(yù)測(cè)的一種可行辦法.4.2采樣時(shí)隙s的測(cè)量算法通過(guò)T-S窗口法測(cè)量平均流量和計(jì)算H參數(shù),H參數(shù)在不同區(qū)間變化時(shí)重新計(jì)算.利用H參數(shù)的相對(duì)穩(wěn)定性和平均流量的即時(shí)性相結(jié)合來(lái)預(yù)測(cè)網(wǎng)絡(luò)的流量.步驟如下:1)使用T-S窗口法測(cè)量平均流量.設(shè)T為測(cè)量窗口的大小,它是成百上千個(gè)分組傳輸所需的時(shí)間,S為采樣時(shí)隙,T=nS,n為大于5的整數(shù);LS為采樣時(shí)隙S內(nèi)的平均負(fù)載,LS總是在每個(gè)采樣時(shí)隙S結(jié)束時(shí)計(jì)算.采用如下策略測(cè)量和估計(jì)負(fù)載m值:在每個(gè)測(cè)量窗口Ti開(kāi)始時(shí),把m置為上一測(cè)量窗口Ti-1內(nèi)包含的所有S中平均負(fù)載,即m=1n∑i=1nLsi,其中S1,S2,…,Sn為T(mén)i-1內(nèi)的n個(gè)時(shí)隙.2)使用R/S方法測(cè)量和計(jì)算網(wǎng)絡(luò)流量,并使用Whittle法來(lái)求H參數(shù)的置信區(qū)間及H參數(shù).3)將m作為平均值,H作為Hurst參數(shù)代入Norros公式,則可求出當(dāng)前等價(jià)帶寬為:CE=m+(κ(Η)-2ln(ε))1Ηa12ΗB-(1-Η)Ηm12Η.(23)4)設(shè)鏈路帶寬為C,將C等分成n個(gè)區(qū)間.若測(cè)量值m在持續(xù)某一個(gè)區(qū)間內(nèi)變化,則不重新計(jì)算H值,即H值不變,僅計(jì)算m值;若m值變化到不同區(qū)間,則啟動(dòng)H值計(jì)算,以此方式來(lái)實(shí)時(shí)跟蹤和監(jiān)測(cè)網(wǎng)絡(luò)流量.4.3通過(guò)h計(jì)算進(jìn)行流量變化時(shí)的流量預(yù)測(cè)由于自相似網(wǎng)絡(luò)流量計(jì)算相對(duì)復(fù)雜,實(shí)時(shí)流量測(cè)量往往會(huì)占用較多的CPU時(shí)間,特別是在流量高峰期或數(shù)據(jù)量變化比較劇烈的時(shí)候,計(jì)算更加復(fù)雜和頻繁.采用本文提出的算法,可將流量劃分成不同區(qū)間,當(dāng)流量在不同區(qū)間跳變時(shí),才進(jìn)行H參數(shù)計(jì)算.而對(duì)于流量的平均值則因?yàn)閷儆诶奂忧笃骄惴?不會(huì)占用較多的資源.由于減少了H參數(shù)的計(jì)算量,因此對(duì)于流量的預(yù)測(cè)可以更快速和準(zhǔn)確,而占用的計(jì)算資源卻相對(duì)較少.1流量低的情況如下當(dāng)流量較小時(shí),比如占用網(wǎng)絡(luò)帶寬不到30%,可以認(rèn)為網(wǎng)絡(luò)流量的平均值可以代替網(wǎng)絡(luò)的實(shí)際流量,此時(shí)可以不啟動(dòng)H參數(shù)計(jì)算.2流量大時(shí)的情況如下當(dāng)流量較大時(shí),比如占有網(wǎng)絡(luò)帶寬超過(guò)80%的情況,可以認(rèn)為網(wǎng)絡(luò)的H參數(shù)基本不變.這一點(diǎn)在以太網(wǎng)的流量自相似研究中得到了驗(yàn)證.3算法復(fù)雜度的變化算法在實(shí)現(xiàn)過(guò)程中,H參數(shù)的計(jì)算復(fù)雜度根據(jù)使用的求解方法不同而變化,設(shè)為O(x).平均值求解的復(fù)雜度是常量,當(dāng)未分區(qū)時(shí),算法實(shí)現(xiàn)復(fù)雜度為O(nx).分區(qū)之后,算法復(fù)雜度減小為O(xlogn).5基于自相似網(wǎng)絡(luò)的多分形研究網(wǎng)絡(luò)業(yè)務(wù)流中的自相似性直接影響著網(wǎng)絡(luò)的性能,而在自相似的基礎(chǔ)上存在著一系列的網(wǎng)絡(luò)業(yè)務(wù)流