齊小剛， 王曉琳， 劉立芳

(1. 西安電子科技大學 數(shù)學與統(tǒng)計學院，陜西 西安 710071;2. 西安電子科技大學 計算機學院，陜西 西安 710071)

在全光網(wǎng)中，故障管理是至關(guān)重要的功能塊．當網(wǎng)絡中的光纖遭到破壞時，鏈路上的所有業(yè)務都會中斷．因此，一旦網(wǎng)絡中發(fā)生故障，就需要進行故障診斷來定位故障發(fā)生的確切位置，從而進行進一步的故障分離和故障修復以恢復中斷的業(yè)務．因為全光網(wǎng)絡具有全光傳輸?shù)奶匦?，光路上的中間節(jié)點不進行光電轉(zhuǎn)換，所以也就不能對信號采用傳統(tǒng)的電子監(jiān)測手段進行監(jiān)測[1]．作為補救，文獻[2]研究了基于鏈路的監(jiān)測，這種監(jiān)測方法對每條鏈路單獨進行一次測試，即通過單跳監(jiān)管光路發(fā)送光信號監(jiān)測每條鏈路，這使得發(fā)送的探測數(shù)等于網(wǎng)絡中的鏈路數(shù)．

為了減少發(fā)送的探測數(shù)，基于鏈路監(jiān)測的進一步發(fā)展是使用一組多跳監(jiān)管光路來發(fā)送光信號，每發(fā)送1次探測可以測試多條鏈路，相關(guān)的研究包括監(jiān)測環(huán)[3]以及監(jiān)測跡[4]，一條監(jiān)管光路末端的監(jiān)測站可以獲得這條監(jiān)管光路上探測信號所經(jīng)過的一組鏈路的狀態(tài)．通過適當?shù)胤峙湟唤M監(jiān)管光路，遠程網(wǎng)絡控制中心依據(jù)監(jiān)測站觸發(fā)的告警就可以定位多條故障鏈路．

非適應性鏈路故障定位已經(jīng)被廣泛研究[4-7]，探測信號在多條監(jiān)管光路上同時發(fā)送．文獻[4]給出了關(guān)于定位大型稀疏網(wǎng)絡中多條故障鏈路的隨機游走算法．隨機游走算法的目的是，使用兩個監(jiān)測站(發(fā)送方和接收方)通過多次隨機游走來構(gòu)造k分離路由矩陣去定位k條故障鏈路．為了使大型稀疏網(wǎng)絡中的每條鏈路有惟一的二進制編碼，探測信號必須從發(fā)送方到接收方隨機地游走多次．因此，在隨機游走算法中每條鏈路會被大量的探測經(jīng)過，這將會增加發(fā)送的探測數(shù)以及每條鏈路上消耗的平均波長．

筆者提出啟發(fā)式的探測選擇方法，解決了隨機游走算法中消耗大量的探測數(shù)以及波長問題．不同于隨機游走算法中的非適應性方案，文中的思想是采用適應性的監(jiān)測方案[3，8]．首先，需要找到用來故障檢測的監(jiān)測路徑，接著在建立的所有監(jiān)測路徑上同時發(fā)送探測信號；然后，在有故障的路徑上，按次序發(fā)送探測信號定位故障鏈路的確切位置，在定位過程中根據(jù)每次探測信號的返回結(jié)果，適應性地調(diào)整下一次的探測路徑．

1　相關(guān)概念

圖1　在監(jiān)測路徑上發(fā)送探測定位故障鏈路

監(jiān)測路徑是一條監(jiān)管光路．在監(jiān)測路徑上發(fā)送探測可以進行故障檢測與定位．如果監(jiān)測路徑上的一條鏈路出故障，那么在這條監(jiān)測路徑上的監(jiān)測站會由于光信號的丟失而產(chǎn)生告警[9]．在監(jiān)測路徑上發(fā)送探測信號，如果探測信號返回到監(jiān)測站，則表示在探測信號所經(jīng)過的路徑上沒有故障鏈路，否則有故障鏈路．如在圖1(a)中建立了一條監(jiān)測路徑，然后在圖1(b)中給出了在監(jiān)測路徑上依次發(fā)送兩個探測來定位故障鏈路(3，5)的過程，其中，節(jié)點1是監(jiān)測站，探測p1所走的路徑為1-5-3-5-1，探測p2所走的路徑為1-5-1．

