基于遍历树的LAP路由算法研究

摘要

链路状态路由协议进行通信之前，需要完成网络拓扑结构的收敛。在开放最短路径(Open Short Path First，OSPF)协议当中，使用洪泛(Flooding)算法进行网络拓扑信息的收敛，Flooding算法使用扩散方式进行信息传播，在链路较多的网络环境当中，这种方式会产生大量重复冗余的信息，造成通信资源的浪费。在目前网络向着大规模复杂化发展方向的趋势下，为了避免这种通信资源的浪费，对OSPF协议下的收敛算法的研究具有一定的实际意义。 本文首先介绍了LAP路由算法，并对LAP存在的问题和下一阶段的研究内容进行了论述;然后在LAP路由算法的基础上，针对一般性的网络的研究，提出了基于遍历树的LAP路由算法。又根据遍历方式的不同，提出了基于广度优先遍历树的LAP路由算法和基于深度优先遍历树的LAP路由算法，并给出了算法的实现步骤;接下来在理论上对算法进行了分析和证明;最后对算法进行了仿真实验证明。 在NS2仿真平台当中，对本文的算法进行了仿真实验，并与LAP路由算法和Flooding算法进行了比较分析。从而得出以下结论:如果网络当中的路由结点数量为一个定值，随着结点之间链路数量的增加，广度优先遍历LAP路由算法完成网络拓扑收敛，需要进行的通信次数逐渐减少;Flooding算法完成网络拓扑收敛，需要进行的通信次数逐渐增加。当链路增加到两者相等的时候称为临界点。低于临界点的时候，Flooding算法的通信次数少于广度优先遍历树的LAP路由算法的通信次数;超过临界点的时候，广度优先遍历树LAP路由算法的通信次数少于Flooding算法的通信次数。

目录

声明

摘要

第1章绪论

1．1路由算法的研究背景、目的及意义

1．1．1研究背景

1．1．2研究目的

1．1．3研究意义

1．2 LAP路由算法的研究现状

1．3问题的提出

1．4本文结构

第2章LAP路由算法

2．1 LAP算法理论概述

2．2 LAP路由算法概述

2．2．1 LAP路由算法

2．2．2新型的LAP路由算法

2．3 LAP路由算法的研究可行性分析

2．4 LAP路由算法存在的不足

2．5本章小结

第3章基于遍历树的LAP路由算法的设计

3．1网络模型的建立

3．1．1单链网络

3．1．2单链加环网络

3．1．2一般性网络

3．2基于遍历树的LAP算法设计

3．2．1深度优先遍历LAP算法

3．2．2广度优先遍历LAP算法

3．2．3深度优先和广度优先LAP算法的对比和分析

3．3基于遍历树的LAP路由算法设计

3．3．1算法的提出

3．3．2算法的描述

3．3．3算法的设计

3．4本章小结

第4章基于遍历树的LAP路由算法的理论分析

4．1时间复杂度分析

4．1．1 Flooding算法单链网络时间复杂度分析

4．1．2 LAP路由单链网络算法复杂度分析

4．1．3基于遍历树的LAP路由算法单链网络时间复杂度分析

4．1．4完全网络的时间复杂度分析

4．2空间复杂度分析

4．3本章小结

第5章基于遍历树的LAP路由算法仿真分析

5．1仿真平台的搭建

5．2仿真模型的设计

5．3单链遍历树LAP路由算法仿真

5．4单链加环遍历树LAP路由算法仿真

5．5一般性遍历树LAP路由算法仿真

5．6本章小结

6．1本文工作总结

6．2本文创新点

6．3存在的不足

6．4面临的挑战

6．4．1大规模网络的部署

6．4．2安全性保障

6．4．3服务质量

6．4．4节能

参考文献

致谢

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