王志釗 陸余良 楊國正 關永耀

(1.電子工程學院, 合肥,230037;2. 中國人民解放軍94647部隊,福州,350001)

一種改進離群區(qū)間計算的PRM帶寬測量算法*

王志釗1陸余良1楊國正1關永耀2

(1.電子工程學院, 合肥,230037;2. 中國人民解放軍94647部隊,福州,350001)

主動式網(wǎng)絡路徑可用帶寬測量是目前網(wǎng)絡路徑帶寬測量使用的主要方法，與被動式網(wǎng)絡路徑可用帶寬測量相比，具有更高的靈活性且部署方便。為解決主動式網(wǎng)絡路徑可用帶寬測量定義不明確、通用性不強、協(xié)議不規(guī)范和結果不準確等問題，規(guī)范定義了探測通信協(xié)議和報文結構，建立了較為完整、統(tǒng)一和規(guī)范的主動式網(wǎng)絡路徑可用帶寬測量框架，提出了序列時延增加度和基于序列時延增加度的離群區(qū)間計算方法，改進了網(wǎng)絡背景流量分析方法，降低了背景流量對網(wǎng)絡路徑可用帶寬測量的干擾，最后使用NS2仿真對比驗證了該算法的有效性。

序列時延增加度；離群區(qū)間；可用帶寬測量；網(wǎng)絡測量

引 言

網(wǎng)絡帶寬測量是指通過主動或被動網(wǎng)絡測量技術，設置或觀測數(shù)據(jù)發(fā)送源的發(fā)送速率、包大小、發(fā)送間隔及其他參數(shù)，獲取測量點與目標設備的數(shù)據(jù)流量、丟包率、包間隔和傳輸時延等測量數(shù)據(jù)的變化特征，利用數(shù)據(jù)發(fā)送速率與路徑帶寬相近時，測量數(shù)據(jù)的變化規(guī)律，根據(jù)探測包間隔模型(Probe gap model,PGM)和探測包速率模型(Prober rate model,PRM)等測量模型，對路徑帶寬進行分析與獲取。被動網(wǎng)絡測量對通過網(wǎng)絡監(jiān)測設備的網(wǎng)絡數(shù)據(jù)、流量和傳輸時延等信息進行被動監(jiān)測和收集，需要在大范圍內(nèi)部署專門的網(wǎng)絡測量設備，實現(xiàn)成本較高而且不利于更新和升級，但對網(wǎng)絡正常通信數(shù)據(jù)流產(chǎn)生的影響較小，測量結果較為準確。而主動測量則通過主動向網(wǎng)絡中發(fā)送探測數(shù)據(jù)來測量數(shù)據(jù)接收速率、丟包率和傳輸時延等信息，不需要大范圍部署網(wǎng)絡監(jiān)測設備，易于實現(xiàn)和更新，缺點是會對正常網(wǎng)絡通信數(shù)據(jù)流產(chǎn)生影響，測量結果準確度相對較低。在實際對網(wǎng)絡路徑帶寬進行測量時，出于規(guī)模成本和實現(xiàn)難度的考慮，通常采用主動網(wǎng)絡測量的方法來實現(xiàn)。

