路由器查表过程模拟

1、课课程程设设计计报报告告课程名称：课程名称： 局域网技术 设计题目设计题目： 路由表查找过程模拟 系系 别：别： 计算机与信息工程学院 专专 业：业： 网络工程 组组 别：别： 第一组 起止日期起止日期: 2012 年 6 月 11 日 2012 年 6 月 24 日指导教师指导教师: 计算机科学与技术系二计算机科学与技术系二一二年制一二年制课程设计任务书课程设计任务书课程设计题目路由表的查找模拟组长学号班级院部计算机与信息工程学院专业网络工程组员 指导教师课程设计目的通过课程设计,加深对路由表的理解,掌握路由表查找的基本原理及功能,具有初步分析实际路由表的组成、构造，并具备准确查找路由表的能

2、力。课程设计所需环境Windows XP，VC+6.0课程设计任务要求本设计的目的是通过设计一个简单的路由表查找过程的模拟来模拟实际网络中路由变化的过程，以掌握这种有用的技术。要求通过距离矢量的 rip 协议和链路状态的ospf 协议来分别实现路由表的查找过程。课程设计工作进度计划序号起止日期工 作 内 容分工情况12012.6.11开会分析讨论，作工作分工史言负责对小组成员进行分工26.126.12作具体分析，查询相关资料36.136.15编写源代码46.166.17对源程序进行调试56.186.22写课程设计报告66.236.24与老师交流，完善报告，并打印教研室审核意见：教研室主任签字：

3、 年 月 日目目 录录1 引言引言 .12 需求分析需求分析 .12.1 设计目的.12.2 设计主要内容及要求.12.2.1 设计内容 .12.2.2 设计要求.22.2.3 使用环境及语言 .23 概要设计概要设计 .23.1 基本功能描述.23.1.1 路由表的结构.23.1.2 路由表的作用.23.1.3 路由表中路由的来源.33.2 IP 路由选择.33.2.1 通过 RIP(路由信息协议)来实现路由选择 .33.2.2 通过 OSPF(开放最短路径优先)来实现路由选择 .53.2.3 Dijkstra 算法.5详细设计详细设计 .64.1 各模块的伪码算法.64.1.1 RIP .

4、64.1.2 ospf .105 调试与结果说明调试与结果说明 .135.1.RIP的调试结果 .135.2.OSPF调试结果.14课程设计总结与体会课程设计总结与体会 .17致谢致谢 .17参考文献参考文献 .18附录附录 .18局域网技术课程设计1课程设计的主要内容课程设计的主要内容1 引言引言随着计算机信息技术的发展，大规模的互联网逐渐流行起来，也为路由器的发展提供了良好的基础和平台。作为不同网络之间互相连接的枢纽，路由器系统构成了基于 TCP/IP 的国际互联网络 Internet 的主体脉络。然而如何准确的发送并接受信息，则需要通过路由表的准确查找，路由表存储着指向特定网络地址的路径

5、（在有些情况下，还记录有路径的路由度量值） 。通过路由表查找过程的设计与模拟可以更好的体现路由的选择，帮助我们准确的理解路由的选择过程。2 需求分析需求分析2.1 设计设计目的目的该程序主要是用来模拟路由器中路由查找的过程。当主机向目的网络发送一个数据包时，对每一个 IP 包，当发送到一个网络拓扑中的时候，可以分别使用 RIP 或 OSPF 协议，来决定数据包通过互联网络的路径。通过模拟算法的实现，我们可以模拟一个简单的路由查找过程，进而找出最优路径，实现路由的查找2.2 设计主要内容及要求设计主要内容及要求2.2.1 设计内容设计内容1rip：距离向量路由协议，距离向量路由协议的特征是它在进

6、行路由更新时，会发送路由表的全部或一部分给邻居路由器（这台邻居路由器也必须运行 rip 协议） ，当路由信息通过这种方式扩散到整个自治系统时，每个路由器会根据 Dijkstra 算法计算出到达每个网段的最优路径，rip 选择到达某个网络的最优路径根据跳数。数据包经过一个路由器就是一跳。2 ospf：路由器的路由选择是基于链路状态，通过 Dijkastra 算法建立起来最短路径树，用该树跟踪系统中的每个目标的最短路径。最后再通过计算域间路由、自治系统外部路由确定完整的路由表。与此同时，OSPF 动态监视网络状态，一旦发生变化则迅速扩散达到对网络拓扑的快速聚合，从而确定出新的网络路由表。因此，需要

