網(wǎng)絡故障預警算法研究

李子為 丁岳偉

摘要：隨著網(wǎng)絡規(guī)模的不斷擴大，為了保障網(wǎng)絡安全、穩(wěn)定運行，需要一種更高效的網(wǎng)絡故障預警算法。通過對傳統(tǒng)網(wǎng)絡故障預警算法優(yōu)缺點的分析，針對其缺點進行優(yōu)化改進，采用離群點檢測算法建立網(wǎng)絡故障預警模型。對異常檢測算法數(shù)據(jù)進行預處理，在Hadoop平臺上計算數(shù)據(jù)異常指數(shù)，并不斷調(diào)整閾值參數(shù)。實驗結果表明，改進型離群點檢測算法故障檢測率達到98%，可對網(wǎng)絡故障進行有效預警。

關鍵詞：網(wǎng)絡故障;故障預警;離群點;Hadoop平臺

DOI：10. 11907/rjdk. 192345 開放科學（資源服務）標識碼（OSID）：

中圖分類號：TP309文獻標識碼：A 文章編號：1672-7800（2020）007-0194-04

Research on Algorithm of the Fault Early Warning of Network

LI Zi-wei，DING Yue-wei

（School of Optical Electrical and Computer Engineering，University of Shanghai for Science and Technology，Shanghai 200093，China）

Abstract：In order to meet the requirements of increasing network scale in automation operation and maintenance， a more efficient network fault early warning algorithm is proposed in this paper. It is hoped to improve the performance of algorithm of the fault early warning of network through the study of? the traditional algorithm of the fault early warning of network and analysis of its advantages and disadvantages. This paper proposes the alarm and fault identification based on outlier detection algorithm. Firstly， the model of fault early warning of network are established. Then the data of outlier detection algorithm are preprocessed， threshold values are adjusted， and the performance of this algorithm is verified on Hadoop platform. The experimental process and results of network fault early warning are analyzed the improved outlier detection algorithm achieves 98% fault detection rate. The result show that this algorithm is efficient to warn network faults.

Key Words： network fault; fault early warning; network; outlier; Hadoop platform

0 引言

隨著移動互聯(lián)網(wǎng)的快速發(fā)展，網(wǎng)絡設備大規(guī)模投入使用必然會出現(xiàn)一些故障，從而影響網(wǎng)絡安全、穩(wěn)定運行。網(wǎng)絡故障在所難免，因此故障管理作為網(wǎng)絡管理中的一個重要組成部分，需要一套科學的管理方法[1]。一旦故障產(chǎn)生，則會在網(wǎng)絡中傳播，產(chǎn)生大量告警事件。如何能快速、有效地從這些告警事件中準確地進行事件關聯(lián)，從而給故障定位，是故障管理過程中一個亟待解決的問題[2]。

如今隨著網(wǎng)絡規(guī)模不斷擴大，網(wǎng)元結構逐漸復雜化，數(shù)據(jù)業(yè)務蓬勃發(fā)展，網(wǎng)絡故障、設備告警呈現(xiàn)出激增趨勢，運營商的網(wǎng)絡運營與維護面臨巨大挑戰(zhàn)[4]。因此，通過對大量設備數(shù)據(jù)的接入和告警關聯(lián)（Alarm Correlation，AC）[5]進行故障智能預警，可減少故障造成的損失。在這一思路的指導下，學者們提出了FP-growth算法、在線學習算法、Aprior算法以及改進型FP-growth算法[6-9]。但這些傳統(tǒng)算法只能針對其中某一個或幾個節(jié)點進行故障預警，而不能從全局角度發(fā)現(xiàn)網(wǎng)絡異常。在日志分析過程中，發(fā)現(xiàn)網(wǎng)絡異常處會形成離群點，因此學者們提出多種離群點檢測算法。如文獻[10]提出一種基于機器學習的貝葉斯網(wǎng)絡離群點檢測算法;文獻[11]指出基于空間的離群點檢測算法有待改進，并提出基于地統(tǒng)計學的離群點檢測算法;文獻[10]-[14]闡述了現(xiàn)有離群點檢測算法存在的對環(huán)境動態(tài)變化適應性差、網(wǎng)絡開銷過大、網(wǎng)絡數(shù)據(jù)庫安全性低、離群點維度較高、異常閾值需要手動設定等諸多缺點。同時，包括離群點檢測算法在內(nèi)的多種傳統(tǒng)異常檢測算法都存在運算數(shù)據(jù)量過于龐大的問題。

