包對(duì)探測(cè)統(tǒng)計(jì)模型與測(cè)量精度分析

(湖南大學(xué) a.計(jì)算機(jī)與通信學(xué)院；b.軟件學(xué)院， 長(zhǎng)沙 410082)

摘 要：包對(duì)模型(PGM)是探測(cè)可用帶寬的主要方法。該方法存在以下問(wèn)題，影響其推廣應(yīng)用：模型沒(méi)有精確的數(shù)學(xué)模型描述，原有模型假設(shè)流量包長(zhǎng)看做無(wú)限小，與實(shí)際網(wǎng)絡(luò)情況不符合；沒(méi)有定量方法計(jì)算探測(cè)精度、樣本容量，給測(cè)量帶來(lái)不便；沒(méi)有分析互聯(lián)網(wǎng)數(shù)據(jù)包突發(fā)性對(duì)測(cè)量帶來(lái)的影響。為解決以上問(wèn)題，通過(guò)對(duì)包對(duì)模型進(jìn)行數(shù)學(xué)建模的方法，證明了模型正確性；定量分析了測(cè)量精度；確定了樣本數(shù)計(jì)算公式；分析了數(shù)據(jù)包突發(fā)性對(duì)探測(cè)造成的影響；最后對(duì)以上分析進(jìn)行了仿真實(shí)驗(yàn)驗(yàn)證，提高了可用帶寬測(cè)試技術(shù)的精度和可信度。

關(guān)鍵詞：計(jì)算機(jī)網(wǎng)絡(luò)；可用帶寬探測(cè)；包對(duì)模型

中圖分類號(hào)：TP393.06文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1001-3695(2009)04-1438-05

Statistical modeling and accuracy analysis of available bandwidth measurement

LIU Juna，ZHANG Da-fangb，JIN Jun-hangb

(a.School of Computer Communication，b.School of Software， Hunan University， Changsha 410082， China)

Abstract:Available bandwidth measurement is widely applied in a dependable network.This paper proposed probe gap model(PGM) as a lightweight and fast available bandwidth estimation method. But a big problem of PGM was its poor accuracy in certain network conditions. The accuracy could’t be trusted. An important assumption behind the PGM was that the model should be statistical robust even the cross traffic follows do NOT follows fluid model. But no verification could prove this assumption. These problems made tools based on PGM could’t be widely used.Constructed a statistical model for PGM. Based on this insight，presented mathematical verification and accuracy analysis for PGM. And also use modeling， measurements to characterize the interaction between probing packets and bursting network traffic.NS simulation shows the modeling and the accuracy analysis is successful. By the model，can know how much can trust the probing results.

Key words:computer network；available bandwidth probing；probe gap model(PGM)

1 現(xiàn)有技術(shù)分析

可用帶寬的測(cè)量是構(gòu)建可信網(wǎng)絡(luò)的重點(diǎn)問(wèn)題。如網(wǎng)格應(yīng)用就必須不斷探測(cè)可用帶寬[1，2]。相關(guān)算法和模型一直是網(wǎng)絡(luò)測(cè)量領(lǐng)域的研究熱點(diǎn)和難題。在網(wǎng)絡(luò)測(cè)量方面，研究小組已做過(guò)一些工作[3~7]。常見(jiàn)的測(cè)量技術(shù)可分為直接探測(cè)[8~12]和迭代探測(cè)[13~15]兩類。文獻(xiàn)[16]提出了一種新的探測(cè)方法，還需要廣泛實(shí)驗(yàn)驗(yàn)證。直接探測(cè)也就是包對(duì)模型(probe gap model，PGM)，基于網(wǎng)絡(luò)瓶頸分隔原理[17]。該模型也可用來(lái)探測(cè)瓶頸帶寬[18]。其原理如圖1所示。

設(shè)探測(cè)包對(duì)P1和P2的發(fā)送1時(shí)間間隔為gi，輸出時(shí)間間隔為go，已知瓶頸鏈路帶寬為bo。如果探測(cè)包P2到達(dá)瓶頸鏈路時(shí)隊(duì)列不為空，即有背景流量包插入到兩個(gè)探測(cè)包之間，則go為傳輸P2耗時(shí)與傳輸背景流量的耗時(shí)之和。因此，傳輸背景流量的時(shí)間為go-gi，這樣背景流量為

bc=[（go-gi）/gi]bo(1)

則得到可用帶寬A：

A=bo-bc=[1-（g0-gi）/gi]bo(2)

以上模型在以下幾點(diǎn)假設(shè)下成立：a)路徑上所有路由器都使用FIFO排隊(duì)[8]；b)流量服從液體流模型(所有流量包長(zhǎng)看做無(wú)限小)[8]；c）平均流量變化不大，在單次測(cè)量階段看做恒定值[8]；d）瓶頸鏈路惟一，并且也是該鏈路的緊鏈路(可用帶寬最小的鏈路)[8];e)被測(cè)流量與測(cè)量鏈路同流[19]。

