基于信任評估的虛擬網故障診斷算法

劉　娜，張順利，王向東

(1.中國電子技術標準化研究院 軟件工程與評估中心，北京 100007；2.中國移動通信集團山西有限公司，山西 太原 030032；3.北京榮之聯科技股份有限公司 解決方案中心，北京 100080)

基于信任評估的虛擬網故障診斷算法

劉娜1，張順利2，王向東3

(1.中國電子技術標準化研究院 軟件工程與評估中心，北京 100007；2.中國移動通信集團山西有限公司，山西 太原 030032；3.北京榮之聯科技股份有限公司 解決方案中心，北京 100080)

摘要:網絡虛擬化環境的新特點(網絡拓撲動態變化、動態癥狀和故障關系、管理域獨立和信息不準確性)對故障診斷提出了新的要求，提出一種改進的針對網絡虛擬化環境下虛擬網和底層網故障診斷模型和診斷算法，通過虛擬網信任評估算法來提高故障診斷的準確率、降低誤報率。仿真研究結果表明，在大規模和噪聲大的虛擬網絡環境中，提出的故障診斷算法取得了較好的診斷效果。

關鍵詞:網絡虛擬化；故障診斷；虛擬網；信任評估

網絡虛擬化可以很好地解決網絡的僵化問題[1]。網絡虛擬化中網絡服務提供商(InternetServiceProvider，ISP)劃分為基礎設施提供商(InfrastureProvider，InP)和服務提供商(ServiceProvider，SP)。InP負責建設底層網絡(SubstrateNetwork，SN)，SP租用SN資源建設虛擬網絡(VirtualNetwork,VN)[2-3]對外服務。網絡虛擬化技術、網絡節點遷移技術、鏈路多分割副本技術[4-8]的應用給SN資源的使用帶來了新的問題，即資源之間彼此容易干擾，負載易出現不均衡而導致性能大幅下降。準確定位并診斷故障對解決此問題非常重要。但是如下網絡虛擬化的新特點對診斷帶來了新的挑戰：

網絡拓撲動態變化：虛擬節點的動態遷移和動態路由等技術使SP可以根據用戶的需求快速動態調整虛擬網拓撲。動態變化與故障對應關系：網絡拓撲結構的變化使得癥狀和故障的對應關系也動態變化。管理域獨立：SP和InP的信息不對稱，底層網絡故障信息對SP是透明的，難以獲取一些關鍵的診斷信息(如故障先驗概率)，而虛擬網服務的運行狀況和性能對InP又是不可知的。信息不準確性：虛擬網環境中噪聲的影響，增加了網絡監控的不準確性。

在傳統故障診斷算法無法有效解決上述問題的情況下，需要一種新的故障診斷方法在虛擬網環境下準確有效地定位根源故障，從而保障虛擬網絡服務的正常運行。

1問題形式化和系統模型

1.1問題形式化

定義1：構件包括虛擬構件和底層構件，虛擬構件由虛擬節點nv和虛擬鏈路lv組成，底層構件包括底層節點ns和底層鏈路ls。虛擬構件的資源由底層構件分配[5-8]。以圖1為例，SN上包含3個虛擬網絡，即VN1，VN2，VN3。VN1的節點A，B，C分別映射到底層網絡a，c，h節點。VN1的虛擬鏈路A-B映射到底層鏈路a-b-c上。B-C映射到底層鏈路c-g-h上。C-A映射到底層鏈路h-a上。

定義2：服務由SP提供的為滿足用戶一定需求的功能集合。一個服務一般依賴多個構件,不同服務可能依賴相同構件。以圖1為例，在VN1上，有一個端到端的服務service1經過路由A-B-C，服務如果要正常運行，虛擬路由A-B-C上的節點和節點之間的鏈路必須正常工作。同時，底層網絡a-b-c-g-h的節點和鏈路正常運行是虛擬構件正常運行的必要條件。

圖1　網絡虛擬化環境下端到端服務

圖2　端到端服務故障貝葉斯網絡模型

1.2層次協作的診斷模型

