基于主动和被动测量的网络测量技术、模型和算法研究

论文题目: 基于主动和被动测量的网络测量技术、模型和算法研究

论文类型: 博士论文

论文专业: 计算机科学与技术

作者: 蔡志平

导师: 殷建平

关键词: 网络测量,主动测量,被动测量,演化网络,收集框架,测量模型,测量技术,近似算法

文献来源: 国防科学技术大学

发表年度: 2005

论文摘要: 随着Internet应用的急剧增长，越来越多的网络应用程序需要了解网络延迟、带宽、吞吐率等网络性能参数，以支持可区分的服务。这些及时的网络性能数据对于许多网管业务，如主动式和被动式的资源管理、流量工程以及端到端的服务质量保证，显得尤为重要。特别是现代的网络管理系统注重于服务级、应用级的管理，网络测量的频率会越来越快，需求的网络性能数据也会越来越多。 近年来网络测量技术和网络测量模型已经成为研究的热点。网络测量方式可以分为主动测量和被动测量两种。主动测量方式通过向目标链路或目标节点发送探测包，来测量链路或端到端的延迟、带宽和丢包率等网络性能参数。被动测量方式通过接入网络的测量探针，记录和统计网络链路或节点上业务流量的信息。本文对基于主动测量和被动测量的网络测量技术、网络测量模型及其近似算法进行了深入研究。本文工作的主要贡献和创新总结如下： (1) 分布式主动测量模型中测量分配问题研究 主动测量的代价包括测量站部署代价和测量代价两个部分。测量站的数量和位置确定下来以后，为了减少测量代价就需要优化测量分配方案，也就是确定链路由哪一个测量站来负责测量。 本文提出了分布式主动带宽测量模型中的测量分配问题，给出了测量分配问题的整数规划形式，并且指出测量分配的最优化问题是NP难的。基于贪婪策略和动态规划的思想，给出了近似比为2的启发式算法，并且通过仿真实验证明了近似算法的有效性。带宽测量分配问题及其解决思路和近似算法，同样可以用来解决测量延迟、丢包率等其它网络性能参数，对分布式主动测量系统的设计和实现具有很强的指导作用。 (2) 链路带宽被动监测模型优化问题研究及其近似算法 被动监测模型的研究重点在于如何部署尽量少的监控器去监控全网的性能，这样一方面减少了安装和维护代价，另一方面也可以减少收集网管数据带来的额外网络流量。利用路由器流守恒规律可以有效减少网管代理的安装数量，从而减少安装代价和收集流量，实现低负载的链路带宽有效监控。 基于流守恒的网络链路带宽被动监测模型的最优化问题可以抽象为无向图中的弱顶点覆盖问题。论文给出了一个从顶点覆盖问题到弱顶点覆盖问题的近似保持归约。根据这个近似保持归约，要想找到弱顶点覆盖问题的一个常数近似比小于2的近似算法也是非常困难的。利用近似算法的原始对偶方法，可以得到一些近似比为2的近似算法。这些算法同样可以应用于解决带禁点的弱顶点覆盖问题。 (3)链路约束的分布式网络收集框架优化问题研究及其近似算法 为了收集实时的网络性能数据，收集过程需要一个稳定可靠的低延迟路由。链路延迟或者路由跳数的限制决定了收集节点负责查询和收集的监控节点的数量是有限的。链路约束的分布式网络收集框架的优化目标是部署尽量少的收集节点收集到所有监控节点的性能数据，其最优化问题是NP难的。论文指出可以把链路约束的分布式收集框架的最优化问题映射到集合覆盖问题，利用贪婪算法可得到

论文目录:

图索引

表索引

摘要

ABSTRACT

第1章 绪论

§1.1 研究背景和意义

1.1.1 网络发展面临的挑战

1.1.2 网络测量研究的意义

§1.2 网络测量研究概述

1.2.1 网络测量的对象

1.2.2 主动测量和被动测量

1.2.3 常用的网络测量工具

1.2.4 国内外相关研究项目

§1.3 论文研究内容

§1.4 论文主要贡献

§1.5 论文组织结构

第2章 网络测量模型和算法进展

§2.1 引言

§2.2 被动测量模型和算法

2.2.1 测量代价和测量回报

2.2.2 挖掘网络流信息

§2.3 主动测量模型和算法

2.3.1 有约束的测量站部署

2.3.2 一般的测量站部署

2.3.3 测量分配

2.3.4 容错的测量站部署和测量分配

§2.4 分布式收集框架

§2.5 其它网络测量模型

