网络性能数据恢复算法

doi:10.11871/jfdc.issn.2096-742X.2020.03.005

数据与计算发展前沿 ›› 2020, Vol. 2 ›› Issue (3): 55-65.

doi: 10.11871/jfdc.issn.2096-742X.2020.03.005

所属专题：下一代互联网络技术与应用

• 专刊：下一代互联网络技术与应用（上） • 上一篇下一篇

网络性能数据恢复算法

欧阳与点(),谢鲲()

湖南大学信息科学与工程学院,湖南长沙 410006

收稿日期:2020-04-10 出版日期:2020-06-20 发布日期:2020-08-19
通讯作者: 谢鲲
作者简介:欧阳与点,湖南大学信息科学与工程学院,博士研究生。主要研究方向为矩阵填充、张量填充和人工智能。
本文主要承担模型设计搭建与实验验证。
Ouyang Yudian is currently a Ph.D. candidate at the College of Computer Science and Electronics Engineering, Hunan University. Her research interests include matrix completion, tensor completion and AI.
In this paper she is mainly responsible for framework design and construction with experimental verification.
E-mail: yudian@hnu.edu.cn|谢鲲,湖南大学以及网络安全鹏程实验室研究中心,教授。已经在计算机主要期刊和会议论文上发表了60多篇文章,包括期刊IEEE / ACM TON,IEEE TMC,IEEE TC,IEEE TWC和IEEE TSC,以及会议SIGMOD,INFOCOM,ICCDS,SECON和IWQoS。主要研究领域为网络测量、网络安全、大数据和人工智能。
本文主要承担工作为文献研究和模型概述。
Xie Kun, is currently a Professor of Hunan University and the Cyberspace Security Research Center, Peng Cheng Laboratory. She has published over 60 articles in major journals and conference proceedings, including journals IEEE/ACM TON, IEEE TMC, IEEE TC, IEEE TWC, and IEEE TSC, and conferences, SIGMOD, INFOCOM, ICDCS, SECON, and IWQoS. Her research interests include network measurement, network security, big data, and AI. In this paper she is mainly responsible for literature research and model overview.
E-mail: xiekun@hnu.edu.cn
基金资助:
国家自然科学基金(61972144)

An Algorithm for Network Monitoring Data Recovery

Ouyang Yudian(),Xie Kun()

The College of Computer Science and Electronics Engineering, Hunan University, Changsha, Hunan 410006, China

Received:2020-04-10 Online:2020-06-20 Published:2020-08-19
Contact: Xie Kun

摘要/Abstract

摘要：

【目的】本文将部分观测的网络性能数据建模为张量,借助于深度神经网络强大的特征提取能力来恢复缺失数据。【方法】与依赖于张量分解的传统张量填充不同,本文基于深度卷积自编码器设计了一种新的张量填充方案（DCAE）。它可以处理稀疏矩阵数据的输入,学习数据的复杂关系,并重构缺失数据。【结果】我们使用了三个公开的真实世界网络性能数据集进行了广泛的实验,实验结果表明,即使采样率非常低,DCAE也可以显著提高恢复精度。【局限】由于网络攻击等,网络性能数据不可避免存在异常,影响恢复结果,未来希望对异常数据进行处理达到鲁棒的恢复效果。【结论】所提模型可以捕获网络性能数据之间的非线性关系,具有高数据恢复精度,可以为高层网络应用恢复缺失数据。

关键词: 张量填充, 稀疏网络测量, 卷积神经网络, 自编码器, 数据恢复

Abstract:

[Objective] This paper models the partially observed network performance data as a tensor, and exploits powerful ability of the deep neural network in feature extraction to recover the missing data. [Methods] Different from traditional tensor completion which relies on tensor decomposition, we design a novel tensor completion scheme based on Deep Convolution Autoencoder (DCAE). DCAE can handle the sparse matrix input, learn the complex relationship of data, and reconstruct the missing data. [Results] We have conducted extensive experiments using three publicly real-world network performance datasets. Our results demonstrate that DCAE can achieve significantly better recovery accuracy even when the sampling ratio is very low. [Limitations] Due to network attacks, network performance data may have unavoidable anomalies, which will deteriorate the recovery accuracy. In the future, we hope that the abnormal data will be able to be processed for a more robust recovery. [Conclusions] The proposed model can capture the non-linear relationship between the network performance data, achieve high data recovery accuracy, and recover missing data for advanced network applications.

Key words: tensor completion, sparse network monitoring, convolutional neural network, autoencoder, data recovery

欧阳与点,谢鲲. 网络性能数据恢复算法[J]. 数据与计算发展前沿, 2020, 2(3): 55-65.

Ouyang Yudian,Xie Kun. An Algorithm for Network Monitoring Data Recovery[J]. Frontiers of Data and Computing, 2020, 2(3): 55-65.

图/表 7

图1

图2

图3

图4

表1

图5

图6

参考文献 47