7、把自治系统划分为多个域，每个域内部维持本域一张唯一的拓扑结构图，且各域根据自己的拓扑图各自计算路由，域边界路由器把各个域的内部路由总结后在域间扩散。这样，当网络中的某条链路状态发生变化时，此链路所在的域中的每个路由器重新计算本域路由表，而其它域中路由器只需修改其路由表中的相应条目而无须重新计算整个路由表，节省了计算路由表的时间。局域网技术课程设计22.2.2 设计要求设计要求任意两个节点，分别在 rip 和 ospf 协议的前提条件下，根据相应的算法找出最优路径。在 rip 协议中，所有的路由都由跳数来描述，到达目的地的路由最大不超过 16 跳，且只保留唯一的一条路由，这就限制了 RIP 的服

8、务半径，即其只适用于小型的简单网络。同时，运行 RIP 的路由器需要定期地（一般 30s）将自己的路由表广播到网络当中，达到对网络拓扑的聚合，这样不但聚合的速度慢而且极容易引起广播风暴、累加到无穷、路由环致命等问题。为此，OSPF 应运而生。OSPF 是基于链路状态的路由协议，它克服了 RIP 的许多缺陷：第一，OSPF 不再采用跳数的概念第二，OSPF 支持不同服务类型的不同代价，从而实现不同 QoS 的路由服务；第三，OSPF 路由器不再交换路由表，而是同步各路由器对网络状态的认识，即链路状态数据库，然后通过 Dijkstra 最短路径算法计算出网络中各目的地址的最优路由。2.2.3 使用

9、环境及语言使用环境及语言编程环境：Microsoft Visual C+6.0编写语言：C+语言3 概要设计概要设计3.1 基本功能描述基本功能描述3.1.1 路由表的结构路由表的结构标准的路由表表目是一个二维组（目的网络地址，下一站地址） ，其中不携带子网信息，不能满足子网寻径。引入子网编址以后，路由表的每一表目中加入子网掩码，于是路由表表目变为三维组：子网掩码、目的网络地址、下一站地址。 表 1 路由表结构及使用表 1 路由表结构及使用目的地址掩码下一跳地址255.25

10、5.255.0路由器依据路由表来为报文寻径，路由表由路由协议建立和维护。路由协议的设计则是依据某种路由算法。 路由器提供了将异构网互联的机制，实现将一个数据包从一个网络发送到另一个网络。路由就是指导 IP 数据包发送的路径信息局域网技术课程设计33.1.2 路由表的作用路由表的作用路由器的主要工作就是为经过路由器的每个数据帧寻找一条最佳传输路径，并将该数据有效地传送到目的站点。由此可见，选择最佳路径的策略即路由算法是路由器的关键所在。为了完成这项工作，在路由器中保存着各种传输路径的相关数据路由表（Routing Table） ，供路由选择时使用。打个比方，路由表就像我们平时使用

11、的地图一样，标识着各种路线，路由表中保存着子网的标志信息、网上路由器的个数和下一个路由器的名字等内容。路由表可以是由系统管理员固定设置好的，也可以由系统动态修改，可以由路由器自动调整，也可以由主机控制。3.1.3 路由表中路由的来源路由表中路由的来源在路由表中有一个 Protocol 字段，指明了路由的来源，即路由是如何生成的。 链路层协议发现的路由（Direct）它的特点是开销小，配置简单，无需人工维护，只能发现本接口所属网段拓扑的路由。 手工配置的静态路由（Static）静态路由是一种特殊的路由，它由管理员手工配置而成。通过静态路由的配置可建立一个互通的网络，但这种配置问题在于：当一个网络

12、故障发生后，静态路由不会自动修正，必须有管理员的介入。静态路由无开销，配置简单，适合简单拓扑结构的网络。 动态路由协议发现的路由（RIP、OSPF 等）当网络拓扑结构十分复杂时，手工配置静态路由工作量大而且容易出现错误，这时就可用动态路由协议，动态（Dynamic）路由表是路由器根据网络系统的运行情况而自动调整的路由表。路由器根据路由选择协议（Routing Protocol）提供的功能，自动学习和记忆网络运行情况，在需要时自动计算数据传输的最佳路径。让其自动发现和修改路由，无需人工维护，但动态路由协议开销大，配置复杂。3.2 IP 路由选择路由选择路由器通常依靠所建立及维护的路由表来决定如何