根據(jù)帶寬測量實現(xiàn)原理的不同，主動帶寬測量模型可分為PGM和PRM兩種。PGM假設路徑中僅存在一條瓶頸鏈路，根據(jù)探測報文發(fā)送間隔和接收間隔的變化來估算路徑可用帶寬，優(yōu)點是速度快、測量數(shù)據(jù)量小、對正常網(wǎng)絡通信流量影響較小，缺點是實際網(wǎng)絡路徑難以滿足只有一條瓶頸鏈路，測量準確度不高，具體實現(xiàn)有Delphi[1]，IGI/PTR[2]，Spruce[3]和CProbe[4]等；PRM則基于自擁塞的原理，調(diào)整測量數(shù)據(jù)發(fā)送速率，當測量數(shù)據(jù)發(fā)送速率接近或者高于路徑可用帶寬時，測量數(shù)據(jù)的傳輸時延會發(fā)生較大變化，選擇離群區(qū)間進行計算測量網(wǎng)絡路徑可用帶寬。優(yōu)點是準確度較高，適應實際網(wǎng)絡路徑的復雜性，缺點則是測量數(shù)據(jù)量較大，會對正常網(wǎng)絡通信流量產(chǎn)生較大影響，具體實現(xiàn)則有：Pathload[5]，Pathchirp[6]，基于報文對序列的測量方法(Trains of packet pairs，TOPP)[7],基于非相鄰探測包間隔的測量方法(Gaps of non-adjacent probing packets，GNAPP)[8]等。以上帶寬測量實現(xiàn)方法從不同角度出發(fā)，針對測量準確度、時間效率、注入數(shù)據(jù)量及網(wǎng)絡路徑復雜性等不同需求偏向時，各有其優(yōu)勢和不足。PRM在測量數(shù)據(jù)影響不大、準確性要求高時比較適用，但是目前PRM的實現(xiàn)方法，缺乏在數(shù)據(jù)發(fā)送速率接近路徑可用帶寬時，離群區(qū)間選擇受背景流量影響的詳細分析，因此測量結果精確度不高。本文針對該問題，結合背景流量對帶寬測量過程中傳輸延遲的影響，提出了一種基于測量序列時延增加度的離群區(qū)間計算方法，有效提高了PRM帶寬測量的精確度。

1 基本概念和相關工作

1988年,Jacobson 在文獻[9]中提出了“Window Flow Control ′Self-clocking′”模型，并對帶寬測量相關概念進行了初步說明?，F(xiàn)對帶寬測量的相關概念進行重新明確，對于由鏈路L1,L2,…，Ln組成的一條網(wǎng)絡路徑，將每一跳鏈路Li在單位時間內(nèi)能達到的最大數(shù)據(jù)傳輸速率定義為鏈路帶寬Ci，其中數(shù)據(jù)傳輸速率為網(wǎng)絡層數(shù)據(jù)的傳輸速率，單位是bit/s，由此可以定義網(wǎng)絡路徑帶寬B為鏈路L1,L2,…，Ln的最小帶寬。

定義1 路徑帶寬B=min(C1,C2,…，Cn)

由于在網(wǎng)絡鏈路中存在其他業(yè)務流量，將鏈路Li中不影響其他業(yè)務流量時能達到的最大數(shù)據(jù)傳輸速率定義為鏈路可用帶寬ABi，同樣，將網(wǎng)絡路徑的可用帶寬AB定義為L1,L2,…，Ln的最小可用帶寬。

定義2 路徑可用帶寬AB=min(AB1,AB2,…，ABn)

劉敏在文獻[10]中從鏈路空閑率的角度，對鏈路在(t1，t2)時段內(nèi)的可用帶寬ABi(t1，t2)進行數(shù)學定義如下。

(1)

PGM是根據(jù)包發(fā)送和接收時間間隔的變化來計算瓶頸鏈路帶寬，如圖1所示，設瓶頸鏈路帶寬為C，包長為L，則可以根據(jù)數(shù)據(jù)接收時間差Δt來計算C=L/Δt。該測量方法發(fā)送測量數(shù)據(jù)量小，速度快，但僅針對網(wǎng)絡路徑中只有一條瓶頸鏈路時有效，且在實際測量中，由于背景流量的存在，其測量結果并不是路徑帶寬B，而是在多路流量下的漸近散布率(Asymototicdispersionrate,ADR)[11]。

圖1 PGM測量模型Fig．1 PGM Model

PRM以自擁塞原理為基礎，調(diào)整測量數(shù)據(jù)的發(fā)送速率并計算數(shù)據(jù)的單向傳輸延遲(One-way delay, OWD)，Pathload根據(jù)定義4和5來判斷數(shù)據(jù)流發(fā)送速率是否達到路徑可用帶寬[12]。

定義4 流成對比測試值(Stream pairwise comparison test,SPCT)

(2)

定義5 流成對差測試值(Stream pairwise difference test,SPDT)

(3)