[1]	Cunha I, Teixeira R, Veitch D, et al. Predicting and tracking internet path changes[C]// Proceedings of the ACM SIGCOMM 2011 conference. 2011: 122-133. http://www.stats.gov.cn/tjsj/tjgb/rdpcgb/qgkjjftrtjgb/.
[2]	Tune P, Roughan M. Spatiotemporal traffic matrix synconfproc[C]// Proceedings of the 2015 ACM Conference on Special Interest Group on Data Communication. 2015: 579-592.
[3]	Adams A, Lapukhov P, Zeng J H. NetNORAD: Troubleshooting networks via end-to-end probing[Z]. Facebook White Paper, 2016.
[4]	Guo C, Yuan L, Xiang D, et al. Pingmesh: A large-scale system for data center network latency measurement and analysis[C]// Proceedings of the 2015 ACM Conference on Special Interest Group on Data Communication. 2015: 139-152.
[5]	Peng Y, Yang J, Wu C, et al. deTector: a topology-aware monitoring system for data center networks[C]// 2017 {USENIX} Annual Technical Conference({USENIX}{ATC} 17). 2017: 55-68.
[6]	Xie K, Wang L, Wang X, et al. Sequential and adaptive sampling for matrix completion in network monitoring systems[C]// 2015 IEEE Conference on Computer Communications (INFOCOM). IEEE, 2015: 2443-2451.
[7]	Xie K, Li X, Wang X, et al. Fast tensor factorization for accurate internet anomaly detection[J]. IEEE/ACM transactions on networking, 2017,25(6):3794-3807.
[8]	Guide to reliable internet services and applications[M]. Springer Science & Business Media, 2010.
[9]	Lakhina A, Papagiannaki K, Crovella M, et al. Structural analysis of network traffic flows[C]// Proceedings of the joint international conference on Measurement and modeling of computer systems. 2004: 61-72.
[10]	Zhang Y, Roughan M, Lund C, et al. Estimating point-to-point and point-to-multipoint traffic matrices: An information-theoretic approach[J]. IEEE/ACM Transactions on networking, 2005,13(5):947-960.
[11]	Barford P, Kline J, Plonka D, et al. A signal analysis of network traffic anomalies[C]// Proceedings of the 2nd ACM SIGCOMM Workshop on Internet measurment. 2002: 71-82.
[12]	Chen Y C, Qiu L, Zhang Y, et al. Robust network compressive sensing[C]// Proceedings of the 20th annual international conference on Mobile computing and networking. 2014: 545-556.
[13]	Du R, Chen C, Yang B, et al. Vanet based traffic estimation: A matrix completion approach[C]// 2013 IEEE Global Communications Conference (GLOBECOM). IEEE, 2013: 30-35.
[14]	Gürsun G, Crovella M. On traffic matrix completion in the internet[C]// Proceedings of the 2012 Internet Measurement Conference. 2012: 399-412.
[15]	Mardani M, Giannakis G B. Robust network traffic estimation via sparsity and low rank[C]// 2013 IEEE International Conference on Acoustics, Speech and Signal Processing. IEEE, 2013: 4529-4533.
[16]	Roughan M, Zhang Y, Willinger W, et al. Spatio-temporal compressive sensing and internet traffic matrices (extended version)[J]. IEEE/ACM Transactions on Networking, 2011,20(3):662-676.
[17]	Gandy S, Recht B, Yamada I. Tensor completion and low-n-rank tensor recovery via convex optimization[J]. Inverse Problems, 2011,27(2):025010.
[18]	Liu J, Musialski P, Wonka P, et al. Tensor completion for estimating missing values in visual data[J]. IEEE transactions on pattern analysis and machine intelligence, 2012,35(1):208-220. doi: 10.1109/TPAMI.2012.39 pmid: 22271823
[19]	Xie K, Li X, Wang X, et al. Graph based tensor recovery for accurate internet anomaly detection[C]// IEEE INFOCOM 2018-IEEE Conference on Computer Communications. IEEE, 2018: 1502-1510.
[20]	Dai K, Wang D, Lu H, et al. Visual tracking via adaptive spatially-regularized correlation filters[C]// Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. 2019: 4670-4679.
[21]	Yu H X, Zheng W S, Wu A, et al. Unsupervised person re-identification by soft multilabel learning[C]// Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. 2019: 2148-2157.
[22]	Jia W, Dai D, Xiao X, et al. ARNOR: Attention Regularization based Noise Reduction for Distant Supervision Relation Classification[C]// Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics. 2019: 1399-1408.
[23]	Yang A, Wang Q, Liu J, et al. Enhancing pre-trained language representations with rich knowledge for machine reading comprehension[C]// Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics. 2019: 2346-2357.
[24]	Pham N Q, Nguyen T S, Niehues J, et al. Very deep self-attention networks for end-to-end speech recognition[J]. arXiv preprint arXiv: 1904. 13377, 2019.
[25]	Zheng S, Liu G, Suo H, et al. Autoencoder-based Semi-Supervised Curriculum Learning For Out-of-domain Speaker Verification[C]// INTERSPEECH, 2019: 4360-4364.
[26]	Kramer M A. Autoassociative neural networks[J]. Computers & chemical engineering, 1992,16(4):313-328.
[27]	Lakhina A, Crovella M, Diot C. Diagnosing network-wide traffic anomalies[J]. ACM SIGCOMM computer communication review, 2004,34(4):219-230.
[28]	Vardi Y. Network tomography: Estimating source-destination traffic intensities from link data[J]. Journal of the American statistical association, 1996,91(433):365-377.
[29]	Liu B, Niu D, Li Z, et al. Network latency prediction for personal devices: Distance-feature decomposition from 3D sampling[C]// 2015 IEEE Conference on Computer Communications (INFOCOM). IEEE, 2015: 307-315.
[30]	Zhu R, Liu B, Niu D, et al. Network latency estimation for personal devices: A matrix completion approach[J]. IEEE/ACM Transactions on Networking, 2016,25(2):724-737.
[31]	Cichocki A, Mandic D, De Lathauwer L, et al. Tensor decompositions for signal processing applications: From two-way to multiway component analysis[J]. IEEE signal processing magazine, 2015,32(2):145-163.
[32]	Obozinski G, Taskar B, Jordan M I. Joint covariate selection and joint subspace selection for multiple classification problems[J]. Statistics and Computing, 2010,20(2):231-252.
[33]	Sun J, Papadimitriou S, Lin C Y, et al. Multivis: Content-based social network exploration through multi-way visual analysis[C]// Proceedings of the 2009 SIAM International Conference on Data Mining. Society for Industrial and Applied Mathematics, 2009: 1064-1075.
[34]	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.
[35]	Acar E, Dunlavy D M, Kolda T G. A scalable optimization approach for fitting canonical tensor decompositions[J]. Journal of Chemometrics, 2011,25(2):67-86.
[36]	Xie K, Wang L, Wang X, et al. Accurate recovery of internet traffic data: A sequential tensor completion approach[J]. IEEE/ACM transactions on networking, 2018,26(2):793-806.
[37]	Xie K, Peng C, Wang X, et al. Accurate recovery of internet traffic data under variable rate measurements[J]. IEEE/ACM transactions on networking, 2018,26(3):1137-1150. doi: 10.1109/TNET.2018.2819504
[38]	Xie K, Wang X, 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. doi: 10.1109/TNET.90
[39]	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. doi: 10.1007/BF02310791
[40]	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):1-84.
[41]	Nair V, Hinton G E. Rectified linear units improve restricted boltzmann machines[C]// Proceedings of the 27th international conference on machine learning (ICML-10). 2010: 807-814.
[42]	Ba J L, Kiros J R, Hinton G E. Layer normalization[J]. arXiv preprint arXiv:1607.06450, 2016.
[43]	The Abilene Observatory Data Collections[Z]. http://abilene.internet2.edu/observatory/data-collections.html, 2004.
[44]	Uhlig S, Quoitin B, Lepropre J, et al. Providing public intradomain traffic matrices to the research community[J]. ACM SIGCOMM Computer Communication Review, 2006,36(1):83-86. doi: 10.1145/1111322
[45]	Zheng Z, 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 (DSN). IEEE, 2008: 392-397.
[46]	Bader B W, Kolda T G. MATLAB Tensor Toolbox Version 2.6. Available online.(February 2015)[Z]. URL http://www.sandia.gov/~tgkolda/TensorToolbox/index-2.6.html, 2015.
[47]	Wen Z, Yin W, 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. doi: 10.1007/s12532-012-0044-1

