A Data Recovery Algorithm for Large-Scale Network Measurements: Association Learning Based Tensor Completion

OUYANG Yu-dian; XIE Kun; XIE Gao-gang; WEN Ji-gang

doi:10.12263/DZXB.20211703

您当前的位置：

首页 >

文章列表页 >

A Data Recovery Algorithm for Large-Scale Network Measurements: Association Learning Based Tensor Completion

PAPERS | 更新时间：2025-12-08

- A Data Recovery Algorithm for Large-Scale Network Measurements: Association Learning Based Tensor Completion
- ACTA ELECTRONICA SINICA Vol. 50, Issue 7, Pages: 1653-1663(2022)
- 作者机构：
  
  1.湖南大学信息科学与工程学院，湖南长沙 410006
  2.中国科学院计算机网络信息中心，北京 100089
  3.中国科学院大学，北京 100089
  4.湖南友道信息技术有限公司，湖南长沙 410006
- 作者简介：
- 基金信息：
- DOI：10.12263/DZXB.20211703
  CLC： TP393;
- Received：25 December 2021，
  
  Revised：2022-04-05，
  
  Published：25 July 2022
- 稿件说明：
移动端阅览
欧阳与点,谢鲲,谢高岗等.面向大规模网络测量的数据恢复算法：基于关联学习的张量填充[J].电子学报,2022,50(07):1653-1663.

OUYANG Yu-dian,XIE Kun,XIE Gao-gang,et al.A Data Recovery Algorithm for Large-Scale Network Measurements: Association Learning Based Tensor Completion[J].ACTA ELECTRONICA SINICA,2022,50(07):1653-1663.
欧阳与点,谢鲲,谢高岗等.面向大规模网络测量的数据恢复算法：基于关联学习的张量填充[J].电子学报,2022,50(07):1653-1663. DOI： 10.12263/DZXB.20211703.

OUYANG Yu-dian,XIE Kun,XIE Gao-gang,et al.A Data Recovery Algorithm for Large-Scale Network Measurements: Association Learning Based Tensor Completion[J].ACTA ELECTRONICA SINICA,2022,50(07):1653-1663. DOI： 10.12263/DZXB.20211703.

摘要

网络应用，如网络状态跟踪、服务等级协议保障和网络故障定位等，依赖于完整准确的吞吐量测量数据.由于测量代价大，网络监控系统通常难以获得全网吞吐量测量数据.稀疏网络测量技术基于采样的方式降低测量代价，通过张量填充等算法挖掘数据内部的时空相关性，从部分网络测量数据恢复缺失数据.然而，现有研究仅考虑了单个性能指标，忽略了多个指标之间的关联信息，导致恢复精度受限且整体测量代价依然很大.本文提出了一个面向大规模网络测量的数据恢复算法——基于关联学习的张量填充（Association Learning based Tensor Completion，ALTC）.为了捕获网络性能指标之间的复杂关系，设计了一个关联学习模型，使用低测量开销的往返时延推测高测量开销的吞吐量，降低网络测量代价.在此基础上设计了一个张量填充模型，同时学习吞吐量测量数据内部的时空相关性和来自往返时延的外部辅助关联信息，最终以更高的恢复精度获取全网吞吐量数据.实验表明，在相同的吞吐量测量代价下，本文所提算法的恢复误差比目前主流方法的恢复误差降低了13%，达到了更好的恢复效果.

Abstract

Network applications

such as network state tracking

service level agreement guarantee

and network fault location

rely on complete and accurate throughput measurement data. Due to the high measurement cost

it is hard to obtain network-wide throughput measurement data for network monitoring systems. Sparse network measurement techniques reduce the measurement cost based on sampling and recover missing data from partial network measurement data by exploiting spatio-temporal correlations within the data through algorithms such as tensor completion. However

existing studies only consider individual performance metrics and ignore the correlation information between multiple metrics

resulting in limited recovery accuracy and high overall measurement cost. This paper proposes a data recovery algorithm for large-scale network measurements—association learning based tensor completion(ALTC). To capture the complex correlations among network performance metrics

an association learning model is designed to reduce the network measurement cost by using the round-trip delay with low measurement overhead to infer the throughput with high measurement overhead. Based on this

a tensor completion model is designed to learn both the spatio-temporal correlation within the throughput measurement data and the external auxiliary correlation information from the round-trip delay