2　探測選擇方法

在大型光網(wǎng)絡中，由于光纖數(shù)據(jù)連接的透明性需求，監(jiān)測站只能被放置在特殊的位置．因為使用的監(jiān)測站越少，所需的管理花費就越少．和隨機游走算法一致，在文中使用兩個監(jiān)測站進行故障檢測．

2.1　故障檢測

網(wǎng)絡中出現(xiàn)故障鏈路時，首先需要建立監(jiān)測路徑，然后在建立好的監(jiān)測路徑上發(fā)送探測信號進行故障檢測．一些監(jiān)測路徑返回故障信息后，網(wǎng)絡管理中心就可以進行故障鏈路的定位．關(guān)于故障鏈路的檢測，要求每條鏈路至少被1條監(jiān)測路徑經(jīng)過，而面臨的問題是如何找到可以檢測到所有鏈路狀態(tài)的最小監(jiān)測路徑集合，即就是優(yōu)化關(guān)于故障檢測所需的監(jiān)測路徑集合．如果存在故障鏈路，那么至少會有1條監(jiān)測路徑會報告故障．為了尋求能夠覆蓋所有鏈路E的最小監(jiān)測路徑集合，首先需要證明關(guān)于故障檢測的最小監(jiān)測路徑集合問題是非確定多項式(Non-deterministic Polynomial，NP)完全問題，然后再給出找到最小監(jiān)測路徑集合的啟發(fā)式算法．

2.1.1最小監(jiān)測路徑集合問題是NP完全問題

定理1最小監(jiān)測路徑集合等價于最小集合覆蓋問題．

證明(最小集合覆蓋問題?最小監(jiān)測路徑集合): 這部分要證的是最小集合覆蓋問題的解是最小監(jiān)測路徑集合的解．最小集合覆蓋問題的解是大小為k的集合C′，即C′覆蓋N中的每個元素．如上述構(gòu)造中提到的，如果集合Cj覆蓋元素n，相當于與Cj對應的監(jiān)測路徑經(jīng)過元素n對應的鏈路e．因此，大小為k的集合C′覆蓋N中的每個元素，C′中表示的這k條監(jiān)測路徑將會經(jīng)過E中的每條鏈路．因此，表示C′中的這些監(jiān)測路徑為大小是k的監(jiān)測路徑集合．

(最小監(jiān)測路徑集合?最小集合覆蓋問題): 這部分要證的是最小監(jiān)測路徑集合的解是最小集合覆蓋問題的解．最小監(jiān)測路徑集合的解是大小為k的一組監(jiān)測路徑，可以經(jīng)過E中的每條鏈路．如上述構(gòu)造中提到的，如果與監(jiān)測路徑m對應的集合Cj覆蓋與鏈路e對應的元素n，則監(jiān)測路徑m經(jīng)過鏈路e．因此，如果監(jiān)測路徑集合中的k條監(jiān)測路徑經(jīng)過所有節(jié)點，則與k條監(jiān)測路徑對應的k個集合將覆蓋鏈路所表示的所有元素．

2.1.2監(jiān)測路徑集合選擇的啟發(fā)式算法

關(guān)于故障檢測的監(jiān)測路徑選擇算法是基于啟發(fā)式的算法來選擇監(jiān)測路徑進行故障檢測的．通過構(gòu)造監(jiān)測路徑使得每條鏈路至少被1條監(jiān)測路徑經(jīng)過．

算法1故障檢測的監(jiān)測路徑選擇．

輸入: 網(wǎng)絡拓撲G(V，E)，兩個監(jiān)測站(一個發(fā)送方s，一個接收方t)．

輸出: 監(jiān)測路徑集合M．

初始化每條鏈路上的計數(shù)器ρ(ei)=0(i=1，2，…，|E|);