本文通過對網(wǎng)絡日志數(shù)據(jù)進行預處理，以減少工作量。在事故發(fā)生的早期檢測到異常情況，可使管理員有更多時間采取正確的行動。傳統(tǒng)異常檢測算法大多是對原始數(shù)據(jù)進行離群點檢測，為了更好地對異常點進行檢測，需要對異常檢測算法進行改進。因此，本文提出一種首先對初始數(shù)據(jù)進行預處理的網(wǎng)絡故障預警算法。網(wǎng)絡故障預警流程如圖1所示， 預警模型如圖2所示。

1 數(shù)據(jù)預處理

1.1 預處理原理

離群點是指與多數(shù)點距離超過某個特定數(shù)值的點。將正常的點進行聚合，根據(jù)密度進行排序，并減少對k近鄰的查找。將數(shù)據(jù)集中形成小集合的相似點去除，選取其中一個點，然后計算該點與其它點的距離，如果與其它集合中心的距離小于等于r/2，則將該點劃入該集合;若大于r/2，則將該點作為新的集合中心。集合中點的個數(shù)小于k的集合保留，其余集合全都刪去。若一個集合的中心點為o，在公式（1）中，集合中數(shù)據(jù)個數(shù)不小于k。在半徑為r的圓中，p、q的距離小于等于r。

因此，去除的點p是非離群點。然后對剩下的點進行整合，劃分為幾個集合，以提高查找效率。按照密度進行排序，并根據(jù)離群點存在于該集合中的程度，將集合中點較少的集合定義為離群點集合，將點較多的集合定義為非離群點集合。對數(shù)據(jù)點進行離群點檢測，通常需要訪問所有對象，并對集合離群程度進行評估。每個對象的k鄰近程度都需要進行評估，導致時間復雜度非常高。因此，此處通過數(shù)據(jù)預處理降低算法計算量。

1.2 預處理方法

