论文部分内容阅读
近年来,随着互联网的飞速发展,网络规模在扩大,复杂性在增长,网络测量的要求越来越高。数据流量测量是网络测量非常重要的一个方面,它主要指测量通信网络中源节点-目的节点(Origin-Destination,OD)对之间的流量。获得准确的数据流量对于网络设计和管理是非常重要的,网络拓扑结构的设计、链路容量的规划和预测以及路由协议的实现等都需要用到OD对之间的流量数据。自Vardi在1996年提出网络断层扫描(Network Tomography,NT)这一概念,网络的流量矩阵测量问题在国际上已经受到越来越多的人们的关注。在目前的技术水平下,要想直接从局域网中测量流量矩阵是很困难的,因为这样的直接测量技术要求在每个路由器上安装专用的数据收集软件和硬件。目前直接测量流量矩阵的方法,像思科公司设计的的Netflow软件仍存在许多问题,一是因为它们昂贵的成本不可能在整个互联网范围内安装,二是它们运行的时候会占用大量的CPU运行时间带来巨大的额外开销。因而,直接测量流量矩阵是不现实的,更多的是通过从网络中已经获得的数据进行流量矩阵的估计。流量矩阵、路由矩阵以及链路流量的关系可以用线性方程Y=AX来表示,其中,链路流量向量Y,可以通过SNMP协议得到,路由矩阵A可以从网络拓扑结构和所使用的路由算法推算出。因而现在普遍将流量矩阵测量问题转化为从Y和A得出OD对之间的数据流量X值的数学统计推断问题。由于在TCP/IP网络中,OD对的个数远远大于链路数,因此A为奇异矩阵,导致方程Y=AX有无数组解,所以问题的难点在于方程的欠定性。本文正是考虑到流量矩阵测量问题的欠定性,在TCP/IP网络具有自相似的特性基础上,建立欧几里德优化模型,找到与某一给定初始流量矩阵欧几里德距离最为接近的解作为流量矩阵的推断值。由于初始流量矩阵的选取对于问题的解决至关重要,而现有的初始流量矩阵产生方法并不是十分有效,因此我们在高斯分布的基础上提出了一种新的初始流量矩阵产生方法。紧接着我们在欧几里德优化模型的基础上,提出了两种推断流量矩阵的新方法。一种通过计算路由矩阵的广义逆来解决欧几里德优化问题,我们称之为{1}-INVERSE方法;另外一种简称为MPLM的方法主要是借助矩阵变换和拉格朗日最优化方法,将要求得的流量矩阵用链路流量和路由矩阵等已知数据推断出来。通过理论分析和实验结果我们可以看出,我们提出的{1}-INVERSE和MPLM方法比其它的相关算法的性能要好,它们得出的流量矩阵推断结果与网络实际值更加接近。