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

劉　娜，張順利，王向東

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

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

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

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

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

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

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

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

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

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

1.1問(wèn)題形式化

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Output:故障集h

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

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

Step3：使用公式(1)對(duì)h1進(jìn)行評(píng)估,如果通過(guò)評(píng)估，轉(zhuǎn)Step 11；

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

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

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

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

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

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

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

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

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

首先VNi將觀測(cè)到的癥狀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中使用可信性評(píng)估提高診斷的性能。Step10使用主動(dòng)探測(cè)方法，提高癥狀集合的準(zhǔn)確度。

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

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

2.1.1第一階段評(píng)估

(1)

2.1.2第二階段評(píng)估

(2)

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

2.2.1第一階段評(píng)估

(3)

2.2.2 第二階段評(píng)估

(4)

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

3評(píng)估

3.1比較方法

本文采用準(zhǔn)確率(Accuracy)及誤報(bào)率(False Positive)兩個(gè)指標(biāo)對(duì)診斷結(jié)果進(jìn)行評(píng)價(jià)。式(5)給出準(zhǔn)確率及誤報(bào)率的計(jì)算方法。F代表實(shí)際故障節(jié)點(diǎn)的集合。→F代表被誤診為故障的節(jié)點(diǎn)的集合。H代表診斷算法計(jì)算的故障節(jié)點(diǎn)的集合。

(5)

3.2網(wǎng)絡(luò)拓?fù)浜鸵?guī)模對(duì)算法性能的影響分析

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

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

為了驗(yàn)證本文算法VIAUNEA在準(zhǔn)確率(Accuracy)、誤報(bào)率(FalsePositive)、診斷時(shí)間(Time)3個(gè)指標(biāo)評(píng)價(jià)診斷效果。本文實(shí)現(xiàn)了新算法VIAUNEA，并與Maxcoverage[13]與Shrink[14]算法做了比較。本文從無(wú)噪聲、有噪聲兩個(gè)方面，對(duì)3個(gè)算法進(jìn)行了比較。

在無(wú)噪聲時(shí)，圖4和圖5比較3個(gè)算法的準(zhǔn)確率與誤報(bào)率。圖4可以看出，3個(gè)算法的診斷準(zhǔn)確率相近，圖5顯示Shrink算法和VIAUNEA算法誤報(bào)率比Maxcoverage算法低。

圖4　無(wú)噪聲時(shí)準(zhǔn)確率比較

圖5　無(wú)噪聲時(shí)誤報(bào)率比較

在5%噪聲時(shí)，圖6和圖7比較3個(gè)算法的準(zhǔn)確率與誤報(bào)率。從圖中可知，3個(gè)算法的診斷準(zhǔn)確率都下降了。但是本文提出的VIAUNEA算法對(duì)虛假癥狀進(jìn)行了過(guò)濾，所以VIAUNEA誤報(bào)率下降。

圖6　噪聲為5%時(shí)3算法診斷準(zhǔn)確率比較

圖7　噪聲為5%時(shí)3算法誤報(bào)率的比較

4總結(jié)及下一步工作

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

參考文獻(xiàn)：

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

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

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

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

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

責(zé)任編輯：許盈

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

中圖分類號(hào):TN915

文獻(xiàn)標(biāo)志碼:A

DOI：10.16280/j.videoe.2016.04.017

收稿日期：2016-01-08

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

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