研究小組實(shí)驗(yàn)[20]發(fā)現(xiàn)，假設(shè)b)一般是不成立的，流量包長(zhǎng)不能看做無(wú)限小，導(dǎo)致探測(cè)得到go數(shù)值是不斷變化的。其他文獻(xiàn)也作了類似分析[8，11，21]，但都沒(méi)有提出數(shù)學(xué)模型。文獻(xiàn)[8]說(shuō)明go變化的原因是包長(zhǎng)造成的，沒(méi)有對(duì)其作深入研究。文獻(xiàn)[11]從實(shí)驗(yàn)解釋go的變化規(guī)律，得出了似是而非的結(jié)論。

為了通過(guò)變化的go數(shù)值計(jì)算背景流量，現(xiàn)有PGM工具都是采用多次探測(cè)，取go的均值的計(jì)算方法。如Spruce[8]缺省用100個(gè)包對(duì)探測(cè)，Abing[11]缺省采用20個(gè)包對(duì)探測(cè)。在這種情況下，設(shè)E(go)為時(shí)間間隔go的數(shù)學(xué)期望，bc′為根據(jù)實(shí)驗(yàn)結(jié)果計(jì)算得到的bc估計(jì)值。PGM模型表達(dá)式為

bc=[（E(go)-gi）/gi]bo(3) 

bc′=[(o-gi)/gi]bo(4) 

式(4)與理想模型的式(1)是不同的。就以上分析，根據(jù)數(shù)理統(tǒng)計(jì)的思想，為提高網(wǎng)絡(luò)測(cè)量的可信度，本文提出四個(gè)問(wèn)題：a)式(4)的均值模型是否有效？圖1模型過(guò)于簡(jiǎn)單不能說(shuō)明這個(gè)問(wèn)題。現(xiàn)有文獻(xiàn)也都想當(dāng)然地認(rèn)為其正確。b)探測(cè)精度如何度量？式(4)表明，go波動(dòng)嚴(yán)重影響bc′的收斂速度。因此，現(xiàn)有測(cè)量工具的測(cè)量精度波動(dòng)很大，現(xiàn)有文獻(xiàn)中都沒(méi)有給出精度計(jì)算方法。c)如何確定式(4)中均值采樣的次數(shù)(樣本容量)？d)IP流量長(zhǎng)相關(guān)、自相似和大突發(fā)[22，23]的特性對(duì)PGM精度影響有多大？

2 包對(duì)探測(cè)模型建模 

2.1 物理建模

網(wǎng)絡(luò)建模有兩類方法，即離散模型和流體流模型。離散模型以排隊(duì)論的方法來(lái)研究路由器等網(wǎng)絡(luò)核心設(shè)備中的數(shù)據(jù)處理、緩存隊(duì)列的排隊(duì)[24]，獲得的結(jié)果較難用于計(jì)算和評(píng)估。Anick等人[25]在研究多個(gè)ON/OFF信源復(fù)用時(shí)引入了流體流方法(fluid flow methods)。該模型基于時(shí)間對(duì)數(shù)據(jù)變化，把微觀的分組排隊(duì)作宏觀意義上的數(shù)理統(tǒng)計(jì)、求取平均，用常微分方程和數(shù)理統(tǒng)計(jì)模型來(lái)描述IP包傳輸、隊(duì)列管理策略等隨機(jī)過(guò)程。可以把包對(duì)探測(cè)看做是一個(gè)無(wú)反饋多輸入單輸出的過(guò)程控制系統(tǒng)，參照流體流理論和混雜系統(tǒng)[26]的思想，對(duì)包對(duì)探測(cè)的排隊(duì)過(guò)程建模。參量見(jiàn)表1。

表1 PGM模型基本量標(biāo)定

參量The output gap

lcProbing packet length

giThe initial gap， gi=gb

gbThe bottleneck gap， gb=lc/bo

boBottleneck bandwidth

lpTraffic packet length

bcCompete traffic throughput

binBandwidth of traffic enter the bottleneck

gonTime gap of ON period， gon=lp/bin

goffTime gap of OFF period， goff=lp/bc-lp/bin

TThe statistic period，T=gon+goff=lp/bc

Δtoffset of probing packet 1 in T

如圖2所示，瓶頸鏈路只有兩種狀態(tài)交替變化，即ON狀態(tài)和OFF狀態(tài)。當(dāng)處于ON狀態(tài)時(shí)，流量包以峰值速率bin進(jìn)入路由器；處于OFF狀態(tài)時(shí)，該接口空閑。圖中深色為流量包，淺色為探測(cè)包，分別從兩個(gè)輸入接口進(jìn)入路由器輸入隊(duì)列queue1和queue2。排隊(duì)器根據(jù)輸入隊(duì)列上包到達(dá)時(shí)間先后進(jìn)行排隊(duì)，輸出隊(duì)列按照排隊(duì)順序?qū)l(fā)送到輸出接口。IP包最后1 bit到達(dá)路由器接口時(shí)刻記為IP包到達(dá)時(shí)刻，在圖上用數(shù)據(jù)包左方的箭頭表示。設(shè)頭一個(gè)流量包首位到達(dá)時(shí)刻到下一個(gè)流量包首位到達(dá)時(shí)刻為一個(gè)ON/OFF統(tǒng)計(jì)周期，記為T。探測(cè)首包到達(dá)隊(duì)列時(shí)刻在T中的偏移量記為Δt。

