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

doi:10.12263/DZXB.20211703

电子学报 ›› 2022, Vol. 50 ›› Issue (7): 1653-1663.DOI: 10.12263/DZXB.20211703

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

欧阳与点¹, 谢鲲¹(), 谢高岗²^,³, 文吉刚¹^,⁴

^1.湖南大学信息科学与工程学院，湖南长沙 410006
^2.中国科学院计算机网络信息中心，北京 100089
^3.中国科学院大学，北京 100089
^4.湖南友道信息技术有限公司，湖南长沙 410006

收稿日期:2021-12-25 修回日期:2022-04-05 出版日期:2022-07-25
- 通讯作者:
- 谢鲲
- 作者简介:
- 欧阳与点女，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)

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¹^,⁴

^1.College of Computer Science and Electronic Engineering, Hunan University, Changsha, Hunan 410006, China
^2.Computer Network Information Center, Chinese Academy of Sciences, Beijing 100089, China
^3.The University of Chinese Academy of Sciences, Beijing 100089, China
^4.Hunan cnSunet Information Technology Co., Ltd, Changsha, Hunan 410006, China

Received:2021-12-25 Revised:2022-04-05 Online:2022-07-25 Published:2022-07-30
- Corresponding author:
- XIE Kun
- Supported by:
- Distinguished Young Scholars Fund supported by National Natural Science Foundation of China (62025201); National Natural Science Foundation of China (61972144)

摘要/Abstract

摘要：

网络应用，如网络状态跟踪、服务等级协议保障和网络故障定位等，依赖于完整准确的吞吐量测量数据.由于测量代价大，网络监控系统通常难以获得全网吞吐量测量数据.稀疏网络测量技术基于采样的方式降低测量代价，通过张量填充等算法挖掘数据内部的时空相关性，从部分网络测量数据恢复缺失数据.然而，现有研究仅考虑了单个性能指标，忽略了多个指标之间的关联信息，导致恢复精度受限且整体测量代价依然很大.本文提出了一个面向大规模网络测量的数据恢复算法——基于关联学习的张量填充（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.

Key words: network monitoring, sparse network measurement, tensor completion, multi-metrics association, deep learning

中图分类号:

TP393

欧阳与点, 谢鲲, 谢高岗, 文吉刚. 面向大规模网络测量的数据恢复算法：基于关联学习的张量填充[J]. 电子学报, 2022, 50(7): 1653-1663.

OUYANG Yu-dian, XIE Kun, XIE Gao-gang, WEN Ji-gang. A Data Recovery Algorithm for Large-Scale Network Measurements: Association Learning Based Tensor Completion[J]. Acta Electronica Sinica, 2022, 50(7): 1653-1663.

图/表 13

图1 网络测量数据的三维张量模型

图2 网络测量数据恢复问题

图3 基于关联学习的张量填充算法的整体框架

图4 吞吐量-往返时延关联

图5 吞吐量-往返时延关联学习模型(图中例子:特征维度D=4,卷积通道数C=5)

图6 基于关联学习的张量填充算法的步骤

图7 ALTC在不同采样率下与传统线性算法对比恢复性能

表1 不同采样率下与神经网络算法比较NMAE

算法	采样率
算法	2%	4%	6%	8%	10%
ALTC	0.429 0	0.395 2	0.379 0	0.369 8	0.356 3
NTC	0.493 1	0.498 3	0.481 8	0.461 9	0.435 5
NTF	0.678 8	0.533 5	0.497 6	0.462 0	0.411 4
NTM	0.633 7	0.721 0	0.650 2	0.639 0	0.632 0
CoSTCo	0.541 2	0.532 1	0.465 5	0.450 1	0.443 0

表2 不同采样率下与神经网络算法比较NRMSE

