禁位排列路由决策算法的研究及应用

摘要

随着计算机网络的不断飞速发展，网络信息量也随之急剧增加，从而造成了网络负载繁重、信息交互速度延缓、通信质量变差等各种问题的出现，这就迫切需要设计一个高效、稳定、灵活的路由决策算法来应对这些不容忽视的问题。事实上，路由决策算法不能单独存在，只有把它运用到某一具体的路由选择协议下才具有现实的意义和价值。
　　OSPF协议是目前比较常见的内部网关协议之一，它的最终目的是实现全网信息的一致性。基于国内外在信息一致性方向的研究不足以及OSPF协议下主流的Dijkstra算法的唯一性考虑，本文给出了一种禁位排列路由决策的创新性算法，它的根本目的是以最快的速度促使全网信息达到一致性。本文对禁位排列路由决策算法的提出、理论支撑、设计、仿真以及展望做了详细的论述。
　　首先，本文提出了OSPF协议下的信息一致性问题，并针对该问题在其他禁位排列原理的基础之上构造了LAP算法。其次，将LAP算法应用到计算机网络中去，以此设计了单链网络LAP路由算法和两种复杂网络LAP路由算法，一是单链网络LAP加环的复杂网络路由算法，二是基于区域捆绑的复杂网络LAP路由算法。在设计三种LAP路由算法的同时，给出了相应的静态仿真实验，实验表明，三种LAP路由算法能够促成网络信息的一致性。最后，在NS2仿真环境下，对三种LAP路由算法进行动态仿真，进一步证明了本文设计的LAP路由算法能够解决网络信息一致性问题，与Dijkstra算法相比有较高的优越性。

目录

声明

摘要

第1章 绪论

1．1 计算机网络路由算法的研究背景及意义

1．1．1 研究背景

1．1．2 研究意义

1．2 典型的计算机网络路由选择协议

1．2．1 RIP协议

1．2．2 OSPF协议

1．2．3 BGP协议

1．3 OSPF协议下信息一致性问题提出

1．4 本文结构安排

1．4．1 论文组织结构

1．4．2 论文研究内容

第2章 LAP算法的思想来源

2．1 创新性理论首次提出的相关引例

2．2 LAP算法的发现

2．2．1 算法的一般发展模式

2．2．2 LAP算法的发现过程

2．3 LAP算法在计算机网络中应用的理论支撑

2．3．1 网络通路的存在性

2．3．2 构造相邻路由器

2．3．3 网络环路的存在性

2．4 本章小结

第3章 LAP算法的提出

3．1 LAP算法的基本理论依据

3．1．1 容斥原理

3．1．2 错位排列

3．2 LAP算法的提出及其证明

3．2．1 其他禁位排列问题研究

3．2．2 LAP算法的提出

3．2．3 最优LA问题的提出

3．3 本章小结

第4章 LAP路由算法设计及仿真实验

4．1 单链网络LAP路由算法设计

4．1．1 用对称布尔表格记录信息交互情况

4．1．2 深度优先遍历规则的采用

4．1．3 脱落结点处理规则的采用

4．1．4 单链网络LAP路由算法描述

4．2 复杂网络LAP路由算法设计

4．2．1 单链网络加环的复杂网络模型

4．2．2 单链网络LAP加环的复杂网络路由算法

4．2．3 基于区域捆绑的复杂网络LAP路由算法研究

4．2．4 基于区域捆绑的复杂网络LAP路由算法算例演示

4．3 LAP路由算法的复杂度分析

4．3．1 时间复杂度分析

4．3．2 空间复杂度分析

4．4 LAP算法与Dijkstra算法对比

4．4．1 LAP算法与Dijkstra算法的相同点

4．4．2 LAP算法与Dijkstra算法的不同点

4．5 本章小结

第5章 基于NS2的LAP路由算法仿真

5．1 NS2简介

5．2 NS2仿真平台搭建

5．3 路由结点移动模型与信息发送接收模型

5．3．1 路由结点移动模型的建立

5．3．2 信息发送与接收模型的设计

5．4 基于NS2的LAP算法与Dijkstra算法对比仿真

5．4．1 单链网络LAP路由算法仿真

5．4．2 单链网络LAP路由加环算法仿真

5．4．3 基于区域捆绑复杂网络LAP路由算法仿真

5．5 本章小结

第6章 工作总结与展望

6．1 本文工作总结

6．2 本文创新点

6．3 存在问题及应用前景展望

6．3．1 存在问题

6．3．2 下一步工作

6．3．3 应用前景展望

参考文献

致谢

攻读硕士学位期间发表的论文等