基于線性松弛方法的網絡故障鏈路診斷

范曉波，李興明

(電子科技大學 通信與信息工程學院，成都 611731)(*通信作者電子郵箱xiaobof@outlook.com)

0 引言

網絡中的鏈路故障會導致終端用戶的連接中斷，因而快速、準確地定位網絡內部的故障鏈路對于維護網絡性能、提升網絡服務質量有著重要意義。除了物理鏈路的故障，一些如路由器配置錯誤等“軟”的錯誤也會導致連接失敗[1]。最簡單、直接的診斷故障鏈路的方法是通過網絡內部節點間的協作直接監測鏈路性能參數，但是出于安全因素的考慮，內部節點通常不協作，因此直接監測的難度較大。近年來，網絡層析(network tomography)技術[2-3]在網絡推理中得到了廣泛的應用。網絡層析技術可以在沒有中間節點協作的條件下，通過主動發送端到端探測包或被動收集有用的信息來估計網絡內部性能參數。由于其僅需要在網絡邊緣進行端到端測量，無需內部節點的協作，適用于復雜網絡環境，同時其可擴展性強，因而受到了廣泛的關注。

采用網絡層析技術識別故障鏈路的思路最早由Coates等[2]和Padmanabhan等[4]提出。其思路是選擇一些路徑，然后通過在這些路徑上主動發送端到端探測包來識別故障鏈路。對于每一條路徑，當且僅當路徑上的任意鏈路出現故障時，整條路徑就會失敗。由于只有兩種狀態，這種層析技術也稱為布爾層析[1,5-8]。布爾層析將鏈路和路徑的狀態看作是布爾型的，其中0表示正常和1意味著失敗，而鏈路和路徑的狀態在布爾代數[6]中是線性相關的。然后將布爾層析成像看作是一個優化問題，即找出最小的鏈路失效集，以解釋所測量路徑的狀態。然而，求解此類優化問題一般是NP(Nondeterministic Polynomial)難的，因此，當前研究中普遍采用貪婪啟發式算法。在文獻[1]中提出了一種TOMO(TOMOgraphy)方法，該方法迭代地選擇那些能解釋最多失效路徑的鏈路當作故障鏈路。文獻[6]提出了一種類似的方法CLINK(Congested Link identification)，該方法可以看作是將鏈路的故障先驗概率作為權重的TOMO加權版本，并提出了一個使用多種測量時隙聯立方程來學習這些概率的方法。類似文獻[6]，文獻[7]提出一種基于因子圖—和積方法來估計先驗概率。然而，由于先驗概率的估計總是需要多個測量時隙，在實際應用中受限。此外，文獻[8]研究了在布爾層析中使用不同的端到端探測機制時定位故障的能力。

不同于已有的故障鏈路檢測技術，受文獻[9]和[10]中凸松弛法的啟發，本文提出了一個簡單而有效的線性規劃(Linear Programming, LP)松弛方法來定位網絡中故障的鏈路。該方法將鏈路狀態的布爾約束松弛到連續區間，然后將問題轉化為一般線性規劃問題。

1 模型和框架

同大多數現有的基于端到端測量來推斷網絡內部性能研究類似，本文將一個無向網絡建模為一個圖G=(V,E)，其中：V表示網絡中的主機或中間路由設備集合，E代表網絡中的鏈路集合。為了監測網絡中的故障情況，從V中選擇一些節點集合M(M?V)作為測量節點，通過在測量節點之間發送和接收探測包得到路徑測量信息，最后從路徑的測量狀態中推斷出網絡內部的鏈路狀態(正常/故障)。

鏈路和路徑的狀態之間的關系可以表示為如下布爾代數模型。令布爾變量yl表示路徑pl的狀態，布爾變量xk表示鏈路ek的狀態，并約定對于路徑和鏈路，均用0代表正常、用1代表故障。由于當且僅當路徑上的任意鏈路出現故障時，整條路徑發送的探測包就會失敗，因此鏈路狀態和路徑的狀態有如下關系式：