若[Avg（p）D（p，ai）

查找p的鄰近點，如果公式（5）與公式（6）成立，則p并非本文所要找的離群點。因為p的離群程度均小于已知點，所以不必繼續(xù)查找p的鄰近點。隨著對另一個數(shù)據(jù)點P的k近鄰查找的進行，P的k近鄰中的最遠者總是會被距離其更近者所取代，因此該數(shù)據(jù)點的k近鄰平均距離，也即離群度隨著查找的進行總是不斷變小。Y是目前已得到n個候選離群點中的最小值，如果目前點P查找到的k近鄰平均距離已小于Y，那么再查找下去，其離群度也只會小于Y，也即是說，其離群度小于所有目前已知的n個候選離群點，因此不需要再計算P與數(shù)據(jù)集中其它點之間的距離。

1.3 預處理過程

算法運行時，p的鄰居會不斷地被更近的鄰居所替代，所以其離群度會持續(xù)降低。已知數(shù)個離群點的最小值，繼續(xù)查找仍不會找到大于Y的離群度，所以無需繼續(xù)查找。對相似度高的數(shù)據(jù)點進行歸類與排序，從而提高預處理效率。相似數(shù)據(jù)會被歸為同類，所以先在同一個類別中查找，可提高查找效率。原始數(shù)據(jù)與預處理后數(shù)據(jù)對比如圖4所示。

2 異常檢測

2.1 異常值

異常值在某些條件下是有意義且充分的，但在聚類不同時無法得到令人滿意的值。離群值不是二元屬性，相反，可為每個對象分配一個離群因子。對于給定p的距離k，p的k距離鄰域包含與p的距離不大于k的鄰域。網(wǎng)絡事件是由所發(fā)生的事件與時間所組成的，網(wǎng)絡節(jié)點日志可直觀反映與記錄網(wǎng)絡當前狀態(tài)的變化。

網(wǎng)絡設備的日志狀態(tài)會在正常狀態(tài)與異常狀態(tài)之間切換，當網(wǎng)絡正常運行時，網(wǎng)絡設備日志顯示正常狀態(tài)，當網(wǎng)絡故障發(fā)生時，網(wǎng)絡設備日志顯示異常狀態(tài)。不同日志之間數(shù)據(jù)也互不相同，對所有類似日志進行歸類，并對相似的日志數(shù)據(jù)進行編碼。根據(jù)時間繪制出日志不同的數(shù)據(jù)點分布圖，且將不同類型日志頻率記錄在案。本文通過該過程對原始、復雜的網(wǎng)絡設備日志進行數(shù)據(jù)化處理，每一個數(shù)據(jù)點之間有不同的動態(tài)過程，可以畫出異常點、離群點的位置從而進行直觀展示。

使用離群點檢測方法對網(wǎng)絡設備日志數(shù)據(jù)點進行衡量。在網(wǎng)絡正常運行時，網(wǎng)絡設備產(chǎn)生的日志中，產(chǎn)生的異常點數(shù)量是微乎其微的，所以使用離群點檢測方法時效率非常高。另外，使用離群點檢測方法對每條日志指數(shù)進行評估，可保證檢測的準確度。

2.2 異常指數(shù)

根據(jù)網(wǎng)絡設備日志數(shù)據(jù)點分布情況，可直觀感受到哪些網(wǎng)絡日志為故障日志。正常網(wǎng)絡日志形成的點密度很高，而故障所產(chǎn)生的點會形成離群點。根據(jù)上述各個過程將網(wǎng)絡設備日志語言轉換成結構化語言，可在全局異常檢測中有效利用日志產(chǎn)生的數(shù)據(jù)。如今很多算法無法從全局進行網(wǎng)絡故障預警，而使用全局異常檢測算法可以更加準確地從宏觀角度進行預警。對每一個網(wǎng)絡日志點進行異常評估，看其是否為離群點。在全局異常檢測中，本文使用異常指數(shù)對異常點進行評估，異常指數(shù)定義如公式（6）所示。

其中，[Nk（p）]表示p的k近鄰距離。p的離群因子捕獲了本文調(diào)用的一個離群點，其是局部可達性比率的平均值。需要注意的是，p的局部可達性密度越低，p最近鄰局部可達性密度的異常指數(shù)值越高。采用全局網(wǎng)絡故障預警方法可以快速、有效地進行網(wǎng)絡故障評估，在某個指定的網(wǎng)絡設備日志中，日志所形成的網(wǎng)絡設備日志點分布能夠直接反映網(wǎng)絡設備在這一時間段的狀態(tài)是否正常。異常因子的異常指數(shù)越低，表明異常值越小，說明該網(wǎng)絡設備的日志點落在密度較大區(qū)域，相反，該日志點離群越遠，該點異常值越高。當異常指數(shù)值高于預定值，則會發(fā)出警告。

網(wǎng)絡設備日志中的絕大多數(shù)日志都是重復且相似的，只需抽出其中相似的日志進行歸納，選取其中一部分進行公式計算，以減少計算量，從而節(jié)省網(wǎng)絡設備日志計算時間，提高執(zhí)行效率。該方式解決了因分析日志導致的大量時間消耗問題，使得全局異常檢測能夠更加精準、高效。

3 實驗研究

3.1 實驗環(huán)境

本文搭建實驗環(huán)境如下：采用偽分布式平臺，Hadoop版本號為2.8.3[20]，將6臺服務器虛擬成一個集群，1臺作為主服務器，其余5臺作為從服務器。本文使用仿真數(shù)據(jù)進行故障預警實驗，并與傳統(tǒng)算法進行比較。

3.2 實驗步驟

實驗具體步驟如下：①對網(wǎng)絡設備日志進行結構化預處理;②使用改進型離群點檢測算法對所得數(shù)據(jù)進行簡化處理;③計算單個網(wǎng)絡節(jié)點不同時間的異常指數(shù)，并將異常程度以折線圖形式表現(xiàn)出來。

3.3 實驗結果分析

改進型離群點檢測算法檢出率如表1所示。

由圖5可知，該網(wǎng)絡設備的故障點異常指數(shù)為7.253，且在圖中表現(xiàn)為離群點，網(wǎng)絡設備在此時出現(xiàn)故障。通過圖5可以輕松找出離群點，實驗結果符合預期。因改進型離群點檢測算法在檢測時保留了數(shù)據(jù)主干，提高了工作效率，彌補了采用傳統(tǒng)算法在非主干數(shù)據(jù)部分需要額外耗時以及準確率不足的缺點，從而提高了全局故障預警效率。由實驗結果可以看出，改進型離群點算法根據(jù)不同時間的離群點分布差異，對結果的分析更為全面、客觀，實現(xiàn)了預期的設計目標。

4 結語

基于大數(shù)據(jù)的網(wǎng)絡運維服務采用各種監(jiān)控、報警及報表服務工具，通過全面的網(wǎng)絡監(jiān)控與大數(shù)據(jù)智能分析，可在早期階段發(fā)現(xiàn)故障并進行預警。通過對傳統(tǒng)網(wǎng)絡故障預警算法優(yōu)缺點的分析，并針對其缺點進行優(yōu)化改進，采用離群點檢測算法建立網(wǎng)絡故障預警模型。實驗結果表明，改進型離群點檢測算法故障檢測率達到98%，可對網(wǎng)絡故障進行有效預警。下一步工作將針對ospf鄰居狀態(tài)抖動、端口flapping、模塊收發(fā)光異常等故障預警進行研究。

參考文獻：

[1] 陸明祥. 計算機網(wǎng)絡故障管理智能化探析[J]. 電子測試，2013（10）：120-121.

[2] 賀艷芳，石堅. SDH告警顯示預處理和告警關聯(lián)分析[J]. 科學技術與工程，2006，6（4）：487-499.

[3] 杜濤. 多用戶網(wǎng)絡高風險連鎖故障區(qū)域預警方法仿真[J]. 計算機仿真，2019，36（7）：328-330.

[4] 陳威. 移動通信運維大數(shù)據(jù)應用價值探討研究[J]. 信息通信，2016（10）：59-60.

[5] ZHAO B， LUO G. An alarm correlation algorithm based on similarity distance and deep network[C].? International Conference on Intelligent Computing，2016：359-368.

[6] HAN J，PEI J，YIN Y. Mining frequent patterns without candidate generation[C]. Proceedings of the 2000 ACM SIGMOD Internal Conference on Management of Data，2000.

[7] 劉啟元，張聰，沈一棟，等. 信度網(wǎng)結構在線學習算法[J]. 軟件學報，2002，13（12）：2297-2304.

[8] JIANG W，CHEN Y， LIAO Y. Correlation analysis of alarm databased on fuzzy rule in power network[M]. Switzerland：Springer，2018.

[9] MAN Y，CHEN Z P，CHUAN J B，et al. The study of cross networks alarm correlation based on big data technology[C]. International Conference on Human Centered Computing，2016：739-745.

[10] DWIVEDI R K，PANDEY S，KUMAR R.A study on machine learning approaches for outlier detection in wireless sensor network[C].? International Conference on Cloud Computing， Data Science & Engineering，2018.

[11] 劉莘， 張紹良， 王飛， 等.? 基于地統(tǒng)計學的空間離群點檢測算法的研究[J].? 計算機應用研究， 2016，33（12）：3700-3704.

[12] WANG ZM，SONG GH，GAO C. An isolation-based distributed outlier detection framework using nearest neighbor ensembles for wireless sensor networks[J].? IEEE Access，2019，7：96319-96333.

[13] SAKR M，ATWA W，KESHK A. Sub-grid partitioning algorithm for distributed outlier detection on big data[C]. 2018 13th International Conference on Computer Engineering and Systems （ICCES），2018：252-257.

[14] NAGAMANI C， CHITTINENI S. Network intrusion detection mechanisms using outlier detection[C]. 2018 Second International Conference on Inventive Communication and Computational Technologies （ICICCT）， 2018.

[15] HAQUE A，MINENO H. Contextual outlier detection in sensor data using minimum spanning tree based clustering[C]. International Conference on Computer， Communication，Chemical， Material and Electronic Engineering （IC4ME2），2018.

[16] LIU R Y，ZHU Q S. A network anomaly detection algorithm based on natural neighborhood graph[C]. International Joint Conference on Neural Networks （IJCNN），2018.

[17] YADAV S，TRIVEDI M C，SINGH V K，et al. Securing AODV routing protocol against black hole attack in manet using outlier detection scheme[C]. IEEE Uttar Pradesh Section International Conference on Electrical， Computer and Electronics （UPCON），2018.

[18] PATIL S D，VIJAYAKUMAR B P. An outlier detection scheme for wireless sensor networks[C]. International Conference on Wireless Networks and Embedded Systems （WECON），2016.

[19] 章鐸.? 基于大數(shù)據(jù)挖掘的故障預警系統(tǒng)研究與實現(xiàn)[D]. 北京：北京郵電大學，2014.

[20] 唐世慶，李云龍，田鳳明，等. 基于Hadoop的云計算與存儲平臺研究與實現(xiàn)[J]. 兵器裝備工程學報，2014（8）：97-100.

（責任編輯：黃 健）