一種基于Pathload改進(jìn)的網(wǎng)絡(luò)可用帶寬測(cè)量方法

李稚春

摘 要：網(wǎng)絡(luò)可用帶寬是評(píng)價(jià)網(wǎng)絡(luò)性能的重要指標(biāo)之一，快速、準(zhǔn)確地測(cè)量網(wǎng)絡(luò)可用帶寬對(duì)網(wǎng)絡(luò)監(jiān)測(cè)、擁塞控制、網(wǎng)絡(luò)流量工程等具有重要意義。在分析傳統(tǒng)Pathload測(cè)量網(wǎng)絡(luò)可用帶寬算法的基礎(chǔ)上，針對(duì)其測(cè)量開(kāi)銷大、收斂速度慢等缺點(diǎn)，提出了一種改進(jìn)方法。該方法完善了Pathload的判斷準(zhǔn)則，進(jìn)一步改進(jìn)了發(fā)送速率調(diào)整算法，NS2仿真結(jié)果表明，提出的改進(jìn)算法在提高了測(cè)量準(zhǔn)確性的同時(shí)，可以降低測(cè)量開(kāi)銷，收斂速度明顯加快。

關(guān)鍵詞：帶寬測(cè)量；網(wǎng)絡(luò)可用帶寬；仿真；Pathload

中圖分類號(hào)：TP393.1 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：2095-1302（2015）05-00-03

0 引 言

網(wǎng)絡(luò)帶寬是指單位時(shí)間內(nèi)鏈路上能夠通過(guò)的最大數(shù)據(jù)位，可用帶寬是指在不影響網(wǎng)絡(luò)路徑背景數(shù)據(jù)流的情況下，端到端通信所能獲得的最大數(shù)據(jù)傳輸率[1]，二者的單位均為b/s。對(duì)于一個(gè)端到端網(wǎng)絡(luò)傳輸系統(tǒng)，可用帶寬具有很高的實(shí)用價(jià)值，網(wǎng)絡(luò)可用帶寬對(duì)網(wǎng)絡(luò)負(fù)載均衡、傳輸速率控制、網(wǎng)絡(luò)擁塞控制等有很重要的意義。設(shè)鏈路帶寬為C b/s，帶寬利用率為u b/s，端到端鏈路跳數(shù)為H，當(dāng)前可用帶寬為A b/s，則有：

（1）

（2）

（3）

目前，測(cè)量端到端鏈路可用帶寬的方法主要分為單端測(cè)量和雙端測(cè)量[2]，單端測(cè)量模式只需在測(cè)量的一端安裝測(cè)試軟件，便可得到鏈路的可用帶寬；雙端測(cè)量模式需要在客戶端和服務(wù)器上都安裝測(cè)試軟件。兩者相比，單端測(cè)量系統(tǒng)實(shí)現(xiàn)比較方便，但測(cè)量精度不如雙端測(cè)量系統(tǒng)。表1列舉了幾種常見(jiàn)網(wǎng)絡(luò)可用帶寬的測(cè)量方法，其中單端測(cè)量方法包括：Cprobe[3]、Pipechar[2]、SProbe[4]、Abget[5]、ICMP-SLoPS[6]；雙端測(cè)量方法包括：Delphi[7]，Pathload[1，8]，Pathchirp[9]，IGI[10]，Spruce[11]，TOPP[12]。

上述測(cè)量網(wǎng)絡(luò)帶寬的方法中，Pathload方法測(cè)量精度最高，但由于其采用自擁塞探測(cè)數(shù)據(jù)流方式，測(cè)量時(shí)間及測(cè)量開(kāi)銷較大，使用該方法測(cè)量一次可用帶寬大約需要花費(fèi)十幾秒的時(shí)間，向網(wǎng)絡(luò)中注入大約1 MB的探測(cè)包，在測(cè)量期間很難保證網(wǎng)絡(luò)流量不發(fā)生變化。而用Pathchirp方法測(cè)量一次網(wǎng)絡(luò)可用帶寬只需花費(fèi)幾秒的時(shí)間，只需要向網(wǎng)絡(luò)中注入200 kB左右的探測(cè)流數(shù)據(jù)。

表1 網(wǎng)絡(luò)可用帶寬測(cè)量分類 方法名稱 通信協(xié)議 技術(shù)特點(diǎn) 年份

單

端

測(cè)

