基于遗传算法的多约束OSPF路由方法研究

摘要

随着宽带IP技术的发展,像视频会议这样的多媒体业务得到了越来越多的应用.一方面在这些业务中,很适合用组播的方式一次性地将报文传送到多个接收者,以节省网络资源;另一方面这些业务都是一些实时性很强的业务,需要提供QoS保障,而这与现有的传统的路由过程不同,难以用经典的最短路径优先算法求解.本文研究了遗传算法在OSPF网络路由规划选择中的应用,重点研究如何快速求得全局最优解并有效改善网络局部拥塞的问题.在此基础上,结合OSPF网络路由的参数特性,运用约束条件以确定搜索的方向,解决OSPF网络路由选择困难的问题.其目的在于探索和应用遗传算法为OSPF网络路由的选择开辟一条新的途径.本文叙述了OSPF网络在当前和今后的信息社会发展中的重要地位,介绍了OSPF网络的性质和路由特性,以及对其进行研究的重要性和必要性.分析了当前流行的一些搜索方法.阐述了有关遗传算法的基本概念,如:建模、编码、杂交、变异等,并在适应度函数值的引导下对复杂的解空间进行有效地搜索,直到获得最优的解.提出了基于遗传算法的路由选择的新方法,考虑网络路由选择过程中必需满足QoS的要求,满足实时性的要求等解决方法.结合遗传算法,提出了改进延时参数的搜索策略.并且通过仿真实验,验证了该方法在解决链路拥塞问题上的有效性.本文利用网络仿真软件OPNET对改进的路由选择策略进行了建模和描述,首先构建一个OSPF的节点系统.在Modeler工作平台上,将此系统作为网络模型对改进的路由选择策略进行仿真,说明改进算法可以有效地均衡链路中的业务流量.本文的最后对OSPF路由选择算法的进一步设计提出了设想,并对其应用前景及未来发展进行了展望.

目录

文摘

英文文摘

独创性说明

引 言

1路由技术概述

1.1网络通信的发展

1.2路由技术的发展与趋势

1.3本文所做的工作

2路由器与OSPF路由选择算法

2.1路由器的发展趋势

2.1.1路由器硬件体系结构的发展

2.1.2路由器软件体系结构的发展

2.2路由器的硬件组成和软件策略

2.2.1路由器的基本组成

2.2.2路由器的软件策略

2.3 OSPF协议分析

2.3.1 OSPF的原理

2.3.2 OSPF的路由更新机制

2.4 OSPF中采用的路由计算方法

2.4.1自动计算路由

2.4.2使用缺省路由代价计算路由

2.4.3使用最短路径树计算路由

2.5几种路由算法的分析

2.5.1最短路径优先算法SPF

2.5.2基于最短路径思想的一些路由算法

2.5.3 QoS问题

3用遗传算法实现多约束OSPF路由选择

3.1遗传算法概述

3.1.1遗传算法的原理

3.1.2基本遗传算法的参数和流程

3.1.3遗传算法的收敛性分析和特点

3.2用遗传算法实现多约束OSPF的全局最优路由选择算法

3.2.1多约束路由问题的术语描述及构造数学模型

3.2.2多约束全局最优路由选择算法描述

3.2.3构造网络模型进行仿真

3.2.4设置网络模型参数

3.2.5采用随机网络模型进行仿真

3.2.6多约束全局最优路由选择算法的流程

3.3实验结果分析

3.3.1一个周期内的三条组播最佳路由

3.3.2随机网络模型中的三条组播最佳路由

3.3.3对引入自适应思想后最短路由选择算法改进的说明

3.3.4算法的性能分析

3.4全局最优多约束路由选择算法的特点

3.4.1遗传算法与其他搜索算法的比较

3.4.2全局最优多约束路由选择算法与SPF算法的比较

4基于OPNET的多约束选路过程仿真

4.1 OPNET概述

4.1.1 OPNET Modeler进行仿真的流程

4.1.2 OPNET Modeler中的网络建模

4.2构造多约束OSPF路由网络模型并配置网络参数

4.3仿真实验及结果分析

4.3.1仿真实验

4.3.2动画过程演示业务流在源和目的节点之间的传送

4.3.3结果分析

结 论

参考文献

攻读硕士学位期间发表学术论文情况

致 谢

大连理工大学学位论文版权使用授权书