面向大规模网络测量的数据恢复算法：基于关联学习的张量填充

欧阳与点; 谢鲲; 谢高岗; 文吉刚

doi:10.12263/DZXB.20211703

您当前的位置：

首页 >

文章列表页 >

面向大规模网络测量的数据恢复算法：基于关联学习的张量填充

学术论文 | 更新时间：2025-12-08

- 面向大规模网络测量的数据恢复算法：基于关联学习的张量填充
- A Data Recovery Algorithm for Large-Scale Network Measurements: Association Learning Based Tensor Completion
- 电子学报 2022年50卷第7期页码：1653-1663
- 作者机构：
  
  1.湖南大学信息科学与工程学院，湖南长沙 410006
  2.中国科学院计算机网络信息中心，北京 100089
  3.中国科学院大学，北京 100089
  4.湖南友道信息技术有限公司，湖南长沙 410006
- 作者简介：
  
  [ "欧阳与点女，1996年5月出生于湖南省衡阳市.湖南大学信息科学与工程学院博士研究生.主要研究方向为网络测量、张量填充和深度学习.E-mail: yudian@hnu.edu.cn" ]
  [ "谢鲲（通讯作者）女，1978年10月出生于湖南省怀化市.博士.湖南大学信息科学与工程学院教授，博士生导师.主要研究方向为计算机网络、网络测量、网络安全、大数据和人工智能.E-mail: xiekun@hnu.edu.cn" ]
  [ "谢高岗男，1974年5月出生于浙江省衢州市.博士.中国科学院计算机网络信息中心研究员，中国科学院大学岗位教授，博士生导师.主要从事计算机网络体系结构与系统的研究工作.E-mail: xie@cnic.cn" ]
  [ "文吉刚男，1978年3月出生于湖南省常德市.博士.中国科学院计算技术研究所博士后.现为湖南友道信息技术有限公司技术首席和湖南大学校外导师.主要从事高速网络测量和管理的研究和开发工作.E-mail: wenjigang@gmail.co" ]
- 基金信息：
  
  国家自然科学基金杰出青年基金(62025201);国家自然科学基金(61972144)
- DOI：10.12263/DZXB.20211703
  中图分类号： TP393;
- 收稿：2021-12-25，
  
  修回：2022-04-05，
  
  纸质出版：2022-07-25
- 稿件说明：
移动端阅览
欧阳与点,谢鲲,谢高岗等.面向大规模网络测量的数据恢复算法：基于关联学习的张量填充[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 .

浏览量

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

面向时序异常检测的可变视距多向扫描方法

基于稀疏平滑自蒸馏的差分隐私深度学习方法

基于非一般类算子融合方法及硬件架构设计

基于注意力融合多尺度特征的解压缩点云质量增强方法