獨立地構(gòu)造M的每一行的過程如下:

while(?ρ(ei)=0)

在G中找一條從s到t的隨機游走mj(mj?M);

把mj放入M中;

對mj經(jīng)過的每條鏈路ei執(zhí)行ρ(ei)++;

end while.

在算法1中使用了局部稀缺最優(yōu)策略，其思想是在每條鏈路ei上安裝一個計數(shù)器ρ(ei) (i=1，2，…，|E|)，ρ(ei)表示每條鏈路上經(jīng)過的監(jiān)測路徑的數(shù)目．這樣就可以控制從發(fā)送方s到接收方t的隨機游走，即不是隨機選擇一個鄰居節(jié)點進行隨機游走，而是選擇計數(shù)器上數(shù)值最小的鏈路進行游走．當在G上找到一條從s到t的隨機游走mj，則在由mj經(jīng)過的所有鏈路上的計數(shù)器加1．算法終止的條件是每條鏈路上的計數(shù)器ρ(ei)≠ 0，即就是每條鏈路至少被1條監(jiān)測路徑經(jīng)過．因此，最小監(jiān)測路徑集合問題就被解決了．最后可以得到一組監(jiān)測路徑M，即就是最小監(jiān)測路徑集合．在M中的所有監(jiān)測路徑上同時發(fā)送探測來進行故障檢測．

2.2　故障定位

當算法1生成監(jiān)測路徑集合后，如果存在故障鏈路，則開始進行故障鏈路定位．當網(wǎng)絡中的故障鏈路被一條監(jiān)測路徑上的探測信號探測到時，將會在這條監(jiān)測路徑上發(fā)送更多的探測．這個故障表示在這條故障的監(jiān)測路徑上存在1個或多個故障鏈路．但是，這些探測可能不會精確地定位故障鏈路的具體位置．因此，在這些有故障的監(jiān)測路徑上將會發(fā)送更多的探測來定位故障鏈路．故障定位需要發(fā)送的探測數(shù)要使得有故障的監(jiān)測路徑上的所有鏈路的狀態(tài)可以被判斷出來．

在故障定位過程中使用一個監(jiān)測站，從監(jiān)測站發(fā)出的探測信號最終會返回到這個監(jiān)測站．因此探測所走的路徑相當于是一條環(huán)路，即每條鏈路上有互反方向的兩個波長．如圖1(b)探測p1所走的路徑是1-5-3-5-1，實際探測所監(jiān)測的范圍是1-5-3，這樣可以引入折半查找的思想來進行快速的故障定位．算法2是基于折半查找方法[3]來明確地定位所有故障鏈路．在折半查找的方法中，對每條有故障的監(jiān)測路徑進行獨立的查找．在每條故障的監(jiān)測路徑上，第1次探測是從監(jiān)測站發(fā)送到監(jiān)測路徑的中間點．如果探測失敗，則接著對第1次探測所經(jīng)過的路徑的前半部分發(fā)送探測；否則，以相同的方式對監(jiān)測路徑的后半部分進行探測．

算法2故障定位的探測選擇．

輸入: 監(jiān)測路徑集合M，1個監(jiān)測站．

輸出: 故障鏈路集合F．

由算法1得到監(jiān)測路徑集合M;

for(M中的每條監(jiān)測路徑)

在所有的監(jiān)測路徑上同時發(fā)送探測信號;

//faultylink(a，b)表示節(jié)點a和節(jié)點b之間的鏈路是故障的

flag←Binarysearch(p，low，high，faultylink(a，b))

while(flag為false)//如果鏈路是故障的，則找到替換路徑

把faultylink(a，b)放入F中;

在節(jié)點a和節(jié)點b之間找到的最短路徑替換faultylink(a，b);

flag←Binarysearch(p，low，high，faultylink(a，b));

end while.

end for.

