基于園區(qū)網(wǎng)絡(luò)拓撲的告警關(guān)聯(lián)規(guī)則挖掘算法

文 /楊滟 黃小紅 馬嚴

園區(qū)網(wǎng)絡(luò)指在有限的地理區(qū)域內(nèi)由多個局域網(wǎng)相互連接組成的網(wǎng)絡(luò)，作為用戶接入互聯(lián)網(wǎng)的基礎(chǔ)，當(dāng)園區(qū)網(wǎng)絡(luò)發(fā)生異常時必須快速準確定位故障根源才能有效保證用戶上網(wǎng)體驗。然而隨著園區(qū)網(wǎng)絡(luò)規(guī)模日益增大，網(wǎng)絡(luò)復(fù)雜化、設(shè)備多樣化等因素使得告警間的關(guān)系也變得錯綜復(fù)雜。同時，由于網(wǎng)絡(luò)故障具有傳播性，單一故障會引發(fā)與之直接或間接關(guān)聯(lián)的節(jié)點故障，造成大量衍生告警，使得故障根源的定位更加困難。

告警關(guān)聯(lián)規(guī)則挖掘技術(shù)由于其貼合網(wǎng)絡(luò)告警時間相關(guān)性的特點，成為近年來興起的網(wǎng)絡(luò)故障根源分析方法之一。但是往往存在不同程度的問題。為了解決以上問題，本文提出基于園區(qū)網(wǎng)絡(luò)拓撲的告警關(guān)聯(lián)規(guī)則挖掘算法（Topo C-OPT算法）；即增加園區(qū)網(wǎng)絡(luò)拓撲作為挖掘依據(jù)，根據(jù)告警實體間的跳數(shù)定量分析空間關(guān)聯(lián)性，計算得到拓撲關(guān)聯(lián)因子，并基于此進一步建立置信度優(yōu)化模型，有效挖掘出時間相關(guān)性雖弱但正確的告警關(guān)聯(lián)規(guī)則，同時增強對時間相關(guān)性雖強但無效的規(guī)則的識別，從而提升園區(qū)網(wǎng)絡(luò)告警分析場景下挖掘結(jié)果集的正確率。

原有算法回顧

SDH-AARM算法（以下簡稱原有算法）同時具備了WINEPI的時序相關(guān)性以及FP-Growth的挖掘高效性，因此本文選用此算法為基礎(chǔ)算法，在該算法的基礎(chǔ)上進行研究改進。告警關(guān)聯(lián)規(guī)則挖掘算法的目的是在一個給定的時序集合中挖掘出所有強告警關(guān)聯(lián)規(guī)則。強告警關(guān)聯(lián)規(guī)則指支持度和置信度均高于閾值的告警關(guān)聯(lián)規(guī)則。原有算法包括以下步驟：

1.采用滑動窗口方法構(gòu)建告警事務(wù)庫；

2.基于支持度挖掘頻繁告警序列；

3.加入告警時序特征，生成告警關(guān)聯(lián)規(guī)則及置信度；

4.基于置信度篩選強告警關(guān)聯(lián)規(guī)則。

置信度是評價某一事件正確概率的一種度量，表示該事件的可靠程度。告警關(guān)聯(lián)規(guī)則A=＞ B中A稱為前件，B稱為后件；A=＞ B的置信度(con)計算公式表示為

其中s(AB)為AB的支持度，表示A、B同時出現(xiàn)的概率；s(A)表示A出現(xiàn)的概率。支持度計算公式如下：

由于構(gòu)建告警事務(wù)庫后，窗口總數(shù)為確定值，所以根據(jù)上述置信度及支持度計算公式可知，原有算法中的置信度是單純基于支持數(shù)計算得到的，忽略了空間關(guān)系的定量影響，導(dǎo)致其準確度與實際情況存在偏差；當(dāng)應(yīng)用于園區(qū)網(wǎng)絡(luò)告警關(guān)聯(lián)規(guī)則挖掘時往往造成漏選正確規(guī)則，同時錯選錯誤規(guī)則的現(xiàn)象。

綜上可知，置信度的準確性對最終強告警關(guān)聯(lián)規(guī)則結(jié)果集的正確率具有決定性作用。因此，本文所提出的Topo C-OPT算法中，關(guān)鍵改進點在于引入園區(qū)網(wǎng)絡(luò)拓撲優(yōu)化告警關(guān)聯(lián)規(guī)則的置信度，提高規(guī)則置信度的準確性從而達到提升強告警關(guān)聯(lián)規(guī)則挖掘結(jié)果集正確率的目的。

