一種任意子路徑的帶寬測(cè)量方法

賈圣文， 高仲合， 趙金龍

（曲阜師范大學(xué) 計(jì)算機(jī)學(xué)院，山東 日照 276826）

0 引言

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

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

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

1 方法設(shè)計(jì)

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

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

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

1.1 測(cè)量前綴路徑的平靜帶寬

設(shè)計(jì)方法測(cè)量兩條子路徑瓶頸帶寬 b1,i-1、b1,j。所用的探測(cè)報(bào)文是包串，該包串由背靠背的 ttl受限的負(fù)載報(bào)文p、q和探測(cè)報(bào)文 m組成，其中用 s表示大小，D表示包達(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個(gè)[pq]背靠背包對(duì)）。

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

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

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

1.2 測(cè)量任意子路徑的平靜帶寬

對(duì)于 b1,i-1= b1,j的情況，上述方法就無能為力，對(duì)于這種情況要按照如下測(cè)量。所用的探測(cè)報(bào)文是一由 x（x = j-i+1）個(gè)背靠背的大小為r的包串組成的包列，每個(gè)包串由ttl受限制的負(fù)載報(bào)文p、q和探測(cè)報(bào)文m組成。例如要測(cè)量子路徑 Li…Lj的瓶頸帶寬，所用的探測(cè)包列是[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è)計(jì)這樣的探測(cè)列的目的是讓所有的探測(cè)包 m到達(dá)鏈路 Ln，所有的負(fù)載報(bào)文p、q分別在Li到Lj的鏈路上逐跳丟棄。

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

1.3 測(cè)量過程總結(jié)

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

2 子路徑瓶頸帶寬的定位

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

3 實(shí)驗(yàn)仿真

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

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

在路徑平穩(wěn)背景流量環(huán)境下測(cè)量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，測(cè)量b1,2，100次得到值均為b1,2=49.97;取包串大小r =2測(cè)得b3,5的結(jié)果如表1。

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

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

在每跳平穩(wěn)背景流量環(huán)境下測(cè)量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測(cè)量2,1b ，100次求平均值，然后分別取r =1和r =2測(cè)量b3,5各100次，最后通過子路徑瓶頸帶寬定位過濾掉那些由于背景流量影響測(cè)得不是瓶頸帶寬的錯(cuò)誤值。圖3、圖4分別是r =1、r =2的測(cè)量結(jié)果，橫坐標(biāo)為測(cè)量的次數(shù)，縱坐標(biāo)為測(cè)量的值。

圖2 每跳背景流量

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

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

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

4 結(jié)語

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

[1] 楊家海，吳建平，安常青.互聯(lián)網(wǎng)絡(luò)測(cè)量理論與應(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àn)測(cè)量中的時(shí)鐘同步問題[J].通信技術(shù),2009，42(10)：125-127.

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

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