IP网络多约束单路径路由算法的研究

摘要

随着IP网络应用日益膨胀，各种服务也层出不穷。对网络应用而言，需要多QoS约束的路由模型来支持可区分的服务。所以多约束单路径路由问题(Multiple Constraints Single Path Routing，MCSPR)的研究非常重要。通过其研究可以实现：1、为每一个接纳的QoS业务连接请求，找到满足其QoS要求的可行路径；2、优化全局资源利用率，平衡网络负载，从而最大化网络接受其他QoS请求的能力。 MCSPR问题很难完全解决的原因是：寻找到优化目标，满足一个以上路径约束的可行路径具有NP完全的计算复杂度，本文主要研究内容包括： 1、形式化地描述了多约束单路径路由的模型，给出了问题的混合规划形式，并基于背包问题的NP完全性证明了多约束单路径路由问题也是NP完全的。 2、设计了该问题的一种集中式求解近似算法；证明了该算法求出的解的一些性质，并基于该算法给出了一个分布式的实现；实验结果表明：该近似算法的近似程度较高，所需运行时间较少。 3、基于多目标遗传进化思想求解多约束单路径路由问题。首先对问题做了扩展，由于在路由问题中多个优化目标的偏好信息很难获得，文章先求解问题的Pareto近似解，然后再根据实际需求对这些Pareto近似解进行分析决策，选择出最终的路由选择方案。算法是基于Strength Pareto Evolutionary Algorithm2(SPEA2)算法思想进行优化选择，并设计相关的遗传算子完成种群进化操作。 4、最后本文对多约束路由问题求解思路进行了扩展，提出用分布式约束满足优化模型来描述问题，并对求解的搜索方法进行了分析。

目录

文摘

英文文摘

论文说明：图表目录

声明

第1章绪论

1.1计算机网络发展概述

1.1.1 IP网络

1.1.2路由基础

1.2路由算法的设计目标与分类

1.3IP网络服务质量

1.4服务质量路由

1.5研究内容和章节安排

第2章基本定义与研究基础

2.1基本定义

2.2约束度量

2.3网络模型

2.3.1网络拓扑建模

2.3.2带权图模型

2.4路由算法分析

2.4.1多项式非启发类

2.4.2约束度量相关

2.4.3探测法

2.4.4扩展距离向量算法

2.4.5限定约束度量

2.4.6路径子空间搜索

2.4.7花费函数

2.5多播多约束路由算法

2.6算法有效性分析

2.6.1路由回路问题

2.6.2陈旧信息的影响

2.6.3网络模型的影响

2.7计算复杂性理论基础

2.8总结

第3章路由模型及基于最优方向搜索的近似算法

3.1多约束单路径路由问题的形式化描述

3.2多约束单路径路由问题的难解性分析

3.3多约束单路径路由问题的混合规划形式

3.4混合规划问题的计算复杂性

3.5基于最优方向搜索的近似算法

3.5.1 1-MCSPR问题求解

3.5.2 d-MCSPR问题求解

3.5.3 d-MCSPR问题求解算法的分布式实现

3.5.4模拟实验

第4章基于遗传算法的问题求解

4.1遗传算法简介

4.2 Pareto优化路径

4.3多目标优化算法描述

4.3.1遗传算子设计

4.3.2算法过程

4.4基于动态规划思想的迭代次数控制

4.4.1动态规划思想

4.4.2迭代计算过程

4.5实验分析

第5章多约束路由问题求解的扩展

5.1问题的一般性求解方法

5.2分布式约束满足

5.2.1约束满足问题

5.2.2分布式约束满足问题

5.3求解分布式约束满足优化问题的算法

5.3.1异步回溯

5.3.2分布式逃逸

5.4总结

总结与展望

参考文献

致谢

附录