摘 要:研究大尺度IP骨干网络流量矩阵估计,通过使用广义回归神经网络来捕捉流量矩阵特征,将流量矩阵估计描述成马氏距离下的最优化过程,能成功克服流量矩阵估计的病态特性,获得精确的估计值。仿真结果表明,该估计算法具有更高的估计精度和显著的性能改善。
0 引言
流量矩阵是网络流量工程的重要输入参数,它表示网络中所有OD(origin-destination)节点对之间流动的流量,给网络操作员提供关于当前网络状态的有价值和全局的信息。由于网络设备缺乏主动配合,网络服务提供商( ISP)处于商业秘密考虑,以及网络测量将占用额外的网络资源等原因,直接测量流量矩阵是非常困难的。流量矩阵常常使用间接测量,采用估计的方式来获得。流量矩阵估计目前引起研究人员的广泛关注[1~6]。流量矩阵估计已被网络操作员用来进行网络规划、负载均衡、故障诊断、路由最优化等网络管理活动。
如何有效地克服这一问题的病态特性是当前面临的主要困难。文献[7]使用Bayesian统计反演技术来克服局域网上流量矩阵估计的病态特性,将OD流建模为独立同分布的Pois-son模型;文献[8]修改这一方法,将OD流建模为独立同分布的正态模型,并修改传统的EM算法来预测局域网上的流量矩阵;文献[1]研究了IP骨干网络流量矩阵,提出流量矩阵具有时间空间分布,分析OD流的均方幂律关系;文献[2]指出了流量矩阵直接测量非常困难的原因,提出分布式的流量矩阵测量方法;文献[3, 4]研究了大尺度IP骨干网络流量矩阵,通过重力模型来捕获流量矩阵的特征,提出了基于重力模型的流量矩阵反演方法;文献[5]使用{1}-Inverse方法来估计流量矩阵;文献[9]综述了流量矩阵最新研究进展。然而文献[6, 9, 10]分析认为,文献[7, 8]中的方法对流量矩阵的先验信息非常敏感,文献[3, 4]中提出的方法尽管降低了对先验信息的敏感性,但是估计结果仍具有较大的误差,特别是当对模型的假设不成立时,估计误差更大。由于流量矩阵估计的高度病态特性,要获得精确的流量矩阵估计非常困难。
本文研究了大尺度IP骨干网络流量矩阵的估计问题,并提出一种新的算法来估计流量矩阵,称为广义回归神经网络递归反演( generalized regression neural network recurrence infe- rence,GRNNRI)。网络流量是一种时变非平稳流量,它具有时间、空间、时空的相关性[1, 6]。能否准确捕获网络流量的这些特征很大程度上决定着流量矩阵估计的精度。广义回归神经网络(generalized regression neural network,GRNN)是一种强大的建模工具,它被广泛用于信号处理、系统建模、时变环境等[11, 12]。GRNN收敛于基本的回归面,能用于任何回归问题的处理。流量矩阵时间相关性就是其回归性的体现,GRNN能准确捕获流量矩阵这一特征。而GRNN的空间并行结构,以及本文使用的多输入多输出模型,将能精确捕捉流量矩阵的空间相关性。通过用输入/输出数据对训练GRNN,能准确建立关于流量矩阵的估计模型。由于流量矩阵估计的病态特性,通过GRNN所获得的估计值常常并不是所需要的。为了进一步克服流量矩阵估计的病态特性,基于建立的估计模型,流量矩阵估计被描述为约束条件下的最优化过程。流量矩阵各个分量是不同的,为了获得需要的流量矩阵,其样本信息对于流量矩阵的精确估计也非常重要。然而传统的度量最优化的欧氏距离尺度不能区分流量矩阵各个分量之间的差别,而且也不能利用已有的样本数据。马氏距离度量尺度则具有明显的优势,它能区分流量矩阵各个分量之间的差别,能充分利用已有的样本信息,并且它与测量单位无关。因此,将流量矩阵估计转变成马氏距离下的寻优过程,能成功地克服这一问题的病态特性。最后使用Abilene网络上的真实数据[13]来验证GRNNRI,仿真结果表明GRNNRI能获得更精确的估计。
1 基于GRNN的估计模型
流量矩阵表示网络中所有OD节点对间的流量,直接测量它非常困难。在大尺度IP骨干网络中,链路负载是流量矩阵根据路由矩阵在链路上汇聚而成,它们之间具有某种线性约束关系。假设大尺度IP网络有p个节点、Q条链路,则网络中有
图1表示了用于流量矩阵估计的GRNN结构,它包括四层,即输入层、模式层、汇聚层和输出层。
流量矩阵x(t)和链路负载y(t)不能直接用于图1所示GRNN网络的训练,这需要进行数据变换处理,以适合GRNN网络对输入/输出数据的要求,否则训练结果所建立的模型将不能准确反映流量矩阵特征。数据变换处理可以用如下等式表示:
2 流量矩阵递归反演
由于流量矩阵估计的病态特性,以及网络流量的时变非平稳特征,要精确得到所需要的估计值是困难的。下面讨论通过将马氏距离作为最优化尺度,把流量矩阵估计描述为马氏距离下的具有约束条件的寻优过程,从而进一步克服流量矩阵估计的病态特性,以获得精确的流量矩阵估计。
2·1 马氏距离
从式(9)(10)可以看到,通过样本协方差矩阵,马氏距离能准确捕获流量矩阵、链路负载的时间空间相关性,并能区分各个分变量之间的差别。因此,马氏距离作为最优化尺度用于流量矩阵估计,将有助于进一步降低此问题的病态特性。
2·2 递归反演
在大尺度IP骨干网络中,各个节点和链路主要用于数据传输,其本身几乎并不消耗网络资源,即使节点之间有管理数据传输,相对整个网络数据传输而言,那也是可以忽略不计的。因此,进入网络和流出网络的流量可以认为满足网络流量总量守恒条件[3]。另外,对于实际可行网络,其每条OD流也满足非负和式(1)这两个约束条件。因而对于大尺度IP骨干网络,流量矩阵满足如下约束条件: a)进出网络流量守恒:E×Ainx(t)=E×Aoutx(t)。其中:Ain、Aout分别对应流量进入和离开网络的路由子矩阵;E为系数加权矩阵; b)线性约束:y(t)=Ax(t)。c)OD流非负:xi(t)≥0(i=1,2,…,P)。将马氏距离作为最优尺度,则根据上述约束条件,可得到如下最优化目标函数:
2·3 反演算法
上面给出了整个GRNNRI算法的推理过程,下面给出这一算法的完整步骤:
a)初始化图1所示估计模型;
b)根据式(3)(4)对流量矩阵和链路负载进行数据变换处理,得到序列u(t)=f(y(t))和v(t)=g-1(x(t));
c)用u(t)、v(t)作为输入/输出数据对训练图1所示模型,得到网络权值矩阵,并构建式(6)表示的流量矩阵估计模型;
d)根据式(6)获得流量矩阵估计初始值x^g(t)
e)根据式(7)(8)分别计算链路负载和流量矩阵的协方差矩阵Cy和Cx;
f)给出误差上限δ、最大迭代步数Γ,并令w=0;
g)根据式(16),计算流量矩阵估计值xw+1(t);
h)计算估计误差ε=‖y(t)-Axw+1(t)‖2;
i)如果ε<δ或w>Γ,则获得流量矩阵的最终估计值x^ (t)并退出;否则,令w=w+1,返回到g)。
3 仿真性能分析
仿真实验使用来自Abilene骨干网络上的真实数据来验证GRNNRI算法。图2表示了用于仿真的美国Abilene骨干网络拓扑结构。其中,圆圈中数字表示路由器编号,箭头旁边数字表示网络内部链路序号。文献[3, 4]的TomoGravity方法和文献[5]的{1}-Inverse方法被报道为目前流量矩阵估计的精确方法。本文将GRNNRI与这两种方法进行比较,分析三种方法的空间相对误差(spatial relative errors, SREs)和时间相对误差(temporal relative errors,TREs)。Abilene网络上连续6周的数据被用来仿真三种方法。其中前三周的数据用于图1所示模型的训练,其余三周数据用于三种方法的性能分析。
为进一步准确评价三种方法的估计精度,采用流量矩阵估计的SREs和TREs的CDFs(cumulative distribution functions)来进行衡量。图5(a)和(b)分别画出了三种方法流量矩阵估计的SREs和TREs的CDFs。从图5(a)可看到,GRNNRI的SREs的CDF曲线在TomoGravity和{1}-Inverse的上方,而TomoGravity和{1}-Inverse的曲线几乎是重叠的。更重要的是,GRNNRI能以0. 95的SREs估计93. 7%以上的OD流,而对于同样的SREs,TomoGravity和{1}-Inverse分别仅能估计84.2%和83.9%的OD流。这表明GRNNRI的SREs要比TomoGravity和{1}-Inverse的低,而TomoGravity和{1}-Inverse的非常接近。
图5(b)显示TomoGravity和{1}-Inverse的TREs的CDF曲线远远低于GRNNRI的相应曲线,但是{1}-Inverse的曲线在TomoGravity的下方。而且相对0. 25的TREs,GRNNRI能精确估计95%以上的测量时刻,而TomoGravity和{1}-Inverse却仅为63. 5%和57. 1%。这说明GRNNRI的TREs也要比To-moGravity和{1}-Inverse的低,但是TomoGravity的TREs要低于{1}-Inverse的。从上面的分析可见, GRNNRI的SREs和TREs都要比TomoGravity和{1}-Inverse的低,因此,相比之下,GRNNRI能更精确地估计大尺度IP流量矩阵。
图6显示了GRNNRI相对于TomoGravity和{1}-Inverse的平均性能改善。图6表明,相对于TomoGravity和{1}-Inverse,GRNNRI的平均性能改善分别达到29. 8%和32. 0%。因此, GRNNRI的估计性能要明显优于TomoGravity和{1}-Inverse。
4 结束语
流量矩阵估计是当前的热点研究问题,它的病态特性使得精确估计流量矩阵非常困难。本文研究了在大尺度IP骨干网络中的流量矩阵估计问题,并提出了一种基于广义回归神经网络的流量矩阵估计算法。通过使用广义回归神经网络的强大建模功能来捕捉流量矩阵特征,本文将流量矩阵估计描述成马氏距离下的迭代寻优过程,从而在迭代过程逐步克服流量矩阵估计的病态特性,并获得精确的估计值。仿真结果表明,与以前的方法相比,本文所提出的估计算法不仅能精确估计较小和较大的OD流,而且具有更低的估计误差和显著的性能提高。
参考文献:
[1] GUNNAR A, JOHANSSONM, TELKAMP T. Trafficmatrix estima-tion on a large IP backbone: a comparison on real data[C] //Proc ofIMC’04. 2004: 149-160.
[2] PAPAGIANNAKIK,TAFTN, LAKHINA A. A distributed approachtomeasure IP trafficmatrices[C] //Proc of IMC’04. 2004: 161-174.
[3] ZHANG Y, ROUGHANM, DUFFIELD N,et al.Fast accurate com-putation of large-scale IP traffic matrices from link loads[ J].ACMS IGMETR ICS Performance Evaluation Review,2003,31(3):206-217.
[4] ZHANG Yin,ROUGHAN M, LUND C,et al.Estmi ating point-to-pointand point-to-multipoint trafficmatrices: an information-theoretic approach[J].IEEE /ACM Trans on Networking,2005,13(5):947-960.
[5] TAN Lian-sheng,WANG Xiang-jun. A novelmethod to estimate IPtrafficmatrix[J].IEEE Comm uNIcations Letters,2007,11(11):907-909.
[6] SOULE A, LAKHINA A, TAFTN,et al.Trafficmatrices: balancingmeasurements, inference and modeling[ J].ACM S IGMETR ICSPerformance Evaluation Review,2005,33(1): 362-373.
[7] TEBALDI C, WESTM. Bayesian inference on network traffic usinglink count data [J].Journal of American S tatistics Association,1998,93(442): 557-576.
[8] CAO Jin, DAVIS D,WEIL S V,et al.Time-varying network tomo-graphy: router link data [J].JournalofAmerican S tatistics Asso-ciation,2000,95(452): 1063-1075.
[9]蒋定德,胡光岷.流量矩阵估计研究综述[J].计算机科学, 2008,35(4): 5-9.
[10] JUVA I. Sensitivity of trafficmatrix estimation techniques to theirun-derlying assumptions [C] //Proc of ICC’07. 2007: 562-568.
[11] GOULEMAS JY, ZENG X J,LIATSIS P,etal.Generalized regressionneural networkswithmultiple-bandwidth sharing and hybrid optimiza-tion[J].IEEE Trans on System s, Man and Cybernetics,2007,37(6): 1434-1445.
[12] GOULERMAS JY, LIATSIS P, ZENG Xiao-jun,et al. Density-drivengeneralized regression neural networks (DD-GRNN) for function ap-proximation [J].IEEE Trans on NeuralNetworks,2007,18(6):1683-1696.
[13] [EB/OL]. http: //www. cs. utexas. edu/~yzhang/research/Abilene-TM /H.
