一種任意子路徑的帶寬測量方法

賈圣文， 高仲合， 趙金龍

（曲阜師范大學 計算機學院，山東 日照 276826）

0 引言

近年來，圍繞網(wǎng)絡(luò)帶寬測量人們設(shè)計了大量的測量算法和系統(tǒng)，這些測試技術(shù)大致可以分為三類[1,3]：用簡單網(wǎng)絡(luò)管理協(xié)議(SNMP)基于網(wǎng)絡(luò)設(shè)備 MIB/RMON查詢方法，被動監(jiān)聽分析方法和主動測量方法。由于前兩種方法都存在一系列的問題，不能準確、靈活的測量到帶寬，因此人們的研究熱點都集中在設(shè)計精確、高效、快速、健壯的主動帶寬測量方法。

在主動測量方法中根據(jù)測量工具到底部署在測量路徑的一端或者兩端，分為單端測量和雙端測量[1]。單端測量僅在發(fā)送端部署測量設(shè)施，利用探測包的往返時延計算帶寬，雙端測量[5]方法要求在發(fā)送端和接收端都部署測量設(shè)施，存在時鐘同步問題[4]。無論是單端測量還是雙端測量都存在網(wǎng)絡(luò)測量設(shè)施部署困難問題，甚至網(wǎng)絡(luò)中不允許在測量的端部署測量設(shè)施。

這里提出的任意子路徑的瓶頸帶寬測量方法可以在一條超路徑的兩端測量任意子路徑的帶寬，解決了無法在測量兩端部署測量設(shè)施的問題。子路徑就是指一條路徑的一部分稱為這條路徑的子路徑，這條路徑稱為子路徑的超路徑。對于一條跳數(shù)為 n的路徑，L1,L2,…,Ln,則 Li,Li+1,…,Lj（1≤i＜j≤n）稱為該路徑的一條子路徑，該路徑稱為子路徑的超路徑。

1 方法設(shè)計

對一條路徑 L1,L2,…,Ln，各跳鏈路容量為 b1,b2,…,bn，目的是測量這條路徑的任意子路徑的瓶頸帶寬，例如對任意的 i，j（i＜j≤n）計算 mini≤k≤jbk，用 bi,j表示子路徑Li…Lj的瓶頸帶寬。設(shè)計的測量思想基于主動測量中的包間隔模型[1,3,6]，探測報文采用包串和包列[2]。

為了測量計算方便，在測量過程中做了一些假設(shè)：①中間路由器采用存儲轉(zhuǎn)發(fā)和先來先服務(wù)（FCFS）模式；②源端和終端只有一條路徑；③源端主機能夠發(fā)送背靠背的探測包列。

1.1節(jié)和 1.2節(jié)分別描述 b1,i-1＞b1,j和b1,i-1=b1,j兩種情況下測量bi,j的思想 。

1.1 測量前綴路徑的平靜帶寬

設(shè)計方法測量兩條子路徑瓶頸帶寬 b1,i-1、b1,j。所用的探測報文是包串，該包串由背靠背的 ttl受限的負載報文p、q和探測報文 m組成，其中用 s表示大小，D表示包達到的目的端。定義該包串格式為 [ p m{ p q}r-1pm]，s(p)＞s(q)=s(m), D(pi)= D(qi)=Li，D ( m )=Ln（說明：{pq}r-1表示r-1個[pq]背靠背包對）。

在發(fā)送端發(fā)送上述定義的包串，則在鏈路 Li-1處，負載報文p、q由于ttl值減為0被丟包，由包間隔模型可知兩個探測報文m之間的時間間隔為：

那么在不考慮背景流量影響的情況下△將保持到目的端。由此可計算出b1,i-1即：

用同樣的方法測量 b1,j。如果測得結(jié)果 b1,i-1＞ b1,j那么bi,j= b1,j，否則繼續(xù)下面的工作。

1.2 測量任意子路徑的平靜帶寬

對于 b1,i-1= b1,j的情況，上述方法就無能為力，對于這種情況要按照如下測量。所用的探測報文是一由 x（x = j-i+1）個背靠背的大小為r的包串組成的包列，每個包串由ttl受限制的負載報文p、q和探測報文m組成。例如要測量子路徑 Li…Lj的瓶頸帶寬，所用的探測包列是[p m{ p q }r-1pm{ p q }r-1pm… { p q }r-1pm]其中 s (p)＞i- 1ii i i+1 i+1 i+1 j j j s(q ) = s (m), D(pi) = D (qi) =Li，D(m ) = Ln，設(shè)計這樣的探測列的目的是讓所有的探測包 m到達鏈路 Ln，所有的負載報文p、q分別在Li到Lj的鏈路上逐跳丟棄。

由包間隔模型理論知道，對于 n跳的鏈路L1，L2…Ln,每跳鏈路的帶寬 b1,b2…bn，如果 b1,i-1≤ bi,n，對 x = n-i+1，r =1的包列[pi-1mpimpi+1m…pnm],如果那么在負載包前后緊鄰的兩個探測報文m在鏈路 Lk處時間間隔是：

