随着信息技术的飞速发展，IP网络规模呈现指数式增长，并且已经发展成为一种异构开放的复杂网络。作为网络运营和网络管理最重要的数据源之一，网络流量数据蕴含着丰富的网络行为信息。然而，获取完整而准确的流量数据却极其困难，原因在于：1）对于大规模网络环境，直接测量全部流量数据代价太高，通常只能采样部分数据，因此获取的流量矩阵中存在大量的缺失值；2）网络流量是由用户多种通信行为共同产生的，流量数据中存在不同类型的流量异常。因此，如何对部分采样的流量数据进行缺失值估计和异常检测成为了网络管理和流量监测领域的热点问题。国内外研究者针对以上问题提出了诸多网络流量估计和异常检测算法，虽然这些算法在其各自的数据集上表现出了良好的性能，但它们在网络流量估计的准确性、异常检测的精确性、适用问题的规模性以及某些OD（Origin-Destination）对数据完全缺失的流量估计等方面仍然存在不足。 针对上述不足，本文首先基于流量矩阵所固有的近似低秩性和时空相关性，引入了低秩矩阵补全理论，将流量矩阵估计和异常检测问题建模为一类融合异常流量先验结构信息的范数正则化矩阵补全模型，并采用机器学习领域中流行的ADMM（Alternating Direction Method of Multipliers）方法进行优化求解。仿真实验表明该算法能够有效地解决网络流量矩阵中所存在的数据缺失和异常检测问题。其次，考虑到传统的ADMM本质上仍属于串行优化方法，难以适用于大规模问题求解，我们进一步引入并行多块ADMM和SPGD（Stochastic Proximal Gradient Descent）来改进模型的求解效率，提出了一种基于并行多块ADMM的大规模网络流量估计和异常检测算法，该算法有效地解决了流量矩阵估计和异常检测的大规模问题。仿真结果表明，与主流的流量估计算法相比，我们所提出的算法具有更好的估计性能。此外，本文所提出的算法还可以对野值异常和结构化异常进行准确定位，这是大规模网络异常诊断的前提。最后，基于归纳型矩阵补全理论，本文还设计出了可以在某些OD对数据完全缺失情况下进行大规模流量估计和异常检测的算法，并且在合成数据集上取得了很好的效果。
展开▼
