陳第全，王賢亮，靳　敏，姜元帥，王　楠,張　炎

(1.重慶市電力公司, 重慶 400015；2.重慶郵電大學 光纖通信技術重點實驗室,重慶 400065;3.重慶電信研究院， 重慶 401336)

?

一種基于最短長度m2圈算法的故障監(jiān)測方案

陳第全1，王賢亮1，靳敏1，姜元帥1，王楠2,張炎3

(1.重慶市電力公司, 重慶 400015；2.重慶郵電大學 光纖通信技術重點實驗室,重慶 400065;3.重慶電信研究院， 重慶 401336)

摘要：針對光突發(fā)交換網絡中“逐跳檢驗”監(jiān)測模式成本較高等問題，提出了一種新的基于最短長度m2圈算法的光突發(fā)交換網絡故障監(jiān)測機制。該機制根據(jù)最短長度m2圈算法尋找光突發(fā)交換網絡中的圈覆蓋放置故障探測模塊，從而形成基于圈覆蓋的光突發(fā)交換網絡故障監(jiān)測模式。同時，在最短長度m2圈算法的基礎上提出一種相應的故障定位算法，利用異或關系衡量告警編碼與鏈路相關編碼是否吻合，從而進行快速故障定位。計算結果表明，基于最短長度m2圈算法的故障監(jiān)測機制具備網絡開銷小、故障定位率高和故障定位快速等特點。

關鍵詞：光突發(fā)交換；最短長度m2圈算法；故障監(jiān)測；故障定位

0引言

光突發(fā)交換(optical burst switching ，OBS)技術由于結合了光電路交換和光分組交換二者的優(yōu)點，成為波分復用光網絡面向高突發(fā)、高速率IP業(yè)務的主要實現(xiàn)方案[1-4]。在OBS網絡中，如果出現(xiàn)短暫的服務中斷，將可能導致大量的數(shù)據(jù)流失，所以其快速的故障檢測和定位就顯得極其重要[5-8]。

在OBS網絡中，故障的檢測可以通過一些網絡性能監(jiān)視器來完成。在文獻[9-11]中提出的圈覆蓋理論能有效地降低檢測成本和監(jiān)視器的數(shù)目，并利用3種啟發(fā)式圈覆蓋算法來發(fā)現(xiàn)網絡的圈覆蓋，即深度優(yōu)先搜索(heuristic depth first searchin，HDFS)、最短路徑歐拉匹配(shortest path eulerian matching，SPEM)和生成樹圈覆蓋算法(heuristic spanning-tree，HST)。三者之中，HST算法相對于其他算法能夠比較好地完成定位故障和減少網絡的資源開銷[9]，但是在故障定位率、圈長度以及監(jiān)視器開銷等方面都需要進一步改進，基于以上思想本文提出了基于最短長度m2圈算法(minimum-length monitoring cycles，m2cycles)的故障監(jiān)測方法。

1故障監(jiān)測方案的描述

1.1m2圈算法

m2圈算法的基本思想是：在一個給定的網絡拓撲中，首先基于一條給定的鏈路，臨時移除這條鏈路，然后找到這條移除鏈路所對應的2個端節(jié)點，并連接這2個節(jié)點之間的所有最短路徑。集合這些基于一條給定的鏈路找到的最短路徑，從而構建成一個最短長度的圈集合。m2圈構建可以分為2個主要步驟：擴展和優(yōu)化。擴展過程就是構造出一系列的m2圈的集合，優(yōu)化過程就是從以上集合中移除(添加)所有多余(遺失)的m2圈。具體過程如下所述。

1)初始化。

首先把圖G(V,E)中所有的鏈路標為未覆蓋。初始化集合B為空集?。對在圖G(V,E)中的每一條鏈路構建m2圈。然后把這些找到的圈按長度升序排列，并且添加到列表θ。

2)對集合B進行擴展。

步驟①搜索列表θ，從中找到第一個的m2圈，此圈含有一些未覆蓋的鏈路，把這些沒有覆蓋的鏈路加入到集合F。