層次協作的診斷模型如圖3所示。各個虛擬網根據自己的監控信息診斷癥狀。如果癥狀由本虛擬網內部故障導致立即對故障進行修復，經過診斷確信不是本虛擬網內部的故障，則生成外部癥狀(ExternalSymptom,Se)。虛擬網不能診斷的癥狀被稱為未診斷癥狀 (un-DiagnosedSymptom,Sun)。虛擬網監控中心將Se和Sun傳遞到承載它的底層網絡的監控中心，對于Se更新底層網絡故障模型并定位故障。對于Sun,底層網絡根據監控中心獲得的癥狀信息和承載的虛擬網的癥狀信息，判斷故障原因并對診斷結果進行可信性驗證。通過可信性驗證則將結果反饋給虛擬網。若沒有通過可信性驗證，使用主動檢測技術對癥狀進行探測，更新癥狀集合后再次診斷。

圖3　層次協作的診斷模型

本文對癥狀進行主動探測，探測之后所產生的可信癥狀集合對診斷起到促進作用。鑒于底層網絡探測結果可靠性和虛擬網業務連續性，本文僅在底層網絡使用主動探測的技術。

2虛擬網和底層網絡內部評估算法

根據以上分析，本文提出一種虛擬網內部評估和底層網絡內部評估算法(VNInternalEvaluationandUnderlyingNetworkEvaluationAlgorithm，VIAUNEA)，由診斷、可信性評估、主動探測3個功能模塊組成。

診斷模塊基于觀測到的癥狀和已有故障診斷先驗知識，使用故障推理算法，確定故障假設集合h(faulthypothesis)解釋所有的癥狀。因本部分工作與現有近似故障診斷研究相同，本文使用其診斷算法[11]。

信任評估模塊判斷診斷結果是否可信。網絡虛擬化環境的新特點使癥狀丟失和虛假癥狀更加嚴重，本文通過設置閾值的方法進行判斷。

主動探測模塊使用研究成果[9]，選擇花費最少、覆蓋范圍最大的探測節點，探測故障假設集合h中每一個故障應出現卻沒有出現的癥狀。

虛擬網故障診斷算法如算法1(偽代碼)所示。

算法1：虛擬網故障診斷算法

Input:VNi內觀察到的癥狀集合SO

Output:故障集h

Step1：VNi將觀測到的癥狀SO作為輸入；

Step2：VNi使用故障診斷算法診斷SO，產生h1；

Step3：使用公式(1)對h1進行評估,如果通過評估，轉Step 11；

Step4：VNi將癥狀傳遞給底層網絡；

Step5：底層網絡對癥狀進行診斷，并得到故障集合h2，使用公式(3)評估h2；

Step6：如果通過可信性評估，轉Step11；

Step7：所有接收到癥狀的虛擬網執行診斷算法；

Step8：VNi使用公式(2)對接收到的診斷結果評估。如果通過評估，轉Step11；

Step9：底層網絡使用公式(4) 對接收到的診斷結果評估; 如果通過評估，轉Step11；

Step10：底層網絡使用主動探測算法，對h2中應該出現但是沒有出現的癥狀進行探測，獲得新的癥狀集合；

底層網絡更新癥狀集合，診斷故障并得到故障集合；

Step11：輸出診斷結果；

首先VNi將觀測到的癥狀SO作為輸入，故障診斷算法[9]能夠根據SO診斷出故障集合h(Step2)。如果故障屬于本虛擬網內部故障，診斷結束。如果故障不能被診斷，傳遞自己的癥狀情況給底層網絡(Step4)。如果底層網絡能夠診斷出故障，將診斷結果反饋給其承載的虛擬網絡。在算法Step3，Step5，Step8，Step9中使用可信性評估提高診斷的性能。Step10使用主動探測方法，提高癥狀集合的準確度。

根據故障發生的位置不同，本文的信任評估分為虛擬網內部故障評估和底層網絡內部故障評估兩種。根據信任評估的執行階段不同，虛擬網內部故障評估和底層網絡內部故障評估都被劃分為兩階段的評估。

