文 /楊滟 黃小紅 馬嚴(yán)

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

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

原有算法回顧

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

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

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

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

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

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

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

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

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

Topo C-OPT算法

Topo C-OPT算法在網(wǎng)絡(luò)拓?fù)潢P(guān)聯(lián)性與告警時(shí)間相關(guān)性相互獨(dú)立的前提下提出，忽略網(wǎng)絡(luò)拓?fù)渚嚯x對(duì)告警傳輸時(shí)延的影響。

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

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

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

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

4.構(gòu)造拓?fù)潢P(guān)聯(lián)因子算法，計(jì)算告警實(shí)體在園區(qū)網(wǎng)絡(luò)拓?fù)渲械年P(guān)聯(lián)性。

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

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

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

拓?fù)潢P(guān)聯(lián)因子算法

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

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

拓?fù)潢P(guān)聯(lián)因子算法包含以下三個(gè)步驟：

1.計(jì)算前后件中告警實(shí)體在網(wǎng)絡(luò)拓?fù)渲械木嚯x；

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

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

第一，計(jì)算源-目的告警實(shí)體對(duì)距離

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

輸入：網(wǎng)絡(luò)拓?fù)?( G( V, E ))，源-目的實(shí)體對(duì)([vS,vD])

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

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

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

圖1 一個(gè)典型的網(wǎng)絡(luò)拓?fù)鋱D

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

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

算法描述：

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

③

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

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

第三，計(jì)算拓?fù)潢P(guān)聯(lián)因子

本研究定義拓?fù)潢P(guān)聯(lián)因子與規(guī)則前后件平均距離成負(fù)相關(guān)關(guān)系。告警關(guān)聯(lián)規(guī)則前后件在園區(qū)網(wǎng)絡(luò)拓?fù)渲械钠骄嚯x越小，可推測(cè)前后件的告警項(xiàng)集具備因果關(guān)系的可能性越大，則定義該規(guī)則的拓?fù)潢P(guān)聯(lián)因子值越大。拓?fù)潢P(guān)聯(lián)因子計(jì)算公式如下：

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

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

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

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

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

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

圖3 'con與con對(duì)比圖

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

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

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

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

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

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

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

實(shí)驗(yàn)結(jié)果與分析

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

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

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

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

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

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