把發(fā)出一對(duì)探測(cè)包看做一次隨機(jī)事件。因?yàn)榘l(fā)送端是隨機(jī)時(shí)間發(fā)包對(duì)，探測(cè)首包可能在任何時(shí)候到達(dá)，Δt落在[0，T]的任何位置的可能性是相等的。根據(jù)連續(xù)型均勻分布的定義，Δt是在[0，T]連續(xù)均勻分布的隨機(jī)變量。下面證明中將詳細(xì)分析探測(cè)包與流量包互相影響的各種情況。

2.2 PGM模型統(tǒng)計(jì)穩(wěn)定性證明

將式(3)改寫為

E(go)=gi+(bc/bo)gi=（lc/bo）(1+bc/bo)(5)

需要證明，式(3)的均值模型成立。如果求出go的數(shù)學(xué)期望符合式(5)，則證明成功。證明思路是通過(guò)概率模型，求出go的概率分布函數(shù)進(jìn)而求出go的數(shù)學(xué)期望E(go)。以下公式推導(dǎo)經(jīng)過(guò)了工具包Microsoft Math 3.0[27]的驗(yàn)證。

證明 根據(jù)探測(cè)包輸入包間距gi取值和探測(cè)包的大小，有四種探測(cè)包與流量包的排列情況。分別計(jì)算這四種情況下go的概率分布函數(shù)和數(shù)學(xué)期望。采用分類—?dú)w納的方法討論。

情況1 gi

由于Δt在[0，T]連續(xù)均勻分布，再細(xì)分為三種情況：

a)當(dāng)Δt∈[0，gon-gi]時(shí)，Δt落在圖3中①~②區(qū)間，包對(duì)間不能夾進(jìn)包。這時(shí)go=gb。

b)當(dāng)Δt∈[gon-gi，gon]時(shí)，Δt落在圖3中②~③區(qū)間，包對(duì)間夾進(jìn)一個(gè)包。go=gb+lp/bo。

c)當(dāng)Δt∈[gon，T]時(shí)，Δt落在圖3中③~④區(qū)間，包對(duì)間不能夾進(jìn)包。go=gb。

綜合圖3(a)~(c)三種情況下go的取值繪制成概率分布函數(shù)曲線如圖3(e)所示。根據(jù)以上得到的概率分布函數(shù)和均勻分布的數(shù)學(xué)期望計(jì)算公式，有

E(go)=∫gon-gi0godt+

∫gongon-gigodt+∫Tgongodt=

[(T-gi)gb+gi(gb+lp/bo)]/T=（lc/bo）(1+bc/bo)

情況2 T>gi>gon時(shí)，這時(shí)可能夾入0~1個(gè)包。類似情況1分析，如圖3(b)所示。

a)當(dāng)Δt∈[0，gon]時(shí)，包對(duì)間夾進(jìn)一個(gè)包。go=gb+lp/bo。

b)當(dāng)Δt∈[gon，T+gon-gi]時(shí)，包對(duì)間不能夾進(jìn)包。go=gb。

c)當(dāng)Δt∈[T+gon-gi，T]時(shí)，包對(duì)間夾進(jìn)一個(gè)包。go=gb+lp/bo。

E(go)=∫gon0godt+∫gon+T-gigongodt+∫Tgon+T-gigodt=

[(T-gi)gb+gi(gb+lp/bo)]/T=(lc/bo)(1+bc/bo)

情況3 nT

a)當(dāng)Δt∈[0，nT+gon-gi]時(shí)，包對(duì)間夾進(jìn)n個(gè)包。go=gb+nlp/bo。

b)當(dāng)Δt∈[nT+gon-gi，gon]時(shí)，包對(duì)間夾進(jìn)n+1個(gè)包。go=gb+(n+1)lp/bo。

c)當(dāng) Δt∈[gon，T]時(shí)，包對(duì)間夾進(jìn)n個(gè)包。go=gb+nlp/bo。

E(go)=∫nT+gon-gi0godt+∫gonnT+gon-gigodt+∫Tgongodt={[(n+1)T-gi][gb+n lp/bo+(gi-nT)][gb+(n+1)lp/bo]}/T=(lc/bo)(1+bc/bo)

情況4 (n+1)T>gi>gon+nT(n=1，2，3，…) 時(shí)，可能夾入n或n+1個(gè)包，如圖3（d）所示；同理有

a)當(dāng)Δt∈[0，gon]時(shí)，包對(duì)間夾進(jìn)n+1個(gè)包。go=gb+(n+1)lp/bo。

b)當(dāng)Δt∈[gon，nT+gon-gi]時(shí)，包對(duì)間夾進(jìn)n個(gè)包。go=gb+n lp/bo。