Pathchirp以指數(shù)級降低包序列中的發(fā)送時間間隔，根據(jù)單向傳輸延遲的變化情況，將第k+1個測量報文的單向延遲q(k+1)比第k個測量報文單向延遲q(k)增大時的k作為區(qū)間左邊界，利用定義6確定子區(qū)間的右邊界，將長度超過L的子區(qū)間定義為離群區(qū)間，然后利用離群區(qū)間對路徑可用帶寬進行估計。

定義6 離群區(qū)間確定方法

(4)

式中：F為延遲降低參數(shù)，對發(fā)送速率低于離群區(qū)間左邊界的測量數(shù)據(jù)，路徑可用帶寬以離群區(qū)間左邊界測量數(shù)據(jù)發(fā)送速率Ei為估計值，對發(fā)送速率高于離群區(qū)間右邊界的測量數(shù)據(jù)，以離群區(qū)間右邊界測量數(shù)據(jù)發(fā)送速率Ej來估計，離群區(qū)間內(nèi)部測量數(shù)據(jù)的發(fā)送速率Ek為路徑可用帶寬估計值，然后利用定義7對路徑可用帶寬進行計算[6]。

定義7 可用帶寬計算方法

(5)

Guerrero等采用K-means聚類方法降低背景流量干擾[13]，Aceto等提出了UANM測量架構改進測量方法[14]。目前國內(nèi)外研究分別針對路徑可用帶寬測量方法和背景流量分析提出了相應的概念和計算方法，但仍存在處理突發(fā)性背景流量時錯誤率高，測量數(shù)據(jù)發(fā)送速率估計精確度低和聚類方法數(shù)據(jù)集依賴性強等問題。針對當前路徑可用帶寬測量算法的不足，本文利用多序列提高測量數(shù)據(jù)發(fā)送速率精度，將序列分窗口計算序列時延增加度對離群區(qū)間進行定位降低突發(fā)背景流量影響，提出了基于測量序列時延增加度的PRM可用帶寬測量算法。

2 基于測量序列時延增加度的PRM可用帶寬測量算法

2.1 測量收發(fā)通信協(xié)議與報文結構

圖2 數(shù)據(jù)發(fā)送時間分布 Fig．2 Data transmission time distribution

對于1 000Mbps的網(wǎng)絡適配器，1K字節(jié)的報文，其理論發(fā)送時間約為8μs。為了獲取實際情況下，測量數(shù)據(jù)讀取系統(tǒng)時間、填充和發(fā)送字節(jié)數(shù)組、循環(huán)判斷與比較等處理時間帶來的數(shù)據(jù)發(fā)送時間誤差，利用配置為1 000Mbps網(wǎng)絡適配器的計算機進行實驗，連續(xù)發(fā)送100個長度為1K字節(jié)的UDP報文，對數(shù)據(jù)實際發(fā)送時間進行記錄，并使用wireshark抓包工具監(jiān)視和對比，100個測量報文的實際發(fā)送時間如圖2所示。

通過對測量數(shù)據(jù)實際發(fā)送時間的分析，連續(xù)兩個測量數(shù)據(jù)的發(fā)送時間間隔為9～12μs，符合網(wǎng)絡適配器的發(fā)送速率。每連續(xù)發(fā)送約10個包，發(fā)送時間間隔會劇烈增大一次，增大幅度在529μs到903μs之間。如Ribeiro在文獻[6]中所述，進程上下文的切換會對測量報文的收發(fā)帶來影響，探測分組大小以及探測序列長度均會對探測結果產(chǎn)生影響[15]，不同軟硬件配置及網(wǎng)絡覆蓋范圍等實際因素也會對測量結果產(chǎn)生影響[16]。在測量報文發(fā)送與接收方式上，pathload采用以發(fā)送速率Rs發(fā)送若干報文列，接收端計算各報文列Spct和Spdt后，與發(fā)送端交互調(diào)整Rs。收發(fā)端的相互交互和報文發(fā)送速率的不斷調(diào)整增加了發(fā)送報文時程序處理時間帶來的誤差，而pathchirp則采用以發(fā)送間隔指數(shù)級降低的方式，發(fā)送一組報文，該種方式降低了發(fā)送端和接收端的相互交互和發(fā)送速率的調(diào)整判斷條件，但是單個報文的單向傳輸延遲變化不能夠準確代表某發(fā)送速率下單向傳輸延遲的變化情況，通過序列分析能夠提高準確性和抗噪聲性[17]。

