數(shù)據(jù)分組網(wǎng)絡(luò)中業(yè)務(wù)模型的研究進(jìn)展

數(shù)據(jù)分組網(wǎng)絡(luò)中業(yè)務(wù)模型的研究進(jìn)展

1泊松或馬爾可夫模型主要作用于網(wǎng)絡(luò)業(yè)務(wù)的特性到目前為止，電信網(wǎng)絡(luò)已經(jīng)發(fā)展成為一個(gè)傳統(tǒng)意義上的電話網(wǎng)絡(luò)，包括我們熟悉而未知的網(wǎng)絡(luò)、移動(dòng)互聯(lián)網(wǎng)、廣播電視網(wǎng)絡(luò)等。本文關(guān)注的是基于數(shù)據(jù)分組交換的網(wǎng)絡(luò),數(shù)據(jù)分組網(wǎng)包括的范圍很廣,在數(shù)據(jù)分組網(wǎng)中,使用了新的技術(shù)和新的網(wǎng)絡(luò)思想,提供給用戶新的業(yè)務(wù)和新的應(yīng)用,那么傳統(tǒng)的業(yè)務(wù)模型對(duì)網(wǎng)絡(luò)業(yè)務(wù)的描述是否仍然適用呢?分組交換網(wǎng)是基于分組交換的,這與傳統(tǒng)電信網(wǎng)的電路交換有根本差別,在分組網(wǎng)中傳送的主要是數(shù)據(jù)業(yè)務(wù),包括正在興起的多媒體業(yè)務(wù),而在傳統(tǒng)的電信網(wǎng)中傳送的主要業(yè)務(wù)是話音業(yè)務(wù)。在傳統(tǒng)的網(wǎng)絡(luò)設(shè)計(jì)和系統(tǒng)分析中采用泊松過(guò)程或馬爾可夫過(guò)程可以得到很好的結(jié)果,但是在對(duì)分組網(wǎng)絡(luò)的業(yè)務(wù)進(jìn)行監(jiān)測(cè)后發(fā)現(xiàn),如果仍然采用泊松或馬爾可夫模型,那么得到的排隊(duì)分析結(jié)果就和實(shí)際情況有很大的差別,比如第一代ATM交換機(jī)根據(jù)傳統(tǒng)的排隊(duì)模型做出的緩存大小的預(yù)測(cè)大大小于實(shí)際需要的緩存容量,這樣的差別是由于實(shí)際網(wǎng)絡(luò)業(yè)務(wù)在多數(shù)甚至全部的時(shí)間尺度內(nèi)表現(xiàn)出很大的變化(長(zhǎng)相關(guān)性),而泊松或馬爾可夫模型是無(wú)記憶、短相關(guān)的,只在很短的時(shí)間范圍內(nèi)表現(xiàn)出突發(fā)性,所以用泊松或馬爾可夫模型分析得到的結(jié)果是過(guò)于優(yōu)化的結(jié)果。近年來(lái),在網(wǎng)絡(luò)業(yè)務(wù)模型的描述中,采用了自相似性(self-similar)或稱(chēng)為長(zhǎng)相關(guān)性(long-range-dependent,LRD)這一概念來(lái)描述實(shí)測(cè)到的網(wǎng)絡(luò)業(yè)務(wù)過(guò)程中表現(xiàn)出的突發(fā)性,這些業(yè)務(wù)包括局域網(wǎng)(LAN)業(yè)務(wù)、廣域網(wǎng)(WAN)業(yè)務(wù)、VBR視頻業(yè)務(wù)、WWW業(yè)務(wù)等。研究人員采用分形(fractal)來(lái)描述這些業(yè)務(wù)并進(jìn)行建模。普通的分形過(guò)程被稱(chēng)為自相似隨機(jī)過(guò)程,或單分形(monofractal)。但是由于網(wǎng)絡(luò)業(yè)務(wù)的時(shí)間尺度可以在很大的范圍內(nèi)變化,實(shí)測(cè)網(wǎng)絡(luò)業(yè)務(wù)不僅表現(xiàn)出長(zhǎng)相關(guān),還表現(xiàn)出了短相關(guān)性,那么用普通的自相似過(guò)程能不能完全地描述網(wǎng)絡(luò)業(yè)務(wù)在很小的時(shí)間尺度下的特性呢?對(duì)小的時(shí)間尺度的網(wǎng)絡(luò)業(yè)務(wù)的特性有沒(méi)有必要描述呢?對(duì)此也有不同的觀點(diǎn),MuradS.Taqqu等認(rèn)為對(duì)LAN和WAN沒(méi)有必要將模型的難度上升到多分形(multifractal),但更多的觀點(diǎn)認(rèn)為多分形模型在網(wǎng)絡(luò)業(yè)務(wù)模型上的研究是有必要的。本文首先描述了自相似隨機(jī)過(guò)程的定義及性質(zhì),包括普通的自相似隨機(jī)過(guò)程(單分形)和多分形;然后介紹已有的效果較好的模擬多分形的業(yè)務(wù)模型,并對(duì)這些模型進(jìn)行分析;最后說(shuō)明這些模型對(duì)網(wǎng)絡(luò)業(yè)務(wù)帶來(lái)的影響。2隨機(jī)過(guò)程的數(shù)學(xué)描述2.1一般的隨機(jī)過(guò)程文獻(xiàn)中對(duì)自相似隨機(jī)過(guò)程的定義有很多種,分為連續(xù)時(shí)間隨機(jī)過(guò)程和離散時(shí)間隨機(jī)過(guò)程。2.1.1意義上的相似參數(shù)一個(gè)時(shí)間連續(xù)的隨機(jī)過(guò)程被稱(chēng)為自相似隨機(jī)過(guò)程,如果其中,λ>0,0<H<1,=d表示分布意義上的相等。H被稱(chēng)作自相似參數(shù),或Hurst參數(shù),H的值是相關(guān)的持續(xù)性的量度:H越大,相關(guān)性越強(qiáng)。由式(1)有:分形布朗運(yùn)動(dòng)(fractionalBrownianmotion,FBm)過(guò)程是一種典型的自相似隨機(jī)過(guò)程,已經(jīng)有比較成功的使用FBm的網(wǎng)絡(luò)業(yè)務(wù)模型。2.1.2隨機(jī)過(guò)程相關(guān)函數(shù)網(wǎng)絡(luò)流量的分析已經(jīng)被嚴(yán)格地限制為離散時(shí)間的二階或近似二階自相似過(guò)程。Leland等及Beran等對(duì)自相似隨機(jī)過(guò)程的定義是:令X={Xt:t=0,1,2,…}為一個(gè)協(xié)方差平穩(wěn)的隨機(jī)過(guò)程,其均值為u,方差為62,自相關(guān)函數(shù)為r(k),k≥0。假設(shè)r(k)形為0<β<1。注意到,這被稱(chēng)為隨機(jī)過(guò)程的長(zhǎng)相關(guān)性(LRD)。對(duì)m=1,2,3,…,令X(m)={Xt(m):t=1,2,3,…}表示由X得到的疊加過(guò)程這是一個(gè)協(xié)方差平穩(wěn)的隨機(jī)過(guò)程。X稱(chēng)為有Hurst參數(shù)H=1–β/2的(嚴(yán)格的)二階自相似過(guò)程,如果對(duì)所有m=1,2,3,…,Var(X(m))=σ2m–β且這里r(m)(k)是X(m)的自相關(guān)函數(shù),如果對(duì)所有足夠大的k,有則X被稱(chēng)作(近似)二階自相似,其中r(k)由式(2)定義。X具有自相似性的意思是X(m)和X具有(嚴(yán)格的或近似的)相同的二階統(tǒng)計(jì)特性。2.2算法的基本思想多分形的概念最早是用于對(duì)湍流(turbulence)現(xiàn)象的間斷性的描述,將間斷性用于描述網(wǎng)絡(luò)業(yè)務(wù)時(shí),其表達(dá)的是網(wǎng)絡(luò)業(yè)務(wù)的突發(fā)性的合成以及在不同時(shí)間尺度下突發(fā)性的不同?？梢韵胂?一個(gè)簡(jiǎn)單的多分形模型就能夠描述基本的(可能是時(shí)變的)LRD業(yè)務(wù)的突發(fā)性。典型的多分形的定義是基于乘法過(guò)程或?qū)盈B模型(multiplicativeprocessesorcascademodels)得到的。假設(shè)有一單位長(zhǎng)度的線段,并且這個(gè)線段有一單位質(zhì)量,將此單位線段分解成一系列小的線段,每一段長(zhǎng)度為ε,同時(shí)將單位質(zhì)量劃分成權(quán)重列{wi},其中wi是第i段線段的質(zhì)量,則其矩為這里q是實(shí)數(shù)。當(dāng)wj為0時(shí),wjq項(xiàng)也為零,不用考慮。q為正數(shù)時(shí)得到的是較大的權(quán)重,而負(fù)的q值得到的是較小的權(quán)重,如果我們有一個(gè)關(guān)于q的實(shí)函數(shù)τ(q),使得對(duì)每一個(gè)q,有且權(quán)重{wi}是不均勻的,那么權(quán)重列wi(ε)組成一個(gè)多分形(multifractal)測(cè)度,注意到歸一化條件說(shuō)明τ(1)=0。{wi}的不均勻性由所謂的廣義維數(shù)(generalizeddimensions)Dq可以比較好地說(shuō)明Dq是關(guān)于q的單減函數(shù),當(dāng){wi}不均勻時(shí),Dq與q密切相關(guān)。目前對(duì)乘法多分形的研究是基于二進(jìn)劃分的,具體方法是,將單位線段分成等長(zhǎng)度的兩段,同時(shí)將單位質(zhì)量劃分成r和1-r兩部分,并將它們分配給分成的兩段線段,參數(shù)r是一個(gè)普通的隨機(jī)變量,有概率密度函數(shù)函數(shù)(pdf)P(r),0≤r≤1,r稱(chēng)為乘子(multiplier),根據(jù)同樣的規(guī)律劃分剛才得到的線段,此過(guò)程的圖解見(jiàn)圖1,乘子r在圖中寫(xiě)成rij,其中i表示第i次分解,第i次分解后每段線段的長(zhǎng)度是2-i,假設(shè)P(r)關(guān)于r=1/2對(duì)稱(chēng),并且有連續(xù)的矩u,u2,這樣rij和1-rij的邊緣分布均為P(r),第N次分解后權(quán){wn,n=1,2,…,2N},可以寫(xiě)為wn=u1u2…uN,這里,ul(l=1,2,…,N)為rij或1-rij,這樣,{ui,i≥1}均為獨(dú)立同分布的具有pdfP(r)的隨機(jī)變量,選擇不同的pdfP(r),就可以得到不同的二進(jìn)乘法多分形過(guò)程。圖2為選擇不同pdf得到的{wi}舉例,其分解次數(shù)為12。將不同的{wi}用于網(wǎng)絡(luò)業(yè)務(wù)模型的排隊(duì)分析中,wi的值的物理意義可以為到達(dá)間隔時(shí)間,也可以為單位時(shí)間內(nèi)業(yè)務(wù)量(分組數(shù)、比特?cái)?shù)等),這樣多分形過(guò)程就可以用于網(wǎng)絡(luò)業(yè)務(wù)的建模。3多分形特性的提出在網(wǎng)絡(luò)業(yè)務(wù)模型的研究中,MuradS.Taqqu的結(jié)論是能夠使用自相似業(yè)務(wù)模型時(shí),沒(méi)有必要采用多分形模型。而Feldmannn和Gilbert等分析了WAN業(yè)務(wù)的多分形特性,得出的結(jié)論是對(duì)WAN業(yè)務(wù)而言,在考慮其短的時(shí)間尺度變化時(shí)需要多分形模型,后來(lái)他們提出了一種復(fù)合模型:短時(shí)間尺度的多分形+長(zhǎng)時(shí)間尺度的LRD模型;美國(guó)萊斯大學(xué)的RudolfH.Riedi等提出了一種基于小波變換的多分形模型(multifractalwaveletmodel,MWM);加州大學(xué)洛杉磯分校的GaoJian-Bo[12～14]提出一種乘法多分形模型。這些模型在對(duì)一些著名的實(shí)測(cè)網(wǎng)絡(luò)業(yè)務(wù)流量數(shù)據(jù)的分析中都表現(xiàn)出比原來(lái)單純使用單分形模型更好的特性。下面主要就后兩種模型進(jìn)行討論。3.1基于多自相似模型的小波模型離散小波變換(discretewavelettransform)用位移和膨脹后的小波函數(shù)ψ(t)以及位移后的比例函數(shù)φ(t)來(lái)替代原來(lái)的信號(hào)X(t),選擇適當(dāng)?shù)男〔ê捅壤瘮?shù),使成為正交基,則信號(hào)X(t)可以表示為其中對(duì)以時(shí)刻0、頻率f0為中心的小波ψ(t),小波因子Wj,k是時(shí)刻2–jk,頻率2jf0時(shí)的信號(hào)內(nèi)容的量度,比例因子Uj,k是時(shí)刻2-jk時(shí)的局部均值的量度。小波變換中,j是分析的尺度:J0表示的是最大的尺度或是最低的分析精度;j越大分析精度越高。Haar小波是最簡(jiǎn)單的正交小波基,其小波和比例函數(shù)見(jiàn)圖3。小波變換可以很好地近似分形布朗運(yùn)動(dòng)(FBm)和分形高斯噪聲(fGn)的Karhunen-Loeve變換。這樣小波變換就可以用于網(wǎng)絡(luò)業(yè)務(wù)的傳統(tǒng)自相似模型中,模擬其LRD特性等。但是真實(shí)的網(wǎng)絡(luò)業(yè)務(wù)本質(zhì)上是正值的,而且其突發(fā)性更強(qiáng),另外除了長(zhǎng)相關(guān)性外,真實(shí)的網(wǎng)絡(luò)業(yè)務(wù)還有短相關(guān)性,這與單純的自相似性不一致。為了使模型中信號(hào)總為正值(與實(shí)際情況相同),有對(duì)所有j,k來(lái)說(shuō),|Wj,k|≤Uj,k,假設(shè)Wj,k=Aj,kUj,k,其中乘子Aj,k是[-1,1]上的獨(dú)立隨機(jī)變量。這就建立了一個(gè)多分形的小波模型(MWM)。如果適當(dāng)?shù)剡x擇Aj,k,與fGn模型一樣,MWM能很好地表示出一組正數(shù)的LRD特性,而且由于MWM的乘法構(gòu)造,MWM還能使其高階統(tǒng)計(jì)特性與實(shí)際情況相符,這是fGn做不到的。圖4為實(shí)際的網(wǎng)絡(luò)業(yè)務(wù)數(shù)據(jù)與分別由WMW和fGn得到的數(shù)據(jù)的比較,可以看到,MWM更好地模擬了實(shí)際情況。乘法過(guò)程用隨機(jī)乘子將一個(gè)節(jié)點(diǎn)流過(guò)的網(wǎng)絡(luò)流量劃分成小的部分,這在時(shí)間尺度小的時(shí)候非常適用于對(duì)網(wǎng)絡(luò)業(yè)務(wù)的模擬。另外由于MWM還能很好的模擬網(wǎng)絡(luò)業(yè)務(wù)的長(zhǎng)相關(guān)性,在已有對(duì)LAN和WAN業(yè)務(wù)的模擬中,可以看到MWM性能的優(yōu)越性。但是WMW需要log2n個(gè)參數(shù),其中n是業(yè)務(wù)流數(shù)據(jù)的長(zhǎng)度,這樣其計(jì)算的復(fù)雜性相應(yīng)就比較大,這也是MWM的一個(gè)缺點(diǎn)。3.2基于數(shù)據(jù)的乘子設(shè)置GaoJian-Bo[12～14]提出了乘法多分形模型來(lái)模擬分組數(shù)據(jù)網(wǎng)絡(luò)的業(yè)務(wù)。此模型包含兩種類(lèi)型:點(diǎn)過(guò)程模型和計(jì)數(shù)過(guò)程模型。這兩種模型都只有1到2個(gè)參數(shù),也就是說(shuō)非常簡(jiǎn)單。GaoJian-Bo在對(duì)著名的Bellcore(現(xiàn)為T(mén)elcordia)給出的網(wǎng)絡(luò)業(yè)務(wù)實(shí)測(cè)數(shù)據(jù)分析以后,發(fā)現(xiàn)LAN和WAN中業(yè)務(wù)流數(shù)據(jù)在一定的時(shí)間尺度范圍內(nèi),其到達(dá)間隔時(shí)間序列與分組長(zhǎng)度序列等點(diǎn)過(guò)程是多分形的;而計(jì)數(shù)過(guò)程雖然只是近似多分形的,但其在視頻變比特率業(yè)務(wù)(VBRtraffic)的業(yè)務(wù)建模中完全適用。另外計(jì)數(shù)過(guò)程在研究網(wǎng)絡(luò)業(yè)務(wù)合成時(shí)比點(diǎn)過(guò)程方便。乘法多分形過(guò)程的構(gòu)造簡(jiǎn)介如下:{Ti}和{Bi}用來(lái)定義實(shí)際網(wǎng)絡(luò)業(yè)務(wù)過(guò)程,{Ti}是到達(dá)間隔時(shí)間序列,其中Ti表示第i與第i+1個(gè)分組之間的到達(dá)間隔時(shí)間,{Bi}表示分組長(zhǎng)度序列,其中Bi表示第i個(gè)分組的長(zhǎng)度。這樣得到的網(wǎng)絡(luò)業(yè)務(wù)稱(chēng)為B流量。在固定分組長(zhǎng)度的網(wǎng)絡(luò)中,設(shè)分組長(zhǎng)度均為,{Ti}同前,這樣得到的網(wǎng)絡(luò)業(yè)務(wù)稱(chēng)為P流量。在網(wǎng)絡(luò)節(jié)點(diǎn)測(cè)得的合成業(yè)務(wù)流被視為隨機(jī)計(jì)數(shù)過(guò)程,表示固定時(shí)間(?t)內(nèi)到達(dá)節(jié)點(diǎn)的比特?cái)?shù)目或分組數(shù)目,分別寫(xiě)為表示第i個(gè)間隔中到達(dá)的比特?cái)?shù),表示第i個(gè)時(shí)隙里到達(dá)的分組數(shù),每個(gè)分組的大小是b個(gè)比特,這些過(guò)程可以直接由B流量和P流量得到,分別稱(chēng)為流量。由?t的選取可以得到網(wǎng)絡(luò)業(yè)務(wù)的多分形性要在一定的尺度范圍內(nèi)才能體現(xiàn)。對(duì)到達(dá)間隔時(shí)間序列與分組長(zhǎng)度序列而言,可以考慮排隊(duì)系統(tǒng)MFe/MFg/1,MFe和MFg表示多分形到達(dá)間隔時(shí)間列和分組大小列的分布分別為雙指數(shù)分布(式(15))和截尾高斯分布(式(16)),選擇適當(dāng)?shù)摩羍和αg,就對(duì)網(wǎng)絡(luò)業(yè)務(wù)建立了模型。圖5是單服務(wù)員FIFO排隊(duì)系統(tǒng)實(shí)測(cè)網(wǎng)絡(luò)業(yè)務(wù)數(shù)據(jù)(虛線)與相應(yīng)的MFe/MFg/1排隊(duì)模型(實(shí)線)得到的等待隊(duì)長(zhǎng)的分布比較,MFe/MFg/1模型的參數(shù)為(αe,αg)=(20,190),圖中三條線的業(yè)務(wù)量強(qiáng)度由上到下分別為ρ=0.7、0.5和0.3。可以證明,MFe/MFg/1模型得到的系統(tǒng)尾分布特性與由實(shí)際情況得到的尾分布特性一致對(duì)計(jì)數(shù)過(guò)程而言,選擇乘子的pdf為選擇參數(shù)對(duì)(p,d),使得到的乘法多分形過(guò)程在系統(tǒng)輕、中、重負(fù)載的情況下都能很好的與實(shí)測(cè)網(wǎng)絡(luò)業(yè)務(wù)相符合。另外注意到對(duì)不算太小的業(yè)務(wù)量強(qiáng)度而言,系統(tǒng)緩存大小超過(guò)一定值時(shí),系統(tǒng)的尾概率幾乎垂直下降,稱(chēng)這一點(diǎn)為膝點(diǎn)(kneepoint),膝點(diǎn)在工程應(yīng)用中很重要,因?yàn)樗容^精確地描述了網(wǎng)絡(luò)業(yè)務(wù)的突發(fā)性。圖6比較了隨業(yè)務(wù)量強(qiáng)度變化的不同業(yè)務(wù)(實(shí)測(cè)與由模型得到的)的膝點(diǎn),圖中,虛線是實(shí)測(cè)業(yè)務(wù),實(shí)線是乘法多分形業(yè)務(wù)模型所得業(yè)務(wù)。3.3主要影響因素多分形模型應(yīng)用與網(wǎng)絡(luò)業(yè)務(wù)的建模時(shí),不但能表現(xiàn)網(wǎng)絡(luò)業(yè)務(wù)的在大的時(shí)間尺度下的突發(fā)性,還能表現(xiàn)單分形模型不能表現(xiàn)的小的時(shí)間尺度下的突發(fā)性,這與多分形過(guò)程本身的多比例特性緊密聯(lián)系在一起。由于小波變換本身固有的比例特性,用小波這個(gè)數(shù)學(xué)工具來(lái)表現(xiàn)多分形是很好的選擇,但是由于小波變換的復(fù)雜性,導(dǎo)致使用小波變換的困難。乘法多分形模型在表現(xiàn)多分形特性時(shí),模型簡(jiǎn)單,參數(shù)比較少,但是在對(duì)實(shí)測(cè)的LAN和WAN中業(yè)務(wù)的計(jì)數(shù)過(guò)程的表示中,不能精確表現(xiàn)網(wǎng)絡(luò)業(yè)務(wù)的多分形特性。另外由于網(wǎng)絡(luò)性質(zhì)的變化很快,在不同網(wǎng)絡(luò)中有不同的表現(xiàn),相應(yīng)參數(shù)就會(huì)改變,那么在網(wǎng)絡(luò)設(shè)計(jì)時(shí),得對(duì)網(wǎng)絡(luò)特性有一個(gè)比較正確的認(rèn)識(shí),使用的模型才能很好地預(yù)測(cè)網(wǎng)絡(luò)的性質(zhì)。對(duì)于網(wǎng)絡(luò)業(yè)務(wù)模型的研究,還會(huì)著眼于其精確性和易實(shí)現(xiàn)性,數(shù)學(xué)工具的選擇非常重要。例如英國(guó)的QueenMaryandWestfieldCollege的RaulJ.MondragonC用混沌映射(chaoticmaps)的方法提出一種業(yè)務(wù)模型來(lái)模擬網(wǎng)絡(luò)業(yè)務(wù),這種研究還在進(jìn)行中。這也是應(yīng)用數(shù)學(xué)的研究方向之一。另外由于我們現(xiàn)在一般網(wǎng)絡(luò)業(yè)務(wù)看作多個(gè)獨(dú)立源業(yè)務(wù)的合成,那么多分形業(yè)務(wù)流的合成是否仍然保持其多分形特性,如果是那么相應(yīng)參數(shù)是否應(yīng)該改變,怎樣改變呢?這也是多分形業(yè)務(wù)研究的一個(gè)方向。在現(xiàn)代移動(dòng)通信(比如第三代移動(dòng)通信)中,引入了越來(lái)越多的除話音以外的業(yè)務(wù),使移動(dòng)通信網(wǎng)中的業(yè)務(wù)也趨向于表現(xiàn)