论文题目: IP网络带宽测量的模型与算法的研究
论文类型: 博士论文
论文专业: 计算机科学与技术
作者: 刘湘辉
导师: 殷建平
关键词: 带宽,测量,模型,算法,完全,难的,近似程度
文献来源: 国防科学技术大学
发表年度: 2005
论文摘要: 随着IP网络应用日益膨胀，各种服务层出不穷。对网络管理者来说，需要了解各个节点之间的带宽信息，以支持可区分的服务。这些及时的带宽信息对于许多网管业务，如主动式和被动式的资源管理、流量工程、端到端的服务质量保证，显得尤为重要。特别是现代的网络管理系统注重于服务级、应用级的管理，带宽的测量过程需要更大的数据量和更高的数据采集频率。 根据是否发送探测包，IP网络带宽测量方法可分为被动测量和主动测量。被动测量不向网络发送探测包，而是监听网络中的IP报文来推测网络的带宽情况，但了解网络全局各链路带宽数值时，需要专门的统一时钟和数据收集机制。主动测量向网络发送探测包，通过对发送的实际业务量的测量来反映网络提供给用户的带宽参数，但这种方法可能因为设置过多的观测节点而增加网络的额外负担。 目前，网络流量的测量方法还只是针对特定感兴趣的链路、路径，人工合理地规划网络的观测节点，并在这些节点上安装特定的测量软件。这种方法难以扩展，不便于动态适应网络的变化。我们强调测量方法的关键是既要准确获取网络流量参数，又要尽量减少数据收集对实际网络传输数据造成的影响。基于此，本文主要研究带宽测量的监测节点的布置问题，对于主、被动测量不同的应用背景提出了不同的带宽测量模型，主要的创新点如下： 1、在被动带宽测量研究中，由于挖掘节点上的流量约束信息，可以把有效观测网络实际使用带宽的问题抽象为求给定图G的最小弱顶点覆盖集的问题，我们证明了最小弱顶点覆盖问题是NP完全的，同时将模型扩展为基于流划分的弱顶点覆盖问题，并对模型的误差做了分析。 2、由于弱顶点覆盖问题是NP难的，至今尚无多项式求解算法，退一步考虑，我们只好寻找模型的多项式时间内的近似解。为此我们设计了贪婪算法和原始对偶算法来求解该问题。算法的近似程度从2(lnd+1)提高到2，其中d是图中最大的顶点度。 3、被动带宽测量虽然能够实现对观察点网络行为的详尽了解，但在了解网络全局各链路带宽的数值时，需要专门的数据收集机制。因此如何既能减少数据收集过程对实际网络上传输数据的影响，又能保证全局视图对数据共享的要求是一个关键的问
论文目录:
目录
图表索引
摘要
ABSTRACT
第一章 绪论
§1.1.IP网络服务质量与IP网络带宽测量的关系
1.1.1.IP网络服务质量的提出与现状
1.1.2.IP网络服务质量的定义与服务质量保证
1.1.3.IP网络带宽测量与服务质量的关系
1.1.4.IP网络带宽测量的重要性
§1.2.IP网络带宽测量的关键技术及发展趋势
1.2.1.引言
1.2.2.IP网络带宽测量的关键技术
1.2.3.IP网络带宽测量的现状与发展趋势
§1.3.本文的主要研究内容
第二章 带宽测量的基本概念和研究前提
§2.1.带宽定义
§2.2.带宽测量方法分类
§2.3.研究前提
2.3.1.IP网络拓扑结构的测量
2.3.2.IP网络拓扑建模
2.3.3.IP网络流量模型
2.3.4.测量协作点之间的统一时钟
2.3.5.计算复杂性理论
§2.4.总结
第三章 基于弱顶点覆盖集的带宽测量模型
§3.1.弱顶点覆盖模型
§3.2.求解弱顶点覆盖模型的难解性证明
§3.3.基于流划分的弱顶点覆盖模型
§3.4.受限弱顶点覆盖集模型
§3.5.弱顶点覆盖模型的误差分析
3.5.1.矩阵条件数及增长因子的基本概念
3.5.2.误差的产生与表示
§3.6.总结
第四章 弱顶点覆盖问题的求解
§4.1.贪婪策略求弱顶点覆盖问题
4.1.1.算法描述
4.1.2.算法近似程度分析
4.1.3.算法时间复杂性分析
§4.2.原始对偶方法求解弱顶点覆盖问题
4.2.1.弱顶点覆盖集的约束关系
4.2.2.弱顶点覆盖集的整数规划形式
4.2.3.算法构造与分析
§4.3.基于流划分的弱顶点覆盖问题求解
§4.4.受限弱顶点覆盖问题求解
§4.5.弱顶点覆盖问题的不可近似性
§4.6.试验验证
§4.7.总结
第五章 分布式网络的监测模型
§5.1.延迟约束的分布式监测模型
5.1.1.模型描述
5.1.2.模型的难解性证明
5.1.3.整数规划形式
§5.2.带宽约束的分布式监测模型
5.2.1.模型描述
5.2.2.模型的难解性证明
5.2.3.带宽约束的分布式监测模型整数规划形式
§5.3.分布式网络监测模型的衍生
§5.4.总结
第六章 分布式网络的监测模型的求解
§6.1.整数规划问题的计算复杂性
§6.2.延迟约束的分布式监测模型的求解
§6.3.带宽延迟约束的分布式监测模型的求解
§6.4.试验验证
§6.5.结论
第七章 多点主动式带宽测量模型
§7.1.主动式带宽测量方法介绍
7.1.1.变包技术
7.1.2.包对技术
7.1.3.两种技术的比较
§7.2.模型描述
§7.3.模型扩展
7.3.1.含维护代价边覆盖问题
7.3.2.预算受限问题
§7.4.总结
第八章 研究总结与展望
§8.1.研究内容总结
§8.2.研究展望
致谢
攻读博士学位期间撰写的文章
攻读博士学位期间参加的科研课题
参考文献
发布时间: 2006-09-22
相关论文
- [1].IP网络性能测量技术研究[D]. 谢高岗.湖南大学2002
- [2].高速互联网性能测量若干关键技术研究[D]. 王俊峰.电子科技大学2004
- [3].IP网络测量和业务性能研究[D]. 朱畅华.西安电子科技大学2004
- [4].有线/无线网络中基于网络测量的拥塞控制研究[D]. 邓晓衡.中南大学2005
- [5].P2P流媒体内容分发关键技术研究[D]. 刘亚杰.国防科学技术大学2005
- [6].对等网络性能测量与改善[D]. 李江涛.北京邮电大学2006
- [7].网络流量特征研究和分布式被动测量系统设计[D]. 马维旻.中国科学院研究生院（计算技术研究所）2004
- [8].大规模网络IP流行为特性及其测量算法研究[D]. 周明中.东南大学2006