記n為網絡中的總鏈路數，根據上式，可以得到：

(1)

其中“∨”表示布爾代數中的OR操作，rlk取值為{0,1}，如果ek∈pl則rlk取值為1；否則取值為0。

不失一般性，假設網絡中總共有m條測量路徑，對于每一條測量路徑，都有如式(1)的等式成立。為了簡便起見，將這m個等式寫成如下矩陣形式：

y=R⊙x

(2)

其中：y=(y1,y2,…,ym)T表示m條端到端測量路徑的狀態，x=(x1,x2,…,xn)T表示n條鏈路的狀態，注意x，y均為布爾向量。R=[rlk]為一個m×n0- 1矩陣，由于其代表的含義為相關路徑是否經過相關鏈路，因而又稱為路由矩陣(routing matrix)。最后，式中的⊙為布爾矩陣中的相乘操作，y的每一項由式(1)所確定。

由于網絡端到端的路由相對固定，因而鏈路故障檢測即為給定R和路徑測量y，求解式(2)中的布爾向量x。在實際測量中式(2)總是存在多個解。由于在網絡中，出現故障的鏈路總是網絡所有鏈路的很小部分，現有的網絡層析技術將問題轉換為找到一個最小的故障集合用來解釋所有觀測到的端到端路徑結果[1]，這可用如下優化問題描述：

(3)

s.t.y=R⊙x,xi∈{0,1}

事實上，如果把網絡里每條路徑看作是鏈路集合，那么式(3)即是如下問題的數學描述：尋找最小的故障鏈路集合，使得該集合與每條故障路徑都要相交，且和每條未發生故障路徑(正常路徑)都不能相交。該問題為最小碰集問題(Minimum Hitting Set)[11]的一個特例，由于最小碰集問題為著名NP難問題，因而求解優化表達式(3)是NP難的。現有的鏈路診斷研究普遍采用貪婪啟發式算法[1,6-8]求解。大體來說，在每一次迭代，它們選擇具有最大“分數”的那條鏈路作為故障鏈路，這里的分數通常被定義為通過鏈路的未被解釋的故障路徑數。

2 線性松弛方法

不同于已有的故障鏈路檢測技術，本文提出了一個簡單而有效的線性規劃(LP)松弛方法來求解式(3)，從而定位網絡中故障的鏈路。在線性松弛過程中分為兩步來進行，首先將優化問題(3)等價變換為二元線性規劃，然后松弛其自變量的二元限制得到常規線性規劃。

顯而易見，式(3)的優化目標是關于x的線性函數：

(4)

s.t.RJx=0,RIx≥yI,xi∈{0,1}

通過上述等價變換，得到的問題(4)實際上是一個二元線性規劃(binary linear programming)，眾所周知，也是一個NP難題。然而，通過松弛布爾限制xi∈{0,1}，可得到一個常規的線性規劃：

(5)

s.t.RJx=0,RIx≥yI, 0≤xi≤1

由于式(5)為常規的線性規劃，即使網絡規模非常大，仍能得到有效的求解，譬如采用內點法[12]。

3 仿真和性能分析

3.1 仿真環境

為了驗證本文方法的有效性，本文使用Matlab搭建仿真平臺，測試了故障檢測算法在不同的網絡拓撲下的表現性能。實驗網絡拓撲采用Rocketfuel項目所測量的實際ISP(Internet Service Provider)骨干網絡拓撲[13]：AS4755和AS7018，AS4755是一個小規模的網絡而AS7018相對較大。對于每個網絡，實驗中選擇邊界節點(度為1的節點)作為測量節點。然后通過最短路徑路由建立任意兩個測量節點之間的測量路徑。注意到有些鏈路可能沒有被任何測量路徑所經過。由于這些鏈路的狀態始終不能被識別，故而刪除這些鏈路。表1總結了實驗中采用的修改后的網絡拓撲和測量路徑。

