潘勝利 楊析儒 張志勇 錢 峰 胡光岷*

1 引言

隨著Internet的發(fā)展，互聯(lián)網(wǎng)越來越多地融入到人們的日常生活中，網(wǎng)絡(luò)的服務(wù)質(zhì)量也越來越關(guān)聯(lián)著人們的日常生活質(zhì)量。然而當(dāng)網(wǎng)絡(luò)擁塞發(fā)生時(shí)，網(wǎng)絡(luò)的整體性能與服務(wù)質(zhì)量將會急劇下降， 伴隨網(wǎng)絡(luò)擁塞而來的高網(wǎng)絡(luò)時(shí)延與高網(wǎng)絡(luò)丟包率等還可能涉及違反相關(guān)服務(wù)等級協(xié)定（Service-Level Agreement, SLA）中的要求。網(wǎng)絡(luò)管理者為了及時(shí)有效地處理網(wǎng)絡(luò)擁塞，往往需要首先高效精確地定位出網(wǎng)絡(luò)中發(fā)生擁塞的鏈路。但由于網(wǎng)絡(luò)管理者通常并不具有直接操控訪問目標(biāo)（對等）網(wǎng)絡(luò)設(shè)備的權(quán)限，使得在目標(biāo)網(wǎng)絡(luò)中直接進(jìn)行擁塞鏈路定位缺乏實(shí)際可操作性。

當(dāng)無法直接對目標(biāo)網(wǎng)絡(luò)進(jìn)行測量時(shí)，網(wǎng)絡(luò)層析成像[1]成為一種重要的候選網(wǎng)絡(luò)測量方法。如同醫(yī)學(xué)B超成像不需要直接借助手術(shù)來觀察內(nèi)部器官那樣，網(wǎng)絡(luò)層析成像可以在完全不借助于網(wǎng)絡(luò)內(nèi)部節(jié)點(diǎn)協(xié)助的情況下，僅通過在網(wǎng)絡(luò)邊緣進(jìn)行端到端測量獲取路徑級性能參數(shù)，進(jìn)而據(jù)此來推斷網(wǎng)絡(luò)內(nèi)部鏈路相關(guān)的性能參數(shù)。在早期的網(wǎng)絡(luò)層析成像研究中，端到端測量常常采用多播測量的方式[1]。但由于多播協(xié)議在Internet中的支持度非常有限，目前被廣泛使用的是基于單播的測量方式，如模仿多播的背靠背[2]與包群測量方式[3]，用于測量共享路徑長度的三明治報(bào)文[4,5]，以及單純地基于單播報(bào)文進(jìn)行路徑擁塞狀態(tài)測量的方式[6,7]等。除了這些端到端測量方式的研究外，還有一些關(guān)于如何減少探測報(bào)文數(shù)目[8]以及如何有效地部署測量監(jiān)控節(jié)點(diǎn)[9]等的討論。

上述端到端測量方法要么假設(shè)端節(jié)點(diǎn)對之間只存在一條路由路徑[2-8,10,11]，要么假設(shè)能夠控制和選擇測量路徑[9,12]。而最近的研究發(fā)現(xiàn)表明，網(wǎng)絡(luò)中的流量均衡現(xiàn)象已經(jīng)較為普遍。其中，基于流的流量均衡方式（即具有相同五元組流具有相同的路由路徑）是網(wǎng)絡(luò)中較為常見的形式[13]。流量均衡將產(chǎn)生多徑路由現(xiàn)象，使得通信節(jié)點(diǎn)之間同時(shí)存在不止一條可用通信路徑，導(dǎo)致端到端探測流的測量路徑存在不確定性。文獻(xiàn)[14]理論上給出了一個(gè)在多徑路由場景下可唯一確定端到端測量路徑的充分條件，但其基于 K-均值聚類的測量路徑識別方法要求事先輸入正確的類數(shù)目[15]，而不正確的類數(shù)目可能會直接導(dǎo)致最終結(jié)果不可用。