步驟②從F中選一條鏈路，然后找到所有覆蓋它的m2圈。若m2圈覆蓋至少一條標注為未覆蓋的鏈路，那么就把這個m2圈添加到集合B中。把這些新的m2圈所覆蓋的鏈路標記為已覆蓋，然后把他們添加到T中。

步驟③把F中的剩余鏈路重復步驟②，直到沒有新的m2圈可以添加到集合B中。

步驟④查找圖G(V,E)所有鏈路還有沒有未被覆蓋到的，如果有的話，再轉入步驟①。否則轉入優(yōu)化階段。

3)針對告警信息的m2圈算法優(yōu)化。

步驟⑤首先構造一個告警編碼列表TA，這個列表中的行向量代表圖G(V,E)中鏈路的告警編碼，列向量代表集合B中的m2圈。初始化時TA的輸入為0，對于每一個m2圈，它所覆蓋到的鏈路標為1，否則標為0。

步驟⑥把TA中的每個列向量依次與其他列向量進行比較，首先列向量被依次標記出來，然后檢查沒有被標記的其他列向量是否出現(xiàn)全零行或者再出現(xiàn)相同告警編碼。如果在移除這個被標記起來的列向量以后，出現(xiàn)一些全零行或者出現(xiàn)個別相同的告警編碼變?yōu)椴煌那闆r，說明這個m2圈不是多余的，然后對下一個列向量進行檢查。否則，把這個列向量從TA中刪除，相應的m2圈也從集合B中刪除。重復步驟⑥直到所有的列向量都被檢查過。

步驟⑦如果TA中出現(xiàn)兩個或者多個相同告警編碼時，算法隨機選取具有相同告警編碼鏈路中的一條，同時從圖G(V,E)中移除具有相同告警編碼的鏈路集合中剩下的鏈路，然后用選取的這條鏈路和其他具有相同告警編碼鏈路的節(jié)點一起建立新的m2圈，這些新的m2圈只覆蓋所選取的那條鏈路，而不覆蓋那些具有相同告警編碼的其他鏈路，反之亦然。如果找到多個這樣的m2圈，只把最短長度的m2圈添加到B中，并且把它變成一個新的列向量添加到TA中。

步驟⑧將集合B初始化為C,C就是我們要找的最后m2圈集合，對應的告警編碼為TA。

1.2基于m2圈的故障定位算法

在圖G(V,E)中，鏈路ei∈E(i=1,2,…,L)和m2圈cj二者的關系可以定義為一個二進制編碼aij來表示

(1)

進而可以通過相關聯(lián)的編碼ai=(ai1,ai2,…,aiM)表示鏈路ei與所有m2圈的關系，此外對于故障時所觸發(fā)的告警mj與m2圈cj也可以得到以下關系

(2)

這樣，所有m2圈的告警編碼就可以表示為m=(m1m2…mM)。

倘若m2圈發(fā)出告警，并產生了告警編碼。為判定鏈路ei是否屬于故障候選鏈路，需要利用異或關系衡量告警編碼與鏈路相關編碼是否吻合，表示為

(3)

(3)式中，i=1,2,…,L，若Fi為0，則表明二者是吻合的，鏈路ei就是告警編碼m=(m1m2…mM)相關的故障候選鏈路。

上述方法對所有的鏈路相關編碼aij進行了逐個檢查，提前判斷出可能的告警編碼mj，進而得到故障告警集合。故障時直接對比定位，有效地減少故障定位的時間。

1.3復雜度分析

本文m2圈算法由圈構造、增加丟失的圈和移除多余的圈3部分組成，分析發(fā)現(xiàn)算法的復雜度是由圈構造這部分決定。N個節(jié)點的網絡拓撲至多有N2條鏈路，對每條未覆蓋的鏈路需要利用最短路徑算法尋找一個圈進行覆蓋，而最短路徑算法的復雜度為O(N2)，因此，圈構造的復雜度不會超過O(N4)。所以，整個m2算法的復雜度至多為O(N4)。

