韓瑞東，殷圣忠，李 萍

(1.運城學院計算機科學與技術系，山西運城044000；2.中國新聞社，北京100037)

基于最小生成樹的網(wǎng)絡故障定位算法研究

韓瑞東1，殷圣忠2，李 萍1

(1.運城學院計算機科學與技術系，山西運城044000；2.中國新聞社，北京100037)

針對網(wǎng)絡中某一個設備故障可能會使其他設備產(chǎn)生告警甚至影響整個網(wǎng)絡運行的這種情況，提出一種基于最小生成樹的網(wǎng)絡故障定位算法以找出故障源。該算法包括時間關聯(lián)分析和空間關聯(lián)分析，時間關聯(lián)分析通過壓縮、過濾、計數(shù)和抑止規(guī)則對告警信息進行處理以減少冗余?？臻g關聯(lián)分析通過預處理、告警分析、調整最小生成樹和鏈路關聯(lián)四部分對進行冗余處理后的告警信息進行處理以確定出真正的故障源。算法結果表明，其可以有效支持校園網(wǎng)絡的故障管理，幫助網(wǎng)絡管理員快速找出故障設備，以提高工作效率。

網(wǎng)絡故障；關聯(lián)分析；定位；故障源

隨著互聯(lián)網(wǎng)的快速發(fā)展，網(wǎng)絡規(guī)模不斷擴大，網(wǎng)絡中出現(xiàn)的故障可能會影響整個網(wǎng)絡，甚至會給社會帶來巨大損失，網(wǎng)絡安全問題變得重要[1]。當網(wǎng)絡中某一個設備產(chǎn)生故障時，可能會使其他正常的網(wǎng)元也發(fā)生告警，從而使整個網(wǎng)絡產(chǎn)生大量的告警信息，在這些告警信息中，要找出真正的故障源，就需要對這些告警信息進行關聯(lián)分析[2]。傳統(tǒng)的算法是基于方法庫的，把產(chǎn)生故障的情況在方法庫中找到最類似的情況排查故障(情況相似度至少高達90%)，實現(xiàn)難度較大，復雜度高，且效率低。因此，提出一種基于最小生成樹的網(wǎng)絡故障定位算法。

1 算法原理

由于一臺設備故障時，不僅會使自身產(chǎn)生重復告警，也會使其他正常的設備發(fā)出相同或相關的告警，要確定具體的故障源，就需要先對重復或相關的告警進行冗余，然后通過具體的網(wǎng)絡拓撲結構來定位出真正的故障源。所以，提出的算法包含兩方面：時間關聯(lián)分析和空間關聯(lián)分析。

1.1 時間關聯(lián)分析

在網(wǎng)絡運行過程中，當某一個網(wǎng)元產(chǎn)生告警信息時，在一段時間內可能會產(chǎn)生大量相同的或相關的告警信息，為了減少冗余，首先對這些告警信息進行時間關聯(lián)分析。根據(jù)網(wǎng)絡實際運行情況設定時間窗口T(兩個告警事件產(chǎn)生的時間差不能大于該值)，然后利用下面四種規(guī)則進行關聯(lián)分析，以減少冗余[3]。

(1)壓縮(Compression)

針對某一臺設備會產(chǎn)生大量的重復告警信息，而在規(guī)定的時間窗口內只需要保留一條即可，其他的自動丟掉，就需要使用壓縮規(guī)則。其規(guī)則如下所示：

該規(guī)則中，Ei代表的是第i個告警事件，Ti代表的是第i個告警事件發(fā)生的時間，根據(jù)IP地址來判斷是不是同一個設備發(fā)出的相同告警事件，用“= =”表示。

(2)過濾(Fliltering)

網(wǎng)絡中產(chǎn)生的大量告警信息有些并不是我們所關心的，對網(wǎng)絡運行也不會產(chǎn)生影響，那就在時間段內直接過濾，針對此情況，就需要使用過濾規(guī)則。其規(guī)則如下：

該規(guī)則中，A代表的是告警條件，S(Ei)代表的是第i個事件發(fā)生時所帶參數(shù)是否符合A的條件。

(3)計數(shù)(Counting)

針對某一個網(wǎng)元在設定的時間窗口內可能只產(chǎn)生一次或幾次告警，就需要使用計數(shù)規(guī)則。根據(jù)網(wǎng)絡實際情況，在這設定一個值M，超過該值時，保留；否則舍掉。其規(guī)則如下：

該規(guī)則中，M為根據(jù)網(wǎng)絡實際情況設置的預定值，N為總事件個數(shù)，count為計算相同事件的參數(shù)。

(4)抑止(Suppression)