量 Cprobe ICMP 直接計(jì)算可用帶寬 1996

Pipechar ICMP 包對(duì)測(cè)量技術(shù) 2001

SProbe TCP 基于TCP和HTTP協(xié)議 2002

Abget TCP 產(chǎn)生“偽造的”ACK信號(hào) 2005

ICMP-SLoPS ICMP 應(yīng)用在IPv6網(wǎng)絡(luò) 2008

雙

端

測(cè)

量 Delphi UDP 指數(shù)遞增分組探測(cè) 2000

Pathload TCP 自載周期流 2001

Pathchirp TCP 探測(cè)間隔呈指數(shù)遞減 2002

IGI TCP 發(fā)送包對(duì)序列 2003

Spruce TCP 采用探測(cè)間隔模型 2004

TOPP TCP 分組對(duì)序列 2005

此外，上述測(cè)量方法都是基于2個(gè)假設(shè)條件：網(wǎng)絡(luò)負(fù)載在路由節(jié)點(diǎn)呈先進(jìn)先出隊(duì)列；網(wǎng)絡(luò)為流體模型，且背景流在測(cè)量周期內(nèi)保持不變。

1 Pathload測(cè)量可用帶寬原理

Pathload采用自載周期流探測(cè)技術(shù)（Self-Loading Periodic Streams，SLoPS）測(cè)量端到端鏈路的有效帶寬。在發(fā)送端以一定速率R向接收端發(fā)送周期性探測(cè)流，通過(guò)分析數(shù)據(jù)包到達(dá)接收端的單向延時(shí)（One-Way Delay，OWD）的分布趨勢(shì)，判斷周期流的發(fā)送速率與端到端鏈路有效帶寬之間的關(guān)系。通過(guò)二分法不斷調(diào)整探測(cè)流的發(fā)送速率，使其逼近鏈路的有效帶寬。

定義[1]：如果發(fā)送速率R>可用帶寬A，則單向時(shí)延差ΔDk>0，呈現(xiàn)上升趨勢(shì)；如果發(fā)送速率R <可用帶寬A，則ΔDk≈0或者趨勢(shì)不明顯。

設(shè)R0為第1組數(shù)據(jù)包的發(fā)送速率，C1為第1個(gè)路由節(jié)點(diǎn)的帶寬，A1為第1個(gè)路由節(jié)點(diǎn)的可用帶寬容量，u1為第1個(gè)路由器的帶寬利用率。

如果R0>A1，則：

A1=（1-u1）C1=C1-u1C1 （4）

R0+u1C1=R0+（C1-A1）=C1+（R0-A1）>C1 （5）

式（5）說(shuō)明第1個(gè)路由節(jié)點(diǎn)已經(jīng)開(kāi)始出現(xiàn)數(shù)據(jù)包積壓，即存在排隊(duì)時(shí)延。設(shè)tk為第k個(gè)數(shù)據(jù)包的到達(dá)時(shí)間，T=L/R0，則在時(shí)間段[tk，tk+T]內(nèi)路由隊(duì)列為：

Δqk1=（L+u1C1T）-C1T=R0T-（1-u1）C1T

=（R0-A1）T>0 （6）

排隊(duì)時(shí)延差：

（7）

同理，可以證明當(dāng)探測(cè)數(shù)據(jù)流的發(fā)送速率R <可用帶寬A時(shí) ，單向時(shí)延差無(wú)明顯上升趨勢(shì)。通過(guò)圖1（a）、圖1（b）、圖1（c）對(duì)這一特性進(jìn)行進(jìn)一步闡述，試驗(yàn)中發(fā)送端每次向接收端發(fā)送100個(gè)探測(cè)數(shù)據(jù)包，每次發(fā)送速率R均恒定，滿足RaA三種情況。從圖1（a）可以明顯看出，當(dāng)發(fā)送速率Ra<可用帶寬A時(shí)，時(shí)延在一定區(qū)域內(nèi)上下波動(dòng)，無(wú)明顯上升或者下降趨勢(shì)；當(dāng)發(fā)送速率Rc>可用帶寬A時(shí)，時(shí)延在整體上呈現(xiàn)上升趨勢(shì)，盡管期間可能存在個(gè)別的波動(dòng)或者下降點(diǎn)，如圖1（c）所示； 圖1（b）前一半探測(cè)流的時(shí)延呈現(xiàn)波動(dòng)趨勢(shì)，說(shuō)明發(fā)送速率Rb<可用帶寬A，后一半探測(cè)流的時(shí)延開(kāi)始呈現(xiàn)上升趨勢(shì)，說(shuō)明可用帶寬開(kāi)始下降，并且小于發(fā)送速率。至此，可以得到有效帶寬的估計(jì)值為A≈Rb 。

