大尺度IP流量矩阵估计关键技术研究

论文摘要

随着IP网络规模指数式增长而带来的对网络管理和维护的迫切需求，流量矩阵估计已成为当前的热点研究问题。IP网络的快速发展，迫使网络操作员需要知道网络中不同节点间数据包的转发情况，以便更好地进行负载均衡、流量检测、路由最优化、网络维护、网络设计和网络规划等网络活动。流量矩阵作为网络活动的重要输入参数，已受到国内外研究人员的广泛关注，现已成为IP网络的重要研究内容。流量矩阵表示网络中源目的（Original-Destination，OD）节点之间流动的网络流量（即OD流大小），流量矩阵的维数等于网络中所有OD流的数目，它从全局的观点来描述整个网络的数据流动情况，是网络操作员决策的重要依据。然而，尽管流量矩阵很重要，但是要通过直接测量的方式来获得流量矩阵非常困难，有时甚至是不可能的。而流量矩阵估计采用间接测量的方式来获得流量矩阵，可避免直接测量流量矩阵所遇到的困难。正是由于这一优点，本文研究大尺度IP骨干网络中的流量矩阵（即大尺度IP流量矩阵）估计问题，主要集中在以下几个方面：大尺度IP流量矩阵的最优化估计、基于Fratar模型的大尺度IP流量矩阵估计、基于回归模型的大尺度IP流量矩阵估计、基于递归神经网络的大尺度IP流量矩阵估计和基于前馈神经网络的大尺度IP流量矩阵估计等关键技术的研究。网络流量根据路由矩阵在网络上流动，并在网络各条链路上汇聚而形成链路负载，因此流量矩阵、路由矩阵和链路负载间具有确定的约束关系。然而，在IP网络中，特别是大尺度IP骨干网络中，OD流的数目远远大于IP网络中的链路数，这导致流量矩阵估计问题具有高度病态特性，如何克服这一问题的病态特性是当前流量矩阵估计面对的主要挑战。针对大尺度IP流量矩阵估计问题的高度病态特性，第二章基于数值最优化理论，探索寻找解决大尺度IP流量矩阵估计过程中解的不稳定性和不唯一性问题的思路，主要包括两方面的工作：（1）基于单纯形方法来估计流量矩阵。通过将流量矩阵估计问题描述为约束条件下的线性规划，然后结合分辨率矩阵和单纯形方法来解决该线性规划，从而获得满足要求的流量矩阵估计值。（2）基于模拟退火方法来求解流量矩阵估计问题。通过将流量矩阵估计问题描述为模拟退火过程，随着温度的不断降低，估计值逐步逼近真实值，从而克服该问题的病态特性，然后利用欧氏距离（Euclid distance）和马氏距离（Mahalanobisdistance）作为最优化尺度来进一步克服该问题的病态特性，并通过迭代反演来获得时变网络条件下的流量矩阵最优化估计值。以前的文献大多基于统计模型来研究流量矩阵估计问题，但是当前的研究表明流量矩阵具有空间的和时间的相关性，统计模型很难捕获流量矩阵的这些特征。第三章基于Fratar模型来估计大尺度IP流量矩阵，主要包括两方面的工作：（1）利用Fratar模型来建模大尺度IP骨干网络中的OD流。通过Fratar模型，能准确捕获流量矩阵的空间时间相关性，从而能获得精确的流量矩阵初始值，然后通过迭代过程来获得流量矩阵的估计值。（2）由于（1）的迭代过程计算复杂，因而需要时间长。基于Fratar模型，本文利用代数重构技术（Algebraic Reconstruction Technique，ART）来估计流量矩阵。ART是图像重构的重要技术，它基于投影和迭代来完成求解过程，需要的计算简单，计算时间短，因此ART能快速获得流量矩阵的估计结果。随着对网络流量的深入研究，研究人员发现网络流量不仅具有空间时间相关性，而且具有重尾分布（Heavy-tailed distributions）、自相似（Self-similarity）、短相关（Short-Range Dependence，SRD）和长相关（Long-Range Dependence，LRD）特性，传统的网络流量模型不能准确地捕获这些特征。第四章基于回归模型来估计大尺度IP流量矩阵，主要包括两方面的研究：（1）为了描述网络流量的时间相关性，将OD流建模为自回归滑动平均（Autoregressive Moving Average，ARMA）模型，并利用马氏距离的优点，将流量矩阵估计问题描述为马氏距离下的最优化过程，通过迭代寻优来获得流量矩阵的精确估计。（2）网络流量的自相关函数表示网络流量是非平稳的，它是一种时变非平稳流量。在时变非平稳情况下，本文用广义自回归条件异方差（Generalized Autoregressive Conditional Heteroscedasticity，GARCH）模型来建模OD流。不同于传统的模型，GARCH模型认为网络流量的方差不再是常量，而是随时间的变化而变化。通过GARCH模型，本文能很好地描述网络流量的重尾分布、自相似和LRD特性，从而能精确估计流量矩阵。尽管流量矩阵的建模方法很多，但是由于流量矩阵的时变非平稳特性、空间时间相关性、重尾分布、自相似、SRD和LRD等特征，要建立精确描述流量矩阵的模型非常困难。递归神经网络具有自学习和归纳的能力，能进行线性和非线性建模，具有强大的建模功能。第五章基于递归神经网络的强大建模功能来估计大尺度IP流量矩阵，主要包括两方面的工作：（1）基于回归多层感知器（RecurrentMultiplayer Perceptron，RMLP）网络来建立流量矩阵估计模型。通过对大尺度IP骨干网络中的每一条OD流用RMLP来建模，然后构建一个多输入多输出的流量矩阵估计模型，获得在满足线性约束条件下的流量矩阵估计值。（2）研究在Elman神经网络下的大尺度IP流量矩阵估计。不同于RMLP，Elman神经网络被用来对所有OD流同时建模。本文通过修改传统的Elman神经网络来更准确地捕获流量矩阵的空间时间相关性，从而获得流量矩阵的精确估计。与传统的建模方法相比，递归神经网络避免了复杂的数学计算，很好地解决了流量矩阵估计的建模问题，但是递归神经网络具有反馈连接结构，因此计算开销大，训练时间长。第六章讨论利用前馈神经网络来估计大尺度IP流量矩阵，主要包括三方面的工作：（1）在BP（Backpropagation）神经网络下，本文将流量矩阵估计问题建模为一个多输入多输出估计模型。通过输入输出数据对训练BP神经网络，就可快速建立该估计模型，然后通过寻找约束条件下的最优解来快速获得流量矩阵的估计值。（2）基于广义回归神经网络（Generalized Regression NeuralNetwork，GRNN）收敛于基本的回归面和能用于处理任何回归问题的特性，本文利用GRNN来研究大尺度IP流量矩阵估计问题。（3） RBF（Radial Basis Function）神经网络是另一种新的建模工具，它在逼近能力、分类能力和学习速度等方面，均优于BP神经网络。本文利用RBF神经网络来讨论大尺度IP流量矩阵的估计问题，通过修改传统的RBF神经网络模型来更准确地捕获流量矩阵的特征，并在欧氏距离和马氏距离下，通过迭代寻优来获得流量矩阵的精确估计。最后，第七章总结全文，回顾了前面所述的研究工作，并根据目前的研究情况对未来的研究方向作了展望。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 研究背景
• 1.2 流量矩阵估计研究动态
• 1.3 本文的主要贡献及内容安排
• 第二章 大尺度IP流量矩阵的最优化估计
• 2.1 引言
• 2.2 基于单纯形的SMBTME算法
• 2.2.1 问题定义
• 2.2.2 流量矩阵估计
• 2.2.3 算法描述
• 2.2.4 仿真和分析
• 2.3 基于模拟退火的SAGI算法
• 2.3.1 问题定义
• 2.3.2 模拟退火过程
• 2.3.3 广义反演
• 2.3.4 算法描述
• 2.3.5 仿真和分析
• 2.4 本章小结
• 第三章 基于Fratar模型的大尺度IP流量矩阵估计
• 3.1 引言
• 3.2 基于Fratar模型的PFMFM算法
• 3.2.1 问题定义
• 3.2.2 流量矩阵估计
• 3.2.3 算法描述
• 3.2.4 仿真和分析
• 3.3 基于Fratar模型的ARTI算法
• 3.3.1 基于ART的递归反演
• 3.3.2 算法描述
• 3.3.3 仿真和分析
• 3.4 本章小结
• 第四章 基于回归模型的大尺度IP流量矩阵估计
• 4.1 引言
• 4.2 基于马氏距离的MDRI算法
• 4.2.1 OD流建模
• 4.2.2 流量矩阵估计中的马氏距离
• 4.2.3 流量矩阵估计
• 4.2.4 算法描述
• 4.2.5 仿真和分析
• 4.3 基于GARCH模型的IP流量矩阵估计算法
• 4.3.1 问题定义
• 4.3.2 流量矩阵估计
• 4.3.3 算法描述
• 4.3.4 仿真和分析
• 4.4 本章小结
• 第五章 基于递归神经网络的大尺度IP流量矩阵估计
• 5.1 引言
• 5.2 基于RMLP的IP流量矩阵估计算法
• 5.2.1 问题定义
• 5.2.2 OD流建模
• 5.2.3 算法描述
• 5.2.4 仿真和分析
• 5.3 基于Elman神经网络的IP流量矩阵估计算法
• 5.3.1 流量矩阵估计模型
• 5.3.2 流量矩阵反演
• 5.3.3 算法描述
• 5.3.4 仿真和分析
• 5.4 本章小结
• 第六章 基于前馈神经网络的大尺度IP流量矩阵估计
• 6.1 引言
• 6.2 基于BP神经网络的BPNNI算法
• 6.2.1 流量矩阵估计建模
• 6.2.2 流量矩阵估计
• 6.2.3 算法描述
• 6.2.4 仿真和分析
• 6.3 基于GRNN的IP流量矩阵估计算法
• 6.3.1 流量矩阵估计模型
• 6.3.2 流量矩阵递归反演
• 6.3.3 算法描述
• 6.3.4 仿真和分析
• 6.4 基于RBF神经网络的TMRI算法
• 6.4.1 问题定义
• 6.4.2 用于流量矩阵估计的RBF神经网络模型
• 6.4.3 流量矩阵估计模型
• 6.4.4 流量矩阵递归反演
• 6.4.5 算法描述
• 6.4.6 仿真和分析
• 6.5 本章小结
• 第七章 全文总结
• 7.1 工作总结
• 7.2 展望
• 致谢
• 参考文献
• 本文作者在攻博期间发表、录用和投出的论文
• 本文作者在攻博期间参加的科研项目
• 本文作者在攻博期间的获奖情况