改進BARINEL算法的網絡時延故障診斷方法

陳莉琳

(福建省數字福建云計算運營有限公司, 福建 福州 350100)

0 引言

為了保證網絡系統能夠正常運行, 需要對復雜的網絡系統進行監測和故障識別, 并對網絡故障進行診斷和定位[1]. 在許多網絡系統中, 某些軟故障難以檢測, 如造成查詢的延遲響應, 可能是服務器過載問題, 也可能是網絡連接問題, 亦或兩者原因都有. 因此, 網絡延遲故障診斷是一個值得研究的問題.

近年來, 基于數據的故障檢測方法取得了較好進展. 尚志信等[2]采用粗集技術進行網絡失效分析, 然后利用經過處理的規則對神經網絡進行訓練. Kim等[3-4]采用LSTM識別網絡異常. 蔣家駒等[5]采用機器學習對現網運行數據進行實時監測, 發現故障隱患. 朱曉榮等[6]采用GAN進行無線異構網絡故障檢測與診斷. 陳紅紅等[7]采用改進極限學習機方法實現無線傳感器網絡故障檢測. 上述方法的優點是通用性強, 但缺乏足夠的標記數據集[8]. 同時, 也有不少研究將圖論和概率模型應用于網絡故障診斷領域[9-10]. BARINEL算法[11]是一種復雜度較低的基于模型診斷技術, 能夠解決多故障程序診斷問題, 但計算過程較為復雜[12]. 文獻[13]提出改進的基于頻譜的錯誤定位方法, 采用STACCATO算法[14]生成故障候選集. 綜上分析, 已有基于數據分析的研究中, 存在模式識別算法的學習周期長、 需要訓練數據量大、 適用性弱等問題, 需要進一步優化故障檢測模型, 提升算法模型的網絡故障檢測能力.

基于此, 本研究提出一種基于模糊邏輯的改進BARINEL算法來進行網絡延遲故障診斷方法, 主要研究工作包括: 1) 針對數據的預處理, 提出一種正態分布延遲注入的數據預處理方法, 能夠較好模擬網絡系統的延遲故障, 解決待分析故障數據集的有效處理. 2) 基于STACCATO算法, 提出一種啟發式最小命中集搜索算法. 通過啟發式函數和相似性系數計算組件的集合排序, 并對集合進行截斷計算, 更快計算得到最小命中集. 3) 提出基于模糊理論拓展的BARINEL算法, 結合誤差診斷方法與貝葉斯模型, 有效得到故障診斷候選者及其故障概率, 提高網絡延時故障診斷能力.

1 背景知識

1.1 基本符號和變量

為了方便描述相關技術方法及算法, 現將一些基礎性符號和變量描述如下, 見表1.

表1 符號和變量Tab.1 Consistent and variable

1.2 最小命中集

本研究中的最小命中集, 是指一個最優的故障診斷候選集合. 具體地, 將最小命中集的描述如下:

設S是N個非空的集合,S={s1,s2, …,sN}.S每個子集si∈S是一個元素的有限集合, 本研究中即故障節點組件.其中每一個子集為一個數字集, 取值范圍為j∈{1, 2, …,M}表示.S的最小命題集則是一個集合滿足?si∈S,si∩d≠?∧?d′?d:si:∩d′=?.S的每個成員都至少有一個d的分量作為成員, 并且d的任何子集都不是命中集.S可能有多個最小命中集, 這就構成了一個最小命中集的集合D={d1,d2, …,dk, …,d|D|}.

本研究中, 集合S被編碼為一個N×M的矩陣A.若元素j是集合i的成員, 則元素aij等于1, 否則等于0.對于j≤M, 行Ai*表示一個組件是否是集合i的成員, 而A*j表示組件j是哪個集合的成員.例如一個節點數M=3的集合S={{1, 3}, {2, 3}}, 集合內包括兩個小集合,S編碼成的矩陣A如表2所示.

表2 S對應的矩陣ATab.2 Matrix A corresponding to S

計算S的最小命中集集合D的一個方法是通過所有可能的組件組合來檢查它是否是一個命中集, 如果是命中集, 檢查它是否是一個最小的集合, 即不被其他任何更低基數的集合所包含.其中一個集合dk的基數是指集合中的元素數量, 表示為|dk|.