（a）RaA

圖1 單向時(shí)延變化趨勢(shì)

2 Pathload判定規(guī)則

Pathload利用兩個(gè)參數(shù)SPCT（Pairwise Comparison Test）和SPDT（Pairwise Difference Test）判定單向時(shí)延是否存在遞增趨勢(shì)[1，8]，如式（8）所示：

（8）

其中，K表示數(shù)據(jù)流的長(zhǎng)度（典型值為100），為了消除個(gè)別時(shí)延大幅波動(dòng)帶來(lái)的影響，引入濾波因子Γ，，將原始數(shù)據(jù)流進(jìn)行分段，并用表示濾波后的每一組時(shí)延均值。當(dāng)條件x成立時(shí)，函數(shù)I（x）為1，否則為零。不難看出，參數(shù)SPCT反映的是橫軸上相鄰兩點(diǎn)具有上升趨勢(shì)的概率，參數(shù)SPDT反映的是縱軸上最后1個(gè)點(diǎn)減去第1個(gè)點(diǎn)在相鄰點(diǎn)時(shí)延累積和上所占的比例。Jain在文獻(xiàn)[8]中指出由于時(shí)延具有隨機(jī)波動(dòng)性，最后一組濾波后的時(shí)延數(shù)據(jù)有可能與第一組時(shí)延數(shù)據(jù)大小相當(dāng)，因此，這兩個(gè)參數(shù)需要結(jié)合使用，才能正確判別時(shí)延是否具有上升趨勢(shì)。

這里將文獻(xiàn)[8]中提到的時(shí)延分布情況做了補(bǔ)充，如圖2所示，圖2（a）、圖2（b）由文獻(xiàn)中給出，圖2（c）、圖2（d）為本文補(bǔ)充?？梢钥闯?，當(dāng)圖2（b）中的第一組時(shí)延數(shù)據(jù)或者最后一組時(shí)延數(shù)據(jù)發(fā)生波動(dòng)時(shí)，參數(shù)SPCT和SPDT均不能正確描述時(shí)延的上升趨勢(shì)。為此，對(duì)參數(shù)SPDT進(jìn)行改進(jìn)，用時(shí)延的最大值代替最后1個(gè)點(diǎn)，用時(shí)延的最小值代替第1個(gè)點(diǎn)。同時(shí)，按照判別參數(shù)的物理意義，將SPCT定義為SPH（Probability in Horizontal），將SPDT定義為SPV （Proportion in Vertical），如式（9）所示，即分別從水平方向和垂直方向判別時(shí)延數(shù)據(jù)的上升趨勢(shì)，二者具有互補(bǔ)性。從圖2（c）、圖2（d）中可以看出，當(dāng)SPDT失效以后，SPV仍然可以對(duì)時(shí)延的上升趨勢(shì)給出正確解釋。

（9）

（a） （b）

（c） （d）

圖2 單向時(shí)延統(tǒng)計(jì)分布

根據(jù)定義可知，00.66或者SPV>0.45時(shí)，判定時(shí)延具有明顯上升趨勢(shì)；當(dāng)SPH<0.54或者SPV<0.45時(shí)，判定時(shí)延無(wú)上升趨勢(shì)；當(dāng)0.54

表2 延上升趨勢(shì)判別方法 SPH<0.54 0.540.66

SPV<0.45 無(wú)趨勢(shì) 無(wú)趨勢(shì) 無(wú)法判別

0.45

SPV>0.45 無(wú)法判別 上升趨勢(shì) 上升趨勢(shì)

3 可用帶寬測(cè)量算法改進(jìn)

根據(jù)Pathload測(cè)量可用帶寬原理，自載周期流速率調(diào)整算法采用二分法計(jì)算下一次的發(fā)送速率，使其逼近端到端的可用帶寬。初始化設(shè)置Gmin=Gmax=0；速率調(diào)整算法如下所示：

（1）時(shí)延無(wú)上升趨勢(shì)：

