摘 要：面對當前幾乎所有網絡管理系統(tǒng)所采用的依次輪詢故障報警的輪詢周期長、實時性低、輪詢數(shù)據(jù)量大的缺點，借鑒傳統(tǒng)網絡拓撲布局算法，利用節(jié)點間的拓撲關系，提出了一種利用啟發(fā)式算法和樹形算法相結合的智能故障報警系統(tǒng)的算法設計。實驗測試結果表明該算法可以大幅提高網絡管理系統(tǒng)故障報警的時效性。

關鍵詞：拓撲；SNMP；輪詢；生成樹

中圖分類號：TP393.07

當前，互聯(lián)網在我國發(fā)展非常迅猛，人們習慣于利用網絡管理系統(tǒng)（NMS）來管理各種intranet，如城域網、園區(qū)網、校園網、企業(yè)網等。國際標準化組織（ISO）在其提出的網絡管理框架（ISO74984）中把網絡管理功能分為五大部分：配置管理、性能管理、故障管理、安全管理、計費管理。NMS系統(tǒng)的高效與否主要取決于其以網絡拓撲圖為操作核心的管理子系統(tǒng)和以故障偵測為核心的故障管理子系統(tǒng)。對于網絡拓撲的生成，主要研究網絡節(jié)點間的關系和布局的問題[1-2]，對于網絡故障管理，主要研究的是如何快速、準確的獲知故障節(jié)點并觸發(fā)告警的問題。本文針對傳統(tǒng)網絡故障管理所采用的全部節(jié)點輪詢的做法的盲點，提出一種基于網絡節(jié)點拓撲關系的策略輪詢算法，它借鑒拓撲圖自動布局的相關算法，將所管理的網絡節(jié)點分成兩組，一組為關鍵節(jié)點組，一組為葉子節(jié)點組。關鍵節(jié)點組的每個節(jié)點出現(xiàn)故障都會影響到普通組中的網絡節(jié)點，在故障管理輪詢時先進行關鍵組的輪詢工作，一旦發(fā)現(xiàn)關鍵組中的某個網絡節(jié)點故障，則可同時對其所影響到的普通組內的網絡節(jié)點觸發(fā)故障報警而不需要再去輪詢，這樣既可以大幅度的提高輪詢效率，提高故障管理的時效性，又能最大限度的節(jié)約輪詢所占的網絡資源、避免重報、誤報率。該算法比較適合中大型園區(qū)網的故障告警管理。

1 故障檢測算法的研究現(xiàn)狀

從被管理設備中收集數(shù)據(jù)的方式有兩種：一種是主動輪詢（polling-only），另一種是基于中斷（interrupt-based）自陷方式[3]。由于當有異常事件發(fā)生時這種基于中斷的自陷方式需要系統(tǒng)資源，如果自陷必須轉發(fā)大量的信息，那么被管理設備可能不得不消耗更多的時間和系統(tǒng)資源來產生自陷，從而影響了它執(zhí)行主要的網絡管理的功能，尤其是當幾個同類型的自陷事件接連發(fā)生，大量網絡帶寬可能將被相同的信息所占用，例如當網絡發(fā)生網絡擁擠問題的時候，因此，通常網管系統(tǒng)都采用通過管理站，從被管設備主動輪詢收集數(shù)據(jù)來監(jiān)視被管設備狀態(tài)，根據(jù)故障管理輪詢的時間間隔，傳統(tǒng)輪詢算法大致分為兩大類：固定時間間隔的常規(guī)輪詢和可變時間間隔的動態(tài)輪詢[4]。固定時間間隔輪詢算法主要研究的是在固定時長的情況下如何提高輪詢效率，比較有代表的有：基于廣播SNMP并行輪詢算法[5]、采用嵌入馬爾可夫鏈和概率母函數(shù)的輪詢算法和移動輪詢算法[5]；動態(tài)輪詢算法主要研究的方向是根據(jù)監(jiān)控設備的某些工作狀態(tài)通過動態(tài)調整輪詢時間間隔的方法來實現(xiàn)提高輪詢效率，其中有代表性的算法有：根據(jù)網絡設備性能參數(shù)值的變化動態(tài)調節(jié)輪詢間隔時間的智能輪詢算法[6]、根據(jù) SNMP輪詢和事件通知獲得的網絡狀態(tài)數(shù)據(jù)，通過預測發(fā)生告警的可能性來動態(tài)調整輪詢間隔的動態(tài)算法和根據(jù)故障征兆參數(shù)值的時間屬性，使用離散傅立葉變換將參數(shù)值分解為不同頻率的正弦函數(shù)，進而根據(jù)系統(tǒng)預先設定的各參數(shù)故障告警閾值，決定使用分解得到的最大或最小頻率作為輪詢間隔的動態(tài)算法[7]。

2 傳統(tǒng)故障檢測算法的主要問題

