一種基于拓?fù)潢P(guān)系的NMS故障報(bào)警算法

摘 要：面對(duì)當(dāng)前幾乎所有網(wǎng)絡(luò)管理系統(tǒng)所采用的依次輪詢(xún)故障報(bào)警的輪詢(xún)周期長(zhǎng)、實(shí)時(shí)性低、輪詢(xún)數(shù)據(jù)量大的缺點(diǎn)，借鑒傳統(tǒng)網(wǎng)絡(luò)拓?fù)洳季炙惴?，利用?jié)點(diǎn)間的拓?fù)潢P(guān)系，提出了一種利用啟發(fā)式算法和樹(shù)形算法相結(jié)合的智能故障報(bào)警系統(tǒng)的算法設(shè)計(jì)。實(shí)驗(yàn)測(cè)試結(jié)果表明該算法可以大幅提高網(wǎng)絡(luò)管理系統(tǒng)故障報(bào)警的時(shí)效性。

關(guān)鍵詞：拓?fù)洌籗NMP；輪詢(xún)；生成樹(shù)

中圖分類(lèi)號(hào)：TP393.07

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

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

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

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

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

3 算法描述

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

4 算法實(shí)現(xiàn)

4.1 算法思想

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

（1）假設(shè)已有網(wǎng)絡(luò)管理系統(tǒng)中的所有管理節(jié)點(diǎn)全集合U；

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

（3）找到關(guān)鍵點(diǎn)集合K中的每個(gè)關(guān)鍵點(diǎn)ki以及他們的影響葉子集合A；

（4）上述集合滿(mǎn)足：K∪T=U；

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

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

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

（8）固定時(shí)間間隔，重新啟動(dòng)輪詢(xún)。

4.2 算法實(shí)現(xiàn)

（1）首先初始化網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，對(duì)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)進(jìn)行生成樹(shù)樹(shù)遍歷，分離出關(guān)鍵節(jié)點(diǎn)和葉子節(jié)點(diǎn)集合。采用Prim算法來(lái)遍歷網(wǎng)絡(luò)拓?fù)鋱D，將網(wǎng)絡(luò)拓?fù)鋱D看成一個(gè)無(wú)權(quán)，無(wú)向圖，以NMS系統(tǒng)檢測(cè)點(diǎn)為根節(jié)點(diǎn)，求解網(wǎng)絡(luò)拓?fù)渥钚∩蓸?shù)，從而分離出葉子節(jié)點(diǎn)集合T和關(guān)鍵點(diǎn)集合K，并滿(mǎn)足K∪T=U，U為全部須監(jiān)控網(wǎng)絡(luò)節(jié)點(diǎn)集合。具體生成樹(shù)算法不再累述。

圖1 典型的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)

（2）輪詢(xún)遍歷關(guān)鍵節(jié)點(diǎn)和葉子節(jié)點(diǎn)，對(duì)于故障節(jié)點(diǎn)及時(shí)觸發(fā)報(bào)警。其流程如圖2所示：

圖2 輪詢(xún)流程圖

基本輪詢(xún)過(guò)程描述如下：

for（i=0，i<=n，i++）//首先對(duì)關(guān)鍵節(jié)點(diǎn)集合進(jìn)行遍歷輪詢(xún)

{對(duì)關(guān)鍵節(jié)點(diǎn)集合K中的關(guān)鍵節(jié)點(diǎn)進(jìn)行遍歷輪詢(xún)；

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

Else{

對(duì)關(guān)鍵節(jié)點(diǎn)ki以及ki的影響節(jié)點(diǎn)結(jié)合A觸發(fā)故障報(bào)警；

重新賦值關(guān)鍵節(jié)點(diǎn)集合K和葉子節(jié)點(diǎn)T

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

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

}

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

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

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

}

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

4.3 算法分析

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

4.4 算法仿真測(cè)試

上述算法已在BSD系統(tǒng)上通過(guò)Perl語(yǔ)言編程實(shí)現(xiàn)，并獲得了良好的結(jié)果，達(dá)到了預(yù)期的要求。

圖3 實(shí)驗(yàn)網(wǎng)絡(luò)拓?fù)?/p>

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

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

實(shí)驗(yàn)環(huán)境理工校園網(wǎng)教育城域網(wǎng)

順序輪詢(xún)一次時(shí)間60S300S600S

本算法輪詢(xún)一次時(shí)間60S180S300S

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

5 結(jié)束語(yǔ)

該算法僅從網(wǎng)絡(luò)節(jié)點(diǎn)間的拓?fù)潢P(guān)系入手對(duì)網(wǎng)絡(luò)故障報(bào)警效率進(jìn)行了改進(jìn)，取得了很好的效果，傳統(tǒng)故障動(dòng)態(tài)輪詢(xún)算法已經(jīng)做了深入研究，比如固定時(shí)長(zhǎng)的嵌入馬爾可夫鏈和概率母函數(shù)的輪詢(xún)算法以及動(dòng)態(tài)調(diào)整輪詢(xún)間隔動(dòng)態(tài)輪詢(xún)算法，因此我們下一步的研究工作將放在如何結(jié)合傳統(tǒng)的故障報(bào)警算法以對(duì)該算法進(jìn)行進(jìn)一步優(yōu)化。

參考文獻(xiàn)：

[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]呂斌斌，包震斌，張明樂(lè).基于SNMP協(xié)議的網(wǎng)絡(luò)拓樸發(fā)現(xiàn)算法分析[J].信息網(wǎng)絡(luò)安全，2012（01）：46-49.

[3]張振國(guó)，林衛(wèi)明.SNMP管理信息庫(kù)的移動(dòng)輪詢(xún)[J].武漢理工大學(xué)學(xué)報(bào)2002（03）：338-339.

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

[5]程春玲，崔國(guó)亮，隋宗見(jiàn).基于廣播SNMP的網(wǎng)絡(luò)管理并行輪詢(xún)算法[J].計(jì)算機(jī)應(yīng)用研究，2010（12）：4711-4713.

[6]張新，常義林，孫方濤，一種改進(jìn)的網(wǎng)絡(luò)故障監(jiān)測(cè)算法[J].西安電子科技大學(xué)學(xué)報(bào)2006（03）：416-417.

[7]崔中杰，胡昌振，唐成華.網(wǎng)絡(luò)安全設(shè)備故障管理中智能輪詢(xún)策略的研究[J].計(jì)算機(jī)工程，2007（11）：126-128.

作者簡(jiǎn)介：朱金山（1976.12-），男，河南商丘人，碩士，中級(jí)（工程師），研究方向：計(jì)算機(jī)網(wǎng)絡(luò)及信息安全。

作者單位：浙江大學(xué)寧波理工學(xué)院圖書(shū)信息中心，浙江寧波 315100