c)當(dāng)Δt∈[nT+gon-gi，T]時(shí)，包對(duì)間夾進(jìn)n+1個(gè)包。go=gb+(n+1)lp/bo。

E(go)=∫gon0godt+

∫nT+gon-gigongodt+∫TnT+gon-gigodt={[(n+1)T-gi][gb+n lp/bo+(gi-nT)][gb+(n+1)lp/bo]}/T=(lc/bo)(1+bc/bo)

綜合情況1~4，四類情況覆蓋了所有g(shù)i和Δt可能的取值組合，E(go)=lc/bo(1+bc/bo)始終恒定。證畢。

3 包對(duì)探測(cè)模型精度分析

大量實(shí)測(cè)數(shù)據(jù)表明，基于PGM模型的測(cè)量工具測(cè)量精度隨參數(shù)設(shè)定和網(wǎng)絡(luò)狀況波動(dòng)很大。為確定網(wǎng)絡(luò)測(cè)量可信度，下面對(duì)PGM探測(cè)的方差和變異系數(shù)進(jìn)行分析。 

3.1 樣本方差

下面給出樣本方差的完整推導(dǎo)過(guò)程。利用方差性質(zhì)：D(bc)=E(bc2)-(E(bc))2，已知(E(bc))2=bc2，求出數(shù)學(xué)期望 E(bc2) 即可得到方差。由gi=gb=lc/bo代入式(3)有

bc=bo[E(go)-gi]/gi=[E(go)bo2/lc]-bo(6)

需求出

E(bc2)=E((E(go)(bo2)/lc-bo)2)=E[(E(go))2bo4/lc2]-E[2E(go)bo2/lc]+bo2(7)

將式(7)分三部分分別求解。在不同探測(cè)包間距gi取值和探測(cè)包的大小情況下，有兩類探測(cè)包與流量包的排列情況。兩類情況式(7)求解方法不同。類似2.2節(jié)，分情況進(jìn)行討論。

情況1 gi

根據(jù)圖3（a）和（b） go的概率分布曲線有

E[(E(go))2bo4/lc2]=bo4E[E2(go)/lc2]=bo4(

∫gon-gi0(go/lc)2dt+∫gongon-gi(go/lc)2dt+∫Tgon(go/lc)2dt)=lpbobc/lc+2bobc+bo2(8)

同樣通過(guò)積分可以得到

E[2E(go)bo2/lc]=2bobc+2bo2(9)

將式(8)(9)的結(jié)果代入式(7)，得到

D(bc)=E(bc2)-(E(bc))2=lpbobc/lc-bc2(10)

情況2 nTgi>gon+nT(n=1，2，3，…)，包對(duì)間可能夾入n~n+1個(gè)包。

將式(7)分三部分分別求解，根據(jù)圖3（c）、（d） go的概率分布曲線按類似式(8)的積分方法可求出：

E[（E（go）)2bo4/lc2]=

-n2bo2lp2/lc2-nbo2lp2/lc2+2nlpbobc/lc+lpbobc/lc+2bobc+bo2(11)

E[2E(go)bo2/lc]=2bobc+2bo2(12)

由式(11)(12)的結(jié)果代入式(7)有

D(bc)=E(bc2)-(E(bc))2=-n2lp2bo2/lc2-nlp2bo2/lc2+2nlpbobc/lc+lpbobc/lc-bc2(13)

由于倍數(shù)n可以寫成n=[lcbc/lpbo]，代入式(13)得到

D(bc)=-（[lcbc/lpbo])2lp2bo2/lc2

-[lcbc/lpbo]lp2bo2/lc2+2[lcbc/lpbo]lpbobc/lc

+lpbobc/lc-bc2(14)

可以看出式(10)為式(14)取n=0的情況，因此，樣本方差D(bc)可以歸結(jié)為式(14)所示。樣本方差表征的量是絕對(duì)誤差。標(biāo)準(zhǔn)差為D(bc)與待測(cè)流量bc綱量相同。

3.2 樣本方差和變異系數(shù)分析

實(shí)際測(cè)量中相對(duì)誤差更為重要。因此，本文引入變異系數(shù)CV (coefficient of variation)描述相對(duì)誤差。變異系數(shù)是表征相對(duì)誤差的一個(gè)無(wú)綱量的值。由定義可知：

CV=D(bc)/E(bc)=1/bc-[lcbc/lpbo]2lp2bo2/lc2-[lcbc/lpbo]lp2bo2/lc2+2[lcbc/lpbo]lpbobc/lc+lpbobc/lc-bc2(15)

從式(15)可以看出，CV是一個(gè)較復(fù)雜的多元函數(shù)。由于Gauss函數(shù)[lcbc/lpbo]造成式(15)無(wú)法求導(dǎo)，下面只能采用繪制曲線分析。由于[lcbc/lpbo]取值不同，有兩種情況：a)giT時(shí)，式(15)為多峰曲面。為了保證典型性，下面對(duì)全部取n=[lcbc/lpbo]≥1時(shí)多峰的情況進(jìn)行分析。