為了降低測量程序在發(fā)送和接收測量數(shù)據(jù)時對報文處理時間帶來的干擾，減小收發(fā)端互操作帶來的影響，提高測量數(shù)據(jù)發(fā)送時間、接收時間和單向傳輸延遲等獲取和計算的準確度，本文提出了新的測量數(shù)據(jù)的發(fā)送、接收協(xié)議和測量報文的結構。根據(jù)網(wǎng)絡OSI或TCP/IP協(xié)議分層標準，收發(fā)通信協(xié)議屬于應用層協(xié)議，在UDP協(xié)議上層實現(xiàn)。測量過程分為兩個階段，如圖3所示。

圖3 收發(fā)端狀態(tài)遷移圖Fig．3 Sender and Receiver state transition diagram

第一個階段是握手階段，發(fā)送端和接收端的交互在第一個階段完成，主要目的是發(fā)送端將測量需要的參數(shù)告知接收端，并通過3次握手數(shù)據(jù)報文的發(fā)送時間與接收時間對發(fā)送端和接收端的時鐘偏差進行估計；第二個階段是測量階段，發(fā)送端按照發(fā)送速率遞增的方法發(fā)送s個測量報文序列，每個測量序列由n個測量報文組成，第i個測量報文序列的發(fā)送速率與第i-1個測量報文序列發(fā)送速率關系為

(6)

根據(jù)收發(fā)通信協(xié)議的通信內(nèi)容，測量報文分為三種類型：發(fā)送端握手報文、接收端握手確認報文和測量報文。因此將測量報文結構定義為：報文第1個字節(jié)代表發(fā)送報文端的狀態(tài)，報文接收端根據(jù)發(fā)送端狀態(tài)解析報文內(nèi)容并調(diào)整接收端狀態(tài)；第2～3個字節(jié)則聲明測量報文的長度，接收端根據(jù)長度字段對緩沖區(qū)大小進行設置，并根據(jù)報文長度計算路徑可用帶寬；第4個字節(jié)作為保留字段；第5～8個字節(jié)用一個32位整數(shù)表示報文序列號，與發(fā)送時間間隔相關聯(lián)；第9～12個字節(jié)用一個32位整數(shù)表示報文在序列內(nèi)的序號，與序列時延增加度相關；第13～20個字節(jié)則用64位整數(shù)表示報文發(fā)送時間，以μs為單位，接收端接收到測量報文后，根據(jù)接收時間和本字段保存的報文發(fā)送時間，對報文的相對單向傳輸延遲進行計算。

2.2 序列時延增加度

考慮發(fā)送端以速率Rs向接收端發(fā)送測量報文序列，路徑可用帶寬為B，利用NS仿真環(huán)境對理想情況下測量報文序列的單向傳輸延遲的分布情況進行模擬，結果如圖4和5所示。

圖4 RsB時單向傳輸時延分布情況 Fig．4 One-way delay distribution when RsB

理想情況下，當發(fā)送速率小于路徑可用帶寬時，測量報文的owd不隨報文序列發(fā)生變化，可以使用定義8進行計算，L代表報文長度。owd分布情況如圖4所示。當發(fā)送速率大于路徑可用帶寬時，測量報文的owd隨報文序列線性增加，第i+1個報文的單向傳輸時延owd(i+1)與第i個報文的單向傳輸時延關系利用定義(9)表示，其owd分布情況如圖5所示。

定義8Rs

(7)

定義9Rs>B時單向傳輸時延關系

(8)

