全光網中定位故障鏈路的探測選擇算法

齊小剛， 王曉琳， 劉立芳

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

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

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

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

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

1　相關概念

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

監(jiān)測路徑是一條監(jiān)管光路．在監(jiān)測路徑上發(fā)送探測可以進行故障檢測與定位．如果監(jiān)測路徑上的一條鏈路出故障，那么在這條監(jiān)測路徑上的監(jiān)測站會由于光信號的丟失而產生告警[9]．在監(jiān)測路徑上發(fā)送探測信號，如果探測信號返回到監(jiān)測站，則表示在探測信號所經過的路徑上沒有故障鏈路，否則有故障鏈路．如在圖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　探測選擇方法

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

2.1　故障檢測

網絡中出現故障鏈路時，首先需要建立監(jiān)測路徑，然后在建立好的監(jiān)測路徑上發(fā)送探測信號進行故障檢測．一些監(jiān)測路徑返回故障信息后，網絡管理中心就可以進行故障鏈路的定位．關于故障鏈路的檢測，要求每條鏈路至少被1條監(jiān)測路徑經過，而面臨的問題是如何找到可以檢測到所有鏈路狀態(tài)的最小監(jiān)測路徑集合，即就是優(yōu)化關于故障檢測所需的監(jiān)測路徑集合．如果存在故障鏈路，那么至少會有1條監(jiān)測路徑會報告故障．為了尋求能夠覆蓋所有鏈路E的最小監(jiā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中的每個元素．如上述構造中提到的，如果集合Cj覆蓋元素n，相當于與Cj對應的監(jiān)測路徑經過元素n對應的鏈路e．因此，大小為k的集合C′覆蓋N中的每個元素，C′中表示的這k條監(jiān)測路徑將會經過E中的每條鏈路．因此，表示C′中的這些監(jiān)測路徑為大小是k的監(jiān)測路徑集合．

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

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

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

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

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

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

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

獨立地構造M的每一行的過程如下:

while(?ρ(ei)=0)

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

把mj放入M中;

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

end while.

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

2.2　故障定位

當算法1生成監(jiān)測路徑集合后，如果存在故障鏈路，則開始進行故障鏈路定位．當網絡中的故障鏈路被一條監(jiān)測路徑上的探測信號探測到時，將會在這條監(jiān)測路徑上發(fā)送更多的探測．這個故障表示在這條故障的監(jiān)測路徑上存在1個或多個故障鏈路．但是，這些探測可能不會精確地定位故障鏈路的具體位置．因此，在這些有故障的監(jiān)測路徑上將會發(fā)送更多的探測來定位故障鏈路．故障定位需要發(fā)送的探測數要使得有故障的監(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次探測所經過的路徑的前半部分發(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，網絡中有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邊連通的網絡中的3條故障鏈路圖3 k條鏈路組成圖中的割

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

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

通過構造法來證明必要性．因為網絡是k+1邊連通的，網絡中的任意k條故障鏈路故障使得網絡至少是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的隨機游走所經過的節(jié)點被存放在vector容器中．由算法2得到的故障鏈路集合F被存放在內部數據結構中(C++中的std::set)，使得找到的F中不存在重復的故障鏈路．每條鏈路上的計數器ρ(ei)存放在平衡二叉查找樹上(C++中的std::map)，這提供了快速查找和修改功能．當執(zhí)行一條隨機游走mj時，則需要更新被這條隨機游走經過的所有鏈路上的計數器．

3　仿真結果

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

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

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

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

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

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

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

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

4　結 束 語

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

參考文獻：

[1] 熊余, 董先存, 李圓圓, 等. 軟件定義光網絡中基于最小點覆蓋的控制平面跨層生存性設計[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] 劉英挺, 朱睿杰, 杜曉明, 等. 全光網中采用可信度模型的故障定位技術[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]張新, 常義林, 孫方濤, 等. 一種改進的網絡故障監(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.