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

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

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

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

1 相關概念

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

表1 變量定義

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

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

(1)

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

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

2 實驗設置

圖2 仿真實驗環境結構圖

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

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

3 測量結果分析

下面著重分析這些因素存在環境下包對表現出的行為特性．

3.1 包丟失

首先給出端到端路徑數據包丟失統計指標的形式化定義：

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

表2 包對丟失情況統計測量

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

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

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

3.2 包大小與時鐘精確度

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

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

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

(2)

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

(3)

(4)

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

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

Cpr=|tstart-tend|.

(5)

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

(a)背景流量數據包大小256 bytes (b)背景流量數據包大小512 bytes (c)背景流量數據包大小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)探測包大小盡可能與背景流量的數據包大小比較接近，即l≈lcross．

4 結束語

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

參考文獻：

[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].計算機研究與發展, 2009, 46(6): 898-904.

[3] 韋安明, 王洪波, 林 宇, 等. IP網帶寬測量技術研究與進展[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].計算機研究與發展, 2007, 44 (1) : 85-91.

[7] 劉星成, 何莉, 余順爭. 網絡可用帶寬的高精度測量算法[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] 周 輝, 李 丹, 王永吉,等.可用帶寬度量系統中的若干基本問題研究[J].軟件學報,2008,19(5):1 234-1 255.