2.1虛擬網內部

2.1.1第一階段評估

(1)

2.1.2第二階段評估

(2)

2.2 底層網絡內部

2.2.1第一階段評估

(3)

2.2.2 第二階段評估

(4)

上面4個評價函數的取值范圍都是[0,1],取值越接近1，說明當前的故障診斷結果越可信。系統管理人員能夠根據長期的觀測結果和經驗定義這些閾值。但是，如果閾值設置的太高，正確的診斷結果可能被忽略。相反，如果閾值定義的太低，錯誤的故障集合可能會被選擇。由于網絡噪聲和虛假癥狀的存在，本文選取的閾值都小于1。

3評估

3.1比較方法

本文采用準確率(Accuracy)及誤報率(False Positive)兩個指標對診斷結果進行評價。式(5)給出準確率及誤報率的計算方法。F代表實際故障節點的集合。→F代表被誤診為故障的節點的集合。H代表診斷算法計算的故障節點的集合。

(5)

3.2網絡拓撲和規模對算法性能的影響分析

與文獻[9-10]相似，本文使用BRITE工具生成Hierarchical模型網絡拓撲。底層網絡包含的節點范圍是(500,3 000)。虛擬網的節點范圍是(20,50)。映射在底層網絡上的虛擬網絡數量從10個增加到100個。映射算法G-MCF[6]被用于實現虛擬網到底層網絡上的映射。

從虛擬網絡中隨機選取10%左右的節點做為實驗用的源節點。源節點選取后，再從虛擬網絡中為每一源節點選取3個目的節點。通過最短路徑法生成虛擬網中的路由。利用一個端到端的服務進行實驗模擬。針對虛擬網絡以及底層網絡，他們的條件概率和先驗故障概率可以采取(0,1)以及[0.001,0.01]之間的均勻分布隨機生成。

為了驗證本文算法VIAUNEA在準確率(Accuracy)、誤報率(FalsePositive)、診斷時間(Time)3個指標評價診斷效果。本文實現了新算法VIAUNEA，并與Maxcoverage[13]與Shrink[14]算法做了比較。本文從無噪聲、有噪聲兩個方面，對3個算法進行了比較。

在無噪聲時，圖4和圖5比較3個算法的準確率與誤報率。圖4可以看出，3個算法的診斷準確率相近，圖5顯示Shrink算法和VIAUNEA算法誤報率比Maxcoverage算法低。

圖4　無噪聲時準確率比較

圖5　無噪聲時誤報率比較

在5%噪聲時，圖6和圖7比較3個算法的準確率與誤報率。從圖中可知，3個算法的診斷準確率都下降了。但是本文提出的VIAUNEA算法對虛假癥狀進行了過濾，所以VIAUNEA誤報率下降。

圖6　噪聲為5%時3算法診斷準確率比較

圖7　噪聲為5%時3算法誤報率的比較

4總結及下一步工作

在分析網絡虛擬化環境下故障診斷的挑戰后，本文提出了一種改進的網絡虛擬化環境下虛擬網和底層網故障內部評估的算法。為了提高診斷的準確率，降低故障的誤報率，在虛擬網絡故障診斷算法中，本文提出了基于信任的評估算法。仿真結果表明本文算法在大規模且有噪聲的網絡虛擬化環境中，取得了較好的診斷結果。后續研究重點將放在如何整合癥狀內在相關性和診斷經驗，降低故障診斷的時間，提高故障診斷的性能等方面。當故障跨越多個服務提供商的虛擬網絡的故障診斷算法，也將是未來研究的一個重點。

參考文獻：

[1]齊勇，羅英偉，孫毓忠.網絡資源虛擬化技術專題前言[J].軟件學報，2014，25(10)：2187-2188.

[2]李小玲，王懷民，丁博，等. 虛擬網絡映射問題研究及其進展[J].軟件學報，2012，23(11)：3009-3028.

[3]CHOWDHURYNMMK，BOUTABAR.Asurveyofnetworkvirtualization[J].Computernetworks，2010，54(5)：862-876.