折半查找在每條監(jiān)測路徑上只能識別出1條故障鏈路．在每條監(jiān)測路徑上，由于探測信號不能在故障鏈路上進行傳送，所以故障鏈路后面的鏈路狀態(tài)無法判斷出來．因此，當在1條監(jiān)測路徑上定位出1條故障鏈路后，找一條最短路徑替換這條故障鏈路，也就是在與故障鏈路相鄰的兩個節(jié)點間找到這條最短路徑．這個過程一直持續(xù)到這條監(jiān)測路徑上的所有故障鏈路都被識別出來．圖2給出示例，節(jié)點4的度為3，網(wǎng)絡中有3條故障鏈路，一條探測所走的路徑是1-4-3-4-1，實際的探測信號監(jiān)測范圍是1-4-3．圖2在路徑1-4-3-4-1上使用折半查找方法可以定位出故障鏈路(1，4)，但是不能定位出故障鏈路(3，4)．由于在節(jié)點1和節(jié)點4之間不能找到無故障的替換路徑，所以在監(jiān)測路徑1-4-3上故障鏈路(1，4)后面的故障鏈路(3，4)不能被定位到．

圖2 在3邊連通的網(wǎng)絡中的3條故障鏈路圖3 k條鏈路組成圖中的割

定理2用1個監(jiān)測站來定位所有可能的k條故障鏈路的充分必要條件是網(wǎng)絡為k+1 邊連通的．

證明通過反證法來證明充分性．假設網(wǎng)絡是k邊連通的而不是k+1邊連通的．因為網(wǎng)絡不是k+1 邊連通的，所以如圖3存在一組k條鏈路，刪掉它們后網(wǎng)絡變得不連通，標記這些鏈路為l1，l2，…，lk．現(xiàn)在假設這k條鏈路都是故障的，當通過折半查找方法定位到故障鏈路l1后，不能找到健康的替換路徑來替換掉l1，因為網(wǎng)絡是k邊連通的，而且這k條鏈路都是故障的．因此，當l1和li(li∈ (l2，…，lk))在同一監(jiān)測路徑上時，l1后面的故障(li)不能被監(jiān)測站定位到，引出矛盾．因此，在k邊連通的網(wǎng)絡中不能定位出k條故障鏈路，即就是k+1 邊連通是構(gòu)造探測集合的充分條件．

通過構(gòu)造法來證明必要性．因為網(wǎng)絡是k+1邊連通的，網(wǎng)絡中的任意k條故障鏈路故障使得網(wǎng)絡至少是1邊連通的．對于任意一個故障鏈路，總能找到健康的替換路徑并使用折半查找方法來定位同一監(jiān)測路徑上的其他故障鏈路．因此，總能找到這樣的探測來定位k條故障鏈路．

在折半查找過程中，low表示探測的起始點，high表示探測的終止點．探測所走的路徑是low-high-low，實際探測所監(jiān)測的范圍R是low-high．在監(jiān)測站發(fā)送每次探測的開始，low是0，high是 |m|-1，|m|表示監(jiān)測路徑的長度．因此，初始的mid是 (|m|- 1)/2>．監(jiān)測站將在監(jiān)測路徑上發(fā)送初始的探測，其探測的終點為high節(jié)點．p表示發(fā)送的探測，flag為折半查找的返回值．當flag為真時，探測路徑上不存在故障鏈路；否則，返回一條故障鏈路．

為了減少計算時間，一條從發(fā)送方s開始到接收方t的隨機游走所經(jīng)過的節(jié)點被存放在vector容器中．由算法2得到的故障鏈路集合F被存放在內(nèi)部數(shù)據(jù)結(jié)構(gòu)中(C++中的std::set)，使得找到的F中不存在重復的故障鏈路．每條鏈路上的計數(shù)器ρ(ei)存放在平衡二叉查找樹上(C++中的std::map)，這提供了快速查找和修改功能．當執(zhí)行一條隨機游走mj時，則需要更新被這條隨機游走經(jīng)過的所有鏈路上的計數(shù)器．

3　仿真結(jié)果