在通過端到端測量得到路徑擁塞狀態(tài)后，文獻(xiàn)[7]通過將所有擁塞路徑的擁塞原因歸咎于它們的共享路徑，提出了最小一致故障集合（Smallest Consistent Failure Set, SCFS）算法來識別網(wǎng)絡(luò)擁塞鏈路。文獻(xiàn)[12]將SCFS從樹型結(jié)構(gòu)推廣到一般mesh網(wǎng)絡(luò)結(jié)構(gòu)，他們結(jié)合路由信息提出了用于故障鏈路定位的Tomo算法。不過這類基于布爾二元模型的擁塞鏈路定位算法只是單純地將路徑定義為正常和擁塞，并沒有有效利用路徑性能差異性所帶來的其他額外信息，在某些多擁塞鏈路場景下表現(xiàn)出較低的檢測率。例如，一條丟包率為10%的路徑相比于一條丟包率為1%的路徑，一般認(rèn)為前者非?？赡芙?jīng)歷了多條擁塞鏈路，而非僅僅是一條擁塞鏈路。此外還有文獻(xiàn)[8]結(jié)合壓縮感知，通過預(yù)估出網(wǎng)絡(luò)鏈路丟包率來識別高丟包鏈路的方法，但該方法不能有效確保丟包率的估計(jì)精度從而使其具有較高的誤檢率。

本文將多徑路由場景下的網(wǎng)絡(luò)擁塞鏈路識別分為如下3個(gè)子步驟：（1）端到端測量路徑識別。通過利用X-均值聚類算法[15]自適應(yīng)聚類測量流，提出一種針對基于流級的多徑路由測量路徑識別的方案；（2）路徑狀態(tài)量化。通過采用LM2丟包率模型[7]獲得多個(gè)丟包率門限值，進(jìn)而將路徑的不同丟包率量化成相應(yīng)不同的擁塞狀態(tài)，將布爾空間擴(kuò)展成多狀態(tài)空間[7]；（3）擁塞鏈路識別?；诰€性模型得到由路徑與鏈路擁塞狀態(tài)構(gòu)成的線性方程組，以此為約束，將擁塞鏈路識別問題轉(zhuǎn)化為一個(gè)約束最優(yōu)化問題，提出基于擴(kuò)展?fàn)顟B(tài)空間多徑路由網(wǎng)絡(luò)擁塞識別（Enlarged State Space based Congestion Link Identification, ESSCLI）算法求解該問題。

2 單源多徑路由網(wǎng)絡(luò)模型

將單源多徑路由網(wǎng)絡(luò)的邏輯拓?fù)浣３梢粋€(gè)有向無環(huán)圖 G = （ V, L），其中V代表網(wǎng)絡(luò)中的節(jié)點(diǎn)，L代表連接這些節(jié)點(diǎn)的有向鏈路。區(qū)別于建立在單徑路由下的單源樹型網(wǎng)絡(luò)拓?fù)?，多徑路由會使得單源網(wǎng)絡(luò)不再具有樹型拓?fù)浣Y(jié)構(gòu)。將G中的根節(jié)點(diǎn)用σ來表示，R代表目的節(jié)點(diǎn)集合。令U代表G中的內(nèi)部節(jié)點(diǎn)，那么有V ={σ}∪R∪U。令ζi,j代表連接從節(jié)點(diǎn)i∈V到節(jié)點(diǎn)j∈V的鏈路。用j∈d（ i）來表示節(jié)點(diǎn)j是節(jié)點(diǎn)i的一個(gè)下一跳節(jié)點(diǎn)，d（ i）是節(jié)點(diǎn)i的下一跳節(jié)點(diǎn)集合。將根節(jié)點(diǎn)σ到目的節(jié)點(diǎn)d∈R構(gòu)成的端節(jié)點(diǎn)對表示為Ωd，它們之間的所有子路徑集合為= {,… ,…}，其中代表第i條子路徑。令Pζi,j表示經(jīng)過鏈路ζi,j的所有路徑集合。當(dāng)|Pd|=1時(shí)，意味著端節(jié)點(diǎn)對Ωd之間是單徑路由，否則為多徑路由。

