劉震宇，曾 彬，張 玫,，黎文偉

(1.中南林業(yè)科技大學(xué)計算機信息與工程學(xué)院，中國 長沙 410004；2.湖南移動長沙分公司，中國 長沙 410001;3.湖南大學(xué)軟件學(xué)院，中國 長沙 410082)

端到端路徑可用帶寬是路徑上的剩余帶寬，或者說是路徑上未被利用的帶寬，決定了在不影響背景流量的條件下，端到端路徑能夠提供的最大傳輸速率．對一條路徑而言，其中帶寬最低點決定了任何時刻的傳輸速度．而不同時刻網(wǎng)絡(luò)不斷發(fā)生的動態(tài)改變使得帶寬測量的結(jié)果差異很大，這使得對可用帶寬的精確測量成為一個相當棘手的問題[1]．文獻[2～3]將已有的測量可用帶寬的方法分為2類：基于探測包間隔(Probe Gap Model， PGM模型)的方法和基于探測流速率(Probe Rate Model，PRM模型)的方法．其中，PGM方法通過考察探測包對間隔變化來估測可用帶寬，耗費的網(wǎng)絡(luò)帶寬小，且實現(xiàn)簡單．但對于一定長度的探測包對，其測量結(jié)果的穩(wěn)定性和準確性直接依賴于帶寬估算者計算包對時間間隔的準確性，而包對時間間隔容易受到背景流量、包異常等因素的干擾．當前的研究大多集中在如何調(diào)整測量模式，以過濾背景流量[4-7]．但少有文獻去分析和總結(jié)存在背景流量等干擾因素下，包丟失等探測包對在傳輸過程的行為對測量結(jié)果精度的影響，缺乏對這些干擾因素與測量結(jié)果準確性之間關(guān)聯(lián)規(guī)律的定量分析．

1 相關(guān)概念

首先定義相關(guān)變量，如表1所示．

表1 變量定義

圖1 PGM模型中的包對測量帶寬原理

PGM模型假設(shè)端到端路徑上的緊張鏈路與瓶頸鏈路是同一跳鏈路，通過建立數(shù)據(jù)包對的時間間隔與背景流量的函數(shù)關(guān)系，計算端到端路徑可用帶寬．如圖1所示[1]，如果在數(shù)據(jù)包對的第1個數(shù)據(jù)包離開瓶頸鏈路之后，到數(shù)據(jù)包對的第2個數(shù)據(jù)包到達瓶頸鏈路之前的這段時間內(nèi)，瓶頸鏈路的隊列沒有被清空．則數(shù)據(jù)包對到達目的端時的時間間隔Δout應(yīng)等于瓶頸鏈路處理探測包對的第2個數(shù)據(jù)包，以及處理Δin時間內(nèi)到達瓶頸鏈路的背景流量一所共用的時間．其中處理背景流量所用的時間為Δout-Δin，則背景流量的平均速率為C(Δout-Δin)/Δin．因此端到端路徑的可用帶寬為：

(1)

如果已知端到端瓶頸帶寬C，源端通過合理的設(shè)置數(shù)據(jù)包對發(fā)送時的時間間隔Δin，使背景流量在瓶頸鏈路插入到數(shù)據(jù)包對的兩個數(shù)據(jù)包之間，然后測量數(shù)據(jù)包對到達目的端時的時間間隔Δout，PGM模型就可以通過式(1)計算端到端路徑有效帶寬．

包傳輸行為主要是指探測包在網(wǎng)絡(luò)中傳輸時表現(xiàn)出來的行為特性，如包丟失、包亂序等．探測包的行為特性也是影響包對測量結(jié)果準確性的重要因素．另外，如果一個探測數(shù)據(jù)包在途中被意外破壞了，那么系統(tǒng)很可能由于無法識別它的特征信息而將它誤認為是背景數(shù)據(jù)包，這同樣會影響到測量的準確性．本次測量和分析的包傳輸行為指標主要有包丟失(packet loss)、包大小(packet length)和時鐘精度(clock precise)．

2 實驗設(shè)置

圖2 仿真實驗環(huán)境結(jié)構(gòu)圖