13、转发。路由表能力是指路由表内所容纳路由表项数量的极限。3.2.1 通过通过 RIP(路由信息协议路由信息协议)来实现路由选择来实现路由选择RIP（Routing information Protocol，路由信息协议）是应用较早、使用较普遍的内部网关协议（Interior Gateway Protocol，IGP） ，适用于小型同类网络的一个自治系统（AS）内的路由信息的传递。RIP 协议是基于距离矢量算法（Distance Vector Algorithms，DVA）的。它使用“跳数”，即 metric 来衡量到达目标地址的路由距离。它是一个用于路由器和主机间交换路由信息的距离向量协议，目前

14、最新的版本为 v4，也就是 RIPv4。 1.RIP 的工作原理局域网技术课程设计4RIP 是一种距离矢量路由协议 RIP 使用跳数作为路由选择的度量。当在进行路由选择是，路由表会根据最小跳数来决定转发的路径 RIP 用“路程段数”（即“跳数”）作为网络距离的尺度。每个路由器在给相邻路由器发出路由信息时，都会给每个路径加上内部距离。在如图 3-1 中，路由器 3 直接和网络 C 相连。当它向路由器 2 通告网络 的路径时，它把跳数增加 1。与之相似，路由器 2 把跳数增加到“2”，且通告路径给路由器1，则 Route1 和 Route0 与 Route2 所在网络 172

15、.16.0.0 的距离分别是 1 跳、2 跳。图 3-1 rip 的工作原理事例2.RIP 报文的格式对于 RIP 报文有两种版本的格式，Version 1 和 Version 2。两种报文稍有不同，如图 3-2 所示： 命令 版本 路由选择 地址族 路径标签 IP 地址 子网掩码 下一个站点的 IP 地址 度量值 前 20 个字节的重复 命令 版本 全零 地址族 全零 IP 地址 全零 全零 度量值 前 20 个字节的重复 (a) Version 1 (b) Version 2 0 31 0 31 图 3-2 rip 报文的两种版本格式局域网技术课程设计5在一开始，所有路由器中的路由表只有路

16、由器所接入的网络（共有两个网络）的情况。现在的路由表增加了一列，这就是从该路由表到目的网络上的路由器的“距离” 。在图中“下一站路由器”项目中有符号“” ，表示直接交付。这是因为路由器和同一网络上的主机可直接通信而不需要再经过别的路由器进行转发。同理，到目的网络的距离也都是零，因为需要经过的路由器数为零。图中粗的空心箭头表示路由表的更新，细的箭头表示更新路由表要用到相邻路由表传送过来的信息。接着，各路由器都向其相邻路由器广播 RIP 报文，这实际上就是广播路由表中的信息。假定路由器 R2 先收到了路由器 R1 和 R3 的路由信息，然后就更新自己的路由表。更新后的路由表再发送给路由器 R1 和

17、 R3。路由器 R1 和 R3 分别再进行更新。3.2.2 通过通过 OSPF(开放最短路径优先开放最短路径优先)来实现路由选择来实现路由选择OSPF 是一种分层次的路由协议，其层次中最大的实体是 AS（自治系统） ，即遵循共同路由策略管理下的一部分网络实体。在每个 AS 中，将网络划分为不同的区域。每个区域都有自己特定的标识号。对于主干（backbone）区域，负责在区域之间分发链路状态信息。这种分层次的网络结构是根据 OSPF 的实际提出来的。当网络中自治系统非常大时，网络拓扑数据库的内容就更多，所以如果不分层次的话，一方面容易造成数据库溢出，另一方面当网络中某一链路状态发生变化时，会引起

18、整个网络中每个节点都重新计算一遍自己的路由表，既浪费资源与时间，又会影响路由协议的性能（如聚合速度、稳定性、灵活性等） 。因此，需要把自治系统划分为多个域，每个域内部维持本域一张唯一的拓扑结构图，且各域根据自己的拓扑图各自计算路由，域边界路由器把各个域的内部路由总结后在域间扩散。这样，当网络中的某条链路状态发生变化时，此链路所在的域中的每个路由器重新计算本域路由表，而其它域中路由器只需修改其路由表中的相应条目而无须重新计算整个路由表，节省了计算路由表的时间。OSPF 的设计实现要涉及到指定路由器、备份指定路由器的选举、协议包的接收、发送、泛洪机制、路由表计算等一系列问题。本文仅就 Dijkst

