基于动态时间扭曲的NFV网络故障检测.pdf

NATURACIENCEMar.,20232023年3月JOURNALOFNANJINGUNIVERSITYVol.59,No.2第59 卷第2 期南京大学学报（自然科学）DOI:10.13232/ki.jnju.2023.02.017基于动态时间扭曲的NFV网络故障检测齐小刚，张皓然*，李家慧，单明媚（西安电子科技大学数学与统计学院，西安，7 10 0 7 1）摘要：网络功能虚拟化（NetworkFunctionsVirtualization，NFV)实现了硬件与软件的解耦，是5G应用与发展的核心技术.NFV网络具有高动态性、层间不可见性、网络组件复杂等特点，给网络管理带来了挑战.为了保证NFV网络的正常高效运行，提出基于动态阈值的NFV故障检测算法DTF-DTW：首先，根据已有的正常样本数据，获得不同虚拟网络功能的故障阈值；然后，采用基于滑动窗口的快速动态时间扭曲算法，检测虚拟网络功能的故障时段并报警，采用真实世界的NFV数据对该算法进行测试，并使用机器学习算法STAD（Sp a t i o-T e mp o r a l A n o ma l y D e t e c t i o n）进行比较，证明提出的算法与现有算法相比，能更加迅速准确地检测出NFV中的异常行为，提高网络运行效率和用户服务满意度。关键词：NFV，网络故障检测，动态时间扭曲，时间序列，滑动窗口，动态阈值中图分类号：TP206.3文献标志码：AFault detection based on dynamic time warpping in NFV networksQi Xiaogang,Zhang Haoran,Li Jiahui,Shan Mingmei(School of Mathematics and Statistics,Xidian University,Xian,710071,China)Abstract:Network Function Virtualization(NFV)decouples hardware and software,which is regarded as the core technologyfor the application and development of 5G.NFV is characterized by high dynamics,invisibility between layers,andcomplexity of network components,which bring challenges to network management.Due to ensure the normal and efficientoperation of NFV networks,this paper presents Dynamic Threshold-based Dynamic Time Warping(DTF-DTW)algorithmfor fault diagnosis.Based on the sliding window,DTF-DTW retains the temporal characteristics of data,and detects the faultperiods for different Virtual Network Functions(VNFs)by Dynamic Time Warping(DTW)method.The proposed DTF-DTW algorithm is tested using real-world NFV environment data and the simulation results shows that our algorithmidentifies the abnormal behaviors in NFV networks more efficiently than existing algorithms,improving the network operationefficiency and user service satisfaction.Key words:NFV,network fault detection,dynamic time wrapping,time-series,sliding window,dynamic threshold下一代网络的愿景是将移动通信系统从世界上数十亿人口的规模扩展到人类、机器和事物之间几乎无限的互联规模，而5G被认为是能够实现这一愿景的网络.预计到2 0 2 5年，5G用户将达到19亿，其中35%的流量将由5G网络承载，这意味着预计全球6 5%的人口将被5G技术覆盖，基金项目：国家自然科学基金（6 18 7 7 0 6 7）收稿日期：2 0 2 2-11-14*通讯联系人，E-mail：8 6 7 7 90 434 q q.c o m通过“互联大陆”，人类、物体和机器可以获得专门的切片和应用 1.在支持和推动上述服务的同时，下一代网络还受到网络和服务的部署和交付方式根本性重组的推动 2 .对于运营商来说，5G整合移动和固定网络，实现了信息、事物和人类的无缝互联的愿景，这种无缝互联通过大规模部署所谓344第59 卷南京大学学报（自然科学）的“软件网络”提高速度、性能、可扩展性和灵活性，5G技术通常依赖于软件定义网络（SoftwareDefinedNetwork,SDN)3、云 4 和网络功能虚拟化(Network Functions Virtualization,NFV)5-6).NFV将网络功能虚拟化，以缓解网络变化并降低软硬件生命周期管理方面的成本.作为一项新兴的技术,NFV的核心是在物理网络上创建一个虚拟网络，将软硬件解耦，避免每个网络都需要使用定制的硬件设备，使虚拟化功能（Virtual Net-workFunctions，VNF)能够部署在统一管理的虚拟资源之上.其将网络功能与专有硬件分离，减少了VNF在大型物理基础设施上的支出以及维护、升级、修理等耗费的时间与金钱成本，NFV将网络资源池化这一特点大大提高了网络灵活性，近年来引起了科研人员与网络运营商的广泛关注，这一特点要求高效和灵活的网络管理，其中依靠人工智能技术的自主管理和认知管理已经成为管理未来网络的一个共识.目前虚拟网络的故障检测模型主要分为基于统计学的方法与基于机器学习的方法多元隐马尔可夫模型 7-8 通过训练不同类型的VNF行为模型来检测NFV的异常，识别所有组件随时间推移的状态序列，从而保护在线的VNF服务.上述统计学方法不需要预先了解目标系统的正常活动，可以从观察中了解系统的预期行为在设置适当的阈值或参数调优后，就能对长时间发生的恶意活动进行准确的通知或报警，但在故障检测中设置不同参数或度量的值来使假阳性和假阴性达到平衡很困难，而且，如果网络出现长时间的故障，期间产生的网络流量可能会被认为是正常的此外，大多数模型依赖于准平稳过程的假设，与实际情况不完全相符.获取当前网络状况的最直观、最方便的方法之一就是测量网络的性能指标.Hou etal9提出无监督方法用于异常检测，通过对整个监测网络的往返时间（Round-Trip Time,RTT)进行分析和挖掘来发现NFV的异常.基于RTT的矩阵差分分解方法 10 可同时对NFV网络中的多个异常进行检测和定位，但只能检出瞬时故障，对波动不明显的长时故障的效果不显著.Cherrardetal11提出自建模方法，观察并考虑模型中定义的逻辑假设来推断根本原因，最终生成指示组件状态和故障传播机理的依赖关系图，精确检测存在故障的网络组件，但其假设诊断在静态模型上进行，即假设故障已完全传播，与实际情况不相符.依赖于托管VNF的虚拟机的底层管理程序提供的数据 12 ,基于自回归差分移动平均模型（A RIM A 13 使用多变量模型学习单个组件的正常系统行为，基于系统大部分时间都在正常状态下运行的假设，通过不断学习每个受监控的数据点来形成表示该组件正常状态的模型，但针对不同组件需训练不同的模型，算法效率低.Dridietal14)提出时间-空间异常检测（Spatio-TemporalAnomalyDetection，ST A D）的框架，使用时间序列而非数据集建立故障检测模型，是单分类支持向量机、支持向量机回归和递归神经网络、长短期记忆网络等机器学习技术的组合：上述机器学习方法可以在没有任何来自环境反馈的情况下检测或分类持久性特征，但训练过程中可能会出现过拟合现象，而且，如果没有可靠的正常流量数据，训练过程会非常困难.本文利用改进的动态时间扭曲方法计算两个时间序列之间的扭曲路径距离，并将其作为两个时间序列相似性的度量依据.然后通过训练历史正常状态下的时间序列，得到VNF在正常情况下两个时间序列之间的相似度.使用统计方法自动为不同的VNF设定故障阈值，使用基于滑动窗口的方法对未知输入序列进行相似度计算，从而实时地进行故障诊断.提出的算法对不同类型的NFV网络异常检测均可达到一定准确度和效率.1相关理论1.1动态时间扭曲方法动态时间扭曲(Dyna-micTimeWarp,DTW)是衡量两个时间序列相似性的常用方法之一 15,其基本思想是通过对序列的各个部分进行拉伸和压缩，从而在两个时间序列间找到最佳的全局对齐，扭曲路径距离是两个时间序列扭曲后差值的度量，由图1a中灰色虚线连接的每对点之间的距离之和计算可得.若两个时间序列完全相同，即扭曲路径距离为零，连接线均为垂直的竖线，则不需要对这两个时间序列进行扭曲图中的红、黑两条曲线分别表示时间序列I和时间序列J，每条345第2 期齐小刚等：基于动态时间扭曲的NFV网络故障检测虚线将时间序列I中的一个点与另一个时间序列J中相应的相似点连接起来.DTW将时间序列进行扭曲来建立序列之间的非线性对齐，这样可以有更好的距离度量效果，再使用两个序列相似点对之间的距离之和（扭曲路径距离）来衡量两个时间序列之间的相似性.使用欧几里得距离衡量序列之间距离，考虑时间序列I=1,2,m),J=y1,y2,yn,其距离矩阵为：d(ai,yi)d(ai,y2)d(a1,y)d(2.yi)d(2,yz)d(t2,y,)D(m,n)=d(amyi)d(amy2)(1)其中，m,n分别为时间序列I和J的长度，,表示I中的点i，y,表示J中的点j.图1b使用网格描述距离矩阵，展示了DTW下两个时间序列的对应关系，图中的黑色实线表示扭曲路径W，则I与J的扭曲路径为：W=(W1,W2,.,Wk,W+1,wt)W=(ai,y,),W+1=(at,y,)(2)max(m,n)lm+n-1iii+1,jjj+l.DTW采用动态规划的思想搜索两个序列的总距离达到最短的扭曲路径：Dist(i,j)=d(a,y,)+minDist(i-1,j),Dist(i,j-1),Dist(i-1,j-1)(3)其中,Dist(i,ji)表示长度为i和j的两个时间序列之间的扭曲路径距离，d(i,y,)表示I中的第i个点和J中的第j个点之间的距离.由于两个序列之间的扭曲路径W的数量可能呈指数级爆炸式增长，因此需要通过定义一组约束条件以减少搜索空间大小：（1)端点/边界约束：由于时间序列的先后次序不可变，所以扭曲路径W的起点和终点需始终固定在(0,0)与(m,n).（2）连续性约束：对齐路径不能跃过时间序列中的某个点进行匹配，因此需确保扭曲路径W中没有中断点，且只与相邻点对齐.即如果w-1=(i,y),则w=(r,yr)需满足i-i1,j-j1.（3)单调性约束：为了保证图中虚线处不相交，扭曲路径W上的点需随时间单调连续递增，即如果k-1=(i,y),则=(u,yr）需满足i-i0,j-j0.综上，两个时间序列的最短路径为满足以上约束的最小距离：Dist(m,n)=Er=,d(we)(4)距离矩阵D直接对齐（扭曲前）波形对齐（扭曲后）(a)(b)图1两个时间序列的对齐Fig.1Alignmentoftwotime-series1.2基于DTW的改进方法fastDTW算法改进了传统的DTW，其主要思想是通过限制减少距离矩阵D的搜索空间并进行数据抽象，从而加速对扭曲路径W的搜索.算法过程如下：（1)粗粒度化：用更少的采样点将时间序列压缩以尽可能精确地表示原曲线.使用减少到原始长度一半的时间序列表示原序列,其中粗粒度数据点是其对应的两个细粒度数据点的平均值.如图2 中，1/1粒度下的原始距离矩阵经过三次粗粒度化后，收缩为1/8 粒度下的距离矩阵。（2)投影：在粗粒度条件下使用DTW方法，找出距离最小的扭曲路径W,并使用W作为初始值，推断较细粒度下的最小扭曲路径.图2 中黑色实线即为在各个粒度下得到的不同扭曲路径，1/11/21/41/8图2在不同粒度空间内执行DTW方法Fig.2Execution of DTW algorithm in different granu-larityspaces346第59 卷南京大学学报（自然科学）(3)细粒度化：对投影得到的扭曲路径进行局部调整.将从粗粒度下投影的扭曲路径W与其周围的点进行细粒度化，再一次搜索最短扭曲路径并求得最终的结果：2动态阈值的NFV故障检测方法网络功能虚拟化条件下的故障检测研究对于保持网络的正常高效运行具有重要意义.在NFV网络中，故障检测的难度主要包括：（1)上层（即虚拟功能层）对底层（即基础设施层）的服务不可见，难以直接获取上层信息来进行详细的故障诊断；（2)针对VNF的故障诊断需要有较高的时效性，但由于获取的数据维数一般较高,所以难以迅速对数据进行故障识别与处理；（3)不同的VNF类型数据特征差异大，并且，由于虚拟资源是由虚拟化基础设施管理器（VirtualizedInfra-structureManager，VIM)自动进行部署与释放的，所以在不同时段数据波动幅度剧烈，难以准确判断是否发生故障。在虚拟化功能网络中，由NFV管理系统(Management and Orchestration,MANO)对虚拟环境中的虚拟机和虚拟网络功能按一定程序非人为地进行管理和编排.本文利用从网络虚拟化功能基础设施(NFVInfrastructure,NFVI)层获取的数据对VNF的健康状况进行推断，由于NFVI层面的虚拟机CPU使用率、内存利用率等数据具有高度动态性的特点，网络管理员难以快速获取所有VNF的特征进行分析研判，所以需要系统地对输人数据进行自动处理分析并输出结果，基于NFV的上述特点，本文将扭曲路径距离引人NFV网络的故障识别过程来表示NFV网络中两个时间序列之间的差异程度.扭曲路径距离越小，两个时间序列的相似度就越高；距离越大，相似性就越低.定义离线训练集中两个正常时间序列的差异为标准扭曲路径距离，在线输入的未知时间序列与正常时间序列之间的差异为待测扭曲路径距离.标准扭曲路径距离通常分布在一定范围内，所以,如果后者远大于前者，说明未知时间序列存在故障，否则，说明未知时间序列处于正常状态.图3为本文提出的NFV故障检测流程.I0操作内存数据CPU数据数据离线训练数据在线输入数据正常行为观察序列未知行为观察序列离线训练在线检测计扭曲距肉主成分分析特征标准化得出动态闽值设定VNF阀值故障检测检测结果图3NFV故障检测流程Fig.3Fault detectioninNFVnetworks2.1基于fastDTW的序列相似度计算传统DTW算法具有O(n)的复杂度,因此在大型数据集上运行非常耗时 16 .而fastDTW算法在O（n)的复杂度下表现良好 17 ,所以本文使用fastDTW对NFV中的故障进行识别.利用优化后的DTW在固定大小的窗口内找到两个时间序列之间的最佳对齐方式，并测量它们的扭曲路径距离，获得两个正常活动的长时间序列的相似度数据集，再根据数据集使用统计学方法为正常活动定义可接受的阈值，进行VNF的在线故障检测.计算多元时间序列的扭曲路径距离的具体步骤如下算法1多多元时间序列的快速扭曲路径距离计算输入：多元时间序列X，Y，向外扩展的粒度数量r输出：两序列的扭曲路径距离dist1.if len(X)time_win orlen(Y)THR)=0.2515.anomalyList.append(K,)16.end if17.end for18.return anomalyList首先，对所有数据进行标准化处理，将输人的测试集数据转换为时间序列模型，再对长序列进行划分，设置合适的滑动窗口的大小，计算任意两个已知正常序列之间的相似性（第2 6 行）.在NFV正常活动期间，两个正常序列之间的距离在一定的范围内若出现连续的异常值，说明NFV中的网络功能存在故障，以测试集中正常序列之间的扭曲距离的平均值作为参考值，计算不同VNF的绝对中位差作为故障检测的阈值THR(第7 行和第8 行）.在故障检测阶段，对实时输人的未知序列标准化后进行故障检测，将其分割为短序列并计算其与已知正常序列之间的距离，判断其是348第59 卷南京大学学报（自然科学）正常情况下bono异常情况下bono以15min为周期的系统平均负载以15min为周期的系统平均负载40%40%20%20%0000.511.5200.511.52时间(s)时间(s)104104正常情况下bono异常情况下bono系统层面CPU的使用时间系统层面CPU的使用时间100%100%50%50%0000.511.5200.511.52时间(s)X104时间(s)104正常情况下sprout异常情况下sprout以15min为周期的系统平均负载以15min为周期的系统平均负载40%40%20%20%0000.511.5200.511.52时间(s)104时间（s)104正常情况下sprout异常情况下sprout系统层面CPU的使用时间系统层面CPU的使用时间100%100%50%50%0000.511.5200.511.52时间(s)104时间(s)104图4两个VNF的正常-异常情况对比Fig.4Normal-anomaly cases of two VNFs否满足条件，若满足，将此序列压栈到故障列表anomalyList，并提交报告给MANO（第12 17行）；若不满足，则进行下个序列的故障识别.3实验及结果分析为了验证基于动态阈值的故障检测方法的有效性，使用基于云的虚拟NFV应用程序用例clearwater.clearwater是一个虚拟化的IP多媒体子系统（vIMS），由bono(SIP边缘代理组件）、ellis（提供用户配置API）、h o me r(XM L 文档管理服务器）、homestead（家庭订阅服务器）、ralf（离线计费）、sprout(SIP注册器和消息路由器）等虚拟化功能组成，并将其部署在openstackVIM上，通过监控系统Monasca以30 s的采样频率收集数据.Monasca是基于python的开源监控服务，收集单个VNF的指标，如CPU使用率、磁盘空间使用率、可用内存百分比、网络平均负载等取其中两个主要VNF和三个次要VNF进行故障检测，对每个VNF的2 6 个维度的17 7 0 0 0 条真实数据进行了仿真实验，测试基于fastDTW的NFV故障诊断算法（DTF-DTW）的准确性和运行时间.为了消除数据集中量纲的影响，提升模型的收敛度与精度，使用标准化后的数据集进行故障检测，具体计算如下：X-XminX(6)Xmax-Xmin其中,X为标准化后的数据，X为原始输人样本数据中的列向量，Xmin为X中的最小值，Xmax为X中的最大值。在实际故障诊断中，不仅需要关注算法中故障的高检出率，“虚假故障”的低出现率也同样重349齐小刚等：基于动态时间扭曲的NFV网络故障检测第2 期要，这直接关系MANO对虚拟网络功能组件的生命周期管理过程，如果虚假故障出现的数量较多，故障识别的准确性降低，可能会导致网络延迟的发生，最终影响虚拟化功能网络的可靠性.本文引入故障检测正确率r。与假阳性率r来评估算法性能 18 ,定义如下：HnF(7)IFIHnF(8)IFI其中,H为进行故障诊断的时间序列,F为真实故障序列,F为虚假故障序列.STAD异常检测机制算法 14 使用由两部分组成的混合深度学习框架检测网络中的异常值，使用时间序列检测网络时间与空间上发生的异常情况，并使用真实的数据集评估算法有效性，与隔离森林、ARIMA等机器学习算法相比，具有较高的准确性与适应性表1是两种算法采用相同时间序列进行故障检测的准确率对比结果，通过比较本文DTF-DTW算法与STAD异常检测机制算法的正确率和假阳性率，可以看出,两个算法的故障诊断正确率相差不多，但STAD的假阳性率明显较高.这是由于STAD算法将实际正常的序列错误识别为VNF出现故障的序列,产生了过多的虚假故障，导致系统存在大量?余数据，降低了故障诊断效率.DTF-DTW算法兼具正确率高与假阳性率低的优点，可以在保证一定准确率的条件下，根据输入数据集进行故障诊断，充分证明了该算法的可靠性由于VNF的故障检测具有较强的时效性,耗时过长会影响NFV对后续功能的管理，继而影响网络的服务质量.图5是两个算法实际运行时间表1DTF-DTW和STAD算法的准确率对比Table 1 Accuracy of DTF-DTW and STAD algorithms正确率r。假阳性率DTF-DTWSTADDTF-DTWSTADbono98.51%92.77%14.16%16.85%sprout87.32%91.94%0416.73%ellis100%86.68%15.97%145.26%ralf96.20%100%15.80%98.32%homestead78.62%73.99%5.42%355.25%bono练用sproutekistahomestead20406080100120140160用时（s)(a)DTF-DTW算法用时bonosprout谢达用elisrafhomeslead020406080100120140用时（）160(b)STAD算法用时图5DTF-DTW和STAD算法的运行时间对比Fig.5Running time of DTF-DTW and STAD algo-rithms的对比结果，由图可见，STAD算法对样本集训练的时间过长，测试速度和DTF-DTW算法相比也有所降低，且对不同的VNF的故障检测用时具有较大波动.而本文所提出的算法可以稳定在较短的时间内对故障进行训练并发出警告：4结论本文提出一种基于动态阈值的NFV网络故障诊断方法，采用改进的动态时间扭曲方法fast-DTW衡量两个时间序列之间的差异程度，和DTW方法相比，运算效率有一定的提高.针对NFV网络中虚拟功能层对基础设施层服务不可见的特点，先对时间序列数据进行标准化，然后根据不同的VNF特点动态设定网络发生故障的阈值，并使用基于滑动窗口的fastDTW方法进行故障检测.最后，在以基于云的虚拟NFV应用程序用例clearwater上进行了仿真实验.仿真结果表明，本文提出的DTF-DTW算法能在保证一定故障诊断准确率的情况下，缩短故障诊断用时，提高NFV网络的故障诊断效率.现实中，由于设备损坏，NFV网络可能无法获得完整的故障检测信息，或由于网络传输速率不同，可能出现不一致故障检测信息的情况，未来将考虑处理如故障检测信息丢失和不一致症状等问题，以提高故障诊断算法的准确性。参考文献1Li X,Samaka M,Chan H A,et al.Network slicingfor 5G:Challenges and opportunities.IEEE InternetComputing,2017,21(5):20-27.2Shafi M,Molisch A F,Smith P J,et al.5G:Atutorial overview of standards,trials,challenges,杨可盛（责任编辑350第59 卷南京大学学报（自然科学）deployment,and practice.IEEE Journal on SelectedAreas in Communications,2017,35(6):1201-1221.3Sezer S,Scott-Hayward S,Chouhan P K,et al.Arewe ready for SDN?Implementation challenges forsoftware-defined networks.IEEE CommunicationsMagazine,2013,51(7):36-43.4Armbrust M,Fox A,Griffith R,et al.A view ofcloud computing.Communications of the ACM,2010,53(4):5058.5Herrera J G,Botero J F.Resource allocation inNFV:A comprehensive survey.IEEE Transactionson Network and Service Management,2016,13(3):518-532.6Hawilo H,Shami A,Mirahmadi M,et al.NFV:State of the art,challenges,and implementation innext generation mobile networks(vEPC).IEEENetwork,2014,28(6):1826.7Cheng Y X,Yao H J,Wang Y,et al.ProtectingVNF services with smart online behavior anomalydetection method.Future Generation ComputerSystems,2019(95):265-276.8Wang W L,Chen Q B,Liu T,et al.Digital-Twinassisted root cause analysis of anomalies in NFVenvironment/IEEE International Conference onCommunications.Montreal,QC,Canada:IEEE,2021:14-23.9Hou B N,Hou C S,Zhou T Q,et al.Detection andcharacterization of network anomalies in large-scaleRTT time series.IEEE Transactions on Networkand Service Management,2021,18(1):793-806.1o Chen J,Chen M,Wei X L,et al.Matrix differentialdecomposition-based anomaly detection andlocalization in NFV networks.IEEE Access,2019(7):2932029331.11 Cherrared S,Imadali S,Fabre E,et al.SFC self-modeling and active diagnosis.IEEE Transactions onNetwork and Service Management,2021,18(3):2515-2530.12 Schmidt F,Suri-Payer F,Gulenko A,et al.Unsupervised anomaly event detection for VNFservicemonitoringusingmultivariateeonlineARIMA/2018 IEEE International Conference onCloud Computing Technology and Science.Nicosia,Cyprus:IEEE,2018:278-283.13 Liu C H,Hoi S C H,Zhao P L,et al.OnlineARIMA algorithms for time series prediction/The3oth AAAI Conference on Artificial Intelligence.Phoenix,AZ,USA:ACM,2016:1867-1873.14 Dridi A,Boucetta C,Hammami S E,et al.STAD:Spatio-temporal anomaly detection mechanism formobile network management.IEEE Transactions onNetwork and Service Management,2021,18(1):894906.15 Itakura F.Minimum prediction residual principleapplied to speech recognition.IEEE Transactions onAcoustics,Speech,and Signal Processing,1975,23(1):6772.16 姬文江，左元，黑新宏，等。基于FastDTW的道岔故障智能诊断方法.模式识别与人工智能，2 0 2 0,33(11):1013-1022.(Ji W J,Zuo Y,Hei X H,et al.Anintelligent fault diagnosis method based on FastDTWfor railway turnout.Pattern Recognition and ArtificialIntelligence,2020,33(11):1013-1022.)17 Salvador S,Chan P.FastDTW:Toward accuratedynamic time warping in linear time and space.Intelligent Data Analysis,2007,11(5):7080.18 Su Y Z,Meng X R,Han X Y,et al.Symptom-awarehybrid fault diagnosis algorithm in the networkvirtualizationenvironment.TurkishJournalofElectrical EngineeringandComputer Sciences,2019,27(5):33263341.