測量數(shù)據(jù)報文在實際網(wǎng)絡中傳輸時，由于網(wǎng)絡設備、背景流量等因素的影響，單向傳輸時延與理想情況有較大差別。為了從受背景流量等因素影響下的單向延遲數(shù)據(jù)中對測量報文發(fā)送速率和路徑可用帶寬的相對關系進行分析，pathload利用SPCT和SPDT來表征報文序列的單向時延逐漸增大的趨勢，Pathchirp則利用定義6分析測量報文發(fā)送速率與路徑可用帶寬的相對關系。SPCT和SPDT以及定義6能夠在一定程度上反映網(wǎng)絡路徑可用帶寬和測量報文發(fā)送速率的關系，但是對不同方式背景流量的干擾，準確性會有所不同，不能夠精確有效地適應各種背景流量狀況。

算法1 序列時延增加度算法

輸入: 序列單向傳輸時延d1,d2,…,dn；窗口個數(shù)k

輸出: 序列時延增加度A

算法:

(1)分別計算每個窗口中單向傳輸時延的最小值

(2)消除背景流量影響，對于任意1≤x≤k，若存在x≤y≤k，滿足window_min[y]≤window_min[x]，則認為x受背景流量干擾，其所處窗口的最小單向時延以window_min[y]為準，即window_min[x]=window_min[y]。

圖6 單向傳輸時延分布 Fig．6 One-way delay distribution

圖6為某發(fā)送速率下單向傳輸時延的分布情況。以圖6為例對序列時延增加度進行分析計算，可在第61個測量報文處獲取最低OWD為2 878 150μs，第81個測量報文處的最低OWD增大到2 878 200μs，第91個測量報文處的最低OWD增大到2 878 350μs。第61個測量報文代表對于發(fā)送速率為Rs的測量報文序列來說，受突發(fā)背景流量最小的測量報文，其單向傳輸時延為2 878 150 μs。而其后的第81個和第91個測量報文分別代表了隨著測量報文的發(fā)送，若發(fā)送速率超過路徑可用帶寬，在突發(fā)背景流量影響最小的情況下，其OWD將逐步增大到2 878 200和2 878 350 μs。取窗口個數(shù)k=10，窗口最小單向傳輸時延結果如表1所示。

根據(jù)統(tǒng)計后獲取到的遞增窗口最小單向時延window_min[1]，window_min[2]，…，window_min[k]，其序列時延增加度用定義10表示，該公式對序列遞增的程度及影響窗口數(shù)進行分析，得出序列的遞增程度。

表1 窗口單向傳輸時延計算結果

定義10 序列時延增加度計算方法

(9)

以表1的數(shù)據(jù)進行計算，其序列時延增加度為0+0+0+0+0+0+0.5+0+0+1.5=2

2.3 基于序列時延增加度的離群區(qū)間和路徑可用帶寬計算

相對于SPCT和SPDT，序列時延增加度用來描述某發(fā)送速率下，連續(xù)發(fā)送的測量報文隨報文增加其相對單向傳輸時延增加的程度。與Pathchirp所定義的離群區(qū)間不同，本文將離群區(qū)間定義為發(fā)送速率范圍[Rsi,Rsj],范圍長度大于L，且在此范圍內(nèi)序列單向時延增加度大于閥值A并連續(xù)增大。不同于文獻[18]，探測序列發(fā)送速率采用按步長遞增的方式，序列時延增加度能夠精確測量出發(fā)送速率是否達到最大可用帶寬，當發(fā)送速率達到離群區(qū)間的左邊界Rsi時，表示發(fā)送速率已經(jīng)達到可用最大可用帶寬。基于序列時延增加度的離群區(qū)間和路徑可用帶寬測量算法如算法2所述。

算法2 網(wǎng)絡路徑最大可用帶寬測量算法

輸入: 測量序列發(fā)送速率R1,R2,…,Rs

測量序列時延增加度A1,A2,…,As

輸出: 路徑最大可用帶寬B

算法:

(1)If(A1,A2,…,AL遞增)

降低探測報文最低發(fā)送速率并重新測量,return；

Else

(2)定位離群區(qū)間[Ai,Ai+L-1]，滿足A

(3)返回網(wǎng)絡路徑可用帶寬B=Ai。

3 實驗驗證