1.3 模糊邏輯

(1)

在模擬邏輯中, 同樣假設延遲高于1 s為不正常, 同時假設延遲低于0.5 s為正常, 延遲時間在0.5～1 s表示一種特殊的錯誤類型. 考慮在這兩個閾值之間遵循一個線性模式, 代表這種特殊類型錯誤的模糊失敗級可以定義如下, 其中tr為響應時間,e(tr)表示節點錯誤類型,μF為隸屬函數.即

(2)

1.4 STACCATO算法

使用基于頻譜的故障定位(spectrum-based fault localization, SFL), 利用啟發式函數計算搜索最小命中集. SFL是一種低成本、 基于統計學的技術, 是能夠按概率大小排序故障候選項的良好預測器[16].

在SFL方法計算中, 需要將由集合S編碼的矩陣A表示故障診斷選項集合, 為表示頻譜矩陣與誤差向量的關系, 將其擴展為(A,e), 其中e是一個二進制列,Ai*對應于有異常的系統行為則e=1, 而正常的系統行為則e=0.在STACCATO算法中, 相似性系數采用Ochiai系數[17], 定義為

(3)

其中

npq(j)=|{i|aij=p∧ei=q|}|

(4)

相似性系數指的是使用n11(j)的元素, 并使用n10(j)和n01(j)除去n11(j)已有的元素和合集.相似性系數提供了一種產生良好診斷精度的集合排序, 排序越高, 對應的集合存在問題的概率越大.

2 基于啟發式函數的最小命中集計算

最小命中集的計算效率會對整個問題的求解時間產生很大影響. 這里, 給出啟發式函數H(j), 即

(5)

將函數應用于節1.1的例子, 則H(1)=1,H(2)=1,H(3)=2得到的排名為<3, 1, 2>, 這個排名被用來指導搜索. 從成分3開始, 它參與了兩個集合, 因此{3}是一個最小基數的最小命中集. 排名的第二位是成分1, 它沒有參與所有的集合, 與那些除了已經被1所覆蓋的集合之外的所有集合中涉及到的成分結合起來, 于是可以找到{1, 2}作為第二個最小命中集.

根據上述的分析, 設計了最小命中集算法, 快速計算并獲得故障診斷中涉及的相關節點數據. 在N個候選集, 每個有M個候選節點中, 算法得到最小命中集C. 算法如下.

算法1 基于啟發式函數的最小命中集算法輸入: 矩陣(A, e), 元素數 M, 修剪參數λ, 截斷參數 L1. 使用啟發式函數計算故障節點的排名2. for 所有組件 do3. 刪除所有故障集合共有的異常節點4. whileD≤L do5. 排名前幾位的節點, 從矩陣中刪除節點的列以及它參與的所有沖突集6. 用 STACCATO算法處理新矩陣7. 組合返回的集合與節點8. 驗證是否為最小命中集9. end while輸出: 最小命中集D

求解最小命中集問題是一個NP-hard問題, 假設每個候選集有M個候選節點時, 暴力求解的時間復雜度為O(2×M).所提出的啟發式函數的最小命中集算法能夠將時間復雜度縮減為O(C×M×(N+logM)), 減低了模型求解最小命中集的時間.

3 故障診斷與定位方法

3.1 故障診斷算法

本研究對BARINEL算法使用模糊邏輯進行擴展, 主要區別在于以下計算方法, 即

(6)

(7)

分析式(6), 看出該公式只能區分通過的測試和失敗的測試, 而式(7)則可以處理軟故障, 例如延遲故障等. 當試圖優化組件的“健康”[17]時, 可以使用這些方程作為優化問題的一部分, 此處的“健康”, 主要區別于故障的組件, 狀態為正常工作、 沒有受到故障影響的組件. 在網絡故障中, 清晰邏輯中節點只有為正常和失敗兩種, 但在實際的網絡延遲故障中, 需要描述不同故障狀態. 故障診斷算法如算法2所示.

