基于探測圈覆蓋的光突發交換網絡故障定位

包宋建

（重慶文理學院 電子電氣工程學院，重慶 402160）

0 引言

光網絡故障的識別和定位是極其重要的，現有的一些故障定位算法主要有Rete算法、數據挖掘算法、圖論里的相關算法等，但是這些算法對于OBS網絡而言，缺乏適用性。本文提出了基于探測圈覆蓋的光突發交換網絡故障定位方案。該方案分為2個階段：1）收集由故障觸發的告警信息，組成相應的二進制告警相關矩陣；2）采用預計算的方式，利用告警矩陣進行定位，能在兼顧漏告警和誤告警的情況下解決多故障定位問題，找到可能的故障設備集合，進行有效定位。

1 OBS網絡設備告警能力分析

對OBS網絡硬件設備告警能力分析主要根據故障發生時網絡硬件設備的反應狀況定義。在對硬件設備的告警能力分析時，主要考慮以下3個特性[1]：

1）自身告警。擁有此特性的設備可以發出關于自身硬故障的告警。

2）外部告警。擁有此特性的設備可以與管理器進行通信，發出關于外部其他設備的故障告警。

3）硬故障屏蔽。擁有此特性的設備可以屏蔽后面的硬件設備硬故障。

對光網絡中硬件設備具體分類如表1所示。從上面的分析可以看出，在OBS網絡中，當某些網絡器件發生故障的時候就有可能產生漏告警以及誤告警的情況，所以在下面的故障定位算法中，考慮了漏告警和誤告警的情況，這樣能夠使網絡管理者快速有效地定位OBS網絡故障，并執行OBS網絡故障管理措施，使得整個OBS網絡有效有序傳輸。

表1 OBS網絡硬件設備告警能力

2 OBS網絡中故障探測和定位算法

在OBS網絡中，無論是單一故障還是多故障都能被告警器探測到并發出警報，為了降低故障管理的復雜度和成本，盡量用最少的監視設備來監視整個OBS網絡元素。干擾告警（誤告警和漏告警）的出現會使得故障定位的難度加大，對此，故障定位方案主要分為2個步驟：1）探測和收集OBS網絡元素的各種告警信息；2）應用提到的故障定位算法，最后得到可能發生故障的OBS網絡故障設備集合。具體流程如圖1所示。

在收到來自監視設備的告警后，無論告警的類型如何，故障定位算法都將運行，把剛收到的告警信息與預先計算出來的告警矩陣進行比較，在這個比較過程中將產生可能發生故障的OBS網絡故障設備集合，然后對發出和接收的信號進行處理和分析，從此集合中確定準確的故障設備。

2.1 基于m2圈的OBS網絡鏈路故障定位算法

在監測范圍內的OBS網絡元素無論何時發生故障，監視設備都將產生告警。但是OBS網絡中也經常受到錯誤告警和漏告警的干擾，原因在其監視設備中的門限值較低或其在監視設備中的門限值較高[2]。在圖G(V,E)中，鏈路ei∈E(i=1,2,…,L)和m2圈cj兩者的關系可以定義為一個二進制編碼aij表示

每一條鏈路ei對應的所有m2圈就可以得到相關聯的編碼ai=(ai1,ai2,…,aiM)，此外對于發生故障時所觸發的告警mj與m2圈cj也可以得到以下關系

這樣，所有m2圈的告警編碼就可以表示為m=(m1,m2,…,mM)。一旦接受到m2圈中的告警，那么告警編碼隨即產生。比較告警編碼mj與每條鏈路所相關的編碼aij，如果鏈路相關編碼和告警編碼吻合，那么這條鏈路就是故障候選鏈路之一，兩者的比較關系用異或關系來衡量，表示為

式中：i=1,2,…,L，如果Fi為0，那么鏈路ei就是告警編碼m=(m1,m2,…,mM)的一個候選故障點。按照以上方法檢查完所有的鏈路相關編碼aij后，就獲得所有的告警候選集合。可以預先列舉出所有可能的告警編碼mj，建立相應的故障告警集合，當故障發生時可以直接進行對比定位，所以這種算法可以節省大量的故障定位時間。

2.2 OBS網絡節點故障定位算法