不論是常規(guī)的等長間隔的算法，還是利用監(jiān)控對象的某些參數(shù)來動態(tài)調整輪詢間隔的動態(tài)，輪詢算法都是把所監(jiān)控對象作為同一平面層次的對象進行考察的，而實際上被監(jiān)控的網絡結構千差萬別，其監(jiān)控的節(jié)點相互之間的拓撲關系往往是相互影響的，實際情況常常會出現(xiàn)其中某一關鍵設備故障，從而影響其他一些節(jié)點故障的現(xiàn)象，這種現(xiàn)象在上述輪詢算法中都會造成故障誤報和浪費資源。

3 算法描述

本算法正是基于傳統(tǒng)輪詢算法對這一現(xiàn)象的盲點，提出了將所監(jiān)控的網絡節(jié)點按照節(jié)點間的相互關系層次化，將自身健康與否能直接影響到其他節(jié)點正常工作的節(jié)點稱之為關鍵節(jié)點，其他出現(xiàn)故障不會影響到別的節(jié)點的節(jié)點稱之為葉子節(jié)點，在設計輪詢算法時，按照先輪詢關鍵節(jié)點后輪詢葉子節(jié)點的順序進行輪詢，當發(fā)現(xiàn)某個關鍵節(jié)點出現(xiàn)故障時，根據(jù)該關鍵節(jié)點和葉子節(jié)點的關系就可以直接跳過對該關鍵節(jié)點所影響的葉子節(jié)點的輪詢，這樣既能大幅提高故障發(fā)現(xiàn)的效率，又能最大限度的減少輪詢所占用的系統(tǒng)資源，當然還有助于網管人員分析解決問題。

4 算法實現(xiàn)

4.1 算法思想

本算法假定已經存在所管理域內的網絡設備信息，并假定網管系統(tǒng)為基于Internet的IP網管，系統(tǒng)中的IP節(jié)點是唯一的。具體算法設計實現(xiàn)：

（1）假設已有網絡管理系統(tǒng)中的所有管理節(jié)點全集合U；

（2）首先要找出所管理域內的關鍵點集合K，以及葉子節(jié)點集合T，滿足K∪T=U；關鍵點的選擇可以根據(jù)多重條件來自定義，比如，網關IP、路由器環(huán)回地址IP，以及路由接口IP等。本算法考慮使用網關IP和路由器環(huán)回地址IP作為關鍵節(jié)點的選擇標準。標準之間是或的關系，理論上關鍵點的覆蓋面越廣、越具有代表性，其算法的效率就越高；

（3）找到關鍵點集合K中的每個關鍵點ki以及他們的影響葉子集合A；

（4）上述集合滿足：K∪T=U；

（5）故障輪詢啟動，首先順序輪詢關鍵點集合K，如果其中某個關鍵點ki出現(xiàn)故障，且其所影響的葉子中不含有關鍵點元素，則葉子集合T=T-A，如果關鍵點間出現(xiàn)相互影響的情形，需要對A和K兩個集合進行比對，如果有相同，則需要將這個相同的元素作為關鍵點處理，直到沒有出現(xiàn)相互影響的關鍵點；

（6）如果ki正常，則繼續(xù)依次輪詢關鍵點集合K，直到關鍵點集合K輪詢完全；

（7）繼續(xù)依次輪詢T直到此集合的每個葉子節(jié)點全部輪詢完全；

（8）固定時間間隔，重新啟動輪詢。

4.2 算法實現(xiàn)

（1）首先初始化網絡拓撲結構，對網絡拓撲結構進行生成樹樹遍歷，分離出關鍵節(jié)點和葉子節(jié)點集合。采用Prim算法來遍歷網絡拓撲圖，將網絡拓撲圖看成一個無權，無向圖，以NMS系統(tǒng)檢測點為根節(jié)點，求解網絡拓撲最小生成樹，從而分離出葉子節(jié)點集合T和關鍵點集合K，并滿足K∪T=U，U為全部須監(jiān)控網絡節(jié)點集合。具體生成樹算法不再累述。

圖1 典型的網絡拓撲結構

（2）輪詢遍歷關鍵節(jié)點和葉子節(jié)點，對于故障節(jié)點及時觸發(fā)報警。其流程如圖2所示：

圖2 輪詢流程圖

基本輪詢過程描述如下：

for（i=0，i<=n，i++）//首先對關鍵節(jié)點集合進行遍歷輪詢