3.2.1 變異系數(shù)與背景流量包長(zhǎng)lp的關(guān)系分析

根據(jù)方差，設(shè)定速率bc=3 Mbps，瓶頸鏈路帶寬bo=10 Mbps，探測(cè)包長(zhǎng)lc=0.008 MB，lp取0~1 500 Byte，取背景流量包長(zhǎng)lp為y軸，繪制式(15)曲線，如圖4所示。從曲線可以看出：lp＜lcbc/bo時(shí)，隨流量包長(zhǎng)增加，CV(bc)呈周期性變化。周期逐漸增大，峰值也隨之增大。求出峰值連線：CV(bc)max=lpbo/2lcbc。因此，在背景流量包長(zhǎng)lp＜2bc/bo時(shí)，CV(bc)max是線性增加的。

當(dāng)lp＞lcbc/bo時(shí)，

CV=1/bclpbobc/lc-bc2(16)

當(dāng)lp＞2lcbc/bo時(shí)，

CV(bc)max=CV(bc)=CV=1/bclpbobc/lc-bc2(17)

CV(bc)max實(shí)際測(cè)量時(shí)很有用，因?yàn)閘p常常測(cè)不準(zhǔn)，必須用CV(bc)max代替式(15)估計(jì)CV。

3.2.2 變異系數(shù)與背景流量bc關(guān)系分析

取鏈路帶寬bo=100 Mbps，探測(cè)包長(zhǎng)lc=0.008 MB，流量包長(zhǎng)lp=0.004 MB，bc取0~100 MB，繪制式(15)CV曲線，如圖5所示。可以看出：求出圖形峰值切線為最壞情況估算。曲線說(shuō)明：隨流量增加，變異系數(shù)振幅隨之減小。這說(shuō)明流量越小越難測(cè)準(zhǔn)。而流量較大時(shí)，曲線趨近于水平，這說(shuō)明流量繼續(xù)增大已經(jīng)對(duì)探測(cè)精度影響不大。

3.2.3 變異系數(shù)與探測(cè)包長(zhǎng)lc關(guān)系分析

取速率bc=8 Mbps，瓶頸鏈路帶寬bo=10 Mbps，背景流量包長(zhǎng)lp=0.004 MB，繪制式(15)CV曲線，如圖6所示，可以看出：隨著探測(cè)包長(zhǎng)lc增加，變異系數(shù)的振蕩幅值隨之減小。這說(shuō)明探測(cè)包長(zhǎng)lc較小時(shí)，測(cè)量精度很低，這是PGM工具都使用大探測(cè)包的原因。在某些點(diǎn)出現(xiàn)了變異系數(shù)為零的情況，這說(shuō)明在某種探測(cè)包長(zhǎng)情況下，可以對(duì)流量(均勻流)進(jìn)行完美探測(cè)，一次采樣就可以得到準(zhǔn)確結(jié)果。而探測(cè)包長(zhǎng)lc較大時(shí)，曲線趨近于水平，這說(shuō)明探測(cè)包長(zhǎng)lc繼續(xù)增大已對(duì)精度影響不大。

3.2.4 變異系數(shù)與瓶頸帶寬bo關(guān)系分析

取bc=8 Mbps，探測(cè)包長(zhǎng)lc=0.008 MB，背景流量包長(zhǎng)lp=0.004 MB，繪制式(15)CV曲線，如圖7所示。可以看出：隨著瓶頸帶寬bo增加，變異系數(shù)的振蕩幅值隨之增大。這說(shuō)明瓶頸帶寬與變異系數(shù)的最壞估計(jì)成正比。瓶頸帶寬越大，探測(cè)相對(duì)精度越低；在瓶頸帶寬大到一定時(shí)，CV就不再按照線性趨勢(shì)增長(zhǎng)；在bo趨近于無(wú)窮時(shí)，CV接近水平線。

4 包對(duì)探測(cè)模型樣本容量計(jì)算

4.1 包對(duì)探測(cè)模型與樣本容量分析

樣本容量是確保對(duì)總體具有代表性的樣本包含的單位數(shù)。如何選取可用帶寬探測(cè)樣本容量一直是一個(gè)困難的問(wèn)題。樣本過(guò)大會(huì)增加測(cè)量流量，延長(zhǎng)測(cè)量時(shí)間；過(guò)小會(huì)使誤差增大甚至測(cè)量失敗。確定樣本容量必須解決精度和置信度兩個(gè)問(wèn)題。為計(jì)算樣本容量，首先分析go的分布。根據(jù)2.2節(jié)，顯見(jiàn)go隨著夾包數(shù)目隨機(jī)變化，是一個(gè)多峰的分布模型。但go的均值如何變化？根據(jù)林德伯格—列維(Lindberg-Levy)定理，獨(dú)立同分布、且數(shù)學(xué)期望和方差有限的隨機(jī)變量序列的標(biāo)準(zhǔn)化和以標(biāo)準(zhǔn)正態(tài)分布為極限。因此，在測(cè)量樣本數(shù)量較大時(shí)，包對(duì)延遲go均值go近似服從正態(tài)分布。測(cè)量目的是求b′c的分布。根據(jù)式(4)，可知