[4]張千，陳朝根，梁鴻. 基于虛擬化技術的私有云計算平臺設計[J].計算機應用，2015，35(11)：3063-3069.

[5]焦術進，白靜.基于寫時重定向的虛擬機磁盤遷移技術[J].電視技術，2013，37(23)：101-105.

[6]YUH，ANANDV，QIAOC，etal.Acostefficientdesignofvirtualinfrastructureswithjointnodeandlinkmapping[J].Networkandsystemsmanagement，2012，20(1)：97-115.

[7]LEETH，TURSUNOVAS，CHOIT.Graphclusteringbasedprovisioningalgorithmforvirtualnetworkembedding[J].IEEEnetworkoperations&managementsymposium，2012，131(5)：175-1178.

[8]BAUMGARTNERA，REDDYVS，BAUSCHERTT.Amodelforcombinedvirtualcorenetworkfunctionplacementandtopologyoptimization[C]//Proc.IEEENETSOFT.[S.l.]：IEEE，2015：1-9.

[9]GUANL，WANGY，LIWJ，etal.Efficientprobingmethodforactivediagnosisinlargescalenetwork.NetworkandServiceManagement(CNSM) [C]//Proc.IEEE9thInternationalConference.[S.l.]：IEEE，2013：198-202.

[10]JIANGHQ，GAOX，GAOZY，etal.Adual-parameteroptimizationKPCAmethodforprocessfaultdiagnosis[C]//Proc.IEEEReliabilityandMaintainabilitySymposium(RAMS). [S.l.]：IEEE，2015：1-7.

[11]MADSENAL，SONDBERGJN,LOHSEN,etal.Amethodologyfordevelopinglocalsmartdiagnosticmodelsusingexpertknowledge[C]//Proc.IEEE13thInternationalConferenceonIndustrialInformatics(INDIN) .[S.l.]：IEEE，2015：1682-1687.

[12]TATIS，BONGJK，GUOHONGC，etal.adaptivealgorithmsfordiagnosinglarge-scalefailuresincomputernetworks[J].IEEEIFIP，2015(3)：1-12.

[13]KOMPELLARR，YATESJ，GREENBERGA.Detectionandlocalizationofnetworkblackholes[C]//Proc.IEEEINFOCOM. [S.l.]：IEEE，2007：2180-2188.

[14]KANDULAS，KATABID，VASSEURJP.Shrink:atoolforfailurediagnosisinIPnetworks[C]//Proc.ACMSIGCOMM. [S.l.]：ACM，2005：173-178.

責任編輯：許盈

Virtualnetworkfaultdiagnosisusingtrustevaluation

LIUNa1,ZHANGShunli2,WANGXiangdong3

(1.Software Engineering and Evaluation Center，CESI, Beijing 100007,China;2. China Mobile group Shanxi Co., Ltd., Taiyuan 030032,China;3. Solution Center, Beijing Ronglian Polytron Technologies Inc., Beijing 100080,China)

Abstract:The characteristics of virtual network bring new challenges to fault diagnosis, such as dynamic network topology, dynamic symptom-fault causality, administrator domain independence and inaccurate information. In this paper， an improved fault diagnosis monitoring model and algorithm are proposed to increase diagnosis accuracy and false alarm rate is reduced by using trust evaluations algorithm which includes two-stage evaluation within virtual network and substrate network. Simulation study shows the algorithm can get better diagnostic effect even in large-scale or noisy virtual network environment.

Key words:network virtualization; fault diagnosis; virtual network; trust evaluation

中圖分類號:TN915

文獻標志碼:A

DOI：10.16280/j.videoe.2016.04.017

收稿日期：2016-01-08

文獻引用格式：劉娜，張順利，王向東.基于信任評估的虛擬網故障診斷算法[J].電視技術，2016，40(4)：80-84.

LIUN，ZHANGSL，WANGXD.Virtualnetworkfaultdiagnosisusingtrustevaluation[J].Videoengineering，2016，40(4)：80-84.