毕业论文-链路状态路由算法的实现.doc

山东建筑大学计算机学院课程设计说明书目 录课程设计任务书I链路状态路由算法的实现2一、 问题描述2二、 基本要求2三、设计思想2四、系统结构4五、 程序流程（或模块划分）5六、 源程序5七、 测试数据10八、 测试情况11结 论15参考文献17课程设计指导教师评语18山东建筑大学计算机学院课程设计说明书山东建筑大学计算机科学与技术学院课程设计任务书设计题目链路状态路由算法的实现(Java或C+)已知技术参数和设计要求1.编程实现右图所示简单网络拓扑的链路状态路由算法。 1.1 结点之间的连接关系固定； 1.2 链路开销可以由用户设定。2.链路状态算法的实现：2.1 链路状态消息的交换(可选，简单起见，可基于静态网络拓扑运行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.数据结构定义：包括网络拓扑结构、链路状态消息、路由表等 4小时5.Dijkstra算法实现 10小时 6.课程设计说明书 10小时设计考核要求1.出勤 202.答辩或演示303.课程设计说明书 50指导教师（签字）： 教研室主任（签字）山东建筑大学计算机学院课程设计说明书链路状态路由算法的实现1、 问题描述利用java或者C+编程实现链路状态路由算法，实现图中所示简单网络拓扑的链路状态路由算法。首先利用邻接矩阵的方式描述/构造图中的网络拓扑，并且将构造的拓扑图中的邻接矩阵保存到文件中；再次利用Dijkstra算法解决最短路径问题；最后将路由表输出。2、 基本要求1.编程实现右图所示简单网络拓扑的链路状态路由算法。 1.1 结点之间的连接关系固定； 1.2 链路开销可以由用户设定。2.链路状态算法的实现：2.1 链路状态消息的交换(可选，简单起见，可基于静态网络拓扑运行Dijkstra算法)；2.2 网络拓扑的描述/构造； 2.3 利用Dijkstra算法计算路由； 2.4 路由表的输出。3.网络拓扑结构的描述(数据结构)，拓扑结构利用文件存储。三、设计思想（一）链路状态路由协议/算法链路状态路由协议是层次式的，网络中的路由器并不向邻居传递“路由项”，而是通告给邻居一些链路状态。与距离矢量路由协议相比，链路状态协议对路由的计算方法有本质的差别。距离矢量协议是平面式的，所有的路由学习完全依靠邻居，交换的是路由项。链路状态协议只是通告给邻居一些链路状态。运行该路由协议的路由器不是简单地从相邻的路由器学习路由，而是把路由器分成区域，收集区域的所有的路由器的链路状态信息，根据状态信息生成网络拓扑结构，每一个路由器再根据拓扑结构计算出路由。链路状态算法是要求网络中所有参与链路状态路由协议的路由器都掌握网络的全部拓扑结构信息，并记录在路由数据库中。链路状态算法中路由数据库实质上是一个网络结构的拓扑图，该拓扑图由一个节点的集合和一个边的集合构成。在网络拓扑图中，结点代表网络中路由器，边代表路由器之间的物理链路。在网络拓扑结构图中，每一条链路上可以附加不同的属性，例如链路的状态、距离或费用等。如果没一个路由器所保存的网络拓扑结构图都是一致的，那么个路由器生成的路由表也是最佳的，不存在错误路由或循环路由。（二）数据结构网络拓扑结构是网络形状，或者是它在物理上的连通性。构成网络的拓扑结构有很多种。网络拓扑结构是指用传输媒体互连各种设备的物理布局，就是用什么方式把网络中的计算机等设备连接起来。拓扑图给出网络服务器、工作站的网络配置和相互间的连接，它的结构主要有星型结构、环型结构、总线结构、分布式结构、树型结构、网状结构、蜂窝状结构等。本次课程设计用到的拓扑结构是网状结构。路由表或称路由择域信息库（RIB）是一个存储在路由器或者联网计算机中的电子表格（文件）或类数据库。路由表存储着指向特定网络地址的路径（在有些情况下，还记录有路径的路由度量值）。路由表中含有网络周边的拓扑信息。路由表建立的主要目标是为了实现路由协议和静态路由选择。路由器的主要工作就是为经过路由器的每个数据包寻找一条最佳的传输路径，并将该数据有效地传送到目的站点。由此可见，选择最佳路径的策略即路由算法是路由器的关键所在。为了完成这项工作，在路由器中保存着各种传输路径的相关数据路由表（Routing Table），供路由选择时使用，表中包含的信息决定了数据转发的策略。打个比方，路由表就像我们平时使用的地图一样，标识着各种路线，路由表中保存着子网的标志信息、网上路由器的个数和下一个路由器的名字等内容。路由表可以是由系统管理员固定设置好的，也可以由系统动态修改，可以由路由器自动调整，也可以由主机控制。（三）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的经过的顶点置为v。4、重复2，3，直到所有的顶点都被访问为止。int main()主函数void createGraph()拓扑图的创建 void printFileGraph() 存储矩阵到文件中 void initRoute()实现路由表的复位void Dijkstra() Dijkstra算法求路径void printRoute()将路径表存到文件中void deleteMemo()释放所有动态空间四、系统结构do if(!fist) 5、 程序流程（或模块划分）开始插入节点数目结束构造网络拓扑保存拓扑到文件中Dijkstra算法打印路由表6、 源程序/VC+#include /标准输入输出流头文件#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; /输入对象到矩阵中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表示无穷大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)Rcnt0=v0; Rcnt1=cnt;RLv0=0; /源节点的标志 visitv0=TRUE; /初始化已经找到最短路径的点集合 for(int i=1;ivexnum;i+) /Dijkstra算法的主循环int min=INFINITY; int v=v0;for(int j=0;jvexnum;j+)if(!visitj)if(RLjmin)v=j; min=RLj;visitv=TRUE; /离V0顶点最近的V加入到S集中for(int k=0;kvexnum;k+) /更新当前最短路径及距离if(!visitk&(min+arcsvkRLk)RLk=min+arcsvk; updateRouteLen(Rk,Rv,k,vexnum);delete visit;visit=NULL;void printRoute(int * R,int RL, int vNum)/打印得到最短路径表ofstream outfile(Route.txt,ios:out|ios:trunc);if(! outfile)cout打开文件时出现错误!endl;exit(1);for(int dest=0;destvNum;dest+)if(RLdest!=0)cout目标节点:destendl;outfile目标节点 :destendl;if (Rdest0=-1)cout最短路径不存在!endl;outfile最短路径不存在!endl;continue;elsecout最短路径是:endl;outfile最短路径是:endl;for(int j=0;jvNum;j+)if(Rdestj!=-1)coutRdestj);outfileRdestj);elsebreak;cout最短路径长度:RLdestendl;cout*endl;outfile最短路径长度:RLdestendl;outfile*endl;cout路由表已经存储在当前目录下Route.txt文件中endl;outfile.close();void deleteMemo(int * weight,int * R, int RL,int num)/释放所有动态空间for(int i=0;inum;i+)delete weighti;weighti=NULL;delete Ri; Ri=NULL;delete weight;weight=NULL; delete R;R=NULL; delete RL;RL=NULL;int main() /主程序int vNum; coutvNum; coutendl; int * weight=new int * vNum; /定义拓扑图中的路径的权值int * shortestRoute=new int * vNum;/记录到达网络中各节点的最短路径int * routeLen=new int vNum; /最短路径长度 createGraph(weight,vNum); printFileGraph(weight,vNum); char isExit=y; bool fist=TRUE; do if(!fist) printFileGraph(weight,vNum); initRoute(shortestRoute,routeLen,vNum); Dijkstra(weight,shortestRoute ,routeLen,vNum); printRoute(shortestRoute,routeLen,vNum); fist=FALSE; coutisExit; coutendl; if(isExit=y) break; while(isExit=n); deleteMemo(weight,shortestRoute ,routeLen,vNum);return OK; 7、 测试数据 构造网络拓扑图，并且存在文件中请输入拓扑图中节点的数目：4请输入路径的权值(用邻接矩阵表示拓扑图的方式)：0 1 3 71 0 1 100003 1 0 27 10000 2 0 测试Dijkstra算法请输入起始节点：38、 测试情况（1） 测试数据截图图1 构造网络拓扑图 图2 将网络拓扑图的邻接矩阵存入到Graph.txt中图3 测试Dijkstra算法图4 将得到最短路径存入Route.txt文件中（2） 各个节点的路由表程序计算得到节点3到其它各节点的路径和长度，并保存在Route文件中。依次可得各节点路由表。 V0的路由表目的节点下一节点最短距离00111212314 V1的路由表目的节点下一节点最短距离00110221323 V2的路由表目的节点下一节点最短距离01211120332 V3的路由表目的节点下一节点最短距离02412322230结 论对于这次课程设计，以前没有做过计算机网络关于链路状态算法以及路由表构造的实验，有得只是课本上的理论知识，没有动手实践过，对于自己来说是个比较大的挑战。由于不懂，先将计算机网络、数据结构两本书中关于链路状态算法、Dijkstra算法、网络拓扑结构以及文件的存储等方面的知识，结合网上的相关资料教程理解掌握。因为我们只有大一接触过一学期的C语言，在接下来的编程中用到的语言都是Java。我就将课程设计简单的定义为用Java来编写，但是在编写的过程中发现同一个方法用Java来实现很麻烦。一个功能的实现往往需要很多类，方法和方法之间还需要衔接，而且在用Java编写过程中，碰到了一个难题，那就是文件的存储。在我印象当中只有在学C语言的时候老师提过文件存储这部分的知识。在用Java编写无法进行下去的时候，想到用C+试试。但是由于老师从来没有讲过C+，只有暑假自己参加比赛的时候，才接触过C+的一些皮毛知识。感觉无从下手，而且熟悉visualC+环境也需要一段时间。经过将近两个星期的网络课程设计及学习，虽然实现的功能不是很多，并且其中还是有些问题，稍显稚嫩，但是还是基本符合要求，让我颇感欣慰，最主要的就是在设计过程中让我学到了很多在课本中学不到的知识，收获颇丰。让我更深层次了解了网络，懂得了怎样快速学习运用软件来编程，来设计东西。懂得怎样快速把自己所学的运用到实际中。在这个过程中我过得很充实,很有意义。最重要的是编程方面的思维不仅仅局限于用Java编写，各种编程语言的思想都是相通的。也了解了矩阵输入输出的简单表示，以及如何存储到文件中。由于多数题目所学要的知识都要借助辅助资料，更加加强了同