一種高精度低負載的可用帶寬測量機制

周逸秋，陳兵，錢紅燕，呂宗磊

1.南京航空航天大學計算機科學與技術(shù)學院，南京210016 2.中國民航大學中國民航信息技術(shù)科研基地，天津300300

一種高精度低負載的可用帶寬測量機制

周逸秋1，陳兵1，錢紅燕1，呂宗磊2

1.南京航空航天大學計算機科學與技術(shù)學院，南京210016 2.中國民航大學中國民航信息技術(shù)科研基地，天津300300

端到端的可用帶寬是網(wǎng)絡(luò)測量的重要性能指標之一.針對現(xiàn)有的大多數(shù)測量工具及方法在估算可用帶寬前需要大量時間分析和測量等問題，在全面分析了網(wǎng)絡(luò)中背景流特征的基礎(chǔ)上，提出一種高精度低負載的可用帶寬測量機制.該機制考慮了高速網(wǎng)絡(luò)環(huán)境中丟包的情況，建立網(wǎng)絡(luò)利用率與探測速率間的關(guān)系模型，結(jié)合擴展卡爾曼濾波實時獲得最新的端到端的可用帶寬.該機制不需要事先知道瓶頸鏈路容量，探測速率可低于可用帶寬，降低了突發(fā)背景流對測量的影響.數(shù)值模擬表明，所提出的機制能快速響應(yīng)突發(fā)背景流，準確高效地測得端到端的可用帶寬.

可用帶寬；突發(fā)背景流；擴展卡爾曼濾波

隨著計算機網(wǎng)絡(luò)規(guī)模的不斷擴大，網(wǎng)絡(luò)流量急劇增長，各種應(yīng)用層出不窮，對網(wǎng)絡(luò)帶寬的需求也越來越大.在實時、多跳、高速的網(wǎng)絡(luò)環(huán)境下，通過網(wǎng)絡(luò)測量及時了解網(wǎng)絡(luò)行為特征顯得尤為重要.端到端路徑上的網(wǎng)絡(luò)可用帶寬作為網(wǎng)絡(luò)性能指標的重要參數(shù)之一，受到了越來越多的關(guān)注.它不僅能進行流量和擁塞控制，優(yōu)化覆蓋網(wǎng)絡(luò)路徑以及提高網(wǎng)絡(luò)利用率，還有助于及時發(fā)現(xiàn)并探測網(wǎng)絡(luò)故障和攻擊，提高網(wǎng)絡(luò)服務(wù)質(zhì)量（quality of service，QoS）.

網(wǎng)絡(luò)流量的動態(tài)性導(dǎo)致無法直接測量端到端的可用帶寬，同時由于背景噪聲等因素的干擾，現(xiàn)有的基于探測間隔模型（probe gap model，PGM）和探測速率模型（probe rate model，PRM）的測量方法低估了可用帶寬，且無法對突發(fā)背景流做出快速的響應(yīng).本文針對雙端測量環(huán)境以及大多數(shù)測量工具不適合實際跟蹤可用帶寬的問題，提出一種高精度低負載的可用帶寬測量機制.

1　相關(guān)研究

