基于矩阵填充的软件定义网络流量矩阵测量方法研究

Traffic Matrix (TM) provides the most important formation for network management, traffic engineering, network anomaly detection, network design and capacity planning. The traffic matrix can serve as the fundamental data to facilitate the SDN (software defined networking) control plane to make network resource management and control decisions. To collect and predict TM at low cost, high accuracy, and high reliability, this project proposes to exploit matrix completion, an emerging sparse representation technique, to accurately infer and predict traffic matrix using only a small number of samples. The main technique issues studied are listed as follows. First, to enable traffic query with different granularity, we propose a new flow table index based on the bloom filter and a quick traffic matching algorithm. Second, to support on-line traffic monitoring required in SDN infrastructure, we propose a sampling engine based on matrix recovery condition to schedule the measurement taken at appropriate locations and time. Third, to ensure the TM obtained to be reliable under various unreliable conditions, we propose a traffic anomaly detection and recovery algorithm. Fourth, to accurately predict the traffic, we propose a multi-dimensional matrix completion based prediction algorithm exploiting the temporal stability and spatial correlation features in the TM. Finally, to solve the scalability problem faced by using the matrix completion technique and quickly infer the traffic values not measured, we propose a parallel and distributed matrix completion algorithm.

流量矩阵(Traffic Matrix, TM)作为网络管理、流量工程、网络异常检测、网络设计和规划的重要输入参数，是SDN(Software Defined Networking)中控制平面资源管控决策的基础。为了低开销、高精度、高可靠地测量和预测TM，本项目采用最新的稀疏处理技术—矩阵填充，通过少部分流量采样数据，来精确推断和预测TM。研究内容包括：为了支持不同粒度的流量查询，提出基于布鲁姆过滤器的流表索引结构和快速流量查询算法；为了支持SDN中在线TM测量，提出基于矩阵恢复条件的流量采集调度引擎，该引擎可在恰当的位置和时间测量流量；提出流量数据异常检测和恢复算法，以在不可靠网络环境中提供可靠的TM；利用TM内时间稳定性和空间相关性，提出基于多维矩阵填充的流量预测算法，以实现准确预测流量；为了解决矩阵填充技术的可扩展性问题并快速实现TM的推断，提出并行和分布式的矩阵填充算法。

大规模网络性能测量会导致大量测量代价。为了降低测量开销并获得网络性能视图（如流量矩阵），本项目提出新的稀疏网络测量框架。该框架通过选择部分节点和路径开展网络测量，利用测量数据高时空相关性，推测出未测量和丢失的网络性能数据。不依赖于随机测量策略，为了进一步降低测量代价，本项目提出新的测量调度框架，可主动确定未来短期测量的位置，从而保证未测量的数据可以通过矩阵填充来精确恢复。在稀疏网络测量中，缺失测量数据恢复高度依赖所采取的数据推测算法。本项目首先将网络测量数据建模为矩阵，提出多个矩阵填充算法，可根据部分测量数据，推测未测量的数据。然后，为了利用数据内部的高阶结构化信息来进一步提高推测精度，本项目将网络性能数据建模为张量，提出多个张量填充算法以更高的精度推测未测量的数据。在测量数据的基础上，本项目研究利用时空信息从网络整体出发来检测和定位网络异常并恢复正常数据。提出多个网络异常检测算法，包括离线和在线异常检测，实现高速和高精度的网络异常检测。基于小波变换和图卷积，本项目研究和提出了网络流量预测算法，实现对动态网络的高精度网络流量预测。除了上述工作外，本项目还提出了基于布鲁姆过滤器的网络流查询算法，以快速查询网络状态。本项目所提的稀疏网络测量框架，可以实现仅测量20%的端到端路径，精确推测全部的端到端路径，大大降低测量开销。本项目发表CCF A杂志和会议论文20篇，CCF B杂志和会议论文7篇，CCF C杂志和会议论文12篇。申请发明专利16项，授权专利8项。