19、ra 算法与路由表的计算进行讨论。3.2.3 Dijkstra 算法算法Dijkstra 算法是路由表计算的依据，通过 Dijkstra 算法可以得到有关网络节点的最短路径树，然后由最短路径优先树得到路由表。1.Dijkstra 算法的描述 初始化集合 E，使之只包含源节点 S，并初始化集合 R，使之包含所有其它节点。初始化路径列 O，使其包含一段从 S 起始的路径。这些路径的长度值等于相应链路的量度值，并以递增顺序排列列表 O. 若列表 O 为空，或者 O 中第 1 个路径长度为无穷大，则将 R 中所有剩余节点标注局域网技术课程设计6为不可达，并终止算法。 首先寻找列表 O 中的最短路径 P

20、，从 O 中删除 P.设 V 为 P 的最终节点。若 V 已在集合 E 中，继续执行步骤 2.否则，P 为通往 V 的最短路径。将 V 从 R 移至 E. 建立一个与 P 相连并从 V 开始的所有链路构成的侯选路径集合。这些路径的长度是 P 的长度加上与 P 相连的长度。将这些新的链路插入有序表 O 中，并放置在其长度所对应的等级上。继续执行步骤 2.2.Dijkstra 算法举例以路由器 A 为例，来说明最短路径树的建立过程：1）路由器 A 找到了路由器 B、C，将它们列入候选列表.（2）从候选列表中找出最小代价项 B，将 B 加入最短路径树并从候选列表中删除。接着从 B 开始寻找，找到了

21、D，将其放入候选列表.（3）从列表中找出C，再由 C 又找到了 D.但此时 D 的代价为 4，所以不再加入候选列表。最后将 D 加入到最短路径树。此时候选列表为空，完成了最短路径树的计算。3.OSPF 路由表的计算与实现有关路由表的计算是 OSPF 的核心内容，它是动态生成路由器内核路由表的基础。在路由表条目中，应包括有目标地址、目标地址类型、链路的代价、链路的存活时间、链路的类型以及下一跳等内容。关于整个计算的过程，主要由以下五个步骤来完成保存当前路由表，当前存在的路由表为无效的，必须从头开始重新建立路由表；域内路由的计算，通过 Dijkstra 算法建立最短路径树，从而计算域内路由；域间路

22、由的计算，通过检查 Summary-LSA 来计算域间路由，若该路由器连到多个域，则只检查主干域的 Summary-LSA；查看 Summary-LSA：在连到一个或多个传输域的域边界路由器中，通过检查该域内的 Summary-LSA 来检查是否有比第（2） （3）步更好的路径；AS 外部路由的计算，通过查看 AS-External-LSA 来计算目的地在 AS 外的路由。通过以上步骤，OSPF 生成了路由表。但这里的路由表还不同于路由器中实现路由转发功能时用到的内核路由表，它只是 OSPF 本身的内部路由表。因此，完成上述工作后，往往还要通过路由增强功能与内核路由表交互，从而实现多种路由协议

23、的学习。OPSF 作为一种重要的内部网关协协议的普遍应用，极大地增强了网络的可扩展性和稳定性，同时也反映出了动态路由协议的强大功能。详细设计详细设计4.1 各模块的伪码算法各模块的伪码算法4.1.1 RIP 1.定义存储类型的三个类：(1)网段类，包含相邻弧的信息（不用 route_f，用 next）,也可用于存储文件读入信息局域网技术课程设计7（用 route_f，不用 next） public:string net_id;string route_f;string route_n;Net_sec* next;(2)路由类相当于头结点class Routepublic:string rout

24、e;Net_sec *next;class Net_sec(3)路由表内容类class Contentspublic:string net_id;int diatance;string next_stop;2.路由表和网段类在路由表网段类中定义了多个函数。void open_file(ifstream& infile)打开文件函数。Route_net()类的构造函数用来表示网络拓扑的邻接状况，bool judge(string str)函数判断一个路由是否已为其添加了路由表，void Init_routes()初始化路由表，void show()显示各路由表，void change(i

25、nt i) 对相邻路由表 change 一下，距离加 1，下一跳变为该路由名字，void update(int i) 对一个路由进行更新操作，void UPDATE()对所有路由进行更新路由表操作，bool neighbor(int i,int j) 判断两路由是否相邻。在类中还定义了一些私有的成员变量。（1）Route_net 类的伪码段：class Route_netpublic:void open_file(ifstream& infile);Route_net();/ 构造函数bool judge(string str);void Init_routes();void show