現(xiàn)有的可用帶寬測量方法大多依賴于瓶頸分隔原理的液體流模型［1］，該模型假設(shè)背景流無限小且速率保持穩(wěn)定.文獻［2］指出Internet中的背景流具有突發(fā)性，無法準確捕捉動態(tài)流量，低估了可用帶寬.文獻［3］使用隱馬爾科夫模型將探測包對分布建模，從而快速且非侵擾地測得可用帶寬，提高了可用帶寬的精度.文獻［4］認為端到端路徑上30%的鏈路處于擁塞時，測得的可用帶寬的平均誤差達到10%，于是文獻［5］提出使用K-means算法來減少測量誤差.文獻［6］基于“自擁塞”的概念，提出降速探測包列測量法（self-loading decreasling rate train，SLDRT），通過構(gòu)造靠背的負載包和速率遞減的探測包組成的探測包列，分析接收端獲得的單向時延變化，當單向時延下降后趨于穩(wěn)定狀態(tài)時的發(fā)送速率為可用帶寬.該方法在多緊鏈路和突發(fā)背景流下精度較高，但在尋找單向時延的轉(zhuǎn)折點時引入了過多的探測包，對網(wǎng)絡(luò)造成一定的影響.文獻［7］提出一種自適應(yīng)的高精度可用帶寬測量算法FPU-ABM，該方法構(gòu)造六包組的探測包列，利用在瓶頸鏈路前后測得時間間隔的變化來估計可用帶寬，并根據(jù)發(fā)送速率與可用帶寬之間的關(guān)系動態(tài)調(diào)整速率，從而減少網(wǎng)絡(luò)負載，提高測量速度；但這種方法需要利用Pathneck［8］測得瓶頸鏈路的位置及容量，且只對測得的可用帶寬樣本取加權(quán)平均，使得測量結(jié)果精度不高.文獻［9］基于卡爾曼濾波（Kalman filter，KF）算法提出一種實時可用帶寬測量方法（bandwith available in realtime，BART），計算探測包列間的時間間隔張力ε（strain）作為KF的測量變量，用新的測量變量更新前一次系統(tǒng)狀態(tài)，從而得到最新的可用帶寬.在具體測量過程中，通過調(diào)整端到端路徑上的不同網(wǎng)絡(luò)狀況來調(diào)整過程噪聲（Q），從而獲得了較好的性能；除此之外，使用累積和的方法應(yīng)對突發(fā)背景流，使其快速響應(yīng)突發(fā)背景流.該方法在突發(fā)背景流的網(wǎng)絡(luò)環(huán)境下性能較好，但精度完全取決于Q，在一定程度上增加了網(wǎng)絡(luò)負載和測量時間，且沒有考慮在高速網(wǎng)絡(luò)環(huán)境下存在丟包的情況，因此在極度擁塞的網(wǎng)絡(luò)路徑上測得的可用帶寬比實際值高.本文基于BART的基本思想，提出一種高精度低負載快速測量可用帶寬的機制，考慮網(wǎng)絡(luò)中突發(fā)背景流和丟包的情況，建立網(wǎng)絡(luò)利用率和探測速率間的關(guān)系模型，結(jié)合擴展卡爾曼濾波將網(wǎng)絡(luò)利用率作為測量變量將可用帶寬和瓶頸容量作為系統(tǒng)狀態(tài)，實時估算更新可用帶寬.

2　測量模型

2.1問題分析

Internet環(huán)境下測量可用帶寬面臨的挑戰(zhàn)如下：

1）由于PGM模型中的假設(shè)條件在Internet中不成立，基于該模型的測量方法低估了可用帶寬［10］.

PGM模型假設(shè)緊鏈路和窄鏈路一致，而在Internet中突發(fā)背景流的影響導(dǎo)致瓶頸鏈路的位置不斷變化，且可能存在多跳緊鏈路.除此之外，該模型需要事先知道瓶頸容量C，這在Internet中無法直接獲得.文獻［11］在探測前使用Pathneck測得瓶頸容量，但此工具將ICMP類型數(shù)據(jù)包作為探測包，在傳輸過程中可能被某些路由器阻止.文獻［12］也指出，Pathneck工具的測量數(shù)據(jù)并非可用帶寬，而是處于可用帶寬與路徑容量間的漸進擴散率（asymptotic dispersion rate，ADR）.

2）基于PRM的測量方法所測的可用帶寬不能超過源節(jié)點的最大發(fā)送速率［13］.

假設(shè)發(fā)送端在1 ms內(nèi)發(fā)送1000 Byte的數(shù)據(jù)包，那么被測網(wǎng)絡(luò)的瓶頸帶寬就不能超過8 Mbit/s，否則數(shù)據(jù)包之間將不可能產(chǎn)生時間間隔.隨著網(wǎng)絡(luò)技術(shù)的不斷發(fā)展，目前的網(wǎng)絡(luò)已經(jīng)達到千兆的帶寬，并向更高的傳輸速率發(fā)展，因此該測量模型無法在高速網(wǎng)絡(luò)環(huán)境下使用.這是因為本機制根據(jù)網(wǎng)絡(luò)路徑利用率與探測速率間的線性關(guān)系估計可用帶寬，其測量范圍不受源節(jié)點最大發(fā)送速率的限制.