Topo C-OPT算法

Topo C-OPT算法在網(wǎng)絡(luò)拓撲關(guān)聯(lián)性與告警時間相關(guān)性相互獨立的前提下提出，忽略網(wǎng)絡(luò)拓撲距離對告警傳輸時延的影響。

Topo C-OPT算法主要包含以下六個步驟。

1.采用滑動時間窗口方法處理告警源數(shù)據(jù)，得到告警事務(wù)庫；由于園區(qū)網(wǎng)絡(luò)中的關(guān)聯(lián)告警必定在相近時間發(fā)生，所以該方法具有實際意義。

2.采用FP-growth算法挖掘頻繁告警序列；

3.基于頻繁告警序列，加入告警的時序特征生成告警關(guān)聯(lián)規(guī)則及其置信度；時序特征包括順序關(guān)系、并列關(guān)系及混合關(guān)系。

4.構(gòu)造拓撲關(guān)聯(lián)因子算法，計算告警實體在園區(qū)網(wǎng)絡(luò)拓撲中的關(guān)聯(lián)性。

5.構(gòu)造置信度優(yōu)化模型；基于上一步驟獲得的拓撲關(guān)聯(lián)因子進一步構(gòu)造置信度優(yōu)化模型，優(yōu)化步驟2中原有置信度，提升置信度值的準確性。

6.基于優(yōu)化后置信度篩選強告警關(guān)聯(lián)規(guī)則。

其中，步驟4和5中提出的拓撲關(guān)聯(lián)因子算法及置信度優(yōu)化模型為本研究的關(guān)鍵改進點，彌補了單純從時間維度計算置信度造成其偏差較大的不足，增強對正確規(guī)則的識別能力，提升強告警關(guān)聯(lián)規(guī)則挖掘結(jié)果集的正確率。

拓撲關(guān)聯(lián)因子算法

本研究所提出的拓撲關(guān)聯(lián)因子定義為：描述告警關(guān)聯(lián)規(guī)則前后件在網(wǎng)絡(luò)拓撲中的關(guān)聯(lián)性，關(guān)聯(lián)性越高，則拓撲關(guān)聯(lián)因子值越大。本算法采用告警實體在網(wǎng)絡(luò)拓撲中的距離，即從源實體到目的實體所需經(jīng)過的最小鏈路數(shù)，作為衡量關(guān)聯(lián)性的參數(shù)。

根據(jù)告警關(guān)聯(lián)規(guī)則的定義可知，規(guī)則前后件均為告警項集合，集合中的告警項為并列關(guān)系，前后件間具有因果關(guān)系。為了研究拓撲關(guān)聯(lián)性對因果關(guān)系的影響，本算法中將前件和后件分別視為整體，計算兩者的關(guān)聯(lián)性，即為拓撲關(guān)聯(lián)因子。

拓撲關(guān)聯(lián)因子算法包含以下三個步驟：

1.計算前后件中告警實體在網(wǎng)絡(luò)拓撲中的距離；

2.將前件、后件分別視為整體，計算前件與后件的告警實體集之間的平均距離。

3.基于告警關(guān)聯(lián)規(guī)則前后件的平均距離，計算拓撲關(guān)聯(lián)因子。

第一，計算源-目的告警實體對距離

計算源實體(Sv )與目的實體(Dv )距離的算法如下：

輸入：網(wǎng)絡(luò)拓撲 ( G( V, E ))，源-目的實體對([vS,vD])

輸出：源-目的實體對的距離(d)算法描述：

(1) 建立隊列sq，d初始賦值為0，將vS從隊尾加入sq；

如圖1 ，給定一個網(wǎng)絡(luò)，該網(wǎng)絡(luò)中源實體 v1到目的實體 v6的最短路徑為，則 v1v2的距離計為2。

圖1 一個典型的網(wǎng)絡(luò)拓撲圖

第二，計算規(guī)則前后件的平均距離

輸入：網(wǎng)絡(luò)拓撲 (G( V, E))，A′，B′

算法描述：

(1) 取B′中任意未標(biāo)記實體 vk，計算vk與A′中所有實體的距離，并相加求平均值得到 vk與A′的平均距離；同時標(biāo)記 vk；平均距離計算公式如公式(3), 其中 nA'表示A′中的實體個數(shù)：

③

(2) 重復(fù)步驟(1)，直到B′中所有的實體均被標(biāo)記；

(3) 將B′中所有實體的平均距離值相加求平均值，即可計算出A′與B′的平均距離，計算公式如公式(4)，其中 n B'表示B′中的實體個數(shù)：

