PGM可用帶寬測量中包行為影響分析

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

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

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

1 相關概念

首先定義相關變量，如表1所示．

表1 變量定義

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

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

(1)

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

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

2 實驗設置

圖2 仿真實驗環(huán)境結構圖

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

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

3 測量結果分析

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

3.1 包丟失

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

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

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

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

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

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

3.2 包大小與時鐘精確度

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

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

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

(2)

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

(3)

(4)

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

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

Cpr=|tstart-tend|.

(5)

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

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

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

綜合上述分析，可以得到結論2：

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

4 結束語

PGM計算端到端路徑可用帶寬方法的優(yōu)點在于能通過發(fā)送少量的探測包，比較穩(wěn)定和準確地實現(xiàn)對被測路徑帶寬的測量．但探測包對間隔容易受到路徑上存在數(shù)據(jù)包異常等的干擾，從而造成對可用帶寬的高估或低估．本文利用理論分析和實驗驗證的方法，針對包傳輸行為，對探測包對的行為特征分別進行了定量分析與總結，分析得到了一系列有價值的結論，為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)帶寬測量技術研究與進展[J]. 電子學報, 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)絡可用帶寬的高精度測量算法[J].電子學報, 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].軟件學報,2008,19(5):1 234-1 255.