3）Internet中背景流具有突發(fā)性.瓶頸鏈路的容量和位置是動態(tài)變化的，從而造成了可用帶寬的動態(tài)性，這需要采用一定的機制來緩和突發(fā)背景流給測量結(jié)果帶來的偏差.本機制采用最優(yōu)化自回歸數(shù)據(jù)處理算法EKF［14］，從一組包含噪聲的測量序列中預(yù)測出最接近于實際值的可用帶寬.

4）低精度的時間戳，增大可用帶寬的測量誤差.目前，很多測量工具通過接收端探測包的時間分布.如果最小的時間精度比測量時間間隔大，那么可獲得時間間隔是最小時間精確度；如果比測量時間間隔小，那么認為數(shù)據(jù)包同時到達.因此，低精度的時間戳使得測得的可用帶寬誤差不斷加大，收斂速度也相應(yīng)減慢.本機制通過比較探測包列中各探測包的單向時延作為EKF的測量變量，防止低精度時間戳對可用帶寬精度的精度造成影響.

5）在高速網(wǎng)絡(luò)環(huán)境下，丟包影響可用帶寬的精度.隨著探測速率的增加，路由器緩沖區(qū)隊列溢出產(chǎn)生丟包現(xiàn)象，而大多測量方法通常假設(shè)節(jié)點的緩沖區(qū)無限大，而沒有考慮丟包的情況，影響了測量精度.本機制沒有丟棄整個探測包列，而是通過探測包列中IP包的標識位找到鄰居節(jié)點的測量值，用該值代替當前丟失節(jié)點的測量值.

2.2數(shù)學模型

本節(jié)在多跳鏈路下分析測量模型，根據(jù)排隊論的思想將端到端路徑中的每條鏈路看作一個隊列，則隊列l(wèi)的利用率ul可表示為

式中，πl(wèi)表示隊列l(wèi)為空的概率.

假設(shè)L個隊列不相關(guān)，則端到端的網(wǎng)絡(luò)路徑利用率可以表示為

若探測包以探測速率r通過所測網(wǎng)絡(luò)，則網(wǎng)絡(luò)路徑利用率可以表示為

當式（3）中的Tq＞0時

式（4）的一階近似值為

由式（5），建立網(wǎng)絡(luò)路徑利用率u（r）和探測速率r之間的關(guān)系，得到擬合后的線性關(guān)系如圖1所示.

圖1　理想情況下u（r）與r間的線性關(guān)系Figure 1 Ideally，the linear relationship between u（r）and r

當探測速率r等于可用帶寬A時，網(wǎng)絡(luò)路徑利用率為100%，此時對應(yīng)的探測速率即為可用帶寬，可表示為

由于網(wǎng)絡(luò)中存在噪聲、小數(shù)據(jù)集等影響網(wǎng)絡(luò)利用率波動的因子，在探測周期內(nèi)測得的網(wǎng)絡(luò)利用率極其不規(guī)律［15］.因此，Internet中網(wǎng)絡(luò)利用率u（r）和探測速率r間是一種動態(tài)的非線性關(guān)系，如圖2所示.

圖2　Internet中u（r）與r的非線性動態(tài)關(guān)系Figure 2 Non-linear relationship between u（r）and r in Internet

3　測量機制

根據(jù)第2節(jié)的分析，在Internet下，網(wǎng)絡(luò)利用率與探測速率是一種動態(tài)的非線性關(guān)系，在無法獲得背景流速率的情況下，如何對動態(tài)系統(tǒng)中的可用帶寬進行實時測量？本文將此問題看作系統(tǒng)狀態(tài)空間模型，建立觀測變量和系統(tǒng)內(nèi)部狀態(tài)之間的關(guān)系，其中系統(tǒng)狀態(tài)是非直接可測的，而系統(tǒng)狀態(tài)及觀測過程都不可避免受噪聲的影響，使用擴展卡爾曼濾波法估計可用帶寬.該方法實時而快速，且接收端無需發(fā)送應(yīng)答包，也不必存儲歷史值，就能及時捕捉動態(tài)網(wǎng)絡(luò)行為，解決了現(xiàn)有的測量工具在得到可用帶寬前需要大量時間分析和測量的問題，適合實時跟蹤可用帶寬.

3.1擴展卡爾曼濾

