劉　娜，張順利，王向東

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

基于信任評估的虛擬網(wǎng)故障診斷算法

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

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

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

關(guān)鍵詞:網(wǎng)絡(luò)虛擬化；故障診斷；虛擬網(wǎng)；信任評估

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

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

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

1問題形式化和系統(tǒng)模型

1.1問題形式化

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

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

圖1　網(wǎng)絡(luò)虛擬化環(huán)境下端到端服務(wù)

圖2　端到端服務(wù)故障貝葉斯網(wǎng)絡(luò)模型

1.2層次協(xié)作的診斷模型

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

圖3　層次協(xié)作的診斷模型

本文對癥狀進行主動探測，探測之后所產(chǎn)生的可信癥狀集合對診斷起到促進作用。鑒于底層網(wǎng)絡(luò)探測結(jié)果可靠性和虛擬網(wǎng)業(yè)務(wù)連續(xù)性，本文僅在底層網(wǎng)絡(luò)使用主動探測的技術(shù)。

2虛擬網(wǎng)和底層網(wǎng)絡(luò)內(nèi)部評估算法

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

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

信任評估模塊判斷診斷結(jié)果是否可信。網(wǎng)絡(luò)虛擬化環(huán)境的新特點使癥狀丟失和虛假癥狀更加嚴重，本文通過設(shè)置閾值的方法進行判斷。

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

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

算法1：虛擬網(wǎng)故障診斷算法

Input:VNi內(nèi)觀察到的癥狀集合SO

Output:故障集h

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

Step2：VNi使用故障診斷算法診斷SO，產(chǎn)生h1；

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

Step4：VNi將癥狀傳遞給底層網(wǎng)絡(luò)；

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

Step6：如果通過可信性評估，轉(zhuǎn)Step11；

Step7：所有接收到癥狀的虛擬網(wǎng)執(zhí)行診斷算法；

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

Step9：底層網(wǎng)絡(luò)使用公式(4) 對接收到的診斷結(jié)果評估; 如果通過評估，轉(zhuǎn)Step11；

Step10：底層網(wǎng)絡(luò)使用主動探測算法，對h2中應(yīng)該出現(xiàn)但是沒有出現(xiàn)的癥狀進行探測，獲得新的癥狀集合；

底層網(wǎng)絡(luò)更新癥狀集合，診斷故障并得到故障集合；

Step11：輸出診斷結(jié)果；

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

根據(jù)故障發(fā)生的位置不同，本文的信任評估分為虛擬網(wǎng)內(nèi)部故障評估和底層網(wǎng)絡(luò)內(nèi)部故障評估兩種。根據(jù)信任評估的執(zhí)行階段不同，虛擬網(wǎng)內(nèi)部故障評估和底層網(wǎng)絡(luò)內(nèi)部故障評估都被劃分為兩階段的評估。

2.1虛擬網(wǎng)內(nèi)部

2.1.1第一階段評估

(1)

2.1.2第二階段評估

(2)

2.2 底層網(wǎng)絡(luò)內(nèi)部

2.2.1第一階段評估

(3)

2.2.2 第二階段評估

(4)

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

3評估

3.1比較方法

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

(5)

3.2網(wǎng)絡(luò)拓撲和規(guī)模對算法性能的影響分析

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

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

為了驗證本文算法VIAUNEA在準確率(Accuracy)、誤報率(FalsePositive)、診斷時間(Time)3個指標評價診斷效果。本文實現(xiàn)了新算法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總結(jié)及下一步工作

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

參考文獻：

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

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

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

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

[5]焦術(shù)進，白靜.基于寫時重定向的虛擬機磁盤遷移技術(shù)[J].電視技術(shù)，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

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

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