基于稀疏性的网络断层扫描研究

发布时间：2020-11-11 03:35

　　 随着互联网技术的飞速发展,网络的规模和复杂性日益提高,准确及时的性能数据对网络管理至关重要。然而,庞大的现代网络以及现有测量技术的限制使得收集完整的测量结果是不切实际的。网络断层扫描是从医学中CT扫描衍生出来的概念,其核心是通过易于观察的量来推断所需测量的量。网络断层扫描可分为两大类,第一类用于推导网络内部链路的性能指标,如链路时延、丢包率等;第二类用于估计网络中源到目的的流量强度。不管是推导网络链路的性能指标还是估计网络OD流,直接测量通常是极其困难的。网络断层扫描并非直接测量这些性能指标,而是从其他易得到的测量量估计出来。然而,从易于观察的量来推断网络的性能数据往往是一个非常难的问题,当前大多数工作采用统计推理的方式。在本文中,我们分析网络数据具有稀疏特性,即网络性能指标本身具有稀疏性或在某些字典下具有稀疏性。作为一种新兴的信号分析和综合方法,信号的稀疏表示吸引了研究者的大量关注,已成功应用到信号编码、压缩感知、盲源分离等领域。当前一些网络断层扫描工作已经展示了网络数据的稀疏特性,因而我们期待充分挖掘网络数据的这种特性能得到良好的估计性能。本文针对这个交叉领域展开研究,取得以下相应成果:1.作为整个论文的基石,本文首先分析了网络数据的稀疏性,包括网络链路参数如延时、丢包率的稀疏性,并以实际网络流量为例,阐述了OD流在基变换下的稀疏表达。然后提出利用稀疏性从路径测量进行链路估计,除了压缩感知领域经典的l_1最小化,特别提出了一种稀疏贝叶斯学习的方法对网络链路状态进行推理。实验结果验证了所提方案的有效性。2.针对网络断层扫描中的测量路径选择问题,提出了一种基于路由矩阵互相干值的路径选择算法。该方法利用了链路参数的固有稀疏性,选择那些路径使得构造的路由矩阵的互相干值最小。首先证明了该方法的NP完全性,并采用子模理论分析优化目标性质。然后提出一种贪婪式算法,在每次迭代,算法优先选择测量路径使得互相干值增长量最小。实验结果证实所提方案能选择少量的测量路径数,同时保持较高的链路辨识度。3.除了链路状态的稀疏特征,本文进一步探索了链路时间相关性,提出一种时空网络拥塞诊断方法:加权l_1最小化方法。该算法结合了链路性能参数的稀疏性和拥塞先验概率,如果把稀疏性看作是链路参数的空间属性的话,那么先验概率就是链路参数的时间相关性。首先在理论上分析了加权l_1最小化的恢复误差,并指出选取合适的权值最终会改善恢复精度。然后采用最大后验概率的方法使用拥塞先验概率来确定权值。实验结果证实所提方案优于仅利用稀疏性的方法或仅利用拥塞概率的算法,具有较高的估计精度。4.针对网络中的OD流矩阵估计问题,提出一种利用流量矩阵稀疏表达的估计方法。该方法将小波基的一部分作为字典表达序列,并以OD流矩阵的列l_1范数的和最小化为优化目标,成功解决了流量估计中的病态性问题。本文从理论上证明所提出方法的无误差估计条件。由于真实的OD流量中通常含有异常分量,因此分别对两者进行建模能得到更精确的结果。理论分析若异常分量和正常分量在各自的字典下充分稀疏,则可无误差恢复OD流矩阵的正常分量和异常分量。实验结果证实从链路测量估计OD流矩阵时,所提方案不管是异常检测还是流量矩阵恢复均具有较高的精度。通过解决上述问题,将稀疏性理论引入到网络断层扫描中,取得了比传统方法更好的结果。同时,由于本文包含了若干关于稀疏性的理论分析,这些分析得出的结论也丰富了稀疏信号处理相关领域的理论体系。
【学位单位】：电子科技大学
【学位级别】：博士
【学位年份】：2018
【中图分类】：TP393.0
【文章目录】：
摘要
ABSTRACT
第一章 绪论
    1.1 研究工作的背景与意义
    1.2 网络断层扫描概述
        1.2.1 基本概念
        1.2.2 基本原理
    1.3 网络断层扫描国内外研究历史与现状
        1.3.1 探测路径选择
        1.3.2 链路参数估计
            1.3.2.1 链路时延估计
            1.3.2.2 链路丢包率估计
            1.3.2.3 链路拥塞检测
        1.3.3 流量矩阵估计
        1.3.4 稀疏性网络断层扫描
    1.4 本文的主要贡献与创新
    1.5 本论文的结构安排
第二章 网络数据的稀疏性及稀疏求解方法研究
    2.1 引言
    2.2 网络数据稀疏模型
        2.2.1 稀疏信号
        2.2.2 网络链路参数的稀疏性
        2.2.3 OD流的稀疏表达
    2.3 链路参数的稀疏求解
        2.3.1 线性方程的稀疏解
1优化寻求稀疏解'>        2.3.2 l₁优化寻求稀疏解
        2.3.3 稀疏贝叶斯学习
    2.4 实验与分析
        2.4.1 时延仿真
        2.4.2 实际网络数据分析
    2.5 本章小结
第三章 基于稀疏性的探测路径选择算法
    3.1 引言
    3.2 模型和符号定义
    3.3 互相干最小算法
        3.3.1 压缩感知测量矩阵设计
        3.3.2 测量路径选择
            3.3.2.1 设计目标
            3.3.2.2 算法流程
    3.4 互相干最小算法的可扩展性
    3.5 实验与分析
        3.5.1 互相干最小算法对最佳解的近似
        3.5.2 链路参数估计
        3.5.3 实验结果及分析
    3.6 本章小结
第四章 基于稀疏性的时空网络拥塞诊断
    4.1 引言
    4.2 网络模型
1优化'>    4.3 加权l₁优化
1优化的恢复误差'>        4.3.1 加权l₁优化的恢复误差
        4.3.2 权重的确定
        4.3.3 先验概率的估计
    4.4 整体框架
1算法的讨论'>        4.4.1 加权l₁算法的讨论
    4.5 实验与分析
        4.5.1 网络拓扑
        4.5.2 模拟器
        4.5.3 性能指标
        4.5.4 实验结果及分析:丢包率估计
        4.5.5 实验结果及分析:拥塞检测
        4.5.6 实际拓扑分析
    4.6 本章小结
第五章 基于稀疏性的流量矩阵估计和异常点检测
    5.1 引言
    5.2 模型和符号定义
    5.3 基于稀疏性的流量矩阵估计
        5.3.1 OD流的稀疏表达
1最小化估计'>        5.3.2 列l₁最小化估计
    5.4 异常流量
        5.4.1 基于稀疏性的流量矩阵估计和异常点检测算法
    5.5 实际考虑
    5.6 实验与分析
        5.6.1 稀疏性对估计误差的影响
        5.6.2 OD流量矩阵估计和异常检测
            5.6.2.1 数据集
            5.6.2.2 性能指标及比对方法
            5.6.2.3 实验结果
            5.6.2.4 结合部分OD流数据进行估计
    5.7 本章小结
第六章 结束语
    6.1 全文总结
    6.2 后续工作展望
致谢
参考文献
攻博期间取得的研究成果

【参考文献】

相关期刊论文 前1条

1 费高雷;胡光岷;;基于k阶马尔可夫链的单播网络丢包层析成像[J];电子与信息学报;2011年09期

本文编号：2878687