26、();void change(int i);void update(int i);void UPDATE();bool neighbor(int i,int j);/j 和 i 相邻吗private:list li; /读取信息存储在这Route routeMAX; /存储图的信息，即各路由的邻接表局域网技术课程设计8list routesMAX; /存储各路由路由表list temp; /用于存储处理后的临时路由表string flectionMAX; /用于对应路由器与存储序列标号int sum; /用于统计路由个数;（2）构造函数Route_net:Route_net()ifstream

27、 infile;istringstream strm;string a_line;Net_sec t1;open_file(infile);while(getline(infile,a_line)strm.str(a_line);_idt1.route_ft1.route_n;li.push_back(t1);strm.clear(); （3）判断一个路由是否已为其添加了路由表bool Route_net:judge(string str)int i=0;while(flectioni!=&inext)p.diatance=1;_id=t-net_id; p.next_stop=直接交

28、付;routesi.push_back(p);（5）显示各路由表void Route_net:show()局域网技术课程设计9int i=0;list:iterator p;for(;isum;i+)cout This is the table of flectioniendl;for(p=routesi.begin();p!=routesi.end();p+)cout(*p).net_id (*p).diatance (*p).next_stopendl;（6）对相邻路由表 change 一下，距离加 1，下一跳变为该路由名字void Route_net:change(int i)Conte

29、nts co;temp.erase(temp.begin(),temp.end();list:iterator p=routesi.begin();for(;p!=routesi.end();p+)co.diatance=(*p).diatance+1;_id=(*p).net_id;co.next_stop=flectioni;temp.push_back(co);（7）对一个路由进行更新操作void Route_net:update(int i)int count=0;list:iterator it1=routesi.begin();list:iterator it2=temp.begi

30、n();for(;it2!=temp.end();it2+)for(it1=routesi.begin();it1!=routesi.end();it1+)if(*it1).net_id=(*it2).net_id)count+;if(*it1).next_stop)=(*it2).next_stop)(*it1).diatance=(*it2).diatance;(*it1).next_stop=(*it2).next_stop;if(*it1).next_stop!=(*it2).next_stop)&(*it1).diatance(*it2).diatance)(*it1).di

31、atance=(*it2).diatance;(*it1).next_stop=(*it2).next_stop;if(count=0)routesi.push_back(*it2);count=0;局域网技术课程设计10（8）对所有路由进行更新路由表操作void Route_net:UPDATE()int j=0,i=0,I;for(I=0;Isum;I+)for(j=0;jsum;j+)for(i=0;isum;i+)if(neighbor(j,i)change(i);update(j);coutThis is the I+1 running.next)if(flectionj=p-rou

32、te_n)return true;return false;4.1.2 ospfOSPF 路由协议是基于链路状态的一种路由协议，通过带宽大小来决定路径，带宽大者优先。1.包含的头文件#include #include #include #include #include #include2.结构体定义（1）将每个路由器看成一个节点，用结构体 VEXTYPE 来定义。结构体内包含变量时名字 name，ip 地址，路由器的序号 num。typedef struct /图中顶点表示点，存放点名称 char name30;char ip12;局域网技术课程设计11int num; VEXTYPE;（2

33、）网络拓扑图用无向图来表示，定义一个无向图的结构体 MGraph，包含 VEXTYPE 类型的数组变量，ADJTYPE 型的矩阵，int 型变量来记录顶点数和边数。 typedef struct VEXTYPE vexsMAXLEN; /顶点的信息 ADJTYPE arcsMAXLENMAXLEN; /邻接矩阵 int vexnum,arcnum ; /顶点数和边数 MGraph; /无向图3.建立无向网的邻接矩阵结构MGraph InitGraph() /*建立无向网的邻接矩阵结构*/ int i, j; MGraph G; G.vexnum =5; /存放顶点数G.arcnum =7; /

34、存放边点数 for(i=0;iG.vexnum;i+) G.vexsi.num=i; strcpy(G.,r0);strcpy(G.vexs0.ip,); strcpy(G.,r1);strcpy(G.vexs1.ip,); strcpy(G.,r2);strcpy(G.vexs2.ip,); strcpy(G.,r3);strcpy(G.vexs3.ip,); strcpy(G.,r4);strcpy(G.

35、vexs4.ip,); for(i=0;iG.vexnum;i+) for(j=0;jG.vexnum;j+) G.arcsij=MAX;G.arcs01=130;G.arcs12=80; G.arcs13=110; G.arcs34=75; G.arcs24=50; for(i=0;iG.vexnum;i+) for(j=0;jG.vexnum;j+) G.arcsji=G.arcsij;return G;4.操作函数局域网技术课程设计12输出每个顶点的信息：void PutOutVex(MGraph *G)，输出每条边的信息：void PutOutArc(MGraph

36、 *G)，修改拓扑图函数：void Change(MGraph *G)，删除某个顶点：void DeleteVex(MGraph *G)，删除某条边：void DeleteArc(MGraph *G)，插入某条边：void InsertArc(MGraph *G)。5.迪杰斯特拉算法求最短路径void Dijkstra(MGraph * G) /迪杰斯特拉算法求最短路径 int v,w,i,min,t=0,x,v0,v1; int final20, D20, p2020; coutv0; if(v0G-vexnum) coutv0; coutv1; if(v1G-vexnum) coutv1;