1.3 測量過程總結(jié)

②比較 b1,i-1和 b1,j大小，如果 b1,i-1≥b1,j，那么 bi,j=b1,j到此就測量出了子路徑的瓶頸帶寬bi,j。否則轉(zhuǎn)到步驟③；

2 子路徑瓶頸帶寬的定位

在以上描述的子路徑瓶頸帶寬測量方法中，可以通過標識探測包 m，定位出瓶頸鏈路。在接收端收到探測包后，根據(jù)探測包的唯一的標識信息，得出是哪兩個相鄰探測包的時間間隔最大，時間間隔最大的即是探測包在通過子路徑瓶頸鏈路時的時間間隔，那么兩個探測包之間的負載報文的 ttl值對應(yīng)的即為子路徑的瓶頸鏈路。由此就可以方便的定位出瓶頸帶寬。在仿真中這里通過用探測包的大小來唯一的標識探測包，在不影響測量精度的范圍內(nèi)，使各個探測包大小不同（相差不能太大，否則影響測量精度）。例如探測包列設(shè)計43，這樣探測包相差很小幾乎不影響精度，如果在終端得到 m1、m2的時間間隔最大那么瓶頸鏈路就是 L3，同樣如果在終端測得m2、m3的時間間隔最大那么瓶頸鏈路就是L4。

3 實驗仿真

在下列實驗中使用 Ns2進行仿真，測量 b1,2、b1,5采用的探測包串 [ p m{ p q}r-1pm]，其中 s (p)= 1 500, s(q)=s(m) = 4 0, D (m)=L6，D(p ) = D (q)在兩次測量中分別為L2和L5。測量b3,5采用的探測包列是

3.1 在路徑平穩(wěn)背景流量環(huán)境下測量b3,5

在路徑平穩(wěn)背景流量環(huán)境下測量b3,5(圖1示)。

圖1 路徑平穩(wěn)背景流量

在由 CBR固定比特率背景流量環(huán)境下,背景包大小為500 bytes，發(fā)送速率依次為 20 Mb/s、30 Mb/s、40 Mb/s、48 Mb/s。采用r =2，測量b1,2，100次得到值均為b1,2=49.97;取包串大小r =2測得b3,5的結(jié)果如表1。

表1 cbr流量產(chǎn)生器和指數(shù)分布流量產(chǎn)生器仿真結(jié)果

3.2 在每跳平穩(wěn)背景流量環(huán)境下測量b3,5

在每跳平穩(wěn)背景流量環(huán)境下測量b3,5(圖2示)。

背景流量分別由指數(shù)分布流量產(chǎn)生器產(chǎn)生，其中“ON”“OFF”狀態(tài)為 100 ms。在 n0,n1, … ,n5背景包的大小分別為 100、300、500、700、900、1 100,不同的鏈路利用率u下首先取r =3測量2,1b ，100次求平均值，然后分別取r =1和r =2測量b3,5各100次，最后通過子路徑瓶頸帶寬定位過濾掉那些由于背景流量影響測得不是瓶頸帶寬的錯誤值。圖3、圖4分別是r =1、r =2的測量結(jié)果，橫坐標為測量的次數(shù)，縱坐標為測量的值。

圖2 每跳背景流量

圖3 指數(shù)分布背景流量r=1測量結(jié)果

圖4 指數(shù)分布背景流量r=2測量結(jié)果

試驗仿真表明，在兩種背景流量環(huán)境下，該方法都能準確的測量出任意子路徑的瓶頸帶寬，并且能夠定位出此瓶頸鏈路。在每跳背景流量下測量結(jié)果相對路徑背景流量較大，隨著鏈路負載越重，所受影響也隨之增大，但仍能測量出此瓶頸帶寬。

4 結(jié)語

該測量方法能在一條路徑的兩端測量出這條路徑上任意一條子路徑的瓶頸帶寬，并且能方便的定位出此瓶頸鏈路，解決了在測量路徑兩端無法部署測量設(shè)施的問題。這里首先介紹了此方法的基本思想，然后理論分析方法的可行性，最后通過在NS2不同背景流量下的仿真表明該方法準確有效。

[1] 楊家海，吳建平，安常青.互聯(lián)網(wǎng)絡(luò)測量理論與應(yīng)用[M] 北京：人民郵電出版社，2009：131-145.

[2] KHALED HARFOUSH,AZER BESTAVROS,JOHN BYTERS. Measuring Capacity Bandwidth of Targeted Path Segments[J]. IEEE/ACM Transactions on Networking,2009,2(17)：80-92.

[3] KEVIN LAI,MARY BAKER. Measuring Link Bandwidths Using a Deterministic Model of Packet Delay[J].ACM SIGCOMM Computer Communication Review.2000,30(04)：283-294.

[4] 聶玉婷，高仲合.單向?qū)嶒灉y量中的時鐘同步問題[J].通信技術(shù),2009，42(10)：125-127.

[5] 韓賓，黃玉清，梁靚.可用帶寬測量算法改進[J].通信技術(shù),2009,42(04)：90-92.

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