基于線性松弛方法的網(wǎng)絡(luò)故障鏈路診斷

范曉波，李興明

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

0 引言

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

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

不同于已有的故障鏈路檢測技術(shù)，受文獻(xiàn)[9]和[10]中凸松弛法的啟發(fā)，本文提出了一個(gè)簡單而有效的線性規(guī)劃(Linear Programming, LP)松弛方法來定位網(wǎng)絡(luò)中故障的鏈路。該方法將鏈路狀態(tài)的布爾約束松弛到連續(xù)區(qū)間，然后將問題轉(zhuǎn)化為一般線性規(guī)劃問題。

1 模型和框架

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

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

記n為網(wǎng)絡(luò)中的總鏈路數(shù)，根據(jù)上式，可以得到：

(1)

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

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

y=R⊙x

(2)

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

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

(3)

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

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

2 線性松弛方法

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

顯而易見，式(3)的優(yōu)化目標(biāo)是關(guān)于x的線性函數(shù)：

(4)

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

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

(5)

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

由于式(5)為常規(guī)的線性規(guī)劃，即使網(wǎng)絡(luò)規(guī)模非常大，仍能得到有效的求解，譬如采用內(nèi)點(diǎn)法[12]。

3 仿真和性能分析

3.1 仿真環(huán)境

為了驗(yàn)證本文方法的有效性，本文使用Matlab搭建仿真平臺，測試了故障檢測算法在不同的網(wǎng)絡(luò)拓?fù)湎碌谋憩F(xiàn)性能。實(shí)驗(yàn)網(wǎng)絡(luò)拓?fù)洳捎肦ocketfuel項(xiàng)目所測量的實(shí)際ISP(Internet Service Provider)骨干網(wǎng)絡(luò)拓?fù)鋄13]：AS4755和AS7018，AS4755是一個(gè)小規(guī)模的網(wǎng)絡(luò)而AS7018相對較大。對于每個(gè)網(wǎng)絡(luò)，實(shí)驗(yàn)中選擇邊界節(jié)點(diǎn)(度為1的節(jié)點(diǎn))作為測量節(jié)點(diǎn)。然后通過最短路徑路由建立任意兩個(gè)測量節(jié)點(diǎn)之間的測量路徑。注意到有些鏈路可能沒有被任何測量路徑所經(jīng)過。由于這些鏈路的狀態(tài)始終不能被識別，故而刪除這些鏈路。表1總結(jié)了實(shí)驗(yàn)中采用的修改后的網(wǎng)絡(luò)拓?fù)浜蜏y量路徑。

表1 實(shí)驗(yàn)中使用的網(wǎng)絡(luò)拓?fù)?/p>

在每一次的仿真模擬實(shí)驗(yàn)中，從網(wǎng)絡(luò)中隨機(jī)挑選k%條鏈路作為故障鏈路，k值表示網(wǎng)絡(luò)所遭受的故障級別。為了仿真在不同的故障級別下算法的性能，本文設(shè)定故障鏈路百分比為5%至30%。實(shí)驗(yàn)步驟簡要總結(jié)如下：

1)選擇網(wǎng)絡(luò)拓?fù)銩S4755或AS7018，并在網(wǎng)絡(luò)中隨機(jī)選擇k%條鏈路視為故障鏈路；

2)在網(wǎng)絡(luò)中的測量節(jié)點(diǎn)之間發(fā)送探測包，根據(jù)測量路徑是否經(jīng)過故障鏈路來判定探測包是否發(fā)送成功；

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

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

其中：Sa表示真正發(fā)生故障的鏈路，Sd表示算法檢測到的故障鏈路。在檢測理論中，F(xiàn)NR和FPR通常聯(lián)合使用用來綜合評估一個(gè)算法的有效性。

3.2 仿真結(jié)果

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

圖1 兩種方法在AS4755的漏報(bào)率和誤報(bào)率對比

圖2 兩種方法在AS7018的漏報(bào)率和誤報(bào)率對比

圖3 兩種方法在AS4755中漏報(bào)率出現(xiàn)次數(shù)對比

4 結(jié)語

本文研究了如何通過端到端路徑測量在通信網(wǎng)絡(luò)中檢測故障鏈路的問題。由于該問題是NP難的，本文采用一種直觀有效的方法，即通過松弛變量的非凸布爾約束，將問題簡單化為線性規(guī)劃。在實(shí)際網(wǎng)絡(luò)拓?fù)渖蠈υ摲椒ǖ男阅苓M(jìn)行了評估，結(jié)果表明，與常用的貪婪算法相比，該算法具有更低的漏報(bào)率和可比的誤報(bào)率。本文研究的是故障鏈路診斷問題，下一步工作重點(diǎn)將是拓展該方法，如何檢測網(wǎng)絡(luò)中特別是無線網(wǎng)絡(luò)中的故障節(jié)點(diǎn)問題。