算法2 改進BARINEL 算法的故障診斷輸入: 頻譜矩陣A和誤差向量e1. γ←e2. D←STACCATO((A, e))計算最小命中集3. for all dk∈D do4. exp r←GENERATEPR((A, e), dk)5. i←06. Pr[dk]i←07. repeat8. i←i+19. for all j∈dk do10. gj←gj+γ·▽exp r(gj)11. end for12. Pr[dk]i-←EVALUATE(exp r, ?j∈dkgj)13. untilPr[dk]i-1-Pr[dk]i≤?14. end for15. return SORT(D, Pr)16. 輸出: 診斷報告D

BARINEL的概率推理算法完成了對候選診斷的鑒別, 給定N個候選診斷集的前提下, BARINEL在診斷鑒別過程的時間復雜度分別為O(N).

3.2 故障定位算法

找出故障節點的最小命中集之后, 提出基于貝葉斯模型的故障定位方法, 候選概率計算方法BARINEL算法.

算法3 基于貝葉斯模型的故障定位算法輸入: 預處理后的路徑節點數據1. i=02. while i<0:3. 選擇隨機路徑, 生成光譜矩陣4. 產生誤差向量5. 使用STACCATO算法生成啟發式最小命中集6. 用模糊邏輯擴展的BARINEL計算故障概率, 對故障節點診斷排序7. 用清晰邏輯對故障診斷進行排序8. 計算和打印平均浪費努力輸出: 故障節點集合故障概率, 平均浪費的代價

具體地, BARINEL算法計算返回在邏輯上與觀察結果一致的診斷候選項dk, 并基于貝葉斯方法計算診斷候選項的概率Pr(dk), 實現候選項的有效排名.為了計算dk是真實診斷的后驗概率, 給定觀察值oi(它指的是測試的覆蓋率和錯誤信息), 具體計算如下式.

(8)

4 實驗結果與分析

4.1 數據集及預處理

實驗數據集cycle-aslinks.l7.t1.c0075 32.20190629, 來源于加州大學圣地亞哥超級計算機中心, 包含對Scramper traceroute跟蹤的自治系統(AS)的相關數據. 該數據集適用于網絡自治系統(AS)的拓撲結構分析及故障診斷等領域.

實驗抽取2019-06-29 上午07:15～2019-06-30 下午03:46之間記錄的數據. 對數據集進行解析, 提取自治系統鏈接和組件, 通過python腳本networkx模塊編碼隨機選擇記錄文件的2 000條邊, 然后, 提取該子圖中最大的連通分量, 剩下1 520個節點和1 721條邊. 同時按以下規則向組件(即路徑中節點)中注入延遲故障.

1) 根據分布μ=0.5、σ=0.62來生成延遲, 如圖1所示.

圖1 延遲注入動態分配圖Fig.1 Dynamic allocation diagram of delayed injection

2) 將低于50 ms的值設置為0 ms, 并將大于200 ms的值設置為200 ms.

3) 將50到200 ms范圍內的延遲注入到5%的組件中.

通過向組件中注入延遲的方法來模擬網絡中的故障. 在實驗產生的子圖的節點中, 有67個被注入了延遲. 延遲故障可視化表示如圖2, 圖中尺寸和顏色強度代表延遲, 一個組件的延遲越多, 它的紅色就越強烈, 大小就越大; 綠色節點的延遲低于錯誤閾值(0.2 ms).

4.2 實驗驗證

分別使用模糊邏輯擴展的BARINEL算法(以下簡稱為Fuzzy BARINEL)和清晰邏輯的BARINEL算法對網絡故障進行診斷實驗. 首先, 創建生成頻譜矩陣和誤差向量的數據, 生成了包含15～30個隨機節點(節點間具有連接性約束)的子數據集; 然后, 在這些節點中隨機選擇路徑, 限制路徑不能在一條路徑中包含所有異常節點; 最后, 將每條路徑作為頻譜矩陣和誤差向量的行, 頻譜矩陣列出路徑中的節點對于創建頻譜矩陣和誤差向量要求: 即如果分量(列)j含在路徑(行)i中, 則頻譜矩陣中的條目為1, 否則為0; 誤差向量由每條路徑的累積延遲組成.

對于每個子數據集, 選擇每個測試次數(10、 20、 30、 50、 100), 隨機選擇測試(路徑)50次, 以計算每種方法的平均浪費代價. 創建包含隨機節點的子數據集. 實驗中有22個節點被選擇為故障候選集, 其中4個節點存在異常延遲. 節點是枚舉的, 都代表一個真實的節點ID. 表3為其中一條路徑的節點和延遲的信息, 計算得到有延遲故障的異常節點, 其余節點的延遲為0.

