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

王志釗 陸余良 楊國正 關(guān)永耀

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

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

王志釗1陸余良1楊國正1關(guān)永耀2

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

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

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

引 言

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

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

1 基本概念和相關(guān)工作

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

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

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

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

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

(1)

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

圖1 PGM測(cè)量模型Fig．1 PGM Model

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

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

(2)

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

(3)

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

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

(4)

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

定義7 可用帶寬計(jì)算方法

(5)

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

2 基于測(cè)量序列時(shí)延增加度的PRM可用帶寬測(cè)量算法

2.1 測(cè)量收發(fā)通信協(xié)議與報(bào)文結(jié)構(gòu)

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

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

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

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

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

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

(6)

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

2.2 序列時(shí)延增加度

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

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

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

定義8Rs

(7)

定義9Rs>B時(shí)單向傳輸時(shí)延關(guān)系

(8)

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

算法1 序列時(shí)延增加度算法

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

輸出: 序列時(shí)延增加度A

算法:

(1)分別計(jì)算每個(gè)窗口中單向傳輸時(shí)延的最小值

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

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

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

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

表1 窗口單向傳輸時(shí)延計(jì)算結(jié)果

定義10 序列時(shí)延增加度計(jì)算方法

(9)

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

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

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

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

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

測(cè)量序列時(shí)延增加度A1,A2,…,As

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

算法:

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

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

Else

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

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

3 實(shí)驗(yàn)驗(yàn)證

圖7 仿真網(wǎng)絡(luò)拓?fù)洵h(huán)境 Fig．7 Network simulate topology environment

圖8 網(wǎng)絡(luò)路徑可用帶寬測(cè)量結(jié)果對(duì)比 Fig．8 Comparison of the measurement result

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

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

4 結(jié)束語

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

表2 測(cè)量結(jié)果與準(zhǔn)確度對(duì)比

[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]劉敏, 李忠誠, 過曉冰, 等.端到端的可用帶寬測(cè)量方法[J].軟件學(xué)報(bào), 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]何莉, 余順爭(zhēng).一種測(cè)量任意鏈路可用帶寬的方法[J].軟件學(xué)報(bào), 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].軟件學(xué)報(bào), 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)絡(luò)沖激響應(yīng)測(cè)量算法[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]張大陸, 胡治國, 朱安奇, 等.一種自負(fù)載降速率包列可用帶寬測(cè)量算法[J].軟件學(xué)報(bào), 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)絡(luò)測(cè)量、信息安全，E-mail：78761186@qq.com。

關(guān)永耀(1983-)，男，本科，研究方向：計(jì)算機(jī)網(wǎng)絡(luò)安全。

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

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