{對關鍵節(jié)點集合K中的關鍵節(jié)點進行遍歷輪詢；

If（ki is ok ？）{執(zhí)行循環(huán)體，繼續(xù)輪詢下一個Ki}

Else{

對關鍵節(jié)點ki以及ki的影響節(jié)點結合A觸發(fā)故障報警；

重新賦值關鍵節(jié)點集合K和葉子節(jié)點T

K=K-ki-A；//由于關鍵節(jié)點ki的影響節(jié)點集合不但包含葉子節(jié)點，還可能包含其他關鍵節(jié)點。

T=T-A；//縮小葉子節(jié)點集合的輪詢范圍。

}

for（i=0，i<=n，i++）//最后對葉子節(jié)點集合進行遍歷輪詢

{If（Ti is ok ？）{next；}

Else {觸發(fā)報警；}

}

（3）對于關鍵節(jié)點的影響節(jié)點集合的確認可以通過以監(jiān)測節(jié)點為原點，葉子節(jié)點為目的地址進行traceroute路由跟蹤以及讀取SNMP路由表項信息分析得出。

4.3 算法分析

此算法從網絡拓撲節(jié)點間的邏輯關系為出發(fā)點，通過將網絡拓撲以監(jiān)控點為根節(jié)點做生成樹分析，并結合兩點之間的路徑信息和SNMP庫中的路由表信息，找到自身故障不影響其他節(jié)點的集合，稱之為葉子節(jié)點集合，找到自身出現(xiàn)故障同時會影響其他網絡節(jié)點的節(jié)點集合，稱之為關鍵點集合。這樣在做故障輪詢管理時一旦發(fā)現(xiàn)某個節(jié)點出現(xiàn)故障，如果該故障節(jié)點為關鍵節(jié)點，則對受其影響的節(jié)點包括葉子節(jié)點和某些關鍵節(jié)點在下次故障輪詢時只要此關鍵節(jié)點故障未恢復，則不再輪詢，這樣就可以大大提高輪詢速度，提高故障管理效率，同時也能有效的避免重復報警，有利于管理員把精力放在主要的關鍵點故障處理上。

4.4 算法仿真測試

上述算法已在BSD系統(tǒng)上通過Perl語言編程實現(xiàn)，并獲得了良好的結果，達到了預期的要求。

圖3 實驗網絡拓撲

圖3是本文的測試環(huán)境，圖中1-14是被監(jiān)測網絡節(jié)點，包括了路由器、交換機。另外，又分別選擇了浙江大學寧波理工學院校園網和寧波市教育科研城域網做了實際環(huán)境的部署測試，其測試結果如下：

表1 本算法與傳統(tǒng)順序輪詢效率對比表

實驗環(huán)境理工校園網教育城域網

順序輪詢一次時間60S300S600S

本算法輪詢一次時間60S180S300S

由該表可以看出該算法對于大型園區(qū)網效率提高明顯，尤其是對星型拓撲結構的網絡故障報警體現(xiàn)的效率最高，在實際測試時，傳統(tǒng)輪詢在網絡狀態(tài)不穩(wěn)定比如多處節(jié)點故障的情況下效率下降明顯，而本算法在此種情況下體現(xiàn)出理想的快速高效。但是在環(huán)形較多的復雜網絡環(huán)境下有一定的誤報率，主要是需要進一步提高分析核心冗余節(jié)點間互相依賴關系的效率。

5 結束語

該算法僅從網絡節(jié)點間的拓撲關系入手對網絡故障報警效率進行了改進，取得了很好的效果，傳統(tǒng)故障動態(tài)輪詢算法已經做了深入研究，比如固定時長的嵌入馬爾可夫鏈和概率母函數(shù)的輪詢算法以及動態(tài)調整輪詢間隔動態(tài)輪詢算法，因此我們下一步的研究工作將放在如何結合傳統(tǒng)的故障報警算法以對該算法進行進一步優(yōu)化。

參考文獻：

[1]AHN B，AHN S，CHUNG J.Topological- order based dynamic polling scheme using biconnected component computation[J].Future Generation Computer Systems，2004（02）：275-282.

[2]呂斌斌，包震斌，張明樂.基于SNMP協(xié)議的網絡拓樸發(fā)現(xiàn)算法分析[J].信息網絡安全，2012（01）：46-49.

[3]張振國，林衛(wèi)明.SNMP管理信息庫的移動輪詢[J].武漢理工大學學報2002（03）：338-339.

[4]Stallings W.SNMP and SNMPv2 the infrastructure for network management[J].IEEE Communications Magazine，1998（03）：37-43.

[5]程春玲，崔國亮，隋宗見.基于廣播SNMP的網絡管理并行輪詢算法[J].計算機應用研究，2010（12）：4711-4713.

[6]張新，常義林，孫方濤，一種改進的網絡故障監(jiān)測算法[J].西安電子科技大學學報2006（03）：416-417.

[7]崔中杰，胡昌振，唐成華.網絡安全設備故障管理中智能輪詢策略的研究[J].計算機工程，2007（11）：126-128.

作者簡介：朱金山（1976.12-），男，河南商丘人，碩士，中級（工程師），研究方向：計算機網絡及信息安全。

作者單位：浙江大學寧波理工學院圖書信息中心，浙江寧波 315100