賈圣文， 高仲合， 趙金龍

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

0 引言

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

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

這里提出的任意子路徑的瓶頸帶寬測量方法可以在一條超路徑的兩端測量任意子路徑的帶寬，解決了無法在測量兩端部署測量設(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，目的是測量這條路徑的任意子路徑的瓶頸帶寬，例如對(duì)任意的 i，j（i＜j≤n）計(jì)算 mini≤k≤jbk，用 bi,j表示子路徑Li…Lj的瓶頸帶寬。設(shè)計(jì)的測量思想基于主動(dòng)測量中的包間隔模型[1,3,6]，探測報(bào)文采用包串和包列[2]。

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

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

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

設(shè)計(jì)方法測量兩條子路徑瓶頸帶寬 b1,i-1、b1,j。所用的探測報(bào)文是包串，該包串由背靠背的 ttl受限的負(fù)載報(bào)文p、q和探測報(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è)探測報(bào)文m之間的時(shí)間間隔為：

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

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

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

對(duì)于 b1,i-1= b1,j的情況，上述方法就無能為力，對(duì)于這種情況要按照如下測量。所用的探測報(bào)文是一由 x（x = j-i+1）個(gè)背靠背的大小為r的包串組成的包列，每個(gè)包串由ttl受限制的負(fù)載報(bào)文p、q和探測報(bào)文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è)計(jì)這樣的探測列的目的是讓所有的探測包 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è)探測報(bào)文m在鏈路 Lk處時(shí)間間隔是：

1.3 測量過程總結(jié)

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

2 子路徑瓶頸帶寬的定位

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

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

在下列實(shí)驗(yàn)中使用 Ns2進(jìn)行仿真，測量 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次，最后通過子路徑瓶頸帶寬定位過濾掉那些由于背景流量影響測得不是瓶頸帶寬的錯(cuò)誤值。圖3、圖4分別是r =1、r =2的測量結(jié)果，橫坐標(biāo)為測量的次數(shù)，縱坐標(biāo)為測量的值。

圖2 每跳背景流量

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

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

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

4 結(jié)語

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

[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àn)測量中的時(shí)鐘同步問題[J].通信技術(shù),2009，42(10)：125-127.

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

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