表3 路徑節點延遲信息Tab.3 Path node delay information

隨機選擇30條路徑, 形成頻譜矩陣與誤差向量, 并用表格進行記錄, 選取部分路徑的頻譜矩陣和誤差向量, 見表4. 最左列表示路徑, 第1行表示路徑上的節點.

表4 頻譜矩陣Tab.4 Spectrum matrix

接著, 用誤差向量表示的模糊錯誤為累積延遲, 將它映射到[0.2, 1.0], 0表示路徑中沒有超過閾值的延遲, 0.2是代表延遲閾值的最低誤差, 1.0是最大累積延遲. 計算得到的誤差向量結果如表5所示.

表5 誤差向量結果Tab.5 Result of Error vector

表5中:Fe表示為標準化后的累積延遲;α表示所設置的清晰邏輯的閾值. 為了對比模糊邏輯與不同閾值下的清晰邏輯的診斷結果, 閾值分別設置為0.2、 0.4、 0.6、 0.8和1.0, 當標準化后的誤差向量大于等于閾值返回1, 小于閾值時則返回0.

將頻譜矩陣和誤差向量輸入到BARINEL代碼中, 用模糊邏輯擴展BARINEL計算出診斷故障節點最小命中集故障概率結果如表6. 表中:F表示為累積延遲, 括號內為可能的故障集, 冒號后為故障概率.

表6 節點集合故障概率Tab.6 Node fault set probability

分析表6中的結果, 通過使用Fuzzy BARINEL, 都為異常節點的診斷(10, 13, 16, 20), 排名第一, 概率為0.504 4. 使用閾值為0.2和0.4的清晰BARINEL給出了相同的結果, 概率分別為0.500 0和0.512 2. Fuzzy BARINEL能夠有效地診斷出可能的異常節點, 得到診斷候選集.

4.3 計算性能對比實驗

為了驗證清晰邏輯和Fuzzy BARINEL算法的計算性能, 開展了相關對比實驗.

診斷性能是用診斷性能指標W來衡量的, 該變量為50次隨機實驗中判斷錯誤的節點數量平均值, 稱為平均浪費代價, 該值計算為W=N/50,N為判斷錯誤的節點數量, 若W=0, 表示沒有浪費額外的代價去測試其他故障集合判斷故障與否.計算用清晰邏輯和模糊邏輯兩種方法在不同路徑數量下找到正確診斷平均浪費的代價W, 在5個子數據集的每個子數據集中隨機選擇50次以計算平均值. 對比結果如表7所示.

表7 找到正確診斷的平均浪費代價對比Tab.7 Average wasted cost of finding the right diagnosis

進一步將上述平均浪費代價平均值結果進行可視化對比, 具體如圖3所示. 圖中的折線對應了模糊邏輯和不同閾值的清晰邏輯的算法在不同路徑數量下的浪費代價平均值, 橫坐標為路徑數量.

圖3 平均浪費代價結果Fig.3 Average wasted cost

由圖3可知, 當清晰邏輯閾值設置較低時, 故障診斷效果明顯低于Fuzzy BARINEL, 如圖中α=0.2和α=0.4時, 在診斷10到30條路徑上產生了較差的效果.而當設置較高閾值時, 如α=0.8,α=1.0, Fuzzy BARINEL在大多數情況下的表現比清晰邏輯好, 浪費代價更少, 較高的閾值可能會誤判測試中異常組件.

5 結語

針對網絡延遲故障分析與定位問題, 本研究先采用基于啟發式函數的最小命中集算法STACCATO, 利用Ochiai相似性系數組件集合排序, 計算出故障組件的排名截, 有效地計算出最小命中集. 進一步使用Fuzzy BARINEL算法得到正確的故障候選集. 實驗表明, 本文提出的算法能夠有效診斷出延遲故障鏈路及故障點, 且具備較高的計算效率.

下一步, 將所提出的Fuzzy BARINEL算法針對多種網絡故障識別開展研究, 使得算法具有更好的適應能力.