（2）時(shí)延呈現(xiàn)上升趨勢(shì)：

（3）時(shí)延分布為灰色區(qū)域：

由于自載周期流速率調(diào)整算法收斂速度較慢，直接導(dǎo)致Pathload存在測(cè)量時(shí)間過(guò)長(zhǎng)、帶寬開(kāi)銷較大的缺陷，如果能夠加快速率調(diào)整算法的收斂速度，就能從整體上提升Pathload算法的實(shí)用性。

由式（7）可知，第k+1個(gè)數(shù)據(jù)包離開(kāi)第1個(gè)路由器與第k個(gè)路由器離開(kāi)第1個(gè)路由器的時(shí)間差ΔT為：

（10）

可以看出，相鄰兩個(gè)數(shù)據(jù)包離開(kāi)路由器的時(shí)間與數(shù)據(jù)包的個(gè)數(shù)k無(wú)關(guān)，即第1組數(shù)據(jù)流離開(kāi)第1個(gè)路由器的速率恒定：

（11）

由此可以推斷出分組數(shù)據(jù)流到達(dá)第i個(gè)路由器的速率Ri-1，與分組數(shù)據(jù)流離開(kāi)第i個(gè)路由器的速率Ri以及該節(jié)點(diǎn)可用帶寬Ai之間的關(guān)系滿足式（12）：

（12）

觀察速率調(diào)整算法中的“時(shí)延呈現(xiàn)上升趨勢(shì)”部分代碼，當(dāng)R（n）≥A時(shí)，如果用分組數(shù)據(jù)離開(kāi)路由器的速率R*（n）代替，即Rmax=R*（n）（if（R（n）≥A）），可以有效降低速率的上限，使其與可用帶寬之間的差值更小，從而加快速率調(diào)整算法的收斂速度，降低算法測(cè)量開(kāi)銷。

4 NS2仿真試驗(yàn)

為了評(píng)估改進(jìn)后的判定準(zhǔn)則及Pathload改進(jìn)算法的性能，本節(jié)通過(guò)網(wǎng)絡(luò)仿真軟件NS2進(jìn)行驗(yàn)證，參考文獻(xiàn)[14]中試驗(yàn)方法設(shè)計(jì)端到端網(wǎng)絡(luò)路徑結(jié)構(gòu)如圖3所示，客戶端與服務(wù)器之間共由5個(gè)路由節(jié)點(diǎn)組成，其中R3與R4之間為緊張鏈路，帶寬容量為10 Mb/s，其余路由節(jié)點(diǎn)為正常鏈路，帶寬容量為20 Mb/s。網(wǎng)絡(luò)上的背景流量由具備自相似性特征的佩瑞多（Pareto）分布的源生成，α=1.9。其中，550 B的數(shù)據(jù)包占50%，40 B的數(shù)據(jù)包占40%，其余10%為1 500 B的數(shù)據(jù)包。

圖3 端到端網(wǎng)絡(luò)仿真拓?fù)鋱D

將鏈路按照網(wǎng)絡(luò)負(fù)載大小劃分為幾個(gè)不同的等級(jí)，分別為u1=20%，u2=40%，u3=60%和u4=80%四組，對(duì)應(yīng)的真實(shí)有效帶寬分別為8 Mb/s，6 Mb/s，4 Mb/s和2 Mb/s。試驗(yàn)中探測(cè)包的長(zhǎng)度設(shè)置為300 B，設(shè)置精度參數(shù)ω=1 Mb/s，χ=0.2Mb/s，當(dāng)發(fā)送10組探測(cè)數(shù)據(jù)流仍未收斂，則強(qiáng)行終止探測(cè)程序，并根據(jù)當(dāng)前可用帶寬的上下界給出一組最合適的估計(jì)值。

原始的測(cè)量方法并沒(méi)有直接給出網(wǎng)絡(luò)可用帶寬的估計(jì)值，而是通過(guò)測(cè)量程序中的上下界給出一個(gè)區(qū)間，在這里將上下界相加取平均值，這樣能夠直接顯示最終的測(cè)量結(jié)果，同時(shí)，也便于數(shù)據(jù)采集器網(wǎng)關(guān)利用該值進(jìn)行發(fā)送速率調(diào)整。試驗(yàn)結(jié)果如表3所示，改進(jìn)后的測(cè)量方法通過(guò)更新時(shí)延上界的下限，使測(cè)量結(jié)果的區(qū)間變窄，最終得到的可用帶寬更接近真實(shí)的可用帶寬值。此外，由于收斂速度變快，使得測(cè)量所需開(kāi)銷明顯減小，對(duì)網(wǎng)絡(luò)自身的影響相應(yīng)降低。