第三，計算拓撲關(guān)聯(lián)因子

本研究定義拓撲關(guān)聯(lián)因子與規(guī)則前后件平均距離成負相關(guān)關(guān)系。告警關(guān)聯(lián)規(guī)則前后件在園區(qū)網(wǎng)絡(luò)拓撲中的平均距離越小，可推測前后件的告警項集具備因果關(guān)系的可能性越大，則定義該規(guī)則的拓撲關(guān)聯(lián)因子值越大。拓撲關(guān)聯(lián)因子計算公式如下：

由上述公式可得到拓撲關(guān)聯(lián)因子與前后件平均距離的關(guān)系曲線，如圖2所示。隨著平均距離的增大，拓撲關(guān)聯(lián)因子呈下降趨勢，兩者成負相關(guān)關(guān)系；拓撲關(guān)聯(lián)因子取值范圍為(0,1]。

置信度優(yōu)化模型

圖2 拓撲關(guān)聯(lián)因子與前后件平均距離關(guān)系曲線，表示園區(qū)網(wǎng)內(nèi)最大距離

按上述算法計算得到的拓撲關(guān)聯(lián)因子，本研究進一步提出置信度優(yōu)化模型，根據(jù)拓撲關(guān)聯(lián)因子值對告警關(guān)聯(lián)規(guī)則的原有置信度(con)進行修正，從而得到準確度更高的新置信度( 'con)。根據(jù)園區(qū)網(wǎng)絡(luò)中告警的空間相關(guān)性可知，告警關(guān)聯(lián)規(guī)則前后件的拓撲關(guān)聯(lián)性越強，則該規(guī)則的可信程度越高；反之，拓撲關(guān)聯(lián)性越弱，則可信程度越低。設(shè)最小置信度閾值為min，置信度優(yōu)化模型公式如下⑥：

模型中a、b、c均為基于con的變量，后文將詳細描述； k1、 k2、 k3為三個臨界點，且滿足 0＜k1＜k2＜k3＜1；三個臨界點將topo的取值劃分為四個階段，分別為C1、C2、C3、C4，每個階段具有不同的優(yōu)化模型；本研究中 k1、 k2、 k3值根據(jù)實際故障處理經(jīng)驗手動設(shè)置。

為了更直觀地說明置信度優(yōu)化模型對告警關(guān)聯(lián)規(guī)則置信度的不同優(yōu)化策略以及優(yōu)化后的效果，圖3展示了topo分別與 con'、con的函數(shù)關(guān)系，并對比了 con'與con曲線。

圖3 'con與con對比圖

由圖3可知，原置信度值不受拓撲關(guān)聯(lián)因子的影響，完全由時間相關(guān)性計算得到，未考慮拓撲關(guān)聯(lián)因素。而新置信度值是在原置信度值基礎(chǔ)上根據(jù)拓撲關(guān)聯(lián)因子優(yōu)化得到，同時參考了時間相關(guān)性及拓撲關(guān)聯(lián)性，旨在提高準確性。下面將詳細闡述置信度優(yōu)化模型各階段的優(yōu)化策略。

C1階段，topo的取值為 (0,k1]，表示告警關(guān)聯(lián)規(guī)則前后件在園區(qū)網(wǎng)絡(luò)拓撲中的關(guān)聯(lián)性非常弱，故在原有置信度的基礎(chǔ)上降低其值。但由于規(guī)則在時間維度上的相關(guān)性仍然具有重要參考意義，故本研究采用控制原置信度下降范圍的方式保證時間相關(guān)性和空間相關(guān)性的平衡。當(dāng)con=1時，根據(jù)其計算公式可知每一次前件發(fā)生時后件均發(fā)生，本研究規(guī)定，該情況下即使前后件拓撲關(guān)聯(lián)性非常弱，該規(guī)則也為強告警關(guān)聯(lián)規(guī)則；因此本研究中將下降范圍控制為，則C1階段優(yōu)化后 con'的取值為。

C2階段，topo的取值為 (k1, k2]，表示告警關(guān)聯(lián)規(guī)則前后件拓撲關(guān)聯(lián)性較弱，但強于C1階段；故降低原置信度值。本模型定義：在 (k1, k2]范圍內(nèi)topo的值越小，表示前后件的拓撲關(guān)聯(lián)性越弱，則對置信度的負向影響程度越大，原有置信度下降程度越大。故本階段采用對數(shù)模型， con'的值域為。本階段公式中b和c均為基于con的變量，公式如下：

C3階段，topo的取值為 (k2, k3]，表示告警關(guān)聯(lián)規(guī)則前后件的拓撲關(guān)聯(lián)性既不強也不弱，故保持原有置信度值不變，即為con。

C4階段中，topo的取值為 (k3,1],表示告警關(guān)聯(lián)規(guī)則前后件在園區(qū)網(wǎng)絡(luò)拓撲中的關(guān)聯(lián)性非常強，故在原有置信度的基礎(chǔ)上提升其值。本模型定義：在 (k3,1] 范圍內(nèi)，topo的值越大，表示前后件的拓撲關(guān)聯(lián)性越強，對置信度的正向影響程度越大，則原置信度提升的程度越大。故本階段采用指數(shù)型增長模型， con'值域為(c on, h]，h值為當(dāng)即拓撲關(guān)聯(lián)性最高時 con'的取值。根據(jù)置信度的定義，置信度描述關(guān)聯(lián)規(guī)則的可信程度，取值范圍為[0,1]；取值為0時表示該規(guī)則完全不可信；取值為1時表示該規(guī)則完全可信。原有置信度依據(jù)告警的時間相關(guān)性計算得到，根據(jù)其計算公式可知，表示并非每一次規(guī)則前件發(fā)生時后件均發(fā)生；本研究規(guī)定：該情況下即使拓撲關(guān)聯(lián)性達到最高值1，該規(guī)則也不可稱為完全可信，故con'的取值為h(h＜1)。

同時，由于時間維度的相關(guān)性依然是置信度計算的重要參考因素，故本研究根據(jù)實際故障處理經(jīng)驗將最大提升空間控制為原有置信度的四分之一，由此可得到以下h值計算公式⑨：

以上詳細闡述了置信度優(yōu)化模型中topo值處于不同階段時的優(yōu)化策略，下面通過實驗驗證模型的有效性。

實驗結(jié)果與分析

為了對所提出方案的有效性進行驗證，本研究選用某高校校園網(wǎng)絡(luò)中2016年6月～2017年4月期間經(jīng)過初步數(shù)據(jù)處理后的10000條網(wǎng)絡(luò)告警數(shù)據(jù)作為數(shù)據(jù)源，并將其按照時間順序平均劃分為5個源告警數(shù)據(jù)庫。

本研究在2核CPU、4G內(nèi)存的LAMP環(huán)境下采用PHP語言開發(fā)。實驗過程如下：首先，分別對5組源告警數(shù)據(jù)采用滑動窗口方法處理生成5組源告警事務(wù)庫。其次，編程實現(xiàn)原有算法與Topo C-OPT算法，并使用兩種算法挖掘相同源告警事務(wù)庫，分別得到強告警關(guān)聯(lián)規(guī)則結(jié)果集R與R'。最后，采用人工標(biāo)記法標(biāo)記出R與R'中所有正確規(guī)則。對一條規(guī)則而言：正確標(biāo)記為1，錯誤標(biāo)記為0；分別統(tǒng)計R與R'中正確規(guī)則的數(shù)量，計算并對比正確率。

實驗中設(shè)置時間窗口為10min、滑動步長為5min；由于在時間窗口和滑動步長確定的情況下，告警事務(wù)庫的窗口總數(shù)為確定值，根據(jù)支持度計算公式(2)可知，此處設(shè)定最小支持數(shù)閾值即可，故設(shè)定1-項最小支持數(shù)閾值為10，n-項集最小支持數(shù)閾值為5(1＞n)；最小置信度閾值為0.80。分別采用原有算法和Topo C-OPT算法挖掘5組源告警事務(wù)庫，得到結(jié)果數(shù)據(jù)如表1所示。

表1 結(jié)果集數(shù)量及正確率

由以上實驗結(jié)果可知，在設(shè)置參數(shù)均相同的情況下，采用Topo C-OPT算法挖掘5組源告警事務(wù)庫得到的強告警關(guān)聯(lián)規(guī)則結(jié)果集的正確率均明顯高于原有算法。由此可證明，本研究所提出的Topo C-OPT算法在提升強告警關(guān)聯(lián)規(guī)則結(jié)果集的正確率方面具有明顯優(yōu)勢。

對于研究提出的拓撲關(guān)聯(lián)因子算法中，園區(qū)網(wǎng)絡(luò)拓撲關(guān)聯(lián)性的計算目前只選取了距離作為依據(jù)，下一步研究可考慮加入網(wǎng)絡(luò)設(shè)備層級關(guān)系等因子，進一步提高拓撲關(guān)聯(lián)性計算結(jié)果的準確度。