令 λ （ ξi, ξj） 表示端到端路徑 ξi與 ξj之間的分支節(jié)點(diǎn)集合；γ （ ξi, ξj） 表示端到端路徑 ξi與 ξj之間的匯合節(jié)點(diǎn)集合。同大多數(shù)現(xiàn)有方法一樣[1]，需假設(shè)? d 1, d 2 ∈R有 | λ）|=1，且當(dāng)d1≠d2時(shí)γ,）=φ。此外，還假設(shè)當(dāng)d1=d2時(shí)，有| γ）|= 1 。這表示達(dá)到不同目的節(jié)點(diǎn)的路徑在分離開后將不能再匯合，而多徑路由的子路徑之間能且也只能分離與匯合各一次。G中將不能出現(xiàn)度數(shù)為2的節(jié)點(diǎn)，且不能出現(xiàn)既為分支節(jié)點(diǎn)又為匯合節(jié)點(diǎn)的內(nèi)部節(jié)點(diǎn)。為了能夠唯一確定多徑路由各端到端測量子路徑，需要假定G滿足文獻(xiàn)[14]中提出的多徑路由拓?fù)湫枰獫M足的充分條件。一個(gè)典型的單源多徑路由網(wǎng)絡(luò)的邏輯拓?fù)鋱D如圖1所示。令∈?（d∈R,?代表自然數(shù)集合）表示路徑∈Pd的擁塞狀態(tài)，∈?表示鏈路ζi,j的擁塞狀態(tài)。令A(yù)表示網(wǎng)絡(luò)中的路由矩陣，其中如果其第i行第j列的元素 aij=1表示第i條路徑經(jīng)過了第j條鏈路。由于多條擁塞鏈路會加重路徑的擁塞狀態(tài)，因此使用路徑與鏈路狀態(tài)的矩陣表達(dá)形式Y(jié) =[…,,… ], X = [……]以及路由矩陣A，將路徑擁塞狀態(tài)與鏈路擁塞狀態(tài)之間的關(guān)系用如下線性系統(tǒng)模型進(jìn)行描述。

圖1 單源多徑路由網(wǎng)絡(luò)邏輯拓?fù)涫疽鈭D

3 端到端測量與擁塞鏈路識別

3.1 端到端測量

網(wǎng)絡(luò)多徑路由會使得網(wǎng)絡(luò)端到端節(jié)點(diǎn)對之間存在多條可達(dá)的路徑[13]。如此需要有兩個(gè)時(shí)隙：第 1個(gè)時(shí)隙獲得每條端到端路徑上的測量流信息；第 2個(gè)時(shí)隙進(jìn)行端到端路徑測量獲得路徑狀態(tài)。第1個(gè)時(shí)隙持續(xù)時(shí)間很短，一般平均每條探測流發(fā)送 200個(gè)左右的探測報(bào)文即能達(dá)到比較良好的路徑識別精度[14]，而且可以優(yōu)先選擇在網(wǎng)絡(luò)運(yùn)行正常的時(shí)候進(jìn)行該項(xiàng)測量。

3.1.1 多徑路由下測量路徑識別 源節(jié)點(diǎn)到目的節(jié)點(diǎn)d之間如果共存在有 n =| Pd|條子路徑，那么部署在端節(jié)點(diǎn)對之間的m條探測流中，每一條探測流都將有n條路由路徑可供選擇。不同于文獻(xiàn)[14]那樣需要假設(shè)已知所有子路徑的路由概率（即Ωd之間一條子路徑成為實(shí)際路由路徑的概率），我們基于 X-均值聚類算法[15]設(shè)計(jì)了一個(gè)自動增加測量流來達(dá)到測量覆蓋所有子路徑的目的。具體實(shí)現(xiàn)流程如下：

輸入 單源多徑路由網(wǎng)絡(luò)拓?fù)銰，目的節(jié)點(diǎn)d∈R, Ωd間路由路徑數(shù)目n =|Pd|

（1）在Ωd之間部署m=n條不同五元組的探測流，如 m = 1 ，為路徑 ξd選擇該探測流 ζd，并終止流程；

（2）按照從每條探測流一個(gè)探測包組成包群的模式對Ωd間路由路徑進(jìn)行探測覆蓋探測；

（3）計(jì)算探測流之間的時(shí)延協(xié)方差，得到 Cm2個(gè)協(xié)方差值，采用X-均值聚類算法輸出n?≤n個(gè)類；

（4）如果n? ＜n時(shí)，增加2（n-?n）條不同五元組的探測流到Ωd之間，并從步驟（1）重復(fù)開始；

（5）如果n?=n時(shí)，根據(jù)文獻(xiàn)[14]所提方法為每條子路徑 ξid∈Pd選擇擇一條探測流ζid，并終止流程。

