Tripartite Graph Aided Tensor Completion For Sparse Network Measurement
Tripartite Graph Aided Tensor Completion For Sparse Network Measurement
复制标题
DOI：
10.1109/tpds.2022.3213259
复制
发表时间：
2023-01
影响因子：
5.3
通讯作者：
Xiaocan Li;Kun Xie;X. Wang;Gaogang Xie;Kenli Li;Jiannong Cao;Dafang Zhang;Jigang Wen
中科院分区：
文献类型：
--
作者：
Xiaocan Li;Kun Xie;X. Wang;Gaogang Xie;Kenli Li;Jiannong Cao;Dafang Zhang;Jigang Wen
网络测量为广泛的网络管理提供关键输入。现有的网络范围的监测方法面临的挑战，招致高的测量成本。最近的一些研究表明，网络范围内的测量数据，如端到端的延迟和流量，具有隐藏的时空相关性，因此低排名的功能。利用低秩的特点，受张量模型强大的信息表示和提取能力的启发，研究了一种新的稀疏测量调度问题，即在未来的时隙中选择一定比例的OD对进行测量，同时通过张量补全保证剩余未测量OD对的数据能够被准确推断。在不知道未来数据结构的情况下找到最佳采样点（OD对），并且在测量样本中存在噪声的情况下推断未测量数据是具有挑战性的。为了克服这些挑战，我们提出了几种技术：一个三方图来说明样本位置和张量分解之间的关系，一个基于图的样本选择算法，和一个基于图的强大的张量完成算法。我们已经进行了广泛的实验，基于两个真实的网络延迟监测跟踪（PlanetLab和哈佛）和其他两个网络监测跟踪（包括流量跟踪Abilene和吞吐量跟踪WS-Dream）。我们的研究结果表明，即使采样率小于5%，我们的计划可以准确地获得完整的网络范围内的监测数据推断缺失的样本的基础上。为了达到类似的恢复性能，最好的对等张量完成算法需要大量的样本，采样率高达25-150倍。
Network measurements provide critical inputs for a wide range of network management. Existing network-wide monitoring methods face the challenge of incurring a high measurement cost. Some recent studies show that network-wide measurement data such as end-to-end latency and flow traffic, have hidden spatio-temporal correlations and thus low-rank features. Taking advantage of the low-rank feature, enlightened by tensor model's strong capability of information representation and extracting, this paper studies a novel sparse measurement scheduling problem which selects a proportion of Origin and Destination (OD) pairs to take measurements in the future time slots, while ensuring the data of the remaining un-measured OD pairs be accurately inferred through tensor completion. It is challenging to find the optimal sampling points (OD pairs) without knowing the structure of the future data and also infer the un-measured data in the presence of noise in the measurement samples. To conquer the challenges, we propose several techniques: a tripartite graph to illustrate the relationship between sample locations and tensor factorization, a graph-based sample selection algorithm, and a graph-based robust tensor completion algorithm. We have conducted extensive experiments based on two real network latency monitoring traces (PlanetLab and Harvard) and two other network monitoring traces (including a traffic trace Abilene and a throughput trace WS-Dream). Our results demonstrate that, even with a sampling ratio of less than 5%, our scheme can accurately obtain the complete network-wide monitoring data by inferring the missing ones based on the samples taken. To achieve similar recovery performance, the best peer tensor completion algorithm needs a significantly larger number of samples, with the sampling ratio up to 25-150 times ours.