网络透视中的链路延迟分布推理算法研究

摘要

网络监测对于网络管理者来说具有十分重要的意义，但是对网络性能参数的直接测量在一些情况下是不可行的。网络透视作为一种有效的解决方法被提了出来，它根据端到端的测量结果推理网络内部链路参数，将数理统计的思想引入了网络测量。
　　本文对网络透视技术进行了分析，在此基础上深入研究了网络透视中的链路延迟分布推理算法，在链路延迟分布推理的基本EM算法的基础上通过效率方面的改进，设计出了适合于大规模网络透视的高效链路延迟分布推理算法ACC-EM算法，讨论了影响该算法准确性和效率的因素，并考虑了该算法在特殊情况下的应用方法。
　　文章首先明确提出了网络透视研究的意义，概括了网络透视研究的分类，介绍了网络透视的主要应用情况，总结了网络透视研究的发展方向。针对大规模网络透视算法的效率问题，本文以链路延迟分布推理的基本EM算法为参照，提出了几点降低延迟推理算法时间复杂性的方法，即减小矢量搜索空间，窗口内加速，窗口间加速，并行探测的方法，设计出了更加高效的ACC-EM算法，给出了该算法的具体实现过程，讨论了影响该算法准确率和效率的几方面因素，即探测包的数量，延迟粒度的大小，拓扑结构中接收节点的个数和拓扑的层数，并将算法应用到多源点和缺失数据的特殊情况中，最大程度的利用了探测数据，扩大了算法的应用范围。
　　实验结果表明，本文设计的适合大规模网络透视的链路延迟分布推理算法ACC-EM在效率上明显优于基本EM算法，在特殊情况下也可获得比较准确的推理结果，对大规模网络监测具有出很好的应用意义。

目录

网络透视中的链路延迟分布推理算法研究

RESEARCH ON LINK DELAY DISTRIBUTION INFERENCE ALGORITHM IN NETWORK TOMOGRAPHY

摘要

Abstract

第1章 绪论

1.1 课题背景

1.2 网络测量

1.2.1 网络测量的要素

1.2.2 网络测量的种类和常用指标

1.2.3 网络测量的体系结构

1.2.4 网络测量的应用

1.2.5 网络测量的研究现状

1.3 网络透视

1.3.1 网络透视研究的意义

1.3.2 网络透视研究的分类

1.3.3 网络透视的应用

1.3.4 网络透视的研究方向

1.4 本文的主要研究内容

第2章 网络透视的理论基础

2.1 网络透视的问题描述

2.2 网络透视的研究方法

2.2.1 拓扑结构

2.2.2 探测机制

2.2.3 随机假设

2.3 延迟推理算法的基本思想

2.3.1 极大似然估计MLE

2.3.2 期望最大化方法EM

2.4 可识别性

2.5 延迟推理算法的性能评定准则

2.6 本章小结

第3章 链路延迟分布推理算法的研究

3.1 模型描述

3.2 链路延迟分布推理的EM算法

3.3 链路延迟分布推理算法的改进

3.3.1 算法本身估计过程的改进

3.3.2 窗口内估计过程的改进

3.3.3 窗口间估计过程的改进

3.3.4 探测方式的改进

3.4 ACC-EM算法的基本应用

3.5 ACC-EM算法的收敛性

3.6 本章小结

第4章 链路延迟分布推理算法的实例分析

4.1 影响ACC-EM算法性能的因素

4.1.1 探测包数量对算法性能的影响

4.1.2 延迟粒度大小对算法性能的影响

4.1.3 拓扑结构对算法性能的影响

4.2 ACC-EM算法与EM算法的效率比较

4.3 特殊情况下的延迟推理算法

4.3.1 多源点情况下的延迟推理算法

4.3.2 缺失数据情况下的延迟推理算法

4.4 本章小结

结论

参考文献

哈尔滨工业大学硕士学位论文原创性声明

哈尔滨工业大学硕士学位论文使用授权书

攻读学位期间发表的学术论文

致谢