周逸秋，陳兵，錢(qián)紅燕，呂宗磊

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

一種高精度低負(fù)載的可用帶寬測(cè)量機(jī)制

周逸秋1，陳兵1，錢(qián)紅燕1，呂宗磊2

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

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

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

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

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

1　相關(guān)研究

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

2　測(cè)量模型

2.1問(wèn)題分析

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

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

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

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

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

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

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

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

2.2數(shù)學(xué)模型

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

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

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

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

當(dāng)式（3）中的Tq＞0時(shí)

式（4）的一階近似值為

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

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

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

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

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

3　測(cè)量機(jī)制

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

3.1擴(kuò)展卡爾曼濾

擴(kuò)展卡爾曼濾波可概括為：在濾波值附近，應(yīng)用泰勒展開(kāi)算法將非線性系統(tǒng)展開(kāi)，對(duì)展開(kāi)式進(jìn)行一階線性化截?cái)喽雎云溆喔唠A項(xiàng)，于是將原系統(tǒng)變成線性系統(tǒng)，再利用標(biāo)準(zhǔn)卡爾曼濾波對(duì)系統(tǒng)線性化模型進(jìn)行濾波.標(biāo)準(zhǔn)卡爾曼濾波以最小均方誤差為最佳估計(jì)準(zhǔn)則，采用狀態(tài)空間模型并根據(jù)前一時(shí)刻的估計(jì)值和當(dāng)前時(shí)刻的觀測(cè)值來(lái)更新對(duì)狀態(tài)變量的估計(jì)，獲得當(dāng)前時(shí)刻的估計(jì)值.主要包括兩個(gè)過(guò)程：一是時(shí)間更新，即利用時(shí)間更新方程建立對(duì)當(dāng)前狀態(tài)的先驗(yàn)估計(jì)，及時(shí)向前推算當(dāng)前狀態(tài)變量和誤差協(xié)方差估計(jì)值，以便為下一個(gè)時(shí)間狀態(tài)構(gòu)造先驗(yàn)估計(jì)值；二是狀態(tài)更新，即在預(yù)估過(guò)程的先驗(yàn)估計(jì)值及當(dāng)前測(cè)量變量的基礎(chǔ)上，利用測(cè)量更新方程對(duì)當(dāng)前狀態(tài)的改進(jìn)的后驗(yàn)估計(jì).

時(shí)間更新方程［14］如下：

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

3.2探測(cè)包列

圖3　探測(cè)包列Figure 3 Structure of probing packets

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

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

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

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

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

3.4算法設(shè)計(jì)

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

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

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

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

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

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

Algorithm 1 Our mechanism Initialization /*初始化x初始化系統(tǒng)初始狀態(tài)b x、可用帶寬估計(jì)值bA、估計(jì)誤差協(xié)方差矩陣bP、最大探測(cè)速率rmax、過(guò)程噪聲Q、測(cè)量噪聲探測(cè)包列中探測(cè)包的數(shù)目M、組數(shù)P、每組實(shí)際收到的探測(cè)包響應(yīng)報(bào)文Mp；*/ Set b x= ? ? ,R,M=0,P=0,L=1500B,N=200；Process：①While（true）/*發(fā)送端以泊松分布速率［0,rmax］間發(fā)送探測(cè)包*/②x=unifrnd（0,rmax）,rp=poissrnd（lambda）；/*由式（13）得到網(wǎng)絡(luò)利用率u（r）*/③u（r）=SendProbingPackets（rp）；/*接收端接收探測(cè)包列后，如果每組中探測(cè)包的數(shù)目不等于M-1?α β,bA=0,bP,rmax,Q= ?λ0 0λP，則存在丟包現(xiàn)象，那么就要找到丟包的位置，用鄰居節(jié)點(diǎn)的u（r）代替.*/④If（Mp6=M-1P），用鄰居節(jié)點(diǎn)的u（r）；/*根據(jù)擴(kuò)展卡爾曼濾波計(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　實(shí)驗(yàn)

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

圖4　網(wǎng)絡(luò)拓?fù)鋱DFigure 4 Topology of simulation

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

式（18）用均方差來(lái)衡量可用帶寬的精度

4.1M和P對(duì)可用帶寬精度的影響

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

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

4.1.1M固定，P變化時(shí)的均方差

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

4.1.2P固定，M變化時(shí)的均方差

由圖6可見(jiàn)，不管當(dāng)前的鏈路負(fù)載情況如何，當(dāng)P固定時(shí)，均方差曲線隨著M的增長(zhǎng)總體呈下降趨勢(shì)，這是由于隨著M的增長(zhǎng)，時(shí)間間隔拉長(zhǎng)，所得可用帶寬的精度更高.

圖6　不同M對(duì)均方差的影響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，測(cè)量P=2，3，4時(shí)的可用帶寬，所得結(jié)果如圖7所示.

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

4.2Q對(duì)可用帶寬精度的影響

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

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

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

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

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

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

圖9　本機(jī)制與BART的測(cè)量精度對(duì)比Figure 9 Comparison between the accuracy of our mechanism and BART

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

5　結(jié)語(yǔ)

本文利用探測(cè)包列在端到端路徑上的單向時(shí)延測(cè)得網(wǎng)絡(luò)利用率，該方法無(wú)需假設(shè)瓶頸容量已知，且探測(cè)速率允許低于可用帶寬，從而減少了對(duì)網(wǎng)絡(luò)正常流量的影響.構(gòu)造由P個(gè)部分組成的探測(cè)包列，為每個(gè)部分的探測(cè)包設(shè)置不同的探測(cè)速率，單獨(dú)計(jì)算每個(gè)部分探測(cè)包在端到端路徑上的利用率u（r），因此測(cè)量精度無(wú)需依賴于Q，同時(shí)測(cè)量時(shí)間和網(wǎng)絡(luò)負(fù)載均大大降低.分析網(wǎng)絡(luò)利用率與探測(cè)速率之間的非線性關(guān)系，引入擴(kuò)展卡爾曼濾波降低突發(fā)背景流對(duì)測(cè)量結(jié)果的影響.考慮高速網(wǎng)絡(luò)環(huán)境下出現(xiàn)的丟包現(xiàn)象，用鄰居節(jié)點(diǎn)代替當(dāng)前丟失節(jié)點(diǎn)的u（r）.因此，該機(jī)制能實(shí)時(shí)、快速、精確地獲得高速網(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)的高精度可用帶寬測(cè)量算法［J］.計(jì)算機(jī)測(cè)量與控制，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］劉敏，李忠誠(chéng)，過(guò)曉冰.端到端的可用帶寬測(cè)量方法［J］.軟件學(xué)報(bào)，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

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

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