and finally obtain the network-wide throughput data with higher recovery accuracy. Experiments show that the recovery error of the proposed algorithm is 13% lower than that of the current mainstream methods at the same throughput measurement cost

achieving better recovery results.

关键词

Keywords

references

CUNHA I , TEIXEIRA R , VEITCH D , et al . Predicting and tracking internet path changes [C]// Proceedings of the ACM SIGCOMM 2011 Conference . New York : ACM , 2011 : 122 - 133 .

JAIN S , KUMAR A , MANDAL S , et al . B 4 : Experience with a globally-deployed software defined wan [C]// SIGCOMM'13: Proceedings of the ACM SIGCOMM 2013 conference on SIGCOMM . New York : ACM , 2013: 3 - 14 .

PENG Y H , YANG J , WU C , et al . deTector: A topology-aware monitoring system for data center networks [C]// Proceedings of the 2017 USENIX Annual Technical Conference . Santa Clara : USENIX Association , 2017 : 55 - 68 .

MATHIS M , ALLMAN M . A Framework for Defining Empirical Bulk Transfer Capacity Metrics [R]. United States : RFC Editor , 2001 .

曾彬 . 基于主动测试的网络性能监测技术研究 [D]. 长沙 : 湖南大学 , 2009 .

ZENG B . Researches on Internet Performance Monitoring Based on Active Measurements [D]. Changsha : Hunan University , 2009 . (in Chinese)

BREITBART Y , C-Y CHAN , GAROFALAKIS M , et al . Efficiently monitoring bandwidth and latency in IP networks [C]// Proceedings IEEE INFOCOM 2001, Conference on Computer Communications, Twentieth Annual Joint Conference of the IEEE Computer and Communications Society(Cat . No . 01 CH 37213 . Anchorage, AK: IEEE , 2001: 933 - 942 .

CLAISE B , SADASIVAN G , VALLURI V , et al . Cisco systems netflow services export version 9 , RFC 3954[EB/OL]. ( 2004-10 )[ 2022-04-05 ]. https://www.rfc-editor.org/info/rfc3954 https://www.rfc-editor.org/info/rfc3954 .

TOOTOONCHIAN A , GHOBADI M , GANJALI Y . OpenTM: Traffic matrix estimator for OpenFlow networks [C]// International Conference on Passive and Active Network Measurement . Berlin, Heidelberg : Springer , 2010 : 201 - 210 .

GUO C X , YUAN L H , XIANG D , et al . Pingmesh: A large-scale system for data center network latency measurement and analysis [C]// SIGCOMM'15: Proceedings of the 2015 ACM Conference on Special Interest Group on Data Communication . London : ACM , 2015 : 139 - 152 .

XIE K , WANG L L , WANG X , et al . Sequential and adaptive sampling for matrix completion in network monitoring systems [C]// 2015 IEEE Conference on Computer Communications . Hong Kong : IEEE , 2015 : 2443 - 2451 .

KONG L H , XIA M Y , LIU X Y , et al . Data loss and reconstruction in sensor networks [C]// 2013 Proceedings of IEEE International Conference on Computer Communications . Turin : IEEE , 2013 : 1654 - 1662 .

ZHANG Y , ROUGHAN M , WILLINGER W , et al . Spatio-temporal compressive sensing and Internet traffic matrices [J]. ACM SIGCOMM Computer Communication Review , 2009 , 39 ( 4 ): 267 - 278 .

KORTAS M , HABACHI O , BOUALLEGUE A , et al . Robust data recovery in wireless sensor network: A learning-based matrix completion framework [J]. Sensors(Basel) , 2021 , 21 ( 3 ): 1016 .

XIE K , CHEN Y X , WANG X , et al . Accurate and fast recovery of network monitoring data: A GPU accelerated matrix completion [J]. IEEE/ACM Transactions on Networking , 2020 , 28 ( 3 ): 958 - 971 .

XIE K , WANG X G , WANG X , et al . Accurate recovery of missing network measurement data with localized tensor completion [J]. IEEE/ACM Transactions on Networking , 2019 , 27 ( 6 ): 2222 - 2235 .