擴展卡爾曼濾波可概括為：在濾波值附近，應(yīng)用泰勒展開算法將非線性系統(tǒng)展開，對展開式進行一階線性化截斷而忽略其余高階項，于是將原系統(tǒng)變成線性系統(tǒng)，再利用標準卡爾曼濾波對系統(tǒng)線性化模型進行濾波.標準卡爾曼濾波以最小均方誤差為最佳估計準則，采用狀態(tài)空間模型并根據(jù)前一時刻的估計值和當前時刻的觀測值來更新對狀態(tài)變量的估計，獲得當前時刻的估計值.主要包括兩個過程：一是時間更新，即利用時間更新方程建立對當前狀態(tài)的先驗估計，及時向前推算當前狀態(tài)變量和誤差協(xié)方差估計值，以便為下一個時間狀態(tài)構(gòu)造先驗估計值；二是狀態(tài)更新，即在預(yù)估過程的先驗估計值及當前測量變量的基礎(chǔ)上，利用測量更新方程對當前狀態(tài)的改進的后驗估計.

時間更新方程［14］如下：

狀態(tài)更新方程［14］如下：

3.2探測包列

圖3　探測包列Figure 3 Structure of probing packets

本文構(gòu)造探測包列后，分別測試了周期、泊松、均勻、帕累托4種抽樣方式.實驗表明使用泊松分布時誤差最小，呈指數(shù)分布的探測不會嚴重影響鏈路的負載，且平均誤差總低于0.07，于是，本機制采用泊松分布的抽樣方式.

在不同鏈路負載的網(wǎng)絡(luò)環(huán)境下，探測包列的長度和包的大小影響可用帶寬的測量.實驗表明，當探測包列長度小于150時，測得網(wǎng)絡(luò)利用率的誤差較大；當探測包列長度大于150時，平均誤差約為0.06.為了權(quán)衡可用帶寬的精確度與測量時間，本文探測包列長度為200.不同探測包的長度也影響測量誤差，經(jīng)多次實驗發(fā)現(xiàn)：40字節(jié)、100字節(jié)的探測包使得測量誤差較大，500字節(jié)、1000字節(jié)、1500字節(jié)的探測包得到的精確度相似.為盡可能地減少發(fā)送探測包列中的探測包以及增大包間的時間間隔，本文選擇1500 B大小的探測包.

3.3估計網(wǎng)絡(luò)路徑利用率

假設(shè)在多跳鏈路環(huán)境下，源端發(fā)送帶有時間戳的探測包列.當一組探測包列到達接收端時，可以得到一組單向時延.在單向時延集合｛D｝中沒有經(jīng)歷排隊時延的探測包的單向時延最小，由此可以推測出比最小單向時延大的探測包在背景流的影響下經(jīng)歷了排隊時延，那么網(wǎng)絡(luò)路徑利用率可以表示為

在探測的過程中，會出現(xiàn)網(wǎng)絡(luò)擁塞和節(jié)點緩沖區(qū)隊列溢出等情況，如果接收端的探測包列每組探測包列的數(shù)目不等于（M-1）/P，那么探測過程中就會出現(xiàn)丟包.通過IP包中的標識找到當前丟失節(jié)點的鄰居節(jié)點，并以鄰居節(jié)點的di代替丟失的數(shù)據(jù)包在端到端路徑上的單向時延，從而獲得網(wǎng)絡(luò)利用率.

3.4算法設(shè)計

本機制將主動探測與擴展卡爾曼濾波算法相結(jié)合，在新的測量變量的基礎(chǔ)上更新系統(tǒng)狀態(tài)，實時獲得最新的可用帶寬.

本文將測得的網(wǎng)絡(luò)利用率u（r）作為擴展卡爾曼濾波算法中的測量變量zk，可表示為

考慮到高階線性化使算法變得復(fù)雜，本機制使用一階Taylor把非線性狀態(tài)空間模型展開，得到標準卡爾曼濾波中的線性空間狀態(tài)模型

式中，uk為輸入控制變量.當以一種方式改變系統(tǒng)狀態(tài)時，本機制中的輸入控制變量是探測包的探測速率.由于探測速率只對瓶頸鏈路造成瞬時擁塞而對系統(tǒng)狀態(tài)的影響較小，本機制將其忽略.

假設(shè)w（k）～η（0，Q）、v（k）～η（0，R），

