论文题目: 因特网QoS路由算法研究
论文类型: 博士论文
论文专业: 计算机科学与技术
作者: 郑彦兴
导师: 窦文华
关键词: 服务质量路由,最优,度量空间,约束最短路径,多约束路径,多约束优化路径,法线测量,覆盖概率,前瞻
文献来源: 国防科学技术大学
发表年度: 2005
论文摘要: 日益增多的网络应用,使得因特网正从尽力而为的网络,进化到对不同网络应用提供不同等级服务质量的网络。因而,网络学术界对网络能否提供QoS能力非常关注,并提出了包括IntServ,DiffServ,MPLS等在内的几个支持QoS的网络模型。然而,目前因特网提供QoS的能力仍然不能满足不同应用的要求,其中重要原因之一是缺乏既有效又实用的解决手段,因而对支持QoS的网络的研究是计算机网络的一个研究热点。 QoS路由(QoSR)是支持QoS的网络体系结构中的重要组成部分。设计有效的QoS路由算法是QoS路由面临的关键问题之一,旨在利用QoS路由协议提供的网络状态信息,为不同网络应用寻找满足QoS需求的可行路径。论文针对QoS路由算法设计问题进行了深入研究,并提出了有效的QoS路由算法。 在QoS路由算法研究过程中,形成了三类重要子问题:约束最短路径问题(RSP);多约束路径问题(MCP);多约束优化路径问题(MCOP)。论文研究发现,这三类子问题都可以通过转化为一个特殊的多目标优化问题而获得解决,考虑到Pareto最优是多目标优化问题中的重要概念,论文首次把Pareto最优的相关概念引入到QoS路由中,并根据这些重要概念,研究了QoS度量空间划分问题,建立了基于Pareto最优的QoS度量空间区分框架POPF。在POPF中,QoS度量空间被划分成三个部分:可行区域、不可行区域以及NP完全区域,这些区域具有明确的实际意义。论文着重讨论了两可加约束QoS路由问题Pareto层的分布特性,对其中Pareto最优点的分布进行了深入的研究。指出Pareto最优点的数目和分布都对QoS度量空间划分产生影响,并给出了一种计算Pareto最优点的方法。POPF不但为在QoS路由中运用Pareto最优概念提供了理论基础,而且从算法采用的搜索方式,到算法的终止条件,甚至路由请求的生成方式等方面,都对QoS路由算法的设计和评估具有一定的指导作用。 论文首先提出了用来解决两可加约束的QoS路由算法。算法充分利用了POPF中的重要结论,因此具有良好的前瞻特性,避免了大量冗余计算。然后,论文定义了基于法线测量的非线性路径长度方程NM_LEN,并基于NM_LEN提出了解决MCP问题的NM_MCP算法。NM_MCP算法分为两个阶段:预计算阶段和在线计算阶段。在预计算阶段,算法具有较小的执行周期,在一定程度上减小了不精确网络状态信息对算法的影响。另一方面,即使需要在线计算,NM_MCP算法也只调用一次Dijkstra算法。由于预计算阶段采用线性搜索方法,而在线计算阶段则采用非线性搜索方法,因而NM_MCP算法成功结合了预计算和在线计算,线性搜索和非线性搜索的优点。仿真实验表明,与
论文目录:
摘要
ABSTRACT
第一章 绪论
1．1 课题研究的背景及意义
1．1．1 QoS研究框架
1．1．2 QoS路由
1．1．3 IP QoS体系结构对QoS路由的需求
1．2 QoS路由算法概述
1．2．1 QoS度量
1．2．2 QoS路由算法分类
1．3 Qos路由算法研究现状
1．3．1 RSP算法
1．3．2 MCP算法
1．3．3 基于不精确网络状态信息的QoS路由算法
1．4 论文研究内容
1．5 论文的组织结构
1．6 论文的主要贡献
第二章 基于Pareto最优的QoS度量空间划分
2．1 QoS度量空间
2．2 Pareto最优
2．3 基于Pareto最优的QoS度量空间划分框架(POPF)
2．3．1 理想情况下的QoS度量空间划分
2．3．2 实用的QoS度量空间划分
2．4 Pareto最优点的位置与QoS度量空间划分
2．5 获得Pareto最优点
2．6 两约束MCMOP问题的Pareto层
2．7 POPF与QoS路由算法设计
2．7．1 POPF与线性搜索
2．7．2 POPF与非线性搜索
2．7．3 POPF与算法的终止条件
2．8 小结
第三章 两可加约束的QoS路由算法
3．1 RSP与MCP在Pareto最优意义上的统一
3．2 冗余计算问题
3．3 DMCA算法
3．3．1 算法的理论基础
3．3．2 算法描述
3．3．3 算法性能评估
3．4 HDSA算法
3．4．1 搜索结果记录策略
3．4．2 搜索策略
3．4．3 启发信息
3．4．4 算法描述
3．4．5 性能评估
3．5 小结
第四章 多约束QoS路由算法
4．1 概述
4．2 NM_MCP算法
4．2．1 预计算阶段
4．2．2 在线计算阶段
4．2．3 算法描述
4．2．4 搜索范例
4．2．5 改进的NM_MCP算法
4．2．6 性能评估
4．3 小结
第五章 不精确网络状态信息下的QoS路由
5．1 概述
5．2 问题描述
5．3 不精确网络状态信息下的QoS度量空间划分
5．3．1 D(p)和C(p)的分布
5．3．2 D(p)和C(p)的方差界
5．3．3 D(p)和C(p)的链路界
5．3．4 路径可行概率计算
5．4 MP-TACPA 算法
5．4．1 MP-TACPA算法概述
5．4．2 生成候选路径
5．4．3 MP-TACPA算法描述
5．5 性能评估
5．5．1 仿真环境
5．5．2 算法成功率
5．5．3 算法的平均计算代价及响应速度
5．5．4 方差界及链路界对算法性能的影响
5．6 讨论
5．6．1 MP-TACPA与其它基于触发机制的链路状态更新协议
5．6．2 性能损失
5．6．3 从两可加约束到多可加约束的扩展
5．7 小结
第六章 结论
6．1 论文所作的工作
6．2 课题研究展望
致谢
作者攻读博士学位期间发表的主要学术论文和主要科研工作
参考文献
发布时间: 2005-11-07
参考文献
- [1].网络QoS及性能评价中若干问题的建模与分析[D]. 方建超.上海大学2004
- [2].Internet QoS路由研究[D]. 江昊.武汉大学2004
- [3].网络中QoS路由问题的研究[D]. 张品.电子科技大学2004
- [4].Internet行为测量与分析研究[D]. 毕经平.中国科学院研究生院（计算技术研究所）2002
- [5].互联网端到端网络性能影响因素的分析与评估[D]. 刘晓红.北京邮电大学2007
- [6].基于小世界和随机图理论的多QoS路由算法研究[D]. 冯杰.大连理工大学2007
- [7].基于MPLS网络的约束路由及故障恢复研究[D]. 王新华.山东师范大学2008
- [8].网络模拟路由策略关键技术研究[D]. 郝志宇.哈尔滨工业大学2007
- [9].面向ICN的可扩展名字路由机理研究[D]. 孙彦斌.哈尔滨工业大学2016
- [10].基于复杂网络的拓扑与信息传输问题研究[D]. 史伟.天津大学2010
相关论文
- [1].基于非精确网络状态信息QoS路由优化算法研究[D]. 王建新.中南大学2001
- [2].基于QoS约束的组播路由算法研究[D]. 王珩.南京理工大学2004
- [3].基于TCP/IP的QoS路由算法的研究[D]. 杨云.南京理工大学2003
- [4].Internet QoS路由研究[D]. 江昊.武汉大学2004
- [5].基于QoS约束的多播路由问题研究[D]. 王燕琳.天津大学2004
- [6].网络中QoS路由问题的研究[D]. 张品.电子科技大学2004
- [7].基于IP网络QoS多播路由技术的研究[D]. 许毅.武汉理工大学2005
- [8].Internet中QoS多播路由技术研究[D]. 颜昕.武汉理工大学2006
- [9].计算机网络中的路由与性能优化[D]. 齐小刚.西安电子科技大学2005
- [10].基于小世界和随机图理论的多QoS路由算法研究[D]. 冯杰.大连理工大学2007
标签：服务质量路由论文; 最优论文; 度量空间论文; 约束最短路径论文; 多约束路径论文; 多约束优化路径论文; 法线测量论文; 覆盖概率论文; 前瞻论文;