算法	采样率
算法	2%	4%	6%	8%	10%
ALTC	0.447 8	0.418 2	0.405 9	0.399 9	0.382 5
NTC	0.530 8	0.473 7	0.449 0	0.425 9	0.414 0
NTF	0.620 6	0.510 5	0.478 2	0.475 7	0.437 9
NTM	0.622 9	0.561 3	0.578 8	0.538 9	0.512 8
CoSTCo	0.528 6	0.464 3	0.459 5	0.423 4	0.412 0

图8 关联学习模型在不同采样率下的推测效果

图9 考虑不同上下文信息的关联学习模型的推测效果

图10 不同的超参数对模型性能的影响

表3 训练时间对比

模型	训练一批数据需要的时间/ms	训练一轮全部数据需要的时间/s
CP	1.367 5	28.598 4
ALTC	1.589 4	300.308 1
ALM	2.591 1	44.602 1

参考文献 30

1	CUNHAI, TEIXEIRAR, VEITCHD, et al. Predicting and tracking internet path changes[C]//Proceedings of the ACM SIGCOMM 2011 Conference. New York: ACM, 2011: 122-133.
2	JAINS, KUMARA, MANDALS, et al.B4: 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.
3	PENGY H, YANGJ, WUC, 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.
4	MATHISM, ALLMANM. A Framework for Defining Empirical Bulk Transfer Capacity Metrics[R]. United States: RFC Editor, 2001.
5	曾彬. 基于主动测试的网络性能监测技术研究[D]. 长沙: 湖南大学, 2009.
	ZENGB. Researches on Internet Performance Monitoring Based on Active Measurements[D]. Changsha: Hunan University, 2009. (in Chinese)
6	BREITBARTY, CHANC-Y, GAROFALAKISM, 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.01CH37213. Anchorage, AK: IEEE, 2001: 933-942.
7	CLAISEB, SADASIVANG, VALLURIV, et al. Cisco systems netflow services export version9, RFC 3954[EB/OL]. (2004-10)[2022-04-05]. .
8	TOOTOONCHIANA, GHOBADIM, GANJALIY. OpenTM: Traffic matrix estimator for OpenFlow networks[C]//International Conference on Passive and Active Network Measurement. Berlin, Heidelberg: Springer, 2010: 201-210.
9	GUOC X, YUANL H, XIANGD, 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.
10	XIEK, WANGL L, WANGX, 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.
11	KONGL H, XIAM Y, LIUX 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.
12	ZHANGY, ROUGHANM, WILLINGERW, et al. Spatio-temporal compressive sensing and Internet traffic matrices[J]. ACM SIGCOMM Computer Communication Review, 2009, 39(4): 267-278.
13	KORTASM, HABACHIO, BOUALLEGUEA, et al. Robust data recovery in wireless sensor network: A learning-based matrix completion framework[J]. Sensors(Basel), 2021, 21(3): 1016.
14	XIEK, CHENY X, WANGX, 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.
15	XIEK, WANGX G, WANGX, et al. Accurate recovery of missing network measurement data with localized tensor completion[J]. IEEE/ACM Transactions on Networking, 2019, 27(6): 2222-2235.
16	DENGL, ZHENGH F, LIUX 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.
17	WANGQ Q, CHENL, WANGQ, 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.
18	XIEK, LIS Q, WANGX, 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.
19	XIEK, LUH L, WANGX, et al. Neural tensor completion for accurate network monitoring[C]//IEEE INFOCOM 2020-IEEE Conference on Computer Communications. Toronto: IEEE, 2020: 1688-1697.
20	CARROLLJ D, CHANGJ J. Analysis of individual differences in multidimensional scaling via an n-way generalization of “Eckart-Young” decomposition[J]. Psychometrika, 1970, 35(3): 283-319.
21	HARSHMANR 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.
22	TUCKERL R. Some mathematical notes on three-mode factor analysis[J]. Psychometrika, 1966, 31(3): 279-311.
23	ZHENGZ B, LYUM 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.
24	张贤达. 矩阵分析与应用[M]. 北京: 清华大学出版社, 2008.
	ZHANGX D. Matrix Analysis and Applications[M]. Beijing: Tsinghua University Press, 2008. (in Chinese)