∈Pd}

通過比較文獻(xiàn)[14]基于 K-均值聚類的方法，可以發(fā)現(xiàn)一旦出現(xiàn)有子路徑上沒有被測量流覆蓋到的情況時(shí)，K-均值聚類算法將無法發(fā)現(xiàn)有路徑上沒有成功部署測量流，并且仍將繼續(xù)輸出與子路徑相對應(yīng)數(shù)目的測量流類。而上述基于 X-均值聚類的方法，最主要的改進(jìn)就是能夠確保所有路徑上都部署有測量流。關(guān)于K-均值與X-均值性能的詳實(shí)比較與分析可以參見文獻(xiàn)[15]，后續(xù)性能分析將會略去這一部分。在通過所提方法得到每條路徑所對應(yīng)的測量流后，將要進(jìn)行第2個(gè)時(shí)隙的測量工作，即端到端路徑丟包率測量[7]。

3.1.2 路徑多擁塞狀態(tài)量化 當(dāng)在網(wǎng)絡(luò)路徑上如果出現(xiàn)了不止一條擁塞鏈路時(shí)，該網(wǎng)絡(luò)路徑的性能往往比只經(jīng)過一條擁塞鏈路的路徑要差，如前者可能具有更高的路徑丟包率。如此，基于LM2丟包率模型可以得到路徑丟包率多門限 T = { 0.01,1-（1 - ? ）2,… ,1 - （1 - ?）n} ，通過如下量化方法得到路徑的擁塞狀態(tài)：

當(dāng)路徑丟包率?＜0.01時(shí)，路徑擁塞狀態(tài)y=0，表示沒有路徑發(fā)生擁塞；而當(dāng)路徑丟包率 ? ≥ 0.01時(shí)，路徑擁塞狀態(tài) y ≥ 1 ，表示路徑發(fā)生了擁塞，擁塞狀態(tài)值y越大則表示擁塞程度越嚴(yán)重。 經(jīng)過這樣的量化處理后，路徑的擁塞狀態(tài)從傳統(tǒng)的二元狀態(tài)（故障或正常）[7]擴(kuò)展到如文獻(xiàn)[11]中所指出的多元狀態(tài)空間里，這將有利于后面的擁塞鏈路識別算法識別出網(wǎng)絡(luò)中更多的擁塞鏈路。

3.2 擁塞鏈路識別

當(dāng)網(wǎng)絡(luò)的運(yùn)行良好時(shí)，網(wǎng)絡(luò)中應(yīng)該是不存在擁塞鏈路或者是網(wǎng)絡(luò)發(fā)生擁塞的概率極低。顯然，當(dāng)網(wǎng)絡(luò)中擁塞鏈路越多時(shí)，網(wǎng)絡(luò)的整體性能就越差，因而網(wǎng)絡(luò)的運(yùn)行狀態(tài)也就越差。令η代表網(wǎng)絡(luò)擁塞狀態(tài)，那么定義網(wǎng)絡(luò)擁塞狀態(tài)如式（3）：

即網(wǎng)絡(luò)擁塞狀態(tài)是所有網(wǎng)絡(luò)鏈路擁塞狀態(tài)之和。此外還需要說明的一點(diǎn)是，網(wǎng)絡(luò)鏈路擁塞狀態(tài)x的大小有兩重含義：一是直接表示該鏈路的擁塞程度的高低；二則可以是表示該鏈路可能也是由多條實(shí)際擁塞的物理鏈路組成，因?yàn)檫壿嬐負(fù)銰中所包含的鏈路為邏輯鏈路，邏輯鏈路可以由多條物理鏈路組成[1]。因此當(dāng)最終確定了網(wǎng)絡(luò)中的擁塞鏈路，實(shí)際上更多地是指確定了一個(gè)擁塞區(qū)間，幫助網(wǎng)絡(luò)管理員縮小排查范圍，使其可以依據(jù)該擁塞區(qū)間以及結(jié)合網(wǎng)絡(luò)拓?fù)湫畔磉M(jìn)一步鎖定實(shí)際擁塞位置。