實驗配置如圖2，由左到右分別為測量源端，帶雙網(wǎng)卡的路由器和測量目的端．由于數(shù)據(jù)量小，因此路由器是采用Red Hat 9自帶的軟件路由：在一臺普通PC機上安裝雙網(wǎng)卡，分別連接源和目的端，設(shè)置靜態(tài)路由表，開啟IP包轉(zhuǎn)發(fā)．這樣源端就可以通過路由器訪問目的端了．再在本機器上安裝網(wǎng)絡(luò)仿真控制NIST Net軟件[8]，可以仿真網(wǎng)絡(luò)環(huán)境中各種參數(shù)的變化，譬如丟包率、延遲、抖動、帶寬等等．

我們在測量源端運行一種典型的PGM測量帶寬工具IGI[5],其形成的探測包對在流經(jīng)NIST Net形成的仿真網(wǎng)絡(luò)時，通過改變NIST Net上的參數(shù)，模擬網(wǎng)絡(luò)變化，在目的端收集最終的相關(guān)測量信息，觀察這些變化對測量結(jié)果準確性的影響．

3 測量結(jié)果分析

下面著重分析這些因素存在環(huán)境下包對表現(xiàn)出的行為特性．

3.1 包丟失

首先給出端到端路徑數(shù)據(jù)包丟失統(tǒng)計指標的形式化定義：

實驗中從源端連續(xù)發(fā)送包對到目的端，數(shù)據(jù)包流經(jīng)由NIST Net網(wǎng)絡(luò)仿真器模擬的網(wǎng)絡(luò)．使用NIST Net，我們可以控制路徑上總的丟包率及背景流量．觀察在不同丟包率的情況下，包對表現(xiàn)出的行為特征．

表2 包對丟失情況統(tǒng)計測量

從表2中可以看出，隨著路徑總丟失率的增加，包對丟失率及包對流丟失率相應(yīng)增加．當路徑總丟失率處于輕度丟包(0～1%)情形，包對丟包率總體上控制在4%以內(nèi)，對最后結(jié)果的統(tǒng)計分析幾乎沒有影響；當路徑總丟失率處于中等丟包(0～2%)情形，包對丟包率總體上控制在10%以內(nèi)，對最后結(jié)果的準確性有一定影響；當路徑總丟失率處于嚴重丟包(2%以上)情形，包對丟包率隨著迅速增加，使得測量無法繼續(xù)進行．因此，可以得到結(jié)論：

結(jié)論1設(shè)D為成功測量次數(shù)的計數(shù)器，p為計數(shù)概率，p的取值與測量方法對結(jié)果的精度要求、運行時間要求等有如下關(guān)系：

文獻[9]指出包丟失是一種比較突出存在的包異常行為．如果測量工具所發(fā)送的探測數(shù)據(jù)包引發(fā)了數(shù)據(jù)包丟失現(xiàn)象，而這些現(xiàn)象又同待測路徑本身就存在的數(shù)據(jù)包丟失現(xiàn)象重疊在一起，那么從終端主機的角度要想準確獲知造成包異常的原因，并正確判斷探測包對時間間隔是非常困難的．本文的實驗分析結(jié)論為提高測量工具在包丟失方面的抗干擾能力提供了直接依據(jù)．

3.2 包大小與時鐘精確度

進一步分析探測包大小對測量結(jié)果的影響．共進行3組實驗，各組的背景流量數(shù)據(jù)包的大小分別設(shè)置為56、512和1 024 bytes，每組中探測包大小均勻分布[56,1 300](bytes)的范圍內(nèi)．圖3是實驗結(jié)果，橫坐標是探測包的包大小，縱坐標是每次測量得到的包對延遲差．其中圖3(a)、(b)、(c)分別對應(yīng)的是背景流量數(shù)據(jù)包大小為56、512和1 024 bytes的情況．

通過對比圖3(a)、(b)、(c)，可以發(fā)現(xiàn)3組實驗分析圖存在以下共同的特點：隨著探測包大小的增加，包對延遲差總體上呈增大趨勢，即對帶寬測量產(chǎn)生低估效應(yīng)．換言之，當采用較小包長的數(shù)據(jù)包對測量路徑帶寬時，相對于采用較大包長的數(shù)據(jù)包對，前者得到的結(jié)果更接近于真實值．

設(shè)端到端路徑由n段鏈路組成，第i跳為瓶頸鏈路，l為探測包長度，Cr為背景流量，Cr[i]是在該跳加入到探測包對間的背景流量，Δi為探測包對離開瓶頸鏈路時的包對間隔，則有：

(2)

根據(jù)PGM模型的假設(shè)，包對間隔將保持不變直到目的節(jié)點，最后Δout=Δi．但實際上，在后續(xù)鏈路上，探測包對可能繼續(xù)排隊，即：

(3)