go與b′c同分布。因此b′c也近似服從正態(tài)分布。所以可按照標(biāo)準(zhǔn)正態(tài)分布計(jì)算樣本容量。

4.2 根據(jù)方差計(jì)算樣本容量

根據(jù)4.1節(jié)，按照正態(tài)整體求解樣本容量，計(jì)算公式為

N=D（b′c）Z2/e2(18)

其中：N表示樣本容量；z為置信度水平；D(b′c)為樣本方差；e為樣本估計(jì)值絕對(duì)誤差。從式(18)可知，樣本容量與樣本方差成正比，與絕對(duì)誤差成反比。舉例說(shuō)明：當(dāng)流量包長(zhǎng)為lp=1 500 Byte，探測(cè)包長(zhǎng)lc=0.006 MB，瓶頸帶寬10 Mbps，要對(duì)約為1 MB的數(shù)據(jù)流進(jìn)行探測(cè)，誤差0.3 MB內(nèi)，置信度95%，由式(14)得到D（bc）=lpbobc/lc-bc2=19，需要采樣數(shù)為N=D(b′c)Z2/e2=811次。

4.3 根據(jù)由變異系數(shù)計(jì)算樣本容量

可以根據(jù)變異系數(shù)計(jì)算樣本容量，計(jì)算公式為

N=CV2Z2/m2(19)

其中：z為置信度水平；CV為變異系數(shù)(%)；m為相對(duì)偏差(%)。

5 互聯(lián)網(wǎng)鏈路測(cè)量與流量突發(fā)性評(píng)估

5.1 PGM互聯(lián)網(wǎng)鏈路測(cè)量的一些考慮

互聯(lián)網(wǎng)上，流量具有突發(fā)性、長(zhǎng)范圍相關(guān)性和自相似性[22，23]的特征。包長(zhǎng)度分布得也是不均勻的，具有一定的經(jīng)驗(yàn)分布[28]。因此，互聯(lián)網(wǎng)進(jìn)行測(cè)量時(shí)，必須估算突發(fā)性對(duì)PGM模型的擾動(dòng)，才能確定PGM測(cè)量的準(zhǔn)確度和精密度。可以證明包對(duì)探測(cè)模型為一個(gè)平穩(wěn)隨機(jī)過(guò)程，在互聯(lián)網(wǎng)上PGM模型仍然是準(zhǔn)確的。但是鏈路數(shù)據(jù)包突發(fā)性造成測(cè)量輸出方差加大。為了求出PGM模型方差，下面通過(guò)定義突發(fā)因子Bu，求出變異系數(shù)估計(jì)公式。

5.2 突發(fā)因子

下面仍采用ON/OFF模型評(píng)估流量突發(fā)。在業(yè)務(wù)流量平均強(qiáng)度不變的條件下，OFF狀態(tài)的時(shí)間間隔goff的方差越大，則表示突發(fā)強(qiáng)度越大。

定義 OFF狀態(tài)的時(shí)間間隔的方差D(goff)為該鏈路在某時(shí)刻的突發(fā)因子Bu。

采樣某一鏈路IP包，采樣得到n+1個(gè)包的首、末位到達(dá)時(shí)間{t1，t2，t3，…，t2n-2，t2n-1}，有

Bu=D(goff)=nj=1(goff j-E(goff))2=

nj=1（(t2j-t2j-1)-1/nnk=1(t2k-t2k-1))2(20)

5.3 互聯(lián)網(wǎng)鏈路測(cè)量變異系數(shù)估算方法

Bu最小為零，數(shù)據(jù)流為均勻流。Bu取最大值說(shuō)明采樣周期內(nèi)全部的數(shù)據(jù)包連接在一起。

Bumax=D(goff)max=n(E(goff))2=1/nnk=1(t2k-t2k-1)2(21)

可以把多個(gè)數(shù)據(jù)包看成一個(gè)大的ON過(guò)程。可證明ON過(guò)程長(zhǎng)度l′p與Bu線性相關(guān)且成正比。所以O(shè)N過(guò)程長(zhǎng)可以近似看成：

l′p≈nE(lp)[Bu(goff)/Bu(goff)max](22)

l′p用來(lái)代替lp，計(jì)算方差和變異系數(shù)。實(shí)驗(yàn)證明這種估計(jì)方法是有效的。由于l′p是一個(gè)期望值，變異系數(shù)只能用最壞情況計(jì)算，公式為

0＜l′p＜lcbc/bo時(shí)，CV′(bc)=CV(bc)max=2bol′p/bc

l′p≥lcbc/bo時(shí)，CV′(bc)=CV(bc)max=1/bcbcbol′p/lc-bc2(23)

6 仿真實(shí)驗(yàn)

6.1 仿真實(shí)驗(yàn)說(shuō)明