圖7 仿真網(wǎng)絡拓撲環(huán)境 Fig．7 Network simulate topology environment

圖8 網(wǎng)絡路徑可用帶寬測量結果對比 Fig．8 Comparison of the measurement result

Pathchirp測量工具由RichardBaraniuk等于2003年開發(fā)，后經(jīng)過不斷改進，目前的版本是2.4.1，是基于PRM且具有較高效率和精確度的測量工具。為了對基于測量序列時延增加度的PRM可用帶寬測量算法進行驗證，選取Pathchirp作為對比，實驗環(huán)境使用NS2作為仿真環(huán)境，網(wǎng)絡拓撲結構定義與Pathchirp一致，如圖7所示。節(jié)點0作為測量點發(fā)送端，節(jié)點2作為測量點接收端，節(jié)點3到節(jié)點2發(fā)送CBR背景數(shù)據(jù)流量。分別對2Mbps到8Mbps間不同速率的CBR背景數(shù)據(jù)流量，測量節(jié)點0到節(jié)點2的最大可用帶寬。測量時序列個數(shù)設置為100，序列內(nèi)探測報文個數(shù)設置為50，窗口個數(shù)為10，實際網(wǎng)絡路徑可用帶寬、Pathchirp測量結果和基于序列時延增加度的測量結果如圖8所示。測量詳細數(shù)據(jù)對比與準確度如表2所示。

NS2的仿真結果顯示，基于序列時延增加度的網(wǎng)絡路徑最大可用帶寬測量算法能夠獲得更加精確的測量結果。與Pathchirp相比，較大地提高了網(wǎng)絡路徑可用帶寬測量的準確度。

4 結束語

背景流量對網(wǎng)絡路徑可用帶寬測量結果的干擾是帶寬測量無可回避的關鍵問題，目前眾多網(wǎng)絡路徑可用帶寬測量算法對背景流量干擾的解決方法均不夠理想。本文使用探測序列代替了Pathchirp中僅使用兩個相鄰探測包的時間間隔來表征發(fā)送速率，規(guī)范定義了測量通信協(xié)議和報文結構，提出了特定發(fā)送速率下表征發(fā)送速率與路徑可用帶寬的序列時延增加度的計算方法，并利用時延增加度來定位和計算離群區(qū)間與網(wǎng)絡最大可用帶寬。利用NS2進行仿真實驗驗證了算法的有效性和準確性，通過與Pathchirp測量結果的對比，基于序列時延增加度的離群區(qū)間計算和網(wǎng)絡路徑可用帶寬測量方法對實際網(wǎng)絡可用帶寬測量具有較高精確性，且在背景流不同的情況下，能夠適應流量變化，準確計算路徑可用帶寬。

表2 測量結果與準確度對比

[1] Ribeiro V, Coates M, Riedi R, et al. Multifractal cross-traffic estimation[C] // Proc of ITC Specialist Seminar on IP Traffic Measurement Modeling & Management. Monterey,USA:Rice University, 2000:1-5.

[2] 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.

[3] 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，USA:ACM,2003: 39-44.

[4] Carter R L, Crovella M E.Measuring bottleneck link speed in packet-switched networks[J].Performance Evaluation, 1996, 27(28):297-318.

[5] Jain M, Dovrolis C. Pathload: A measurement tool for end-to-end available bandwidth[C] // Passive and Active Measurement Workshop.Ft Collins:Springer, 2002:14-25.

[6] Ribeiro V, Riedi R, Baraniuk R, et al. Pathchirp: Efficient available bandwidth estimation for network paths[C] // Passive and Active Measurement Workshop. San Diego:Springer,2003(4):6-8.

[7] Melander B, Bjorkman M, Gunningberg P. A new end-to-end probing and analysis method for estimating bandwidth bottlenecks[C] //Global Telecommunications Conference. San Francisco,USA: IEEE, 2000(1): 415-420.

[8] Li M, Wu Y L, Chang C R.Available bandwidth estimation for the network paths with multiple tight links and bursty traffic[J].Journal of Network and Computer Applications, 2013, 36(1):353-367.