3.2.1 基于約束最優(yōu)化的擁塞鏈路識別 實(shí)際上，網(wǎng)絡(luò)運(yùn)營商由于受服務(wù)等級協(xié)定的約束，其網(wǎng)絡(luò)的故障率是需要被控制在一個(gè)較低水平的。當(dāng)兩條路徑擁塞時(shí)，我們可以認(rèn)為它們共享鏈路上存在擁塞，或者認(rèn)為所有經(jīng)過的鏈路都存在擁塞。如果假設(shè)網(wǎng)絡(luò)中每條鏈路發(fā)生擁塞概率都相同，明顯前者發(fā)生的可能性將會更高。如此，網(wǎng)絡(luò)擁塞鏈路識別的一個(gè)合理目標(biāo)是找到一組擁塞鏈路，從而使得網(wǎng)絡(luò)擁塞狀態(tài)η達(dá)到最小。此外，這樣一組擁塞鏈路還需要能夠解釋端到端觀測結(jié)果，即需要滿足式（1）。通過以式（1）為約束，以最小化網(wǎng)絡(luò)擁塞狀態(tài)η為目標(biāo)，將網(wǎng)絡(luò)擁塞鏈路識別問題轉(zhuǎn)化為一個(gè)如式（4）所示的約束最優(yōu)化問題。

根據(jù)擁塞狀態(tài)量化公式（2）可以知道，如果當(dāng)所得到的鏈路狀態(tài) 0x＞ 時(shí)，該鏈路即為擁塞鏈路。不同于傳統(tǒng)的布爾模型僅僅只識別出鏈路是否擁塞，通過上述約束最優(yōu)化問題所得到的擁塞鏈路狀態(tài)x還能一定程度指示鏈路的擁塞程度。

3.2.2 ESSCLI算法 傳統(tǒng)SCFS算法以及Tomo算法認(rèn)為所有擁塞路徑的擁塞完全是由它們的共享鏈路發(fā)生擁塞所引起的。ESSCLI算法則認(rèn)為這只能解釋部分路徑發(fā)生的擁塞，并不能解釋為什么路徑擁塞程度上存在的差異性。事實(shí)上，擁塞程度越嚴(yán)重的路徑往往預(yù)示著其經(jīng)歷了不止一條擁塞鏈路。因此，ESSCLI并不會在找到公共擁塞鏈路后停止搜索，反而會進(jìn)一步依據(jù)路徑擁塞程度的不同來搜索其他可能存在的擁塞鏈路。為了求解上述約束最優(yōu)化問題式（4），首先將對單源多徑路由網(wǎng)絡(luò)拓?fù)溥M(jìn)行分解。

定理 給定單源多徑路由網(wǎng)絡(luò) G = （ V, L），存在一種圖割方法使得得到的兩個(gè)子圖中：其中一個(gè)子圖的內(nèi)部節(jié)點(diǎn)全是分支節(jié)點(diǎn)，另外一個(gè)子圖的內(nèi)部節(jié)點(diǎn)全是匯合節(jié)點(diǎn)。

證明 根據(jù)網(wǎng)絡(luò)模型定義可知單源多徑路由網(wǎng)絡(luò)G是一個(gè)連通圖。網(wǎng)絡(luò)G內(nèi)部節(jié)點(diǎn)由分支節(jié)點(diǎn)與匯合節(jié)點(diǎn)組成，如此則有， U ={λ）|d1, d2∈R} ∪ {γ（）|d1, d 2 ∈R}。但根據(jù)單源多徑路