2性能比較

2.1探測圈的評價標準

為評價不同圈發(fā)現(xiàn)算法的性能，直觀有效地發(fā)現(xiàn)合適的圈，在OBS網絡環(huán)境中定義以下變量和參數(shù)來衡量圈覆蓋發(fā)現(xiàn)算法。

給定網絡的物理拓撲為有限無向連通圖G(V,E)，V(G)是網絡中節(jié)點的總數(shù)，E(G)是網絡中鏈路的總數(shù)。

定義L(ci)為圈ci的邊數(shù)，等于通過跳數(shù)計算出的探測突發(fā)(probeburst,PB)的生命周期。同時，應盡量減小圈長度，以此保證PB與數(shù)據(jù)突發(fā)(databurst,DB)使用通道時不發(fā)生沖突。|L(ci)|為圈長L(ci)的數(shù)量，圈覆蓋C的總長度可以表示為

(4)

(4)式中，M為C中元素的個數(shù)。當發(fā)現(xiàn)一個圈覆蓋C時，C中圈的平均長度為

avrg_length(C)=L(C)/M

(5)

當發(fā)現(xiàn)一個圈覆蓋時，C中所有圈的最大長度為

max_length(C)=max{l(ci)|i=1,2,…,M}

(6)

當發(fā)現(xiàn)一個圈覆蓋時，圖G(V,E)中平均每個節(jié)點需要配置的監(jiān)測設備的個數(shù)表示為

(7)

因此，基于m2圈的監(jiān)測算法主要目的就是盡可能減少cost(p)。

文獻[12]中提到對于給定的一個拓撲，其在度數(shù)為2的路徑上的鏈路(一條路徑上除了這條路徑的端點的度數(shù)以外，其所有內部節(jié)點的度數(shù)都為2)需要額外增加監(jiān)視器才能進行完全定位。同時，為了客觀地反映增加的監(jiān)視器帶來的損耗，定義了損耗減少率為

(8)

(8)式中：M為監(jiān)視器增加之前的個數(shù)；M′表示完全定位需要增加的監(jiān)視器個數(shù)。

T(ei)表示當發(fā)現(xiàn)一個圈覆蓋時，鏈路ei被覆蓋的次數(shù)，這里ei∈E。T(ei)越大，表明監(jiān)視器耗用鏈路ei的帶寬越多，又設圖G(V,E)的圈覆蓋C中被覆蓋T(ei)次的鏈路有|T(ei)|條。當發(fā)現(xiàn)一個圈覆蓋時，平均每條鏈路被覆蓋的次數(shù)表示為

(9)

在真實通信網絡中，大多數(shù)鏈路都是可以完全定位的，但它并不能保證始終達到這一目的，因為一些告警編碼對于特殊鏈路是不能精確定位的(例如：在度數(shù)為2的路徑上的鏈路，其告警編碼是一樣的)。因此，需要一個最低定位門限來衡量，定義為故障定位率，用DL來表示

(10)

(10)式中：E(G)表示所有被監(jiān)視鏈路的總和，即為圖G(V,E)中鏈路的總數(shù)；A為所有告警編碼的集合總和。因為可能出現(xiàn)很多被覆蓋到的鏈路其告警編碼是一樣的，所以，E(G)要大于A，為了達到較準確的定位，我們要盡可能找到一種圈發(fā)現(xiàn)算法，其定位率盡可能趨近于1，最理想的情況是達到完全精確定位，即DL=1。

2.2m2圈覆蓋算法與其他算法的統(tǒng)計比較

圖1為4種典型的MESH網絡拓撲。采用圖1中國教育和科研計算機網(chinaeducationandresearchnetwork,CERNET)、國家科學基金網(nationalsciencefoundationnetwork,NSFNET)、貝爾通信研究中心(Bellcommunicationsresearchcenter,BELLCORE)，小型網絡(smallnetwork,SMALLNET)的拓撲來仿真，并對幾種圈覆蓋算法的監(jiān)測成本用以上幾個標準進行比較分析，仿真結果如圖2—圖7所示。