[9] Jacobson V. Congestion avoidance and control[C]// ACM Sigcomm Computer Communication Review. New York,USA: ACM,1988(18): 314-329.

[10]劉敏, 李忠誠, 過曉冰, 等.端到端的可用帶寬測量方法[J].軟件學報, 2006, 17(1):108-116.

Liu Min,Li Zhongcheng, Guo Xiaobing, et al. An end-to-end available bandwidth estimation methodology[J]. Journal of software,2006,17(1):108-116.

[11]Dovrolis C, Ramanathan P, Moore D. What do packet dispersion techniques measure?[C] // Twentieth Annual Joint Conference of the Computer and Communications Societies. Anchorage, USA: IEEE, 2001(2): 905-914.

[12]Jain M, Dovrolis C. End-to-end available bandwidth: Measurement methodology, dynamics, and relation with TCP throughput[C]// ACM SIGCOMM Computer Communication Review. New York,USA:ACM,2002(32): 295-308.

[13]Guerrero C D, Morillo D S. On the reduction of the available bandwidth estimation error through clustering withk-means [C] // Latin-America Conference on Communications. Cuenca,USA:IEEE，2012: 1-5.

[14]Aceto G, Botta A, Pescapé A, et al.Unified architecture for network measurement: The case of available bandwidth[J].Journal of Network and Computer Applications, 2012, 35(5):1402-1414.

[15]何莉, 余順爭.一種測量任意鏈路可用帶寬的方法[J].軟件學報, 2009, 20(4):997-1013.

He Li,Yu Shunzheng. Methodology for measuring available bandwidth on arbitrary links[J].Journal of Software,2009,20(4):997-1013.

[16]周輝, 李丹, 王永吉.可用帶寬度量系統(tǒng)中的若干基本問題[J].軟件學報, 2008, 19(5):1234-1255.

Zhou Hui,Li Dan,Wang Yongji.Fundamental problems with available bandwidth measurement systems[J].Journal of Software, 2008, 19(5):1234-1255.

[17]黃翔東, 李文元, 王兆華.基于快速序列變換的線性網(wǎng)絡沖激響應測量算法[J].數(shù)據(jù)采集與處理, 2006, 21(2):142-148.

Huang Xiangdong,Li Wenyuan,Wang Zhaohua.Determination algorithm for impulse responses of LTI-Meshwork based on fast m-sequence transform[J].Journal of Data Acquisition and Processing, 2006,21(2):142-148.

[18]張大陸, 胡治國, 朱安奇, 等.一種自負載降速率包列可用帶寬測量算法[J].軟件學報, 2012, 23(2):335-351.

Zhang Dalu, Hu Zhiguo, Zhu Anqi,et al. Self-loading decreasing rate packet train method for available bandwidth estimation[J].Journal of Software,2012,23(2):335-351.

Improved Outlier Range Calculation Algorithm for PRM Bandwidth Measurement

Wang Zhizhao1, Lu Yuliang1, Yang Guozheng1, Guan Yongyao2

(1.Electronic Engineering Institute, Hefei, 230037, China; 2. PLA 94647,Fuzhou,350001,China)

Active measurement has been a primary method used in network path bandwidth measurements to date,with greater flexibility and deployment convenience compared to the passive one.The available bandwidth measurement probe model is not precise enough for background traffic and problems with high error rate, so we define the communication protocol, detect packet structure, and propose the calculation method of the increase rate of sequence delays and the outlier range. The algorithm can reduce the interference of background traffic on the network path. The effectiveness of the algorithm has been verified by using NS2 simulation.

increase rate of sequence delay; outlier range; available bandwidth measurement; network measurement

2014-05-31；

2015-01-31

TP39

A

王志釗(1988-)，男，碩士研究生，研究方向: 網(wǎng)絡測量、信息安全，E-mail：78761186@qq.com。

關永耀(1983-)，男，本科，研究方向：計算機網(wǎng)絡安全。

陸余良(1964-)，男，教授，博士生導師，研究方向：信息安全。

楊國正(1982-)，男，博士，研究方向：計算機網(wǎng)絡安全。