生存性實施的故障定位只需將故障定位到資源即可[3]。資源是相對于業務而言的。下面介紹一種故障定位機制，在這個機制之中C代表所有OBS網絡器件的集合，M代表所有監視器集合，OBS光網絡器件v的一個告警域（當v發生故障時，引起告警的所有監視設備集合）用Domain(v)表示。定義響鈴的監視設備集合用MR表示（MR?M）。同理，定義MS為沒有響鈴的監視設備集合（MS=M/MR）。設定C ′是C的一個子集，MA(C ′)為在沒有誤告警和漏告警的情況下，C′中的所有設備發生故障時監視器都會正常發出告警。那么當告警產生干擾的情況下，MA(C ′)≠MR。誤告警可表示為MF(C ′)=MR/MA(C ′)。同理可得，漏告警可表示為MM(C ′)=MS?MA(C ′)。多故障定位的目標就是在覆蓋告警矩陣中所有響鈴的告警（即在告警矩陣中為1的告警）而不是未響鈴告警（即在告警矩陣中為0的告警），盡量使得最終的故障設備集合最小，達到精確定位的目的。所以本文想找到C的一個子集C′，其中故障設備集| |C′的數量盡量最小，并且沒有誤告警時，上述情況滿足MF(C′)=φ；沒有漏告警的情況滿足MM(C′)=φ。在定位算法中，需要考慮以下4種情況：

1）沒有誤告警和漏告警的故障定位問題

其實在理想情況下的多故障定位問題等同于一個集覆蓋問題（set cover問題），而集覆蓋問題又是一個完全NP問題[4]。為了解決這個問題，本文借鑒集覆蓋中的自適應貪婪優化算法來對多故障進行定位，此算法在告警矩陣中反復逐一選取告警域中包括最多響鈴告警的故障設備。

對任意一個OBS網絡拓撲，首先通過探測圈發現算法得到一個告警矩陣，然后對其運行故障定位算法，并滿足條件Domain(c)?MR。對于多故障的情況，把收到的告警編碼求并，在定位算法運行期間告警矩陣中的各個網絡設備（網絡節點）根據條件逐一進行定位比較，即滿足

2）有一個誤告警，沒有漏告警的情況

OBS網絡是通過時域共享、統計復用光波長信道來有效支持上層協議或高層用戶產生的突發業務，所以信道中光信號的有無是隨機的，無光（Loss-of-light）并不意味著一定有故障事件發生。這使得通過監測光信號的有無來確定是否產生告警的故障監測點會產生過多的誤告警，以至于故障定位算法無法定位故障，或者由于監視設備中的告警門限值設置較低時，也可能產生此情況[5]。所以當收到響鈴的告警集MR時，其中可能存在一些誤告警，需要確定一個網絡設備集FD?C，它有最少的誤告警數目（即| MF(FD)|最小）并且滿足MM(C′)=φ。具體算法為：

3）有一個漏告警，沒有誤告警的情況

這是在監視設備中的告警門限值設置較高時可能產生的情況。需要確定一個網絡設備集FD?C，它有最少的漏告警數目（即| MM(FD)|最小）并且滿足MF(C ′)=φ。由于漏告警的問題是一個完全NP問題，所以其相對于誤告警的糾正要困難得多[6]，所以應該設置監視器的告警門限，使得漏告警的數目達到最少，以減少故障定位過程中帶來的干擾。具體算法為：

4）有一個誤告警和一個漏告警的情況

在真實OBS網絡中，網絡的運行狀況是很復雜的，很難確定只有一個漏告警或者只有一個誤告警的發生，因此本文提出這樣一個算法盡量對兩者同時發生時共同進行考慮。具體算法為：

基于探測圈的故障定位算法考慮了4種情況：1）沒有誤告警和漏告警；2）一個誤告警，沒有漏告警；3）一個漏告警，沒有誤告警；4）一個誤告警和一個漏告警。本算法舉例見表2。

表2 告警相關矩陣

對于任意一個OBS網絡拓撲，先確定找到所有的最短長度m圈，然后產生如表2所示的告警矩陣，假如接收到一個告警集合為{1，1，1，0，0}，那么說明M3，M6，M7觸發了告警，而M1，M13處于未觸發狀態。對于情況1）來說，都是正常告警，現在網絡節點4的告警域可以表示為Domain(ND4)?MR，同理可以得出Domain(ND6)?MR，Domain(ND10)? MR，Domain(ND12)?MR。根據多故障定位算法可以得到｛ND4，ND6，ND10，ND12｝屬于故障設備FC（Faulty Component）；對于情況2），有一個誤告警，那么找到的告警集合就會多出｛（1，1，0，0，0），（1，0，1，0，0），（0，1，1，0，0）｝；對于情況3），告警集合就會多出｛（1，1，1，1，0），（1，1，1，0，1）｝；對于情況4），就會多出｛（0，1，1，1，0），（0，1，1，0，1），（1，0，1，1，0），（1，0，1，0，1），（1，1，0，1，0），（1，1，0，0，1）｝幾個告警集合，然后分別運行多故障定位算法來進行定位。