網(wǎng)絡運行過程中某一個網(wǎng)元(如路由器、交換機等)發(fā)生告警信息時，其每個端口都會產(chǎn)生告警信息，根據(jù)每個端口告警信息的優(yōu)先級(以告警信息的嚴重程度來判斷)來進行關聯(lián)分析，丟掉優(yōu)先級低的，保留高的。針對該情況，就需要使用抑止規(guī)則。其規(guī)則如下：

該規(guī)則中，sIP代表的是同一臺設備不同端口發(fā)出的告警信息，S代表的是嚴重級別。

1.2 空間關聯(lián)分析

空間關聯(lián)分析主要是根據(jù)網(wǎng)絡的拓撲結構來進行的，通過利用最小生成樹的相關知識分析被管網(wǎng)元之間的關系來尋找出故障源[4]。圖1所示為告警關聯(lián)流程圖，利用實際網(wǎng)絡的拓撲結構，可以看做是圖，再利用相關算法實現(xiàn)最小生成樹，在最小生成樹中利用設備之間的關系來判斷出故障事件，以達到目的。

由于現(xiàn)實網(wǎng)絡中并不是所有的設備都兩兩相連，所以可以把網(wǎng)絡拓撲看做是一個稀疏圖，用鄰接表來存儲。這樣就能很好地節(jié)省空間，并且能夠支持算法的實現(xiàn)。該算法是根據(jù)網(wǎng)絡拓撲模塊提供的相關信息找出一個最小生成樹，然后再根據(jù)這個最小生成樹對故障信息進行關聯(lián)分析。對于最小生成樹來說，若兩個節(jié)點在相同的子樹上，則這兩個節(jié)點之間有且只有一條鏈路。通過數(shù)據(jù)結構知識中最小生成樹的性質，保留關鍵的信息，消除一些不必要的鏈路信息。當收到告警信息時，算法就會判斷是否為鏈路故障信息，如果是最小生成樹的路徑，就把該最小生成樹拆成兩個不同的子樹，算法就會搜索這兩個子樹的所有節(jié)點，查出不包含的網(wǎng)絡監(jiān)控的子樹，就會過濾掉這棵子樹所有節(jié)點的告警信息，只保留關鍵路徑告警信息。數(shù)據(jù)結構中，最小生成樹有兩種經(jīng)典算法，普里姆(Prim)算法和克魯斯卡爾(Kruskal)算法，Prim算法的時間復雜度為O(n2)，而Kruskal算法的時間復雜度為O(eloge)[5]。對比這兩個算法，Kruskal算法主要是針對邊來展開，邊數(shù)越少越有效，對稀疏圖有優(yōu)勢；而Prim算法對稠密圖會更好一些。根據(jù)對比，本算法的實現(xiàn)采用Kruskal算法。

圖1 告警關聯(lián)流程圖

2 算法實現(xiàn)

算法由預處理、告警分析、調整最小生成樹以及鏈路關聯(lián)等組成，時間復雜度為O(eloge)，e是鏈路數(shù)。如圖2所示。

圖2 空間關聯(lián)分析流程圖

2.1 預處理

該階段主要是通過拓撲發(fā)現(xiàn)模塊得到網(wǎng)絡拓撲結構用鄰接表來存儲，然后利用Kruskal算法實現(xiàn)最小生成樹，流程圖如圖3所示。

圖3 預處理流程圖

2.2 告警分析

當接收到一個告警信息時，如果已經(jīng)被上文提到的時間關聯(lián)分析過濾掉的話，那就無需再對其進行空間關聯(lián)分析了。若沒有被規(guī)則關聯(lián)掉，則判斷其是否為拓撲告警，否的話就把它放到延遲隊列等待下一步處理。是的話就需要再次判斷該拓撲告警是否為最小生成樹的鏈路告警，或判斷是否為連接兩棵不同的最小生成樹的鏈路告警，判斷是，則調整最小生成樹，否則需要把其放入延遲隊列等待下一步處理。其流程圖如圖4所示。

圖4 告警分析流程圖

2.3 調整最小生成樹

調整最小生成樹包括拆分與合并最小生成樹兩方面。

接收到告警信息時，如果其是最小生成樹上的鏈路告警時，就將最小生成樹拆成兩個子樹，再次運行Kruskal算法，尋找是否存在另外一條路徑能夠將這兩棵子樹相連，若存在，則調整最小生成樹，把這個新的路徑替換掉原來的那條路徑并去除，然后把該告警信息放入延遲隊列等待下一步處理。若不存在，就需要對其進行鏈路關聯(lián)，如果主干鏈路故障，就把其產(chǎn)生的告警信息進行關聯(lián)壓抑，消除冗余。