結(jié)合擴展卡爾曼的估計和糾正兩個階段的公式，可以估計得到α、β，根據(jù)式（7）實時得到可用帶寬A，即為圖中的轉(zhuǎn)折點.偽代碼如下：

Algorithm 1 Our mechanism Initialization /*初始化x初始化系統(tǒng)初始狀態(tài)b x、可用帶寬估計值bA、估計誤差協(xié)方差矩陣bP、最大探測速率rmax、過程噪聲Q、測量噪聲探測包列中探測包的數(shù)目M、組數(shù)P、每組實際收到的探測包響應(yīng)報文Mp；*/ Set b x= ? ? ,R,M=0,P=0,L=1500B,N=200；Process：①While（true）/*發(fā)送端以泊松分布速率［0,rmax］間發(fā)送探測包*/②x=unifrnd（0,rmax）,rp=poissrnd（lambda）；/*由式（13）得到網(wǎng)絡(luò)利用率u（r）*/③u（r）=SendProbingPackets（rp）；/*接收端接收探測包列后，如果每組中探測包的數(shù)目不等于M-1?α β,bA=0,bP,rmax,Q= ?λ0 0λP，則存在丟包現(xiàn)象，那么就要找到丟包的位置，用鄰居節(jié)點的u（r）代替.*/④If（Mp6=M-1P），用鄰居節(jié)點的u（r）；/*根據(jù)擴展卡爾曼濾波計算更新可用帶寬*/⑤xk=f（xk-1+uk-1）+wk-1,zk=h（xk+uk）+vk；⑥Fk|k= h?f（xk,uk）i i?xk xk=b xk|k,uck=b uck,Hk|k-1= h?h（xk,uk）?xk xk=b xk|k-1；⑦Prediction b xk|k=b xk|k-1+Kk xk|k-1=Fk|k-1b xk-1|k-1,Pk|k-1=Fk-1|k-1Pk-1|k-1FT k-1|k-1+Qk-1；⑧correction b i-1 Pk|k=?I-KkHk|k-1 ?Pk|k-1；?zk-h?b xk|k-1,uk?? Kk=Pk|k-1HT k|k-1 h Hk|k-1Pk|k-1HT k|k-1+Rk⑨bA= ?α β ?；⑩If（r 6bA）,Wait（）,Goto（1）；else Goto（3）；End R、

4　實驗

MATLAB的庫函數(shù)能簡單快速地求解擴展卡爾曼濾波算法中的非線性方程，且擅長建模，于是本節(jié)使用MATLAB來驗證突發(fā)背景流下該機制可用帶寬的測量精度.分別編寫程序產(chǎn)生背景流，模擬類似NS2產(chǎn)生的端到端網(wǎng)絡(luò)路徑、探測序列、背景流的發(fā)送和接收端及路由器，測量不同場景下各種參數(shù)（如Q、M、P）對其精確度的影響，選出不同場景下最合適的參數(shù)；其次在各參數(shù)配置相同的情況下，與使用卡爾曼濾波的BART測量方法進行對比.網(wǎng)絡(luò)拓撲如圖4所示，該拓撲是單瓶頸鏈路，與BART中的拓撲類似，端到端的網(wǎng)絡(luò)路徑的瓶頸鏈路位于兩個路由器間.

圖4　網(wǎng)絡(luò)拓撲圖Figure 4 Topology of simulation

瓶頸鏈路容量C［10 Mbit/s，100 Mbit/s］可用體現(xiàn)所測網(wǎng)絡(luò)不同的負載情況，探測包列中每組探測包的速率在［1 Mbit/s，20 Mbit/s］內(nèi)服從泊松分布，探測包列的長度N為200，探測包的大小S為1500B.

式（18）用均方差來衡量可用帶寬的精度

4.1M和P對可用帶寬精度的影響

在不同鏈路負載和突變背景流場景下，探測包數(shù)目M和組數(shù)P對可用帶寬精度的影響，如圖5～7所示.

圖5　不同P對均方差的影響Figure 5 Impact of P on mean square error

4.1.1M固定，P變化時的均方差

從圖5中可以看出：不管當前的鏈路負載情況如何，當M固定時，均方差曲線隨著P的增長總體呈下降趨勢，因此增加分組數(shù)能提高可用帶寬的精度.

4.1.2P固定，M變化時的均方差