表1 實驗中使用的網絡拓撲

在每一次的仿真模擬實驗中，從網絡中隨機挑選k%條鏈路作為故障鏈路，k值表示網絡所遭受的故障級別。為了仿真在不同的故障級別下算法的性能，本文設定故障鏈路百分比為5%至30%。實驗步驟簡要總結如下：

1)選擇網絡拓撲AS4755或AS7018，并在網絡中隨機選擇k%條鏈路視為故障鏈路；

2)在網絡中的測量節點之間發送探測包，根據測量路徑是否經過故障鏈路來判定探測包是否發送成功；

3)記I為發送失敗的路徑，J為發送成功的路徑，然后求解線性規劃式(5)得到鏈路狀態向量x*；

同時為了驗證所提出的方案的有效性，將所提出的線性松弛方法和啟發式算法TOMO[1]進行了比較，TOMO被廣泛運用于IP網絡中的故障診斷。評價指標采用漏報率(False Negative Rate, FNR)和誤報率(False Positive Rate, FPR)。FNR是指將故障鏈路錯誤的判定為正常鏈路的比率，而FPR是指將正常鏈路判定為故障鏈路的比率。其計算公式如下：

其中：Sa表示真正發生故障的鏈路，Sd表示算法檢測到的故障鏈路。在檢測理論中，FNR和FPR通常聯合使用用來綜合評估一個算法的有效性。

3.2 仿真結果

對于每次參數設定下的仿真結果，給出其500次實驗的平均值。仿真結果顯示在圖1～2中，分別對應網絡AS4755和AS7018。從圖中可以看出線性松弛方法和TOMO方法具有類似的變化趨勢，具體來說，隨著鏈路故障數的增加，這兩種算法的漏報率和誤報率都越來越高。這是因為在存在很多個鏈路故障時，很難找到網絡中所有的故障。從結果中還可以看出，檢測故障鏈路主要的錯誤來源是漏報率(在大多數情況下，誤報率都小于0.1)，也就是說，算法很容易忽略一個真正的鏈路故障，而不是錯誤地將一條正常鏈路識別為故障鏈路，這和文獻[1]的結論是一致的。最后，從圖1和圖2可以看出，線性松弛方法比TOMO方法的漏報率要低，特別是當鏈路故障比例較高時。譬如，當故障鏈路比率大于20%時，從圖中可以看出本文的線性松弛方法的FNR明顯低于TOMO算法(對于拓撲AS4755約改善30%，拓撲AS7018約改善10%)。這一點也可從圖3中得到驗證，圖3顯示了在500次仿真中漏報率FNR出現的次數，設定實際故障鏈路數為3，因而漏報率取值范圍為{0,1/3,2/3,1}。由圖可見，線性松弛法大多數情況下漏報率為0，而TOMO方法出現高漏報率次數顯然較多。綜合實驗結果分析可以得知，線性松弛方法在漏報率上要低于TOMO方法，而誤報率兩個算法都很小且近似相等(LP松弛法有極小幅增加)，證實了線性松弛方法的有效性。

圖1 兩種方法在AS4755的漏報率和誤報率對比

圖2 兩種方法在AS7018的漏報率和誤報率對比

圖3 兩種方法在AS4755中漏報率出現次數對比

4 結語

本文研究了如何通過端到端路徑測量在通信網絡中檢測故障鏈路的問題。由于該問題是NP難的，本文采用一種直觀有效的方法，即通過松弛變量的非凸布爾約束，將問題簡單化為線性規劃。在實際網絡拓撲上對該方法的性能進行了評估，結果表明，與常用的貪婪算法相比，該算法具有更低的漏報率和可比的誤報率。本文研究的是故障鏈路診斷問題，下一步工作重點將是拓展該方法，如何檢測網絡中特別是無線網絡中的故障節點問題。