表3 網(wǎng)絡(luò)可用帶寬測(cè)量結(jié)果比帶寬

利用率 真實(shí)可用

帶寬 Mb/s 原方法 改進(jìn)方法

測(cè)量結(jié)果Mb/s 測(cè)量開(kāi)銷 Mb 測(cè)量結(jié)果

Mb/s 測(cè)量開(kāi)銷

Mb

u1=20% 8 2.24 13.44 1.99 6.72

u2=40% 6 4.47 13.19 4.23 7.41

u3=60% 4 6.5 12.78 6.31 8.72

u4=80% 2 8.31 11.52 8.18 9.6

5 結(jié) 語(yǔ)

本文針對(duì)Pathload測(cè)量網(wǎng)絡(luò)可用帶寬方法中存在的測(cè)量開(kāi)銷大、收斂速度慢等不足，從判斷準(zhǔn)則、發(fā)送速率調(diào)整兩個(gè)方面入手對(duì)Pathload測(cè)量算法進(jìn)行改進(jìn)，加速更新可用帶寬上下界， 從而加快收斂速度， 降低網(wǎng)絡(luò)測(cè)量開(kāi)銷。NS2仿真試驗(yàn)結(jié)果證明了該方法的有效性，改進(jìn)后的方法測(cè)量開(kāi)銷明顯降低，收斂速度明顯加快。

參考文獻(xiàn)

[1] Jain M， Dovrolis C. End-to-End available bandwidth： Measurement methodology， dynamics， and relation with TCP throughput [J].IEEE/ACM Transactions on Networking， 2003，11 （4）：537-549.

[2] 周輝，李丹，王永吉.可用帶寬度量系統(tǒng)中的若干基本問(wèn)題[J].軟件學(xué)報(bào)，2008，19（5）：1234-1255.

[3] Carter R L， Crovella M E. Measuring bottleneck link speed in packet-switched networks [J].Performance Evaluation， 1996，27–28：297-318.

[4] Saroiu S， Gummadi P K， Gribble S D. Sprobe： A fast technique for measuring bottleneck bandwidth in uncooperative environments[C].Proc. of the IEEE INFOCOM， IEEE，2002.

[5] Antoniades D， Athanatos M， Papadogiannakis A， et al. Available bandwidth measurement as simple as running wget[C].Proceedings of the Passive and Active Measurement Conference， 2006.

[6] 查新天，許曉東.IPv6中利用ICMP測(cè)量網(wǎng)絡(luò)可用帶寬[J].微計(jì)算機(jī)信息，2008，24（3）：121-123.

[7] Ribeiro V J， Coates M J， Riedi R H， et al. Multifractal Cross-Traffic estimation[C].Proc ITC Specialist Seminar on IP traffic Measurement， Modeling， and Management， Monterey， California： 2000.

[8] Jain M， Dovrolis C. Pathload： A measurement tool for End-to-End available bandwidth[C].In Proceedings of Passive and Active Measurements （PAM） Workshop， Fort Collins： 2002.

[9] Ribeiro V J， Riedi R H， Baraniuk R G， et al. PathChirp： Efficient available bandwidth estimation for network paths[C].Work shop on Passive and Active Measurement （PAM）， La Jolla， California： 2003.

[10] Hu N， Steenkiste P. Evaluation and characterization of available bandwidth probing techniques [J].IEEE Journal on Selected Areas in Communications， 2003，21 （6）：879-894.

[11] Strauss J， Katabi D， Kaashoek F. A measurement study of available bandwidth estimation tools[C].Proceedings of the 3rd ACM SIGCOMM conference on Internet measurement， New York： ACM，2003.

[12] Melander B， Bjorkman M， Gunningberg P. A new end-to-end probing and analysis method for estimating bandwidth bottlenecks[C].Global Telecommunications Conference， IEEE，2000，1：415-420.

[13] 曾彬，張大方，黎文偉，等.WPathload：一種改進(jìn)的可用帶寬測(cè)量方法[J].計(jì)算機(jī)研究與發(fā)展，2009，46（6）：898-904.