由圖6可見，不管當前的鏈路負載情況如何，當P固定時，均方差曲線隨著M的增長總體呈下降趨勢，這是由于隨著M的增長，時間間隔拉長，所得可用帶寬的精度更高.

圖6　不同M對均方差的影響Figure 6 Impact of M on mean square error

4.1.3幾組不同的（P，M）下可用帶寬

本文假設(shè)P在區(qū)間［1，5］，M在區(qū)間［16，100］，從圖5和6可看出M在［30，40］，P在［4，5］后變化趨于平緩，于是選取M=34和BART中設(shè)置的M=17，測量P=2，3，4時的可用帶寬，所得結(jié)果如圖7所示.

比較圖7中的（a）和（b）可看出：當M取小值時，增大P會降低可用帶寬的精度.然而，只要選擇一個稍大的M及合適的P，就能獲得較好的測量精度.實驗結(jié)果表明：當M=34，P=3時，測得的可用帶寬的精度最高.

4.2Q對可用帶寬精度的影響

根據(jù)第3.4節(jié)所述，Q中λ是可調(diào)節(jié)的.令M=34，P=3，測量結(jié)果如圖8所示.

圖7　不同P、M情況下可用帶寬的精度對比Figure 7 Accuracy comparison of available bandwidth about diferent P，M

圖8　Q對可用帶寬精度的影響Figure 8 Impact of Q on accuracy of available bandwidth

圖8表明：調(diào)整Q對可用帶寬精度的影響較小.由于本機制的探測包列中每組使用不同的探測速率，加大了網(wǎng)絡(luò)利用率的變化，因此不調(diào)整Q對可用帶寬測量精度的影響不大，使得網(wǎng)絡(luò)負載和測量時間降低.

4.3在突發(fā)背景流下，本機制與BART對比

使用BART中設(shè)置的參數(shù)M=17，取P=2，測量結(jié)果如圖9所示.

圖9　本機制與BART的測量精度對比Figure 9 Comparison between the accuracy of our mechanism and BART

實驗表明：本文提出的機制在突發(fā)背景流的網(wǎng)絡(luò)環(huán)境下，測量精度高于BART.當M=17，P=2時，使用BART測得的可用帶寬的均方差為0.01，而使用本文所提出的機制測得的均方差為0.007.如果將參數(shù)設(shè)置成M=34，P=3，那么將獲得更高精度的可用帶寬，此時均方差為0.005.

5　結(jié)語

本文利用探測包列在端到端路徑上的單向時延測得網(wǎng)絡(luò)利用率，該方法無需假設(shè)瓶頸容量已知，且探測速率允許低于可用帶寬，從而減少了對網(wǎng)絡(luò)正常流量的影響.構(gòu)造由P個部分組成的探測包列，為每個部分的探測包設(shè)置不同的探測速率，單獨計算每個部分探測包在端到端路徑上的利用率u（r），因此測量精度無需依賴于Q，同時測量時間和網(wǎng)絡(luò)負載均大大降低.分析網(wǎng)絡(luò)利用率與探測速率之間的非線性關(guān)系，引入擴展卡爾曼濾波降低突發(fā)背景流對測量結(jié)果的影響.考慮高速網(wǎng)絡(luò)環(huán)境下出現(xiàn)的丟包現(xiàn)象，用鄰居節(jié)點代替當前丟失節(jié)點的u（r）.因此，該機制能實時、快速、精確地獲得高速網(wǎng)絡(luò)環(huán)境下的可用帶寬，具有良好的性能.

［1］KIM J C，LEE Y.An end-to-end measurement and monitoring technique for the bottleneck link capacity and its available bandwidth［J］.Computer Networks，2014，58（14）：158-179.

［2］H'AGA P，DIRICZI K，VATTAY G，CSABAI I.Understanding packet pair separation beyond the fuid model：the key role of trafc granularity［C］//International Conference on Computer Communications，2006.

［3］GUERRERO C D，LABRADOR M A.Traceband：a fast，low overhead and accurate tool for available bandwidth estimation and monitoring［J］.Computer Networks，2010，54（6）：977-990.［4］GUERRERO C D，LABRADOR M A.A hidden Markov model approach to available bandwidth estimation and monitoring［C］//Orlando：Proceedings of the Internet Network Management Workshop，2008.

