文 /楊滟 黃小紅 馬嚴

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

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

原有算法回顧

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

1.采用滑動窗口方法構建告警事務庫；

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

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

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

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

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

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

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

Topo C-OPT算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

算法描述：

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

③

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

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

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

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

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

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

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

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

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

圖3 'con與con對比圖

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

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

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

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

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

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

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

實驗結果與分析

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

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

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

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

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

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