圖2為4種圈覆蓋發(fā)現(xiàn)算法在不同拓撲中的cost(p)，從圖2中可以看出，m2圈算法和HST算法使用的探測突發(fā)監(jiān)測設備數(shù)目最多，而SPEM算法使用的數(shù)目最少，大約少使用了接近一半的探測突發(fā)監(jiān)測設備。圖2為4種不同網絡拓撲中所需監(jiān)測器的個數(shù)情況，而監(jiān)測器個數(shù)就是圈覆蓋中圈的個數(shù)。由于HST所需要的監(jiān)測器的個數(shù)是多于HDFS和SPEM的[9]，因此，這里只對HST和m2圈算法的監(jiān)測器個數(shù)進行分析。由于HST的圈覆蓋是基于生成樹機制進行構造的，所有構造的圈沒有多余。相反，m2圈覆蓋算法構造的圈是有多余的，不過m2圈可以針對告警信息對圈覆蓋進行優(yōu)化，去除多余的圈，這就保證了m2圈覆蓋算法的圈個數(shù)不會多于HST算法，因此，其監(jiān)測器個數(shù)也不會多于HST算法。

圖1　4種典型的MESH網絡拓撲Fig.1　Topologies of four typical network

圖2　4種圈覆蓋發(fā)現(xiàn)算法在不同拓撲中的cost(p)Fig.2　cos t(p)computed by four cycle finding algorithms

圖3和圖4主要對4種算法尋找到的圈覆蓋的平均圈長度和最大長度分別進行了對比分析。無論對于平均圈長度還是最大長度，m2圈算法尋找到的圈覆蓋都優(yōu)于其他算法，因而m2算法可以極大地緩解PB與DB對數(shù)據(jù)通道的競爭。

圖3　4種圈覆蓋發(fā)現(xiàn)算法在不同拓撲中的avrg_length(C)Fig.3　avrg_length(C) computed by four cycle finding algorithms

圖5為4種算法尋找到的圈覆蓋對鏈路的平均覆蓋次數(shù)。雖然m2圈算法中鏈路平均覆蓋次數(shù)不是最少的，一定程度上增加了PB消耗掉的鏈路帶寬。不過，由于PB消耗的帶寬數(shù)量級遠低于波長信道，因此PB額外消耗的鏈路帶寬對算法性能的影響很小。

圖4　4種圈覆蓋發(fā)現(xiàn)算法在不同拓撲中的max_length(C)Fig.4　max_length(C) computed by four cycle finding algorithms

圖5　4種圈覆蓋發(fā)現(xiàn)算法在不同拓撲中的avrg_T(E)Fig.5　avrg_T(E) computed by four cycle finding algorithms

圖6為4種圈覆蓋發(fā)現(xiàn)算法在不同拓撲中的DL。從圖6中可以看出,在故障定位率方面m2圈算法和HST算法的定位率較高，相比其他2種算法在定位方面要精確很多。圖6中的仿真參數(shù)定位率為鏈路總數(shù)與不重復告警編碼集合的比值，可見定位率由不重復的告警編碼集合決定。由于HST算法的定位率是優(yōu)于HDFS和SPEM的，因此，這里只對HST和m2圈算法的定位率進行分析。如果兩條故障鏈路的告警編碼一樣，m2圈算法需要移除兩條故障鏈路中的一條并重新為另外一條鏈路尋找一個圈。倘若m2圈算法找不到這樣一個圈，就無法區(qū)分這兩個故障，并表明這兩條故障鏈路在一個圈上，那么這個圈必為HST構造的圈覆蓋中僅有的一個圈，因此，HST同樣無法區(qū)分這2個故障。同理，如果m2圈覆蓋算法可以區(qū)分這2個故障，那么HST算法也可以區(qū)分這2個故障。所以HST和本文m2圈覆蓋算法的故障定位率是相同的。

圖6　4種圈覆蓋發(fā)現(xiàn)算法在不同拓撲中的DLFig.6　DL computed by four cycle finding algorithms