如果存在分支節(jié)點(diǎn)到匯聚節(jié)點(diǎn)這樣類型的鏈路，則表明存在兩條經(jīng)過該鏈路的路徑與，其中d 1 = d 2 ∈R且有 | Pd1|＞ 1 。因?yàn)閷τ趦蓷l具有不同目的節(jié)點(diǎn)的路徑，其 γ）=φ。那么，與在它們最終同時(shí)達(dá)到 d1時(shí)，必然還經(jīng)過一個(gè)匯合節(jié)點(diǎn)。如此一來，有 | γ） |≥ 2 ，而這與單源多徑路由網(wǎng)絡(luò)G假設(shè) | γ） |= 1 的要求不相符。因此，即證明網(wǎng)絡(luò)G中不存在分支節(jié)點(diǎn)到匯聚節(jié)點(diǎn)這樣類型的鏈路。由分支節(jié)點(diǎn)與匯合節(jié)點(diǎn)構(gòu)成的鏈路類型有：分支節(jié)點(diǎn)到分支節(jié)點(diǎn)、分支節(jié)點(diǎn)到匯合節(jié)點(diǎn)以及匯合節(jié)點(diǎn)到匯合節(jié)點(diǎn)，共3種類型。通過上面的證明可以知道匯合節(jié)點(diǎn)只存在由根節(jié)點(diǎn)到多徑路由目的節(jié)點(diǎn)之間（|Pd|＞ 1 ）。因此，將網(wǎng)絡(luò)G中所有分支節(jié)點(diǎn)到匯合節(jié)點(diǎn)這種類型的鏈路分割，必將得到兩個(gè)部分：一個(gè)是以根節(jié)點(diǎn)構(gòu)成的樹型拓?fù)?；另外一個(gè)是由所有多徑路由目的節(jié)點(diǎn){d ||Pd|＞ 1 }構(gòu)成的森林。由于分割得到的森林是由反向樹組成的，因而其內(nèi)部節(jié)點(diǎn)全是匯合節(jié)點(diǎn)；顯然，由根節(jié)點(diǎn)構(gòu)成的樹型拓?fù)鋬?nèi)部節(jié)點(diǎn)全是分支節(jié)點(diǎn)。至此，定理得證。

輸入 G以及其一個(gè)分割T與T，路徑端到端測量值{yrj|r ∈R,∈Pr}，初始的擁塞鏈路集合=φ。

（2）?i∈α ，得到β=d（ i）。如果β ≠ φ，那么?j ∈ β, xij= m in{y ∈ Pζi,j}，并且對于 ? y ∈ Pζi,j，更新 y = y - xij；

（3）更新 α = ∪i∈αd（ i） ，如果 α=φ 則已完成對樹型拓?fù)滏溌窊砣麪顟B(tài)的?估計(jì)，否則執(zhí)行第（2）步；

（6）對τ'，執(zhí)行上述第（2）與第（3）步；

（7）將τ'中所有最后一條鏈路的擁塞狀態(tài)復(fù)制給G中對應(yīng)?的分割鏈路；

4 仿真與性能評估

4.1 仿真場景設(shè)置

為了比較所提擁塞鏈路識別算法的性能，將基于使用網(wǎng)絡(luò)仿真軟件 NS[16]開展相關(guān)的網(wǎng)絡(luò)實(shí)驗(yàn)并進(jìn)行。如文獻(xiàn)[13]所指出的那樣，基于五元組流的均勻網(wǎng)絡(luò)流量均衡是網(wǎng)絡(luò)中較為常見的網(wǎng)絡(luò)流量均衡類型，本文基于哈希分類算法實(shí)現(xiàn)相應(yīng)的流量均衡模塊。根據(jù)網(wǎng)絡(luò)端到端路徑數(shù)目的多少，仿真網(wǎng)絡(luò)共分有10種不同的規(guī)模（見表1）。在所采用的各仿真網(wǎng)絡(luò)中，網(wǎng)絡(luò)內(nèi)部鏈路的帶寬為10 Mbit/s而網(wǎng)絡(luò)邊緣鏈路的帶寬為5 Mbit/s。內(nèi)部鏈路傳輸?shù)裙潭〞r(shí)延設(shè)定為20 ms，邊緣鏈路則設(shè)定為10 ms。網(wǎng)絡(luò)流量由基于 UDP與 TCP傳輸協(xié)議的通信流組成。其中UDP流為服從帕累托分布，TCP流為FTP文件傳輸流。網(wǎng)絡(luò)正常鏈路的帶寬利用率≤75%，丟包率≤0.1%；擁塞鏈路的帶寬利用率≥93%,1%≤丟包率≤1.5%。仿真網(wǎng)絡(luò)中擁塞鏈路形成機(jī)制為通過加載大量通信流到相應(yīng)鏈路上使其擁塞而產(chǎn)生大量網(wǎng)絡(luò)丟包。