25	BADERB W, KOLDAT G. Tensor toolbox for MATLAB, version 3.2.1[EB/OL]. (2021-04-05)[2022-04-05]. .
26	WENZ W, YINW T, ZHANGY. 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.
27	ACARE, DUNLAVYD M, KOLDAT G, et al. Scalable tensor factorizations for incomplete data[J]. Chemometrics and Intelligent Laboratory Systems, 2011, 106(1): 41-56.
28	WUX, SHIB X, DONGY 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.
29	CHENH Y, LIJ. 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.
30	LIUH P, LIY G, TSANGM, 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.

[1]	吴靖, 叶晓晶, 黄峰, 陈丽琼, 王志锋, 刘文犀. 基于深度学习的单帧图像超分辨率重建综述[J]. 电子学报, 2022, 50(9): 2265-2294.
[2]	李雪莹, 王田路, 梁鹏, 王翀. 基于系统模型的用户评论中非功能需求的自动分类[J]. 电子学报, 2022, 50(9): 2079-2089.
[3]	琚长瑞, 秦晓燕, 袁广林, 李豪, 朱虹. 尺度敏感损失与特征融合的快速小目标检测方法[J]. 电子学报, 2022, 50(9): 2119-2126.
[4]	张志昌, 于沛霖, 庞雅丽, 朱林, 曾扬扬. SMGN：用于对话状态跟踪的状态记忆图网络[J]. 电子学报, 2022, 50(8): 1851-1858.
[5]	张亚洲, 俞洋, 朱少林, 陈锐, 戎璐, 梁辉. 一种量子概率启发的对话讽刺识别网络模型[J]. 电子学报, 2022, 50(8): 1885-1893.
[6]	王飞扬, 冀鹏欣, 孙笠, 危倩, 李根, 张忠宝. 一种基于深度学习的动态社交网络用户对齐方法[J]. 电子学报, 2022, 50(8): 1925-1936.
[7]	徐兴荣, 刘聪, 李婷, 郭娜, 任崇广, 曾庆田. 基于双向准循环神经网络和注意力机制的业务流程剩余时间预测方法[J]. 电子学报, 2022, 50(8): 1975-1984.
[8]	裴炤, 邱文涛, 王淼, 马苗, 张艳宁. 基于Transformer动态场景信息生成对抗网络的行人轨迹预测方法[J]. 电子学报, 2022, 50(7): 1537-1547.
[9]	彭闯, 王伦文, 胡炜林. 融合深度特征的电磁频谱异常检测算法[J]. 电子学报, 2022, 50(6): 1359-1369.
[10]	杨伟超, 杜宇, 文伟, 侯舒维, 徐常志, 张建华. 基于多重分形谱智能分析的卫星信号调制识别研究[J]. 电子学报, 2022, 50(6): 1336-1343.
[11]	李政伟, 李佳树, 尤著宏, 聂茹, 赵欢, 钟堂波. 基于异质图注意力网络的miRNA与疾病关联预测算法[J]. 电子学报, 2022, 50(6): 1428-1435.
[12]	张波, 陆云杰, 秦东明, 邹国建. 一种卷积自编码深度学习的空气污染多站点联合预测模型[J]. 电子学报, 2022, 50(6): 1410-1427.
[13]	廖勇, 李玉杰. 一种轻量化低复杂度的FDD大规模MIMO系统CSI反馈方法[J]. 电子学报, 2022, 50(5): 1211-1217.
[14]	冀振燕, 韩梦豪, 宋晓军, 冯其波. 面向激光光条图像修复的循环相似度映射网络[J]. 电子学报, 2022, 50(5): 1234-1242.
[15]	潘敏婷, 王韫博, 朱祥明, 高思宇, 龙明盛, 杨小康. 基于无标签视频数据的深度预测学习方法综述[J]. 电子学报, 2022, 50(4): 869-886.

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

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

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 13

参考文献 30

相关文章 15

编辑推荐

Metrics