37、 for(v=0;vvexnum;v+) / 初始化 final20,p2020,finalv=1 即已经求得 v0 到 v 的最短路径， /pvw=1 则是 w 从 v0 到 v 当前求得最短路径上的顶点，Dv带权长度 finalv=0; Dv=G-arcsv0v; for(w=0;wvexnum;w+) pvw=0; if(DvMAX) pvv0=1;pvv=1; Dv0=0;finalv0=1; for(i=1;ivexnum;i+) min=MAX; for(w=0;wvexnum;w+) if(!finalw) if(Dwmin)v=w;min=Dw; finalv=1; 局域网技术

38、课程设计13 for(w=0;wvexnum;w+) if(!finalw&(min+G-arcsvwarcsvw; for(x=0;xvexnum;x+) pwx=pvx; pww=1; cout从到的最短路径长度为：Dv1endl; cout路径为：; for(int j=0;jvexnum;j+) if(pv1j=1) endl; 5 调试与结果说明调试与结果说明5.1.rip 的调试结果的调试结果当网络拓扑中使用 rip 的时候，最短路径的查找如图 5-1 所示局域网技术课程设计14图 5-1 rip 调试

39、结果图 5-1 rip 调试结果（续）5.2.ospf 调试结果调试结果1.运行 ospf 的时候，首先会有个选择菜单，按 0 时会输出网络拓扑中节点的信息，本实验中有 5 个节点 r0、r1、r2、r3、r4。如图 5-2 所示：图 5-2 ospf 输出顶点信息2.当按 1 的时候可以查看各个边的信息，用无向图中的权值来替代带宽，图中有 5 条链路分别为：（r0,r1）=130,（r1,r2）=80,（r1,r3）=110,（r2,r4）=50,(r3,r4)=75。如图 5-3 所示：局域网技术课程设计15图 5-3 ospf 输出边的信息3.当按 2 的时候可以更改节点间边上权值及带宽

40、的信息如是更改(r1,r3)=78,调试结果如图 5-4 所示：图 5-4 ospf 边更改后信息4.当按 3 的时候显示源节点到目的的最短路径及,如 r0 到 r4,调试结果如图 5-5 所示：局域网技术课程设计16图 5-5 ospf 输出最短路径信息5.当按 4 的时候显示删除某个节点，如删除 r4 后显示的节点信息，调试结果如图 5-6 所示：图 5-6 ospf 删除顶点后输出信息6.当按 5 的时候显示删除某个边，如删除(r2，r3)后显示的边信息，调试结果如图 5-7 所示：局域网技术课程设计17图 5-7ospf 删除边后输出信息7.当按 6 的时候显示插入某个边，如插入(r2

41、,r3)后显示的边信息，调试结果如图 5-8 所示：图 5-8 ospf 删除边后输出信息课程设计总结与体会课程设计总结与体会本次课程设计主要是通过设计一个简单的路由表查找过程的模拟来模拟实际网络中路由变化的过程，以掌握这种有用的技术。要求通过距离矢量的 rip 协议和链路状态的 ospf协议来分别实现路由表的查找过程。在使用 rip 和 ospf 协议的时候都是用到了数据结构中图的邻接矩阵的存储，带权无向网的建立及 Dijkstra 算法的使用。在使用 rip 协议的网络拓扑中，程序是根据两个节点中的跳数来计算最优路径的。在 ospf 协议的网络拓扑中，是根据带宽即图中边的权值来计算最优路径

42、的。在课程设计报告的撰写过程中，遇到了格式，字体等的不正确在老师的指导下都一一解决。通过实验使得小组各个成员对路由表的查找过程有了更清楚的认识和理解。在实验过程中，通过对系统模拟算法的实现以及使用 rip 和 ospf 时的实现过程，加深对路由查找的局域网技术课程设计18了解。并在实验中懂得无论多复杂的问题，都可以转化为简单的算法模拟实现，使之更形象更具体。总之，此次课程设计既让该小组成员掌握了路由表查找过程原理，还提高了自身的动手能力和团队合作能力。致谢致谢首先我们要感谢胡老师在这一学期里对我们的教育，他教会我们的知识对这次课程设计起到关键作用。在此我们这一小组对刘老师表示感谢！其次，我们还

43、要感谢在设计中给予我们帮助的同学，最后还要感谢我们的母校给予我们良好的的设计环境，良好的学习环境，以及优秀的教师资源等等！在此我们该小组表示感谢！参考文献参考文献1胡学钢.数据结构(C 语言版)M.北京:高等教育出版社,20082 严蔚敏,吴伟民.数据结构(C 语言版)M.北京:高等教育出版社,20033 谢希仁.计算机网络M.北京:电子工业出版社,19994 陆姚远.计算机网络技术M.北京:高等教育出版社,2000附录附录Ospf:#include #include #include #include #include #include #define MAX 10000 #define M

44、AXLEN 8 #define ADJTYPE int typedef struct /图中顶点表示点，存放点名称 char name30;char ip12; int num; VEXTYPE; typedef struct VEXTYPE vexsMAXLEN; /顶点的信息 ADJTYPE arcsMAXLENMAXLEN; /邻接矩阵 int vexnum,arcnum ; /顶点数和边数 MGraph; /无向图MGraph b; MGraph InitGraph()局域网技术课程设计19 /*建立无向网的邻接矩阵结构*/ int i, j; MGraph G; G.vexnum =

45、5; /存放顶点数G.arcnum =7; /存放边点数 for(i=0;iG.vexnum;i+) G.vexsi.num=i; strcpy(G.,r0);strcpy(G.vexs0.ip,); strcpy(G.,r1);strcpy(G.vexs1.ip,); strcpy(G.,r2);strcpy(G.vexs2.ip,); strcpy(G.,r3);strcpy(G.vexs3.ip,); strcpy(G.v

46、,r4);strcpy(G.vexs4.ip,); /*strcpy(G.,超市 r5); strcpy(G.vexs5.ip,); strcpy(G.,综合实验楼 r6);strcpy(G.vexs6.ip,); strcpy(G.,校医院 r7);strcpy(G.vexs7.ip,); */ for(i=0;iG.vexnum;i+) for(j=0;jG.vexnum;j+) G.arcsij=MAX;G.arcs01=1

47、30;G.arcs12=80; G.arcs13=110; G.arcs34=75; G.arcs24=50; /G.arcs34=120; /G.arcs23=265; /G.arcs35=85; /G.arcs36=400; /G.arcs46=350; /G.arcs56=120; /G.arcs47=200; /G.arcs67=150; for(i=0;iG.vexnum;i+) for(j=0;jG.vexnum;j+) G.arcsji=G.arcsij;return G;局域网技术课程设计20void Menu() /输出菜单 cout需要输出顶点的信息请按 0n; cout需

48、要边的信息输出请按 1n; cout需要修改请按 2n; cout需要求出最短路径请按 3n; cout需要删除某个顶点请按 4n; cout需要删除某条边请按 5n; cout需要插入某条边请按 6n; cout需要退出请按 7n; void PutOutVex(MGraph *G) /输出每个顶点的信息int v; for(v=0;vvexnum;v+) coutvexsv.num vexsv.ipendl; void PutOutArc(MGraph *G) /输出每条边的信息for(int i=0;ivexnum;i+) for(int j=0;jvexnum;j

49、+) if(G-arcsijMAX) cout从 到 arcsijendl; void Change(MGraph *G) /修改 int v0,v1,length; coutv0; cinv1; coutlength; G-arcsv0v1=G-arcsv1v0=length;void Dijkstra(MGraph * G) /迪杰斯特拉算法求最短路径 int v,w,i,min,t=0,x,v0,v1; int final20, D20, p2020; coutv0; if(v0G-vexnum) coutv0; 局域网技术课程设计21 coutv

50、1; if(v1G-vexnum) coutv1; for(v=0;vvexnum;v+) / 初始化 final20,p2020,finalv=1 即已经求得 v0 到 v 的最短路径， /pvw=1 则是 w 从 v0 到 v 当前求得最短路径上的顶点，Dv带权长度 finalv=0; Dv=G-arcsv0v; for(w=0;wvexnum;w+) pvw=0; if(DvMAX) pvv0=1;pvv=1; Dv0=0;finalv0=1; for(i=1;ivexnum;i+) min=MAX; for(w=0;wvexnum;w+) if(!finalw) if(Dwmin)v=

51、w;min=Dw; finalv=1; for(w=0;wvexnum;w+) if(!finalw&(min+G-arcsvwarcsvw; for(x=0;xvexnum;x+) pwx=pvx; pww=1; cout从到的最短路径长度为：Dv1endl; cout路径为：; for(int j=0;jvexnum;j+) if(pv1j=1) endl;局域网技术课程设计22 void DeleteVex(MGraph *G) /删除某个顶点int row,col;int v0;coutv0;for(int

52、 i=v0;ivexnum;i+)G-vexsi=G-vexsi+1;G-vexnum-;for(row=0;rowvexnum;row+)for(col=v0;colvexnum;col+)G-arcsrowcol=G-arcsrowcol+1;for(col=0;colvexnum;col+)for(row=v0;rowvexnum;row+)G-arcscolrow=G-arcscolrow+1;void DeleteArc(MGraph *G) /删除某条边 int v0,v1; coutv0v1; G-arcsv0v1=MAX; G-arcsv1v0=MAX;void InsertA

53、rc(MGraph *G) /插入某条边 int v0,v1,l=0; coutv0v1; coutl; G-arcsv0v1=l; G-arcsv1v0=l;void main() /主函数 int a; 局域网技术课程设计23 b=InitGraph(); Menu(); cina; while(a!=7) switch(a) case 0:PutOutVex(&b);Menu();break; case 1:PutOutArc(&b);Menu();break; case 2:Change(&b);Menu();break; case 3:Dijkstra(&am

54、p;b);Menu();break; case 4:DeleteVex(&b);Menu();break; case 5:DeleteArc(&b);Menu();break; case 6:InsertArc(&b);Menu();break; case 7:exit(1);break; default:break; cina; Rip:/以下是模拟 RIP 协议实现的 C+代码#include#include#include#include#includeusing namespace std;#define MAX 100 /最大路由数/*下面是存储类型的三个类*

55、/class Net_sec;/网段类/路由类相当于头结点class Routepublic:string route;Net_sec *next;/网段类，包含相邻弧的信息（不用 route_f，用 next）,也可用于存储文件读入信息（用route_f，不用 next）局域网技术课程设计24class Net_sec public:string net_id;string route_f;string route_n;Net_sec* next;/路由表内容类class Contentspublic:string net_id;int diatance;string next_stop;/

56、*上面是存储类型的三个类*/路由表和网段类class Route_netpublic:void open_file(ifstream& infile);Route_net();/ 构造函数bool judge(string str);void Init_routes();void show();void change(int i);void update(int i);void UPDATE();bool neighbor(int i,int j);/j 和 i 相邻吗private:list li; /读取信息存储在这Route routeMAX; /存储图的信息，即各路由的邻接表l

57、ist routesMAX; /存储各路由路由表list temp; /用于存储处理后的临时路由表string flectionMAX; /用于对应路由器与存储序列标号int sum; /用于统计路由个数;/打开文件函数void Route_net:open_file(ifstream& infile)string filename;coutfilename;局域网技术课程设计25infile.open(filename+.txt).c_str();if(!infile)cerrfile open error!_idt1.route_ft1.route_n;li.push_back(t

58、1);strm.clear(); /以上把文件内容存入了类属性 li 中list:iterator it1=li.begin(),it2;int i=0;Net_sec *t2,*t3;for(;it1!=li.end();it1+)if(judge(*it1).route_f) flectioni=(*it1).route_f;routei.route=flectioni;t3=t2=routei.next=new Net_sec();for(it2=li.begin();it2!=li.end();it2+)if(flectioni=(*it2).route_f)t2-net_id=(*i

59、t2).net_id;t2-route_n=(*it2).route_n;t3=t2;t2-next=new Net_sec();t2=t2-next;if(flectioni=(*it2).route_n)t2-net_id=(*it2).net_id;t2-route_n=(*it2).route_f;t3=t2;t2-next=new Net_sec();t2=t2-next;局域网技术课程设计26t3-next=NULL;i+;if(judge(*it1).route_n) flectioni=(*it1).route_n;routei.route=flectioni;t3=t2=routei.next=new Net_sec();for(it2=li.begin();it2!=li.end();it2+)if(flectioni=(*