在Visual studio 2010上模擬全光網(wǎng)故障定位仿真系統(tǒng)，依據(jù)BA模型[10]生成平均節(jié)點度為2和3，節(jié)點范圍為50～500，鏈路數(shù)從100到500的大型無標度網(wǎng)絡，在生成的大型無標度網(wǎng)絡上測試隨機游走[4]算法和探測選擇算法的性能．對于生成的每一個無標度網(wǎng)絡，在故障檢測過程中，固定兩個最大度節(jié)點，分別為發(fā)送方和接收方(兩個監(jiān)測站)，以及任意選擇一個最大度節(jié)點作為故障定位過程中的監(jiān)測站．文中給出發(fā)送的探測數(shù)和每條鏈路上探測相關(guān)的平均波長數(shù)的仿真結(jié)果．由于在故障檢測過程中所有的探測信號在監(jiān)測路徑上同時發(fā)送，則會造成每條鏈路上消耗過多的監(jiān)測資源[11-12]．而在故障定位過程中每條探測在監(jiān)測路徑上按次序發(fā)送，探測經(jīng)過的每條鏈路上消耗單個波長[13]，因此，文中只考慮故障檢測過程中平均每條鏈路上消耗的監(jiān)測波長．通過統(tǒng)計定位故障所發(fā)送的探測和每個探測的路徑長度，來得出仿真結(jié)果要呈現(xiàn)的探測數(shù)和平均每條鏈路上消耗的監(jiān)測波長．探測選擇算法運行結(jié)果的仿真圖描繪的每一點為在不同網(wǎng)絡拓撲上100次實驗的平均值，而隨機游走算法的結(jié)果是通過不斷地增加監(jiān)測跡的數(shù)量來找到能夠惟一定位故障鏈路所需的監(jiān)測跡的數(shù)量，即就是發(fā)送的探測的數(shù)量．

3.1　在平均節(jié)點度為2的網(wǎng)絡中定位所有的單鏈路故障

由BA模型生成無標度網(wǎng)絡的過程可以知道平均節(jié)點度為2的網(wǎng)絡的邊連通度為2．依據(jù)定理2，在邊連通度為2的網(wǎng)絡中所有的單鏈路故障可以被定位出來．圖4(a)給出了在平均節(jié)點度為2的網(wǎng)絡中定位所有單鏈路故障時，隨機游走算法和探測選擇算法需要發(fā)送的探測數(shù)．從圖4(a)可以看出，隨機游走算法比探測選擇算法需要發(fā)送更多的探測．圖4(b)給出了在定位所有單鏈路故障時兩種算法消耗的平均波長數(shù)的對比．為了在平均節(jié)點度為2的網(wǎng)絡中定位所有的單鏈路故障，探測選擇算法在每條鏈路上大約需要的平均波長數(shù)為6，而隨機游走算法在每條鏈路上大約消耗的波長是22．

圖4　平均節(jié)點度為2的網(wǎng)絡中隨機游走算法和探測選擇算法的性能

3.2　在平均節(jié)點度為3的網(wǎng)絡中定位任意兩條鏈路故障

基于BA模型，平均節(jié)點度為3的網(wǎng)絡的邊連通度為3．圖5(a)給出了定位平均節(jié)點度為3的網(wǎng)絡中的任意兩條故障鏈路時，隨機游走算法和探測選擇算法所需發(fā)送的探測數(shù)．對比探測選擇算法，圖5(a)表明隨機游走算法需要更多的探測，圖5(b)比較了定位任意兩條鏈路故障時，兩種算法在每條鏈路上需要的平均波長數(shù)．在每條鏈路上，探測選擇算法大約需要的波長數(shù)為5，而隨機游走算法需要的波長數(shù)大約為20．

圖5　平均節(jié)點度為3的網(wǎng)絡中隨機游走算法和探測選擇算法的性能

文中也研究了算法的穩(wěn)健性，可通過增加鏈路數(shù)來增加網(wǎng)絡規(guī)模．如圖4(a)和5(a)所示，隨著網(wǎng)絡規(guī)模的增加，定位鏈路故障所需的探測數(shù)也在增加．因為鏈路數(shù)越多，定位越困難．

4　結(jié) 束 語

