黄 畅,刘晏嘉,罗晟庭
(北京交通大学,北京 100044)
随着网络应用服务不断更新迭代和网络用户流量规模剧烈增长,传统网络管控手段已经难以应对现有网络“高速率、大规模、多接入、不可预期”等特点带来的管控挑战。此研究相对于传统网络监测及故障排除方法更加具有创造性和革新性,能够应对网络状态测量、网络故障检测、故障精准定位与及时恢复网络性能等场景的网络管控,此解决方案对于网络管理者而言已是迫在眉睫。与传统网络测量方案不同,带内测量将数据包转发和网络测量相结合,通过路径中间交换节点对数据包依次插入元数据的方式完成网络状态采集。相较于传统网络测量方案,带内测量能够对网络拓扑、网络性能和网络流量实现端到端测量。
带内网络遥测是网络数据平面可编程的重要应用场景,拓展了传统网络测量边界。现阶段带内网络遥测的相关研究多集中于遥测架构和应用上,处于“能测就行”的起步阶段,缺少对带内网络遥测缺失数据补全算法的研究。带内网络遥测通过用户数据包承载遥测数据,用户数据包的丢包会导致网络遥测数据缺失。带内网络遥测数据本质是时间序列数据,网络遥测数据缺失往往属于随机数据缺失,而这种丢包现象是不可避免的,每当发生丢包,势必会引起网络层面上的一些重大故障,导致测量结果的不准确,故在遥测方向的背景下缺失数据的处理,本文通过多种方法对缺失的数据进行补全并对补全效果进行研究。
首先,在对带内网络遥测过程中缺失的网络状态测量值进行处理之前,了解相关网络节点测量值缺失机制及其类别是必要的。如果在测量过程中得到的数据中不包含任何缺失值,则将其称为完全变量,若测量得到的数据中含有任一缺失数据则称其为不完全变量,Roderick J.A.Little和Donald B.Rubin 定义了如下三种数据缺失机制:
(1)完全随机缺失(Missing Completely at Random,MCAR)[1]。数据的缺失与完全变量和不完全变量都无关;随机缺失(Missing at Random,MAR)。数据的缺失仅仅与完全变量有关;非随机不可忽略缺失(Not Missing at Random,NMAR[2],or Non-ignorable)。不完全变量中数据的缺失依赖于它自身的特性,这种缺失在实际应用中不可忽略。
(2)缺失值插补针对两种类型:单一插补(single imputation)[3]以及多重插补(multiple imputation)。单一插补指使用特定方法,对因为无响应造成的缺失值仅构造一个合理替代值,并将该替代值插补到原缺失数据位置,从而构造出完整数据集。多重插补是一种基于重复模拟的处理缺失数据的方法。它从一个包含缺失数据的数据集中生成一组完整的数据集,每个数据集中的缺失数据用蒙特·卡罗法来填补。从缺失数据的所属类别上看,如果所有的缺失数据为同一类型,这种缺失称为单值缺失;如果缺失数据属于不同类型,为任意缺失。对于时间序列类的数据,可能存在随着时间的缺失,这种缺失称为单调缺失,分析可以得出,网络遥测数据的缺失是一种单值单调的随机数据缺失。
故在本文研究中,利用目前数据平面带内网络遥测主要研究之一,P4 联盟主导的带内网络遥测(In-band Network Telemetry,INT)[4]模拟现实中网络情况,将一段时间的时间序列数据导出,得到时间戳及其相应时间上所对应的网络的逐跳延迟等若干数据,然后人为进行数据的随机丢失处理,接着使用不同方法进行缺失数据的填充,比较验证各类数据补全方法在带内网络遥测领域的有效性与可靠性。
删除元组法是将缺失的数据直接删除,得到完备的信息集合,集合中数据为完整原始的测量数据,但是被删除数据所包含信息和其缺失所带来的影响不可忽视。如果样本容量足够大,这个方法是有效的,然而这种方法却有很大的局限性。它以减少部分测量数据来换取数据集合的完备性,造成测量资源以及测量时间的大量浪费,增加测量成本负担。此外,丢弃的这些包含缺失数据的对象中还隐藏着大量的测量信息,这些数据的丢弃对测量的准确性和客观性带来了影响,同时对后续的测量结果分析工作也造成了一定的困难。在样本容量不足的情况下,删除少量数据就足以严重影响到测量结果的准确性,性能非常差。因此,当缺失数据所占百分比较大,特别是当缺失数据服从随机分布时,这种方法容易导致数据发生大偏差,进而在分析测量结果的过程中可能会得出错误结论。
而在本实验过程中,我们将人为随机丢失的部分数据直接进行删除的操作,可以看出删除元组法在准确性上具有较大的局限,与原有数据存在极大的偏离,在实际带内网络遥测领域中,这种程度的误差范围是我们所不能接受的,会引起诸如增大网络开销、遥测精度降低等一系列性能问题。
这类方法是通过一些分析方法得出较为合适的数据去填充缺失数据,从而使数据集完整化。一般基于统计学原理,根据未缺失数据取值的分布情况以及数据之间内在联系对缺失数据进行合理补齐,在遥测仿真网络中所提取到的部分性能数据恢复完整数据的质量,依赖于此统计技术,而当下常用的有以下几种填充方法:
1.2.1 均值填充(Mean/Mode Completer)
为了尽可能保证涉及到所有数据,平均数考虑了每一个个体对总体的贡献,给每个测量数据赋予相同或不同的权重占比。平均数:
少量的缺失数据能够直接删除处理。除此之外,由于均值很好地保留并反映了样本或总体的集中特点,以均值作为填充数据来填补缺失位置也是一个合适的方式。在本次实验中,带内网络遥测仿真环境所导出的数据类型是一个二维数组,具体是不同时间戳下所对应遥测网络中节点的逐跳时延,由于空值是属于数值型的,故我们采用的是逐跳延迟的平均值进行填充,在此处我们还进行了一项改进,如果取的是丢失数据补集的所有元素平均值来进行填充的话,无法反映出数据在其时间戳上的特殊性,所以我们将区间尽可能缩小,从而让填充值与时间的对应关系尽可能贴近原有数据,并能够恢复出一定的变化趋势,但由于本次实验导出的逐跳延迟数据性质具有一定的随机性,在某些跳变大的区间内恢复精度会受到影响。
数学方法可以在一定程度上实现丢失遥测数据的填充,但是很大程度上忽视了数据间以及局部数据与整体数据之间的内在联系。为了实现网络性能数据模型中数据更好的交互,当下国内外已有许多学者使用张量模型对网络流量数据进行填充,充分利用了数据的多重相关性(即隐藏的时空相关性),其通常将源节点、目的节点和时间间隔的特征投影到一个空间中,利用该空间的潜在因子向量的内积表示三者间的内在联系。这一分析过程是基于三者间的联系是线性的假设,然而实际的网络遥测过程中很大部分的数据之间并不是简单的线性关系,往往存在比较复杂的非线性关系。因此,在实际情况下,不能只用简单的线性关系来理解数据间的关联,进而导致数据恢复的精度受限。因此,我们引入了深度神经网络学习。
深度神经网络学习在自然语言处理、计算机视觉、语音识别等领域上取得了巨大的成就,因此可以类比这些处理方式,将深度学习应用于遥测数据的补全上,通过大量数据的学习,找寻不同时间戳下逐跳时延值的内在规律及关系。此处,我们只采用了一种EM 算法进行实验,诸如决策树、向量机等深度学习算法也是可行的,在结果上存在细微的差别,但从整体上的还原效果大致类似。
1.2.2 期望值最大化方法(Expectation maximuzation,EM)
随着网络日益复杂化,细粒度网络监控的可靠性、灵活性等面临着前所未有的挑战。相比于传统的监控方式和处理手段,通过机器学习的方式则可以做出更优化的决策。在随机性缺失的情况下,假设该模型对于一个完整样品来说都是正确和合适的,那么我们就可以通过观察数据边沿的分布来对其中一些未知的参数做出极大似然性估计,将之称为忽略缺失值的极大似然估计,在实际应用过程中经常采取的一种计算方式是预测期望值的最大化(Expectation Maximization,EM)[5]。该方法较之于删除元组法和简单的多值插入法更符合一个整体的数据集,原因在于这种算法适用于大样本数据集,适用于本次带内网络遥测实验中。有效样本数量足够来保障其估计值是渐近无偏的且符合正态分布,然而该算法可能会陷入局部极值,收敛速度不快,计算较复杂。
EM 算法是一种在不完全数据情况下计算极大似然估计或者后验分布的迭代算法。在每一迭代循环过程中交替执行两个步骤:E 步(Expectationstep,期望步)和M步(Maximzation step,极大化步),算法在E 步和M 步之间不停交替迭代直到收敛为止,即在两次迭代中所得到的参数之差小于一个提前设定的阈值之时,迭代结束,其实施过程如下:
极大似然估计已知一个样本集符合某种概率分布,但是该分布的某些参数未知,通过寻找使得样本重复的概率最大化的参数作为未知参数的估计值,假设未知参数为X,与参数X 有关的隐含量Z。
首先随机估计一个X 值,接着进行E 步:在固定参数X 后,使下界拉升的函数Q(Z)的计算公式为条件概率,基于这个论断,就解决了Q(Z)如何抉择的问题,建立了样本集的联合概率L(X)的下界。之后,对于每一个i,依据上一次迭代的模型参数来计算出隐性变量的后验概率即隐性变量的期望,以此作为隐藏变量的估计值。然后进行M 步:在给定Q(Z)后,调整参数X,极大化L(X)的下界。
如此循环重复,不停迭代,直到收敛就可以得到使似然函数L(X)最大化的参数X 了。
数据描述:本文利用目前数据平面带内网络遥测主要研究之一,P4 联盟主导的带内网络遥测(In-band Network Telemetry,INT)模拟现实中网络情况,将一段时间的时间序列数据导出,得到时间戳及其相应时间戳所对应的网络中逐跳延迟的若干数据,然后进行数据的随机丢失处理操作。考虑到缺口处的大小可能会对实验结果产生一定的影响,所以在丢失数据操作时,对缺口数据量也进行了一定的控制,在一定数据范围内设置了五处缺口位置,根据每处缺失数据量的区间大小分为三组,第一组每处缺失1 个数据,第二组每处缺失5 个数据,第三组每处缺失10 个数据。分别采用删除元组法,均值填补法以及EM 算法进行数据补全,最后通过计算并对比误差大小来判断各类方法的特点。
通过数据补全后作图,将逐跳延迟数据丢失前以及补全后的对比展示如下。
通过对比相同缺失位置,不同缺失量之间的差别,我们可以看出,删除元组法对于数据的处理效果随着丢失数据数量的增加逐渐变差,当数据丢失较多时,这样的处理方式会导致大量数据丢失,一些关键起伏点的缺失如果用这种方法进行处理的话,会导致测量的准确度大幅下降。而通过对比相同缺失量,不同缺失位置之间的差异,我们可以得出,删除元组法对于变化趋势相对稳定,起伏不明显的缺失位置的处理效果要优于对有较大变动、变化趋势变化较明显的位置的处理效果。这种方法的优势在于操作简单、计算成本较低,但是会造成数据的缺失,对于大量数据缺失的场景处理效果并不理想(见图1-图3)。
图1 第一组删除元组方法补全效果图
图2 第二组删除元组方法补全效果图
图3 第三组删除元组方法补全效果图
由实验结果可以看出,均值补全法相对于删除元组法,其补全的数据更加贴近于原始数据的起伏变化,尽可能不丢失原始数据,对于较多数据缺失的情况也可以较好恢复。虽然其补全的数据可以更大程度地接近原始数据的变化趋势,但是有部分数据补全后与原始数据相差较大,这也使得补全数据的总体误差上升。这种方法的优势在于可以较好地还原原始数据的变化趋势,然而补全数据的准确性还有待提高(见图4-图6)。
图4 第一组均值填充方法补全效果图
图5 第二组均值填充方法补全效果图
图6 第三组均值填充方法补全效果图
EM 算法相较于删除元组法,其没有丢失大量的数据。相对于均值填充法,其补全数据更加贴近原始数据,但是对于缺失部位的数据变化没有很好地反映。EM 算法的优势在于其补全值与缺失部位周围的数据水平比较接近,而缺失位置周围的数据某种程度上也可以反映原始数据的信息,所以其补全数据的准确性更好。但是问题在于,如果缺失部位全部用一个数据填充会忽略缺失部位原始数据变化的特点(见图7-图9)。
图7 第一组EM 算法填充方法补全效果图
图8 第二组EM 算法填充方法补全效果图
图9 第三组EM 算法填充方法补全效果图
使用图像进行对比判断分析是一种直接但较为定性的方法,所以我们还引入了三个性能指标从而细致地分析实验结果,分别是:误差率(Error Ratio,ER)、平均绝对误差(Mean Absolute Error,MAE)、均方根误差(Root Mean Square Error,RMSE)。
其中Xij和Xˆij分别表示导出数据的原始值和丢失后的补全值,Ω 表示丢失数据的索引集合。性能指标的计算公式如表1。
表1 性能指标的计算公式
由于删除元组法不满足性能指标的计算要求,故只能从图像上进行定性的分析。
以下是均值补全和EM 算法补全的性能指标对比(图10-图12)。
图10 均值补全和EM 算法补全的性能指标对比
图11 均值补全和EM 算法补全的性能指标对比
图12 均值补全和EM 算法补全的性能指标对比
通过三个性能指标对不同补全方法的定量分析可以得出与之前对数据补全前后图像的定性分析相似的结果,EM 算法填充所得到的补全数据相对于均值填充准确性更高,误差更小。
通过对三种方法定性、定量的分析,我们可以直观地得出他们的优缺点。显然,单独运用一种方法并不能达到我们预期的数据补全效果,因此,我们可以将三种数据处理方式结合,面对不同类型的缺失数据采取与之对应的处理方法。
在带内网络遥测领域中,随着数据丢失缺口的增大,补全难度也随之大幅增大,效果降低;在采用的四种方法中,删除元组法较为局限,只适用于缺失数据占比小且缺失部位数据变化趋势较平缓的情况,而均值填充和EM算法在图像对比中可以看出,两者补全效果均较为理想,相对而言均值填充能够更好地反映图像的变化特性,而EM 算法填充数据更加准确。从三个性能指标中不难分辨,EM 算法无论是误差率,平均绝对误差还是均方根误差都明显小于均值填充法,证明其补全稳定性及准确性在本次实验中优于均值填充法。
基于以上实验结果和理论分析,我们可以得出以下结论。在数据缺失数量较少的情况下,如果成本为主要考虑因素的话,可以采用删除元组法,直接删除丢失数据以换取较完备的数据集;如果准确性为主要考虑因素的话,可以采用EM 算法进行填充。当缺失数据占比大,数据波动不明显时,可以采用EM 算法或者均值填充进行补全。而当数据波动显著时,可以结合EM 算法和均值填充法进行补全,先通过EM 算法确定缺失部位的数据水平,然后根据此数据水平对均值填充得到的数据集进行调整,以达到既能很好地反映数据变化缺失,又能准确还原数据的目的。