［5］GUERRERO C D，MORILLO D S.On the reduction of the available bandwidth estimation error through clustering with K-means［C］//INFOCOM Twentieth Annual Joint Conference of the IEEE Computer and Communications Societies，Italy，2013.

［6］HU Z，ZHANG D，ZHU A，CHEN Z，ZHOU H.SLDRT：a measurement technique for available bandwidth on multi-hop path with bursty cross trafc［J］.Computer Networks，2012，56（14）：3247-3260.

［7］趙衛(wèi)虎，孟相如，麻海圓，莊緒春.一種自適應(yīng)的高精度可用帶寬測量算法［J］.計算機測量與控制，2011，19（6）：1297-1300. ZHAO W H，MENG X R，MA H Y，ZHUANG X C.An adaptive method of accurate available bandwith measurement［J］.Computer Measurement&Control，2011，19（6）：1297-1300.（in Chinese）

［8］HU N，LI L E，MAO Z M，STEENKISTE P，WANG J.Locating Internet bottlenecks：algorithms，measurements，and implications［C］//ACM Special Interest Group on Data Communication，New York，2004.

［9］BERGFELDT E，EKELIN S，KARLSSON J M.Real-time available-bandwidth estimation using fltering and change detection［J］.Computer Networks，2009，34（4）：41-54.

［10］LAO L，DOVROLIS C，SANADIDI M Y.The probe gap model can underestimate the available bandwidth of multihop paths［C］//Special Interest Group on Data Communication，Italy，2006.

［11］LI M，WU Y L，CHANG C R.Available bandwidth estimation for the network paths with multiple tight links and bursty trafc［J］.Journal of Network and Computer Applications，2013，36（1）：353-367.

［12］JAIN M，DOVROLIS C.Ten fallacies and pitfalls on end-to-end available bandwidth estimation［C］//New York：Proceedings of the 4th ACM SIGCOMM Conference on Internet measurement，2004.

［13］劉敏，李忠誠，過曉冰.端到端的可用帶寬測量方法［J］.軟件學報，2006，17（1）：108-116. LIU M，LI Z C，GUO X B.An end-to-end available bandwith estimation methodology［J］. Journal of Software，2006，17（1）：108-116.（in Chinese）

［14］NILSSON M.Measuring available path capacity using short probe trains［C］//in INFOCOM Twentieth Annual Joint Conference of the IEEE Computer and Communications Societies，New York，2010.

［15］NGUYEN U C，TRAN D T，NGUYEN G V.A taxonomy of applying flter techniques to improve the available bandwith estimations［C］//Proceedings of the 8th International Conference on Ubiquitous Internation Management and Communication ACM，New York，2014.

（編輯：王雪）

Accurate and Low Overhead Mechanism for Measuring Available Bandwidth

ZHOU Yi-qiu1，CHEN Bing1，QIAN Hong-yan1，Lü Zong-lei2
1.College of Computer Science and Technology，Nanjing University of Aeronautics and Astronautics，Nanjing 210016，China 2.Information Technology Research Base of Civil Aviation Administration of China，Civil Aviation University of China，Tianjin 300300，China

The available end-to-end bandwidth is an important specifcation in network measurement.Most tools need to spend much time in measuring and analyzing before calculating the available bandwidth.This paper proposes a low overhead mechanism for accurate and fast measurement of the available bandwidth by analyzing the cross trafc efect in the Internet.A model is established to refect the relationship between utilization and the sending rate of probe packets，which is combined with an extended Kalman flter to obtain the new available bandwidth.This mechanism does not require any prior knowledge of the bottleneck link capacity and can reduce the efect of accuracy.Besides，the sending rate of probing packets can be much lower than the available bandwidth.Performance of the mechanism is verifed numerically，showing fast response to burst cross trafc，low estimation error，and short convergence time.

available bandwidth，burst cross trafc，extend Kalman flter

TN911.2

0255-8297（2015）02-0155-12

10.3969/j.issn.0255-8297.2015.02.005

2014-10-16；

2014-12-03

中國民航信息技術(shù)科研基地開放課題基金（No.CAAC-ITRB-201301）資助

陳兵，教授，博導(dǎo)，研究方向：計算機網(wǎng)絡(luò)，E-mail：cb_china@qq.com