DENG L , ZHENG H F , LIU X Y , et al . Network latency estimation with leverage sampling for personal devices: An adaptive tensor completion approach [J]. IEEE/ACM Transactions on Networking , 2020 , 28 ( 6 ): 2797 - 2808 .

WANG Q Q , CHEN L , WANG Q , et al . Anomaly-aware network traffic estimation via outlier-robust tensor completion [J]. IEEE Transactions on Network and Service Management , 2020 , 17 ( 4 ): 2677 - 2689 .

XIE K , LI S Q , WANG X , et al . Expectile tensor completion to recover skewed network monitoring data [C]// IEEE INFOCOM 2021-IEEE Conference on Computer Communications . Vancouver : IEEE , 2021 : 1 - 10 .

XIE K , LU H L , WANG X , et al . Neural tensor completion for accurate network monitoring [C]// IEEE INFOCOM 2020-IEEE Conference on Computer Communications . Toronto : IEEE , 2020 : 1688 - 1697 .

CARROLL J D , CHANG J J . Analysis of individual differences in multidimensional scaling via an n-way generalization of “Eckart-Young” decomposition [J]. Psychometrika , 1970 , 35 ( 3 ): 283 - 319 .

HARSHMAN R A . Foundations of the PARAFAC procedure: Models and conditions for an “explanatory” multimodal factor analysis [J]. UCLA Working Papers in Phonetics , 1970 . 16 : 1 - 84 .

TUCKER L R . Some mathematical notes on three-mode factor analysis [J]. Psychometrika , 1966 , 31 ( 3 ): 279 - 311 .

ZHENG Z B , LYU M R . WS-DREAM: A distributed reliability assessment mechanism for web services [C]// 2008 IEEE International Conference on Dependable Systems and Networks With FTCS and DCC . Anchorage : IEEE , 2008 : 392 - 397 .

张贤达 . 矩阵分析与应用 [M]. 北京 : 清华大学出版社 , 2008 .

ZHANG X D . Matrix Analysis and Applications [M]. Beijing : Tsinghua University Press , 2008 . (in Chinese)

BADER B W , KOLDA T G . Tensor toolbox for MATLAB, version 3.2. 1[EB/OL]. ( 2021-04-05 )[ 2022-04-05 ]. https://www.tensortoolbox.org https://www.tensortoolbox.org .

WEN Z W , YIN W T , ZHANG Y . Solving a low-rank factorization model for matrix completion by a nonlinear successive over-relaxation algorithm [J]. Mathematical Programming Computation , 2012 , 4 ( 4 ): 333 - 361 .

ACAR E , DUNLAVY D M , KOLDA T G , et al . Scalable tensor factorizations for incomplete data [J]. Chemometrics and Intelligent Laboratory Systems , 2011 , 106 ( 1 ): 41 - 56 .

WU X , SHI B X , DONG Y X , et al . Neural tensor factorization for temporal interaction learning [C]// WSDM'19: Proceedings of the Twelfth ACM International Conference on Web Search and Data Mining . Melbourne : ACM , 2019 : 537 - 545 .

CHEN H Y , LI J . Neural tensor model for learning multi-aspect factors in recommender systems [C]// Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence . Yokohama : International Joint Conferences on Artificial Intelligence Organization , 2020 : 2449 - 2455 .

LIU H P , LI Y G , TSANG M , et al . CoSTCo: A neural tensor completion model for sparse tensors [C]// KDD'19 Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining . Anchorage : ACM , 2019 : 324 - 334 .

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Variable Horizon Multi-Directional Scanning Method for Time Series Anomaly Detection

Differentially Private with Sparse and Smooth Self-Distillation

Operator Fusion Method and Hardware Architecture Design Based on Non-Standard Operators

A Method for Enhancing the Quality of Decompressed Point Clouds Based on Attention-Fused Multi-Scale Features

Related Author

Yu-dian OUYANG

Gao-gang XIE

Kun XIE

Ji-gang WEN

HUANG Yu-zhe

GUAN Yong-yuan

WEI Song-jie

ZHAO Deng-feng

Related Institution

College of Computer Science and Electronic Engineering， Hunan University

Computer Network Information Center， Chinese Academy of Sciences

Hunan cnSunet Information Technology， Inc

School of Computer Science and Engineering, School of Cyber Science and Engineering, Nanjing University of Science and Technology

School of Information, Renmin University of China

⁰