單源多徑路由網(wǎng)絡擁塞鏈路識別

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

1 引言

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

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

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

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

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

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

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

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

圖1 單源多徑路由網(wǎng)絡邏輯拓撲示意圖

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

3.1 端到端測量

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

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

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

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

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

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

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

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

∈Pd}

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

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

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

3.2 擁塞鏈路識別

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

即網(wǎng)絡擁塞狀態(tài)是所有網(wǎng)絡鏈路擁塞狀態(tài)之和。此外還需要說明的一點是，網(wǎng)絡鏈路擁塞狀態(tài)x的大小有兩重含義：一是直接表示該鏈路的擁塞程度的高低；二則可以是表示該鏈路可能也是由多條實際擁塞的物理鏈路組成，因為邏輯拓撲G中所包含的鏈路為邏輯鏈路，邏輯鏈路可以由多條物理鏈路組成[1]。因此當最終確定了網(wǎng)絡中的擁塞鏈路，實際上更多地是指確定了一個擁塞區(qū)間，幫助網(wǎng)絡管理員縮小排查范圍，使其可以依據(jù)該擁塞區(qū)間以及結(jié)合網(wǎng)絡拓撲信息來進一步鎖定實際擁塞位置。

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

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

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

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

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

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

輸入 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） ，如果 α=φ 則已完成對樹型拓撲鏈路擁塞狀態(tài)的?估計，否則執(zhí)行第（2）步；

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

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

4 仿真與性能評估

4.1 仿真場景設(shè)置

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

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

4.2 性能評估

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

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

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

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

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

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

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

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

5 結(jié)束語

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

[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.