圖7為4種圈覆蓋發(fā)現(xiàn)算法在不同拓撲中的G。在4種拓撲都達到完全定位時，m2圈相比其他3種圈發(fā)現(xiàn)算法，其監(jiān)視器的損耗減少率是最多的。圖7中的仿真參數(shù)損耗減少率經過分析可以看出是由監(jiān)視器增加之前的個數(shù)和完全定位需要增加的監(jiān)視器個數(shù)決定的。由于HST和本文m2圈算法的故障定位率相同，因此，達到完全定位m2圈算法需要增加的監(jiān)測器個數(shù)不會多于HST算法。而經過圖2對監(jiān)測器個數(shù)的分析，可知m2圈算法監(jiān)測器增加之前的個數(shù)不會多于HST算法。從而m2圈算法監(jiān)視器增加之前的個數(shù)與完全定位需要增加的監(jiān)視器個數(shù)之和也不會多于HST算法，即m2圈覆蓋算法的損耗減少率是不少于HST算法的。然而由于不同網絡拓撲的平均連通度不同，所以，在有些網絡拓撲上2種算法的損耗減少率是相同的。

圖7　4種圈覆蓋發(fā)現(xiàn)算法在不同拓撲中的GFig.7　G computed by four cycle finding algorithms

圖2—圖7表明：圈覆蓋算法可有效地減少探測模塊的數(shù)量。但是4種算法要針對不同網絡拓撲進行有效地選擇,m2圈算法不僅有較高的故障定位率，并且相對于其他3種算法所需要的平均圈長度和最長圈長度最小。

3結論

本文提出了一種新的基于m2圈覆蓋的故障監(jiān)測方法,運用圈覆蓋理論減少OBS網絡中需要的故障監(jiān)視器的數(shù)量，并在4個典型網絡拓撲中對4種不同圈覆蓋算法的故障定位率、監(jiān)視器的損耗概率、對于鏈路的負荷方面進行了性能比較。仿真表明，基于m2圈覆蓋的OBS網絡故障監(jiān)測機制可以對監(jiān)視器成本和鏈路帶寬開銷進行很好的折中，相對于逐跳校驗模型，該監(jiān)測機制在探測模塊昂貴時可以有效地降低網絡監(jiān)測成本。

參考文獻：

[1]WU G, ZHANG T, CHEN J, et al. An index-based parallel scheduler for optical burst switching networks[J]. Lightwave Technology, 2011, 29(18): 2766-2773.

[2]BELBEKKOUCHE A, HAFID A, GENDREAU M, et al. Path-based QoS provisioning for optical burst switching networks[J]. Journal of Lightwave Technology, 2011, 29(13): 2048-2063.

[3]AKAR N, KARASAN E, VLACHOS K G, et al. A survey of quality of service differentiation mechanisms for optical burst switching networks[J]. Optical Switching and Networking, 2010, 7(1): 1-11.

[4]KLINKOWSKO M,PEDRO J,CAREGLIO D,et al.An overview of routing methods in optical burst switching networks[J].Optical Switching and Networking,2010,7(2):41-53.

[5]OGINO N, NAKAMURA H. All-optical monitoring path computation based on lower bounds of required number of paths[C]//Communications (ICC), 2011 IEEE International Conference on.Kyoto,Japan: IEEE Press,2011:1-6.

[6]GARG A K. An efficient fault localization or detection mechanism for high speed optical networks[J]. Optik-International Journal for Light and Electron Optics, 2013, 124(21): 5127-5130.

[7]HE W, WU B, HO P H, et al. Monitoring trail allocation for SRLG failure localization[C]//Global Telecommunications Conference (GLOBECOM 2011). Houston ,USA:IEEE Press, 2011: 1-5.

[8]ALI M L, HO P H, TAPOLCAI J. Fault localization in all-optical linear networks[C]//Knowledge and Smart Technology (KST), 2014 6th International Conference on. Chon buri, Thailand: IEEE Press, 2014: 93-98.

