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

李稚春

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

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

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

0 引 言

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

（1）

（2）

（3）

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

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

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

單

端

測

量 Cprobe ICMP 直接計算可用帶寬 1996

Pipechar ICMP 包對測量技術(shù) 2001

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

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

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

雙

端

測

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

Pathload TCP 自載周期流 2001

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

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

Spruce TCP 采用探測間隔模型 2004

TOPP TCP 分組對序列 2005

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

1 Pathload測量可用帶寬原理

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

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

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

如果R0>A1，則：

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

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

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

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

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

排隊時延差：

（7）

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

（a）RaA

圖1 單向時延變化趨勢

2 Pathload判定規(guī)則

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

（8）

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

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

（9）

（a） （b）

（c） （d）

圖2 單向時延統(tǒng)計分布

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

表2 延上升趨勢判別方法 SPH<0.54 0.540.66

SPV<0.45 無趨勢 無趨勢 無法判別

0.45

SPV>0.45 無法判別 上升趨勢 上升趨勢

3 可用帶寬測量算法改進

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

（1）時延無上升趨勢：

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

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

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

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

（10）

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

（11）

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

（12）

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

4 NS2仿真試驗

為了評估改進后的判定準(zhǔn)則及Pathload改進算法的性能，本節(jié)通過網(wǎng)絡(luò)仿真軟件NS2進行驗證，參考文獻[14]中試驗方法設(shè)計端到端網(wǎng)絡(luò)路徑結(jié)構(gòu)如圖3所示，客戶端與服務(wù)器之間共由5個路由節(jié)點組成，其中R3與R4之間為緊張鏈路，帶寬容量為10 Mb/s，其余路由節(jié)點為正常鏈路，帶寬容量為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ò)仿真拓撲圖

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

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

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

利用率 真實可用

帶寬 Mb/s 原方法 改進方法

測量結(jié)果Mb/s 測量開銷 Mb 測量結(jié)果

Mb/s 測量開銷

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é) 語

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

參考文獻

[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)中的若干基本問題[J].軟件學(xué)報，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測量網(wǎng)絡(luò)可用帶寬[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].計算機研究與發(fā)展，2009，46（6）：898-904.