根據(jù)文獻(xiàn)[13]中所述網(wǎng)絡(luò)中多徑路由比例大小，在各仿真網(wǎng)絡(luò)中將所有端到端路徑中多徑路由路徑比例設(shè)置為40%左右，即|{Pd|d ∈R,| Pd|＞1}|/|{Pd|d ∈R}|≈40%。由于網(wǎng)絡(luò)一般不會出現(xiàn)大量同時(shí)擁塞的鏈路，因此將擁塞鏈路的最高比例設(shè)置為19%。各不同網(wǎng)絡(luò)仿真場景重復(fù)實(shí)驗(yàn)30次，并選取適用于一般 Mesh網(wǎng)絡(luò)的 Tomo算法[12]和 L1-L2算法[8]與所提ESSCLI算法進(jìn)行比較。相應(yīng)評價(jià)算法檢測性能的指標(biāo)采用檢測率 DR= | ? ∩| /|? |，以及誤檢率 FPR= | {L ? } ∪| /|{L ? } | （這其中?表示G中實(shí)際擁塞鏈路集合）。

4.2 性能評估

圖2與圖3分別是ESSCLI, Tomo以及L1-L2算法在網(wǎng)絡(luò)1（見表1）中不同擁塞鏈路比例下的檢測率DR與誤檢率FPR性能。根據(jù)圖2可以看出，所有3個(gè)算法的DR隨著網(wǎng)絡(luò)中擁塞鏈路的增多而呈現(xiàn)出不同程度的降低。其中Tomo算法的DR下降得最劇烈，這是由于其采用了一個(gè)較為保守的貪婪策略：將端到端擁塞路徑的擁塞原因僅僅歸結(jié)為它們的共享鏈路上發(fā)生了擁塞。這樣的貪婪策略會阻止Tomo算法進(jìn)一步發(fā)現(xiàn)更多的擁塞鏈路。相反，ESSCLI算法通過對路徑狀態(tài)映射到多元狀態(tài)來反映路徑不同的擁塞程度，并基于不同擁塞狀態(tài)所帶來的額外信息繼續(xù)搜索擁塞鏈路，直到所有路徑的不同擁塞狀態(tài)得到解釋。而 L1-L2算法也能取得比Tomo算法較好的DR，這主要得益于其線性模型也利用了路徑丟包率不同所帶來的額外有用信息。但其由于其在鏈路丟包率估計(jì)時(shí)所引入的較大誤差，可以發(fā)現(xiàn)L1-L2算法的DR要比ESSCLI算法低，而且更重要的是，估計(jì)不準(zhǔn)確的鏈路丟包率還導(dǎo)致L1-L2表現(xiàn)出非常不理想的 FPR。值得注意的是，Tomo算法正是得益于其保守的貪婪策略使得其具有最小的FPR。盡管如此，隨著網(wǎng)絡(luò)擁塞鏈路的增多，能夠解釋端到端路徑擁塞的擁塞鏈路集合也增多了，從而會導(dǎo)致算法的FPR相應(yīng)地增大，如圖3所示。

圖4與圖5展示的是3種算法當(dāng)網(wǎng)絡(luò)鏈路擁塞比例設(shè)定為0.1時(shí)，在如表1所示的不同網(wǎng)絡(luò)規(guī)模下的檢測率與誤檢率性能。如圖4與圖5所示的3種算法的檢測率和誤檢率隨著網(wǎng)絡(luò)規(guī)模的增大而呈現(xiàn)正常的波動，但是整體趨勢上看，3種算法的性能均都沒有明顯地表現(xiàn)出隨網(wǎng)絡(luò)規(guī)模增大而相應(yīng)地增大或減小的趨勢。雖然網(wǎng)絡(luò)規(guī)模對于檢測性能影響不大，但是網(wǎng)絡(luò)規(guī)模大小卻直接關(guān)聯(lián)著算法的計(jì)算復(fù)雜度。表2為在Intel i5-3317U@1.70 GHz中央處理器與4 GB內(nèi)存計(jì)算機(jī)上各算法平均運(yùn)行一次所需的對數(shù)計(jì)算時(shí)間。從表2可以看出，ESSCLI算法由于具有較Tomo大的搜索深度，其計(jì)算時(shí)間也相應(yīng)要表現(xiàn)得略高些。但相比于直接搜索的ESSCLI與Tomo算法，L1-L2算法因其迭代搜索方式增加了計(jì)算復(fù)雜度，導(dǎo)致計(jì)算時(shí)間明顯增加。

