第 43 卷 第 6 期 电 子 科 技 大 学 学 报 Vol.43 No.6
2014年11月 Journal of University of Electronic Science and Technology of China Nov. 2014
分布式环境下动态网络时延矩阵正则化重建
王 聪，张凤荔，杨晓翔
(电子科技大学计算机科学与工程学院
成都 611731)
【摘要】时延矩阵的重建是延迟敏感型应用优化的重要基础。在深入探讨分布式网络环境下一类基于矩阵分解的非梯度
下降重建算法鲁棒性的基础上，分析了时延序列抖动对算法中的不适定与病态问题反演求解的强烈影响。为了降低这种影响，
在引入正则化项改善系数矩阵谱特征的基础上，提出了一种时延序列的中值-卡尔曼时空联合滤波框架以抑制抖动污染，并通
过统计特征的提取实现了拓扑突变感知，从而提高动态环境下的时延矩阵重建的性能。实验结果表明，滤波重建算法可在保
留时延序列主要统计特征的基础上有效避免时延噪声造成的性能损失，并提供平稳的时延估计服务，始终将应力系数保持在
较低的水平上。
关 键 词 滤波器; 网络测量; 矩阵重建; 正则化方法
中图分类号 TP3936.01 文献标志码 A doi:10.3969/j.issn.1001-0548.2014.06.022
A Distributed Regularization Method for Latency
Matrix Completion in the Wild
WANG Cong, ZHANG Feng-li, and YANG Xiao-xiang
(School of Computer Science and Engineering, University of Electronic Science and Technology of China Chengdu 611731)
Abstract Latency matrix completion is an important foundation of latency-sensitive applications
optimization. On the basis of the in-depth discussion of the robustness of a kind of matrix-factorization based
non-gradient descending completion methods, this paper analyzes the significant impact to the intrinsic ill-posed
and ill-conditioned inverse problems in the methods caused by the oscillations of the latency sequences. To
mitigate the impact and improve the performance of the matrix completion methods in the wild, a regularization
factor is introduced to improve the spectrum signature of the coefficient matrix, a median-Kalman filter, a
time-spatial federated filtering scheme, is proposed to smooth the latency sequences, and then the topology
mutation is obtained through extracting the statistic characters of the latency sequences. The experiments show that
our method can avoid the performance degradation caused by noises without losing the major characteristics of the
latency sequences, provide robust latency estimation capability, and keep the stress coefficient at a low level about
0.13 during the whole life cycle of the network.
Key words filter; internet measurement; matrix completion; regularization method
收稿日期：
2013 05 15；修回日期：2014 05 22
基金项目：
国家高技术研究发展计划(2011AA010706)；国家自然科学基金(61133016)
作者简介：王聪(1981 )，男，博士生，主要从事IP网络测量与增强技术方面的研究.
时延敏感型应用在网络环境下占据重要地位，
诸多互联网应用性能，包括内容分发
[1]
、电子竞技
[2-3]
、云计算
[4-5]
及洋葱路由
[6]
等都强烈依赖于实体间
的传输时延。点对点的测量虽然能准确感知时延矩
阵的任一元素，却因为其O(n
2
)的测量负载而无法广
泛地部署。如何利用有限的不完整的测量数据尽可
能精确地填充和重建时延矩阵，一直是一个热点研
究领域。
文献[7]提出时延矩阵具备明显的近似稀疏性，
即矩阵仅有少量的特征值具有较大的模，而这种稀
疏特征已在文献[8]中得到了理论上的深入分析与阐
述。按照文献[8]的观点，虽然时延矩阵缺失元素的
填充是一个欠定问题，但在施加必要的稀疏性约束
以限制模型复杂度后，该问题一般可得到唯一的可
行解
[9]
。这种约束通常为矩阵的零范数或迹范数的
极小化约束。然而在具体的应用环境，如对等网络
或分布式控制系统中，时延矩阵通常由全体网络节
点共同维护，难以抽取一个全局一致的时延矩阵映
像。折中方法是给出一个能满足重建矩阵稀疏性约
束的零范数先验估计，并将重建矩阵的左右特征向
量分布在全网中，使得每个参与计算的节点均持有
一个行向量和列向量，节点可通过向量的点积运算
资源评论
weixin_38722164
- 粉丝: 2
- 资源: 912