[9]ZENG H, HUANG C, VUKOVIC A. Spanning-tree based monitoring-cycle construction for fault detection and localization in mesh AONs[C]//Communications(ICC), 2005 IEEE International Conference on. Seoul, Korea: IEEE Press, 2005: 1726-1730.

[10] ZENG H, HUANG C. Fault detection and path performance monitoring in meshed all-optical networks[C]//Global Telecommunications Conference, 2004. Texas, USA: IEEE Press, 2004: 2014-2018.

[11] 王汝言, 常交法, 隆克平, 等. 基于圈覆蓋的光突發(fā)交換網狀網故障監(jiān)測方案[J]. 北京郵電大學學報, 2007, 30(4): 111-115.

WANG R,CHANG J,LONG Keping, et al. Fault Detection Mechanism Based on Probe Cycle Cover in Meshed Optical Burst Switching Networks[J]. Journal of Beijing University of Posts and Telecommunications, 2007，30 (4):111-115.

[12] WANG R Y, LONG K P, WU W, et al. A Limited Deflection Routing Algorithm Based on Burst Loss Threshold in OBS Networks[J]. The Journal of China Universities of Posts and Telecommunications, 2005, 12(3): 44-48.

DOI：10.3979/j.issn.1673-825X.2016.03.016

收稿日期：2014-09-21

修訂日期：2015-07-18通訊作者：陳第全chendiquancq@163.com

基金項目：國家電網公司科技項目(SGTYHT/13-JS-175)；重慶市電子信息產品測試工程技術研究中心，重慶市工程技術中心(渝科委發(fā)[2014]1號)；重慶市科技平臺與基地建設計劃項目(工程技術研究中心)(cstc2014pt-gc40002)

Foundation Items：The science and technology projects of State Grid(SGTYHT/13-JS-175)；The Chongqing Engineering Research center of Electronic Information Products Testing[2014]1); The R & D Base Capacity Improvement Project of Chongqing Science & Technology commission(cstc2014pt-gc40002)

中圖分類號：TN929

文獻標志碼：A

文章編號：1673-825X(2016)03-0377-06

作者簡介：

陳弟全(1969-)，男，重慶人，工程師，主要研究方向為電力通信。E-mail: chendiquancq@163.com。

王賢亮(1975-)，男，重慶人，碩士研究生，副高級工程師，主要研究方向為信息通信技術研究。E-mail: wangxliang163@163.com。

靳敏(1989-)，女，重慶人，本科。主要研究方向為信息通信運維工作，參與信息通信相關項目實施，開展信息通信技術研究。E-mail: jinminm163@163.com。

姜元帥(1983-)，男，重慶人，專科，主要研究方向為變電運行維護、信息運行維護、電力營銷等工作。E-mail: jiangys163@163.com。

(編輯：田海江)

A fault detection mechanism based on minimum-length probe cycle cover algorithm

CHEN Diquan1，WANG Xianliang1，JIN Min1，JIANG Yuanshuai1，WANG Nan2，ZHANG Yan3

(1. Chongqing Electric Power Company, Chongqing 400015, P.R. China；2. Key Laboratory of Optical Fiber Communication, Chongqing University of Posts and Telecommunications, Chongqing 400065, P.R. China；3. Chongqing Institude of Telecommunications, Chongqing 401336, P.R. China)

Abstract:A new fault detection mechanism based on minimum-length probe cycle cover algorithm is proposed in terms of costly sing-hop test module in optical burst switching networks. The minimum-length cycle finding algorithm is used to find cycle cover for optical burst switching networks. After that, a probe module is assigned for each cycle and a fault detection mechanism based on probe cycle cover is formed in optical burst switching networks. Meanwhile a corresponding fault localization method based on minimum-length probe cycle cover is developped. The mechanism compares the alarm code with the associative code to achieve fast link localization. The computation and statistic results show that this fault detection mechanism has the features of the least amount of network resources, higher fault localization degree and fast fault localization, etc.

Keywords：optical burst switching; minimum-length probe cycle cover algorithm; fault detection; fault localization