(4)

另外，圖3(a)中探測包大小在接近256 bytes 時得到的測量結(jié)果比較接近理想值，而且比較穩(wěn)定；以推斷探測包長度與背景流量數(shù)據(jù)包長度比較接近同樣地，圖3(b)和圖3(c)中探測包大小在接近512 bytes和1 024 bytes時測量結(jié)果比較準確．

為了說明時鐘精確度，假定接收端的時鐘精確度為Cpr，tstart是終端主機將數(shù)據(jù)包中的所有字節(jié)通過網(wǎng)卡從物理媒介上完整接收進來的時刻，并設(shè)tend是系統(tǒng)所記錄的它完成這一操作的時刻，則時鐘精確度Cpr可以表示為：

Cpr=|tstart-tend|.

(5)

設(shè)理論上的包對時間間隔為Δt．顯然，時鐘精確度的值至少不能比探測包對間隔低，否則包對時間間隔是無法測量得到的，也即是：Cpr≥Δt.

(a)背景流量數(shù)據(jù)包大小256 bytes (b)背景流量數(shù)據(jù)包大小512 bytes (c)背景流量數(shù)據(jù)包大小1 024 bytes圖3 不同包長度條件下包對延遲差測量結(jié)果的分布

又設(shè)探測包大小為l，路徑的瓶頸帶寬為Cp，由PGM原理可知 Δt=l/Cp，則有：l≥Cp·Cpr.

綜合上述分析，可以得到結(jié)論2：

結(jié)論2設(shè)lcross為背景流量包大小的期望值，lmin為探測包能取到的最小值．則要提高測量的精確度，對于探測包大小的選擇需滿足：(1)探測包的最小值要大于路徑瓶頸帶寬與時鐘精確度的乘積，即l≥Cp·Cpr；(2)探測包盡可能取小包，即l→lmin；(3)探測包大小盡可能與背景流量的數(shù)據(jù)包大小比較接近，即l≈lcross．

4 結(jié)束語

PGM計算端到端路徑可用帶寬方法的優(yōu)點在于能通過發(fā)送少量的探測包，比較穩(wěn)定和準確地實現(xiàn)對被測路徑帶寬的測量．但探測包對間隔容易受到路徑上存在數(shù)據(jù)包異常等的干擾，從而造成對可用帶寬的高估或低估．本文利用理論分析和實驗驗證的方法，針對包傳輸行為，對探測包對的行為特征分別進行了定量分析與總結(jié)，分析得到了一系列有價值的結(jié)論，為PGM測量工具的改進與完善提供依據(jù)．

參考文獻：

[1] ZHOU H, WANG Y J, WANG X L,etal. Difficulties in estimating available bandwidth:Proc of IEEE International Conference on Communications, Istanbul, Turkey, 2006[C].Istanbul:[s.n.],2006.

[2] 曾 彬, 張大方, 黎文偉, 等. WPathload：一種改進的可用帶寬測量方法[J].計算機研究與發(fā)展, 2009, 46(6): 898-904.

[3] 韋安明, 王洪波, 林 宇, 等. IP網(wǎng)帶寬測量技術(shù)研究與進展[J]. 電子學(xué)報, 2006, 34(7) :1 301-1 310.

[4] JALN M, DOVROLIS C．End-to-End available bandwidth: measurement methodology, dynamics, and relation with TCP throughput[J]．IEEE/ACM Trans on Networking, 2003, 11(4): 537-549.

[5] HU N, STEENKISTE P. Evaluation and Characterization of available bandwidth probing techniques[J]. IEEE Journal on Selected Areas in Communication: Special Issue in Internet and WWW Measurement, Mapping, and Modeling, 2003, 21(6):879-894.

[6] 黃國偉, 吳功宜, 徐敬東. 基于排隊分析的端到端路徑可用帶寬的測量[J].計算機研究與發(fā)展, 2007, 44 (1) : 85-91.

[7] 劉星成, 何莉, 余順爭. 網(wǎng)絡(luò)可用帶寬的高精度測量算法[J].電子學(xué)報, 2007, 35 (1) : 68-72.

[8] MARK CARSON, DARRIN SANTAY. NIST Net: a Linux-based network emulation tool[J]. ACM SIGCOMM Computer Communication Review, 2003,33(3): 111-126.

[9] 周 輝, 李 丹, 王永吉,等.可用帶寬度量系統(tǒng)中的若干基本問題研究[J].軟件學(xué)報,2008,19(5):1 234-1 255.