基于信任评估的虚拟网故障诊断算法

刘　娜，张顺利，王向东

(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.