對(duì)PGM模型進(jìn)行NS-2[29]仿真。拓?fù)淙鐖D8所示。設(shè)置探測(cè)包發(fā)送端 Probe Sender和三個(gè)CBR流的發(fā)送端CBR1、CBR2和CBR3。路由器R1和R2均采用FIFO排隊(duì)策略。實(shí)驗(yàn)?zāi)繕?biāo)是驗(yàn)證PGM模型的準(zhǔn)確性式(4)與精度式(14)、樣本容量式(18)。

實(shí)驗(yàn)采用了文獻(xiàn)[30]提出的分層采樣算法。在每個(gè)樣本時(shí)間單元內(nèi)，隨機(jī)地選擇時(shí)刻進(jìn)行網(wǎng)絡(luò)流量數(shù)據(jù)采樣。探測(cè)包采用背靠背的UDP包對(duì)，根據(jù)對(duì)鏈路帶寬與發(fā)送包長(zhǎng)的關(guān)系計(jì)算包對(duì)內(nèi)發(fā)送間隔。

實(shí)驗(yàn)進(jìn)行了一次4 000個(gè)包對(duì)的連續(xù)測(cè)量和四組32次組合測(cè)量。測(cè)量方差按樣本容量累計(jì)后取均值。測(cè)量按照計(jì)算出的方差大小來(lái)估計(jì)測(cè)量樣本，取置信度因子為0.90，取實(shí)驗(yàn)誤差最大值為0.521 7 M。這時(shí)式(18)計(jì)算出采樣次數(shù)恰好是方差的10倍。

6.2 測(cè)量結(jié)果

6.2.1 連續(xù)測(cè)量結(jié)果

為了能夠連續(xù)輸出結(jié)果，參考Spruce[2]將結(jié)果進(jìn)行連續(xù)滑動(dòng)窗口平均。由式(14)求得D(b′c)=36，取窗口為360，即360次采樣平均。取CBR1-3流的速率bc=3 Mbps，瓶頸鏈路帶寬bo=10 Mbps，探測(cè)包長(zhǎng)lc=0.008 MB，背景流量包長(zhǎng)lp=1 500 Byte。實(shí)驗(yàn)共進(jìn)行200 s，共發(fā)出4 000個(gè)包對(duì)。測(cè)量結(jié)果如圖9所示。b′c輸出在標(biāo)準(zhǔn)值3MB上下振動(dòng)。由于采樣數(shù)據(jù)不夠360個(gè)，開(kāi)始18 s沒(méi)有輸出。

6.2.2 組合測(cè)量結(jié)果

共進(jìn)行四組32次測(cè)量。第一組測(cè)量調(diào)整背景流量包長(zhǎng)，第二組測(cè)量調(diào)整背景流量，第三組測(cè)量調(diào)整探測(cè)包長(zhǎng)，第四組測(cè)量調(diào)整瓶頸帶寬。測(cè)量詳細(xì)參數(shù)和結(jié)果如圖10和表2所示。由表2的測(cè)量結(jié)果可見(jiàn)，PGM模型準(zhǔn)確度和模型精確度計(jì)算公式都得到很好驗(yàn)證：探測(cè)背景流量b′c與設(shè)置流量非常符合，誤差符合估計(jì)。方差測(cè)量值和式(14)方差計(jì)算值非常符合，絕對(duì)誤差符合預(yù)期。四組32輪測(cè)量，共發(fā)現(xiàn)4個(gè)異常點(diǎn)誤差絕對(duì)值超出預(yù)期的0.521 7 MB，87.5%的數(shù)值在誤差范圍內(nèi)，與設(shè)置的置信度90%很接近。樣本容量公式得到很好驗(yàn)證。雖然樣本量不大，但實(shí)驗(yàn)結(jié)果說(shuō)明b′c的分布與正態(tài)總體的符合度很高。

表2 各種網(wǎng)絡(luò)條件下組合測(cè)量環(huán)境與測(cè)量結(jié)果

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

從統(tǒng)計(jì)的觀點(diǎn)來(lái)看，現(xiàn)有的包對(duì)模型沒(méi)有精確的數(shù)學(xué)模型描述，在準(zhǔn)確性和精確性方面存在問(wèn)題。本文在解決這些問(wèn)題上做了一些工作，為基于PGM帶寬探測(cè)工具開(kāi)發(fā)提供了數(shù)學(xué)模型。小組開(kāi)發(fā)的探測(cè)工具可以通過(guò)調(diào)節(jié)模型參數(shù)適應(yīng)變化的網(wǎng)絡(luò)情況以滿足測(cè)量對(duì)精度的要求。該模型和測(cè)量工具，在Internet初步測(cè)量效果很好。研究小組正在進(jìn)行進(jìn)一步規(guī)模測(cè)試。

參考文獻(xiàn)：

［1］

GGF Network Measurement Working Group(NMWG)[EB/OL].http://nmwg.internet2.edu/.

[2]EGEE R-GMA.Relational grid monitoring architecture[EB/OL].http://www.r-gma.org/.