文中研究了全光網(wǎng)中使用適應性探測方案定位故障鏈路的探測選擇算法，證明了最小監(jiān)測路徑集合問題是NP完全問題，接著通過啟發(fā)式的監(jiān)測路徑選擇算法來找到最小監(jiān)測路徑集合．進一步提出了在網(wǎng)絡連通度方面用一個監(jiān)測站來定位故障鏈路的充分必要條件．探測選擇算法首先獲得關(guān)于故障檢測的一組監(jiān)測路徑，接著在有故障的監(jiān)測路徑上按次序發(fā)送探測信號來進行故障定位，避免了隨機游走算法中消耗的大量探測和波長問題．仿真結(jié)果表明，探測選擇算法有更優(yōu)越的性能，具有很強的實際意義．

參考文獻：

[1] 熊余, 董先存, 李圓圓, 等. 軟件定義光網(wǎng)絡中基于最小點覆蓋的控制平面跨層生存性設計[J]. 電子與信息學報, 2016, 38(5): 1211-1218.

XIONG Yu, DONG Xiancun, LI Yuanyuan, et al. The Cross-layer Survivable Design of Control Plane Based on Minimum Point Covering in Software Defined Optical Network[J]. Journal of Electronics & Information Technology, 2016, 38(5): 1211-1218.

[2]HARVEY N J A, PATRASCU M, WEN Y G, et al. Non-adaptive Fault Diagnosis for All-optical Networks via Combinatorial Group Testing on Graphs[C]//Proceedings of the 2007 26th IEEE International Conference on Computer Communications. Piscataway: IEEE, 2007: 697-705.

[3]ALI M L, HO P H, TAPOLCAI J. SRLG Failure Localization Using Nested M-trails and Their Application to Adaptive Probing[J]. Networks, 2015, 66(4): 347-363.

[4]XUAN Y, SHEN Y, NGUYEN N P, et al. Efficient Multi-link Failure Localization Schemes in All-optical Networks[J]. IEEE Transactions on Communications, 2013, 61(3): 1144-1151.

[5]ALI M L, HO P H, TAPOLCAI J. A Novel M-trail Allocation Method for SRLG Fault Localization in All-optical Networks[J]. Optical Switching and Networking, 2017, 23(2): 179-188.

[6]TAPOLCAI J, RONYAI L, HOSSZU E, et al. Signaling Free Localization of Node Failures in All-optical Networks[C]//Proceedings of the 2014 IEEE Conference on Computer Communications. Piscataway: IEEE, 2014: 1860-1868.

[7] 劉英挺, 朱睿杰, 杜曉明, 等. 全光網(wǎng)中采用可信度模型的故障定位技術(shù)[J]. 西安電子科技大學學報, 2016, 43(6): 152-157.

LIU Yingting, ZHU Ruijie, DU Xiaoming, et al. Mechanism for Fault Location Based on the Credibility Model of All Optical Networks[J]. Journal of Xidian University, 2016, 43(6): 152-157.

[8]NATU M, SETHI A S, LLOYD E L. Efficient Probe Selection Algorithms for Fault Diagnosis[J]. Telecommunication Systems, 2008, 37(1/3): 109-125.

[9]張新, 常義林, 孫方濤, 等. 一種改進的網(wǎng)絡故障監(jiān)測算法[J]. 西安電子科技大學學報, 2006, 33(3): 416-421.

ZHANG Xin, CHANG Yilin, SUN Fangtao, et al. An Improved Algorithm for Monitoring the Network Fault[J]. Journal of Xidian University, 2006, 33(3): 416-421.

[10]ALBERT R, BARABASI A L. Statistical Mechanics of Complex Networks[J]. Quantitative Biology, 2001, 74(1): 47-97.

[11]THAI M T. Group Testing Theory in Network Security: Advanced Solution[M]. New York: Springer, 2012: 3-4.

[12]ALI M L, HO P H, TAPOLCAI J. SRLG Fault Localization Using Nested M-trails[J]. Computer Networks, 2015, 85: 63-79.

[13]WANG B, HO P H. Energy-efficient Routing and Bandwidth Allocation in OFDM-based Optical Networks[J]. Journal of Optical Communications and Networking, 2016, 8(2): 71-84.