表1 仿真網(wǎng)絡(luò)規(guī)模參數(shù)

圖2 不同擁塞鏈路比例下的算法檢測率

圖3 不同擁塞鏈路比例下的算法誤檢率

圖4 不同網(wǎng)絡(luò)規(guī)模下的算法檢測

表2 各算法平均運(yùn)行一次所需的對數(shù)（lg）計(jì)算時(shí)間（s）

圖5 不同網(wǎng)絡(luò)規(guī)模下的算法誤檢率

5 結(jié)束語

基于自適應(yīng)聚類算法能夠規(guī)避路徑漏測的風(fēng)險(xiǎn)。所提算法能有效地應(yīng)對多擁塞鏈路網(wǎng)絡(luò)場景，且能快速高效地識別出網(wǎng)絡(luò)中的擁塞鏈路并且保持較低的誤檢率。良好的檢測性能論證了將擁塞鏈路識別問題轉(zhuǎn)化為約束最優(yōu)化問題的合理性。但注意到準(zhǔn)確的丟包率測量需要較長的測量周期，研究如何基于路徑時(shí)延特征來衡量路徑擁塞狀態(tài)進(jìn)而達(dá)到大大縮短測量周期的目的，將是未來可能的一個(gè)研究方向。

[1] Castro R, Coates M, Liang G, et al.. Network tomography:recent developments[J]. Statistical Science, 2004, 19（3）:499-517.

[2] Duffield N and Presti F. Network tomography from measured end-to-end delay covariance[J]. IEEE/ACM Transactions on Networking, 2004, 12（6）: 978-992.

[3] Duffield N, Presti F, Paxson V, et al.. Inferring link loss using striped unicast probes[C]. Proceedings of IEEE INFOCOM,Anchorage, 2001, 2: 915-923.

[4] Coates M, Castro R, Nowak R, et al.. Maximum likelihood network topology identification from edge-based unicast measurements[C]. Proceedings of ACM SIGMETRICS,Marina Del Rey, 2003: 11-20.

[5] Malekzadeh A and MacGregor M. Network Topology inference from end-to-end measurements[C]. the 27th IEEE Advanced Information Networking and Applications Workshops, Barcelona, 2013: 1101-1106.

[6] Wei W, Wang B, Towsley D, et al.. Model-based identification of dominant congested link[J]. IEEE/ACM Transactions on Networking, 2011, 19（2）: 456-469.

[7] Duffield N. Network tomography of binary network performance characteristics[J]. IEEE Transactions on Information Theory, 2006, 52（12）: 5373-5388.

[8] Matsuda T, Nagahara M, and Hayashi K. Link quality classifier with compressed sending based on12-??optimization[J]. IEEE Communications Letters, 2011, 15（10）:1117-1119.

[9] Ma L, He T, Leung K, et al.. Monitor placement for maximal identifiability in network tomography[C]. Proceedings of IEEE INFOCOM, Toronto, 2014: 1447-1455.

[10] Eriksson B, Dasarathy G, Barford P, et al.. Efficient network tomography for Internet topology discovery[J]. IEEE/ACM Transactions on Networking, 2012, 20（3）: 931-943.

[11] Ghita D, Argyraki K, and Thiran P. Toward accurate and practical network tomography[J]. ACM SIGOPS Operating Systems Review, 2013, 47（1）: 22-26.

[12] Dhamdhere A, Teixeira R, and Dovrolis C, et al..NetDiagnoser: troubleshooting network unreachabilities using end-to-end probes and routing data[C]. Proceedings of ACM CoNEXT, New York, 2007: 18.

[13] Augustin B, Friedman T, and Teixeira R. Measuring multipath routing in the Internet[J]. IEEE/ACM Transactions on Networking, 2011, 19（3）: 830-840.

[14] Pan S, Zhang Z, Yu F, et al.. End-to-end measurements for network tomography under multipath routing[J]. IEEE Communications Letters, 2014, 18（5）: 881-884.

[15] Pelleg D and Moore A. X-means: extending k-means with efficient estimation of the number clusters[C]. Proceedings of ICML, Stanford, 2000: 727-734.

[16] Henderson T. ns-3.21 released[OL]. http://www.nsnam.org/news/ns-3-21-released/. 2014.9.