2.5.1 演化网络

2.5.2 结合主动与被动的测量技术

2.5.3 动态可移动测量

§2.6 小结

第3章 分布式链路带宽主动测量模型中测量分配问题研究

§3.1 概述

§3.2 相关研究工作

§3.3 测量分配问题

3.3.1 问题提出

3.3.2 问题描述

3.3.3 整数规划形式

3.3.4 测量分配问题的难解性

§3.4 测量分配问题的近似算法

3.4.1 近似算法

3.4.2 算法的近似比

§3.5 仿真实验

§3.6 小结

第4章 链路带宽被动监测模型中弱顶点覆盖问题难解性研究

§4.1 概述

§4.2 弱顶点覆盖问题

4.2.1 有效测量集

4.2.2 流守恒规律

4.2.3 弱顶点覆盖问题

4.2.4 相关研究工作

§4.3 近似保持归约

4.3.1 近似保持归约

§4.4 近似算法

4.4.1 整数规划形式

4.4.2 弱顶点覆盖问题的原始对偶算法

§4.5 带禁点的弱顶点覆盖问题

§4.6 小结

第5章 链路约束的网络收集框架的优化问题研究

§5.1 引言

§5.2 链路约束的分布式网络收集框架的优化问题

5.2.1 延迟约束

5.2.2 代价函数

5.2.3 整数规划形式

5.2.4 优化问题的难解性

§5.3 收集框架优化问题的解决方案

5.3.1 把优化问题映射到集合覆盖问题

5.3.2 集合覆盖问题的难解性

5.3.3 贪婪算法

§5.4 链路约束值对优化解的影响

5.4.1 仿真网络设置

5.4.2 最短距离

5.4.3 链路约束的影响

5.4.4 讨论

§5.5 小结

第6章 链路约束的分布式演化网络监测模型

§6.1 引言

§6.2 系统模型

6.2.1 代价函数

6.2.2 整数规划

6.2.3 复杂性分析

§6.3 近似算法

6.3.1 贪婪算法

6.3.2 贪婪算法的时间复杂性

6.3.3 贪婪算法的近似比

§6.4 小结

第7章 网络延迟主动测量结果的被动测量校准方法

§7.1 引言

§7.2 利用用户包数量校准主动测量数据

§7.3 利用相邻探测包的测量值变化校准主动测量数据

§7.4 数据包延迟变化分析

§7.5 仿真结果

7.5.1 单跳拓扑模拟结果

7.5.2 多跳拓扑模拟结果

§7.6 小结

第8章 总结和展望

§8.1 工作总结

§8.2 研究展望

致谢

攻读博士学位期间发表的主要论文

作者在攻读博士期间参与的主要研究工作

参考文献

发布时间: 2006-09-22

参考文献

• [1].网络测量中的抽样技术研究[D]. 潘乔.西安电子科技大学2008
• [2].云环境下网络性能测量与服务优化的研究[D]. 丁浩.北京科技大学2016
• [3].分组抽样下网络测量可扩展性问题及其关键算法的研究[D]. 张海.华南理工大学2010
• [4].P2P网络测量与安全关键技术研究[D]. 余杰.国防科学技术大学2010
• [5].网络可重构测量关键技术研究[D]. 王晶.解放军信息工程大学2015
• [6].网络测量数据隐私保护若干关键技术研究[D]. 张沛.北京邮电大学2012
• [7].基于主动测试的网络性能监测技术研究[D]. 曾彬.湖南大学2009
• [8].端到端高精度网络宽测量与流量特征监测技术研究[D]. 刘俊.湖南大学2009
• [9].基于异构关系的微博网络意见动力学研究[D]. 樊鹏翼.国防科学技术大学2013
• [10].互联网在宏观拓扑结构下传播行为的研究[D]. 李超.东北大学2009

相关论文

• [1].IP网络性能测量技术研究[D]. 谢高岗.湖南大学2002
• [2].有线/无线网络中基于网络测量的拥塞控制研究[D]. 邓晓衡.中南大学2005
• [3].网络流量特征研究和分布式被动测量系统设计[D]. 马维旻.中国科学院研究生院（计算技术研究所）2004
• [4].端到端互联网性能监测技术研究[D]. 黎文伟.湖南大学2006
• [5].基于主动测量的网络性能分析[D]. 孙红杰.哈尔滨工业大学2007

标签：网络测量论文;  主动测量论文;  被动测量论文;  演化网络论文;  收集框架论文;  测量模型论文;  测量技术论文;  近似算法论文;