如果收到的告警信息是一個恢復正常的鏈路信息時，且這個鏈路連接的是兩個不同的最小生成樹，則這個最小生成樹也需要調整，將這兩個最小生成樹調整為一棵最小生成樹，然后把告警信息放入延遲隊列中等待下一步的關聯(lián)處理。其流程圖如圖5所示。

圖5 調整最小生成樹流程圖

2.4 鏈路關聯(lián)

其主要目的是對由于鏈路故障產(chǎn)生的誤報的告警信息進行關聯(lián)壓抑。當最小生成樹被拆分成兩棵子樹時，算法會遍歷這兩個子樹的所有節(jié)點，查找出網(wǎng)絡監(jiān)控節(jié)點所在的那個子樹。然后查找延遲隊列里的所有告警信息，將沒有網(wǎng)絡監(jiān)控節(jié)點的那棵最小生成樹上的所有節(jié)點的告警信息消除，把剩下的告警信息再放回到延遲隊列等待進一步的關聯(lián)分析。

3 算法驗證

通過該算法，實現(xiàn)了對告警信息進行關聯(lián)分析，能夠定位出故障源。圖6顯示了該算法與傳統(tǒng)算法所用時間的對比[6]。較之一般方法(引言中所提)，基于最小生成樹的網(wǎng)絡定位算法能夠將告警過濾時間提升40%，降低了因為分析無關網(wǎng)絡節(jié)點所浪費的時間。

圖6 拓撲方法與一般方法時間對比圖

從上圖所示的數(shù)據(jù)對比與驗證，證明了該算法的正確性及有效性，并能夠快速地定位出故障源。

4 結語

在實際網(wǎng)絡情況中，當某一網(wǎng)絡設備發(fā)生故障時，可能會引起其他一些正常的設備也產(chǎn)生告警，為了能快速高效地查找出真正的故障源，本文提出一種基于最小生成樹的網(wǎng)絡故障定位算法。該算法根據(jù)具體的網(wǎng)絡拓撲結構生成最小生成樹并根據(jù)具體情況來調整最小生成樹以定位出故障源。在基于空間關聯(lián)分析之前，首先要對時間段內的告警信息進行時間關聯(lián)分析以減少冗余。通過驗證，該算法能夠快速高效的定位出故障，與一般方法相比，具有一定的優(yōu)勢。并且極大地方便了網(wǎng)絡管理員排查故障的困難性，提高了效率，減少了損失。

[1]郭軍.網(wǎng)絡管理(第三版)[M].北京:北京郵電大學出版社,2008.

[2]鄭秋華.網(wǎng)絡故障智能診斷關鍵技術研究[D].杭州:浙江大學,2007.

[3]楊洪濤,王繼龍.網(wǎng)絡事件管理系統(tǒng)中關聯(lián)技術的選擇及實現(xiàn)[J].計算機工程,2006,32(4):197-199.

[4]WANG Yingying,LI Qiuju,CHANG Ming,et al.Research on Fault Diagnosis Expert System Based on the Nerual Network and the Fault Tree Technology[J].Procedia Engineering,2012(31):1206-1210.

[5]程杰.大話數(shù)據(jù)結構[M].北京:清華大學出版社,2012.

[6]彭熙,李艷,王倩,等.基于網(wǎng)絡拓撲結構的智能故障定位系統(tǒng)設計與實現(xiàn)[J].計算機工程,2005,31(2):219-231.

Research on Network Fault Location Algorithm Based on Minimum Spanning Tree

Han Rui-dong1,Yin Sheng-zhong2,Li Ping1
(1.Department of Computer Science and Technology,Yuncheng University,Yuncheng Shanxi,044000; 2.China News Service,Beijing,100037)

A network fault location algorithm based on minimum spanning tree(spatial correlation analysis)is proposed to identify the source of failure,aiming at the situation that a device failure in the network may cause the other devices to generate alarms and even affect the whole network operation.This algorithm includes time and spatial correlation analysis,using time correlation analysis by compressing,filtering,counting and suppressing rules to handle alarms to reduce redundancy.Using spatial correlation analysis to handle alarms of redundant processing to find the real source of failure by four parts:preprocessing,alarm analysis,adjusting the minimum spanning tree and link correlation.After the operation of the algorithm proved that it can support the campus network fault management effectively,help network administrators to identify the fault of the equipment quickly and improve efficiency.

network failure;correlation analysis;location;fault source

TP393

A

〔責任編輯 高海〕

1674-0874(2017)04-0010-04

2017-03-26

運城學院協(xié)同創(chuàng)新項目[CI-2015018]

韓瑞東(1988-)，男，山西運城人，碩士，助教，研究方向:軟件技術開發(fā)。