《毕业论文-链路状态路由算法的实现》由会员分享，可在线阅读，更多相关《毕业论文-链路状态路由算法的实现（19页珍藏版）》请在金锄头文库上搜索。
1、山东建筑大学计算机学院课程设计说明书目 录课程设计任务书I链路状态路由算法的实现2一、 问题描述2二、 基本要求2三、设计思想2四、系统结构4五、 程序流程（或模块划分）5六、 源程序5七、 测试数据10八、 测试情况11结 论15参考文献17课程设计指导教师评语18I山东建筑大学计算机学院课程设计说明书山东建筑大学计算机科学与技术学院课程设计任务书设计题目链路状态路由算法的实现(Java或C+)已知技术参数和设计要求1.编程实现右图所示简单网络拓扑的链路状态路由算法。 1.1 结点之间的连接关系固定； 1.2 链路开销可以由用户设定。2.链路状态算法的实现：2.1 链路状态消息的交换(可选，
2、简单起见，可基于静态网络拓扑运行Dijkstra算法)；2.2 网络拓扑的描述/构造； 2.3 利用Dijkstra算法计算路由； 2.4 路由表的输出。3.网络拓扑结构的描述(数据结构)，拓扑结构利用文件存储。设计内容与步骤1.分析链路状态路由协议与Dijkstra算法；2.熟悉线程间通信与同步机制/或进程间通信机制；3.网络拓扑的数据结构定义及文件存储；4.链路状态消息的交换；5.Dijkstra算法实现；6.结点路由表的显示；7.课程设计任务说明书。设计工作计划与进度安排1.熟悉链路状态协议/算法 4小时2.链路状态算法的实现方式分析 4小时3.链路状态算法实现框架结构设计 8小时4.数
3、据结构定义：包括网络拓扑结构、链路状态消息、路由表等 4小时5.Dijkstra算法实现 10小时 6.课程设计说明书 10小时设计考核要求1.出勤 202.答辩或演示303.课程设计说明书 50指导教师（签字）： 教研室主任（签字）I山东建筑大学计算机学院课程设计说明书链路状态路由算法的实现一、 问题描述利用java或者C+编程实现链路状态路由算法，实现图中所示简单网络拓扑的链路状态路由算法。首先利用邻接矩阵的方式描述/构造图中的网络拓扑，并且将构造的拓扑图中的邻接矩阵保存到文件中；再次利用Dijkstra算法解决最短路径问题；最后将路由表输出。二、 基本要求1.编程实现右图所示简单网络拓扑
4、的链路状态路由算法。 1.1 结点之间的连接关系固定； 1.2 链路开销可以由用户设定。2.链路状态算法的实现：2.1 链路状态消息的交换(可选，简单起见，可基于静态网络拓扑运行Dijkstra算法)；2.2 网络拓扑的描述/构造； 2.3 利用Dijkstra算法计算路由； 2.4 路由表的输出。3.网络拓扑结构的描述(数据结构)，拓扑结构利用文件存储。三、设计思想（一）链路状态路由协议/算法链路状态路由协议是层次式的，网络中的路由器并不向邻居传递“路由项”，而是通告给邻居一些链路状态。与距离矢量路由协议相比，链路状态协议对路由的计算方法有本质的差别。距离矢量协议是平面式的，所有的路由学习完
5、全依靠邻居，交换的是路由项。链路状态协议只是通告给邻居一些链路状态。运行该路由协议的路由器不是简单地从相邻的路由器学习路由，而是把路由器分成区域，收集区域的所有的路由器的链路状态信息，根据状态信息生成网络拓扑结构，每一个路由器再根据拓扑结构计算出路由。链路状态算法是要求网络中所有参与链路状态路由协议的路由器都掌握网络的全部拓扑结构信息，并记录在路由数据库中。链路状态算法中路由数据库实质上是一个网络结构的拓扑图，该拓扑图由一个节点的集合和一个边的集合构成。在网络拓扑图中，结点代表网络中路由器，边代表路由器之间的物理链路。在网络拓扑结构图中，每一条链路上可以附加不同的属性，例如链路的状态、距离或费
6、用等。如果没一个路由器所保存的网络拓扑结构图都是一致的，那么个路由器生成的路由表也是最佳的，不存在错误路由或循环路由。（二）数据结构网络拓扑结构是网络形状，或者是它在物理上的连通性。构成网络的拓扑结构有很多种。网络拓扑结构是指用传输媒体互连各种设备的物理布局，就是用什么方式把网络中的计算机等设备连接起来。拓扑图给出网络服务器、工作站的网络配置和相互间的连接，它的结构主要有星型结构、环型结构、总线结构、分布式结构、树型结构、网状结构、蜂窝状结构等。本次课程设计用到的拓扑结构是网状结构。路由表或称路由择域信息库（RIB）是一个存储在路由器或者联网计算机中的电子表格（文件）或类数据库。路由表存储着指
7、向特定网络地址的路径（在有些情况下，还记录有路径的路由度量值）。路由表中含有网络周边的拓扑信息。路由表建立的主要目标是为了实现路由协议和静态路由选择。路由器的主要工作就是为经过路由器的每个数据包寻找一条最佳的传输路径，并将该数据有效地传送到目的站点。由此可见，选择最佳路径的策略即路由算法是路由器的关键所在。为了完成这项工作，在路由器中保存着各种传输路径的相关数据路由表（Routing Table），供路由选择时使用，表中包含的信息决定了数据转发的策略。打个比方，路由表就像我们平时使用的地图一样，标识着各种路线，路由表中保存着子网的标志信息、网上路由器的个数和下一个路由器的名字等内容。路由表可以
8、是由系统管理员固定设置好的，也可以由系统动态修改，可以由路由器自动调整，也可以由主机控制。（三）Dijkstra算法按阶段进行，在每个阶段选择一个顶点v，它在所有unkown顶点中具有最小的dv。阶段的其余部分由dw值的更新组成。Dijkstra算法执行下列步骤：1、初始情况时，除了选择的顶点距离为0外，到其余所有顶点的距离dist都是不可达的(INFINITY)。置所有的顶点known属性都是false。2、选择一个dist为最小的顶点v，将其known属性置为true。3、对每一个与顶点v邻接的顶点w，依次判断v.dist+cv,w与w.dist的大小，更改w.dest的值。将w的经过的顶
9、点置为v。4、重复2，3，直到所有的顶点都被访问为止。int main()主函数void createGraph()拓扑图的创建 void printFileGraph() 存储矩阵到文件中 void initRoute()实现路由表的复位void Dijkstra() Dijkstra算法求路径void printRoute()将路径表存到文件中void deleteMemo()释放所有动态空间四、系统结构do if(!fist) 五、 程序流程（或模块划分）开始插入节点数目结束构造网络拓扑保存拓扑到文件中Dijkstra算法打印路由表六、 源程序/VC+#include /标准输入输出流头
10、文件#include /文件输入输出头文件#include /防止编译exit（）时出错#include /因为使用了setw（）语句#includeusing namespace std;const int INFINITY=10000;const int OK=1;const int updateTime=10;void createGraph(int *arcs,int & num)/创建并初始化网络拓扑图cout请输入路径的权值(用邻接矩阵表示拓扑图的方式):endl;for (int i=0;inum;i+)arcsi=new int num;for(int j=0;jarcsij;
11、 /输入对象到矩阵中void printFileGraph(int *arcs,int num)/把拓扑图中的邻接矩阵保存到文件中ofstream outfile(Graph.txt,ios:out|ios:trunc);if(! outfile)cout打开文件时出现错误!endl;exit(1); /异常退出outfile拓扑图的邻接矩阵endl;for(int i=0;inum;i+) for(int j=0;jnum;j+)outfilesetw(10)arcsij; if(j+1)%num=0)outfileendl;outfile注：endl;outfileINFINITY表示无穷
12、大endl;cout拓扑图已经存储在当前目录下Graph.txt文件中endl;outfile.close();void initRoute(int * R ,int RL,int vNum)/路由表数据复位for(int i=0;ivNum;i+)RLi=INFINITY;Ri=new intvNum;for(int j=0;jvNum;j+)Rij=-1;void updateRouteLen(int R1, int R2,int dest,int num)/用路径R2给R1赋值for(int i=0;inum;i+)R1i=R2i;for(int j=0;jnum;j+)if (R1j=-1)R1j=dest;break;void Dijkstra(int * arcs,int * R,int RL,int vexnum)/Dijkstra算法int v0; /定义源节点 bool * visit=new bool vexnum;/已经确定最短路径的节点的集合 coutv0; coutendl; for(int cnt=0;cntvexnum;cnt+) /进行主要循环之前先初始化visitcnt=FALSE;RLcnt=arcsv0cnt;if(RLcntINFINITY)R