3 仿真性能比較

C.Mas對于WDM光網絡的故障探測和定位研究做了探討，并且仿真性能證明了二叉樹模型是一種快速有效的故障定位算法[1]。但是隨著網絡節點和故障數目的增加，二叉樹的枝葉數和各個根節點的數目會迅速增長，所以需要超大的存儲空間，并且在最終故障定位的準確度方面有待提高。本文提出的算法主要是針對以上特點進行全面的考慮，在接收到一個告警編碼時，考慮了所有漏告警和誤告警的情況，找到每種情況下可能出現的OBS網絡故障設備數目，然后對其求均值；同理找到傳統二叉樹定位算法的故障設備數目的均值，對兩個定位算法進行比較，性能比較如圖2和圖3所示。

通過分析C.Mas二叉樹故障定位算法的運行過程，得出如下結論：

1）網絡依賴模型二叉樹的建立過程（即預計算過程）復雜，網絡中告警設備的種類和數量不能太少，否則就沒有足夠的告警信息進行關聯，無法準確地進行故障定位。如果輸入的告警信息為0001010000000時，這種算法獲取單個故障定位的結果不是唯一的，導致了多個故障和漏（誤）告警情況下故障定位的準確率降低。

2）如果告警設備集中只有一個告警設備告警，當發生漏告警時，將無法定位網絡中發生故障的設備。

3）這種基于信道編碼的方法中，每個信道的最后一個設備的告警設備集總是為空，如果這些設備發生故障，就無法對其進行定位。而基于探測圈的故障定位算法在考慮漏（誤）告警的同時，因為借鑒了集覆蓋中的自適應貪婪優化算法，所以在以上幾方面都有很大的改善，只需要找到告警域中包含最多響鈴告警的故障設備即可。

由圖2和圖3比較可以看出兩種算法在同樣考慮漏告警和誤告警的情況下，基于探測圈的故障定位算法無論在單一故障還是多故障時，其最終找到的故障設備數目要小，使得故障管理人員縮小故障搜索范圍，達到準確定位。

4 小結

本文根據OBS網絡拓撲等特點，提出一種基于探測圈覆蓋的故障定位方案。此方案主要針對OBS網絡鏈路和節點進行雙重定位，使得故障定位更加準確。對于一個網絡拓撲首先利用最短長度m圈算法建立故障監視器與網絡拓撲中的節點、鏈路建立相關性模型，然后分別對其進行多故障定位，并且考慮了漏告警與誤告警等常見干擾的情況。由仿真結果可以看出，在同樣考慮干擾告警的情況下，本文提出的基于探測圈的故障定位算法相對與傳統的二叉樹故障定位算法擁有較精確的定位范圍，能夠最終實現OBS網絡的快速有效的故障定位。

[1]MAS C，THIRAN P.An efficient algorithm for locating soft and hard failures in WDM networks[J].IEEE Journal on Selected Areas in Communications，2000，18（10）：1900-1911.

[2]NAYEK P，PAL S，CHOUDHURY B，et al.Optimal monitor placement scheme for single fault detection in optical network[C]//Proc.IEEE 2005 7th International Conference on Transparent Optical Networks.Barcelona，Spain：IEEE Press，2005，1：433-436.

[3]WANG Ruyan，CHANG Jiaofa，LONG Keping.A fault detection and location mechanism for optical burst switching networks[J].Journal of Optoelectronics Laser，2006，17（12）：1477-1481.

[4]HOCHBAUM D S.Approximation algorithms for NP-hard problems[M].[S.l.]：Course Technology，1996.

[5]江城，張重陽，余松煜.基于異常檢測與雙流編碼的視頻監控系統設計[J].電視技術，2011，35（1）：111-114.

[6]CARR R D，DODDI S，KONJEVOD G，et al.On the red-blue set cover problem[EB/OL].[2010-10-09].http：//portal.acm.org/citation.cfm?id=338219.338271.