名称	计算方式
ER	$\frac{\sqrt{\sum_{(i,j,k)\in \bar{\Omega}}(x_{ijk}-\hat{x}_{ijk})^{2}}}{\sum_{(i,j,k)\in \bar{\Omega}}x_{ijk}^{2}}$
MAE	$\frac{1}{\|\bar{\Omega}\|}\sum_{(i,j,k)\in \bar{\Omega}}\|x_{ijk}-\hat{x}_{ijk}\|$
RMSE	$\sqrt{\frac{1}{\|\bar{\Omega}\|}\sum_{(i,j,k)\in \bar{\Omega}}(x_{ijk}-\hat{x}_{ijk})^{2}}$

网络性能数据恢复算法

An Algorithm for Network Monitoring Data Recovery

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 7

参考文献 47

相关文章 5

编辑推荐

Metrics

本文评价

[1]	石雪梅,朱克亮,张祥民,张树涛,陈良锋. 基于生成对抗网络的有遮挡人脸修复方法[J]. 数据与计算发展前沿, 2022, 4(4): 123-131.
[2]	肖楠,周明珠,邢军,罗泽,李晓辉. 基于高分辨率网络和注意力机制的真伪卷烟包装鉴别[J]. 数据与计算发展前沿, 2021, 3(5): 118-129.
[3]	张猛,李健. 鸟类音频数据预处理方法[J]. 数据与计算发展前沿, 2021, 3(5): 130-140.
[4]	陈子健,李俊,岳兆娟,赵泽方. 基于自编码器与属性信息的混合推荐模型[J]. 数据与计算发展前沿, 2021, 3(3): 148-155.
[5]	刘晓东,倪浩然. 深度学习技术在学科融合研究中的应用[J]. 数据与计算发展前沿, 2020, 2(5): 99-109.