單源多徑路由網絡擁塞鏈路識別

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

1 引言

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

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

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

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

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

2 單源多徑路由網絡模型

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

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

圖1 單源多徑路由網絡邏輯拓撲示意圖

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

3.1 端到端測量

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

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

輸入 單源多徑路由網絡拓撲G，目的節點d∈R, Ωd間路由路徑數目n =|Pd|

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

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

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

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

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

∈Pd}

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

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

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

3.2 擁塞鏈路識別

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

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

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

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

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

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

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

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

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

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

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

4 仿真與性能評估

4.1 仿真場景設置

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

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

4.2 性能評估

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

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

表1 仿真網絡規模參數

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

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

圖4 不同網絡規模下的算法檢測

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

圖5 不同網絡規模下的算法誤檢率

5 結束語

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

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