[3]黎文偉，張大方，楊金民，等.端到端路徑容量測(cè)量工具性能分析[J].計(jì)算機(jī)應(yīng)用，2006，26(10):2275-2277.

[4]LI Wen-wei，ZHANG Da-fang，YANG Jin-min，et al.On evaluating the differences of TCP and ICMP in network measurement[J].Compu-ter Communications，2007，30(2):428-439.

［5］謝鯤，張大方，文吉?jiǎng)偅?基于Winpcap的實(shí)時(shí)網(wǎng)絡(luò)流量監(jiān)測(cè)系統(tǒng)[J].湖南大學(xué)學(xué)報(bào)，2006，33(2):118-121.

[6]范超，謝高崗，張大方，等.基于主動(dòng)測(cè)試的HTTP業(yè)務(wù)性能分析[J].計(jì)算機(jī)研究與發(fā)展，2005，42(3):493-500.

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

[8]STRAUSS J，KATABI D，KAASHOEK F.A measurement study of available bandwidth estimation tools[C]//Proc of ACM SIGCOMM Conference on Internet Measurement.2003.

[9]IBEIRO V，COATES M，RIEDI R，et al.Multifractal cross traffic estimation[C]//Proc ofITC Specialist Seminar on IP Traffic Measurement， Modeling，and Management.2000.

[10]CARTER R L，CROVELLA M E.Measuring bottleneck link speed in packet-switched networks[C]//Proc of Perform Evaluation.1996:297-318.

[11]NAVRATIL J，ABW E.A practical approach to available bandwidth[C]//Proc ofPAM.2003.

[12]HU Ning-ning，STEENKISTE P.Evaluation and characterization of available bandwidth probing techniques [J].IEEE Journal on Selected Areas in Communications SAC Special Issue in Internet and WWW Measurement，Mapping，and Modeling，2003，21(6)：879-894.

[13]JAIN M，DOVROLIS C.End to end available bandwidth，measurement methodology，dynamics，and relation with TCP throughput[C]//Proc of ACM SIGCOMM ’02.2002.

[14]MELANDER B，BJORKMAN M，GUNNINGBERG P.A new end to end probing and analysis method for estimating bandwidth bottlenecks[C]//Proc ofIEEE GLOBECOM.2000.

[15]PASZTOR A.Accurate active measurement in the Internet and its applications[D].Victoria:Department of Electrical and Electronic Engineering，University of Melbourne，2003.

[16]劉敏，李忠誠(chéng)，過(guò)曉冰，等.端到端的可用帶寬測(cè)量方法[J].軟件學(xué)報(bào)，2006，17(1):108-116.

[17]KESHAV S.A control-theoretic approach to flow control[C]//Proc of ACM SIGCOMM.1991.

[18]謝高崗，李忠誠(chéng)，張大方，等.鏈路帶寬測(cè)量方法改進(jìn)[J].計(jì)算機(jī)研究與發(fā)展，2003，40(1):68-74.

[19]LI Lao，DOVROLIS C，SANADIDI Y M.The probe gap model can underestimate the available bandwidth of multihop paths[C]//Proc of ACM SIGCOMM Computer Communications Review.2006:29-34.

[20]黎文偉，王俊峰，謝高崗，等.基于包對(duì)采樣的IP網(wǎng)絡(luò)時(shí)延變化測(cè)量方法[J].計(jì)算機(jī)研究與發(fā)展，2004，41（8）：1352-1360.

[21]畢經(jīng)平，吳起，李忠誠(chéng).Internet延遲瓶頸的測(cè)量與分析[J].計(jì)算機(jī)學(xué)報(bào)，2003，26(4):406-416.

[22]PAXSON V，F(xiàn)LOYD S.Wide area traffic:the failure of poisson mode-ling[J].IEEE/ACM Trans on Networking，1995，3(3):226-244.

[23]LELAND W E，TAQQU M S，WILLINGER W，et al.On the self-similar nature of ethernet traffic (extended version)[J].IEEE/ACM Trans on Networking，1994，2(1):1-15.

[24]ROBERTAZZI T G.Computer networks and systems[M].[S.l.]:Springer，2000.

[25]ANICK D，MITRA D，SONDHI M M.Stochastic theory of a data handling system with multiple sources [J].Bell System Technical Journal，1982，61(8):1871-1894.

[26]HESPANHA J P，BOHACEK S，OBRACZKA K，et al.Computation and control[M].Berlin:Springer-Verlag，2001.

[27]Microsoft student with encarta premium[EB/OL].(2007).http://support.microsoft.com.

[28]SINHA R，PAPADOPOULOS C，HEIDEMANN J.Internet packet size distributions;some observations[EB/OL].(2005).http://www.isi.edu/~johnh/ PAPERS/Sinha07a.html.

[29]NS-2[EB/OL].http://www.isi.edu/nsnam/ns.

[30]CLAFFY K，POLYZOS G，BRAUM H.Application of sampling methodologies to network traffic characterization[J].Computer Communication Review，1993，23(4):194-203.