路由器查表课程设计报告

1、PAGE PAGE 56滁州学院课程设计报告课程名称： 计算机网络 设计题目： 路由表查找过程模拟 院 部： 计算机与信息工程学院 专 业： 网络工程（无线传感器网络方向） 组 别： 第 二 组 起止日期: 2012年12月29日 2012年12月30日 指导教师: 张 老师 计算机与信息工程学院二一二年制课程设计题目路由器查表过程模拟组长曹学号2011211班级网工113班院部计算机与信息工程学院专业网络工程（无线传感器网络方向）组员指导教师张课程设计目的通过课程设计,加深对路由表的理解,掌握路由表查找的基本原理及功能,具有初步分析实际路由表的组成、构造，并具备准确查找路由表的能力。课程设计

2、所需环境Windows XP，VC+6.0课程设计任务要求编程模拟路由器查找路由表的过程，用（目的地址 掩码 下一跳）的IP路由表以及目的地址作为输入，为目的地址查找路由表，找出正确的下一跳并输出结果。课程设计工作进度计划序号起止日期工 作 内 容分工情况12012.12.29分析讨论，进行相关的分工以及查阅相关的资料曹对组员进行分工。每个组员查阅资料，摘取相关的信息22012.12.29编写源代码，对源程序进行调试编写源代码，对程序代码进行调试32012.12.30撰写课程设计报告。与老师进行交流，对报告进行相关的修改，并打印根据课程设计报告模板，组员在一起撰写实验报告，并和老师在一起交流，

3、进行报告的相关修改，最后打印实验报告指导教师签字： 年 月 日系（教研室）审核意见：系（教研室）主任签字： 年 月 日课程设计任务书目 录 HYPERLINK l _Toc344987394 2.3.1 设计内容 PAGEREF _Toc344987394 h 2 HYPERLINK l _Toc344987395 2.3.2设计要求 PAGEREF _Toc344987395 h 2 HYPERLINK l _Toc344987396 2.3.3使用环境及语言 PAGEREF _Toc344987396 h 3 HYPERLINK l _Toc344987399 3.1.1路由表的结构 PA

4、GEREF _Toc344987399 h 3 HYPERLINK l _Toc344987400 3.1.2路由表的作用 PAGEREF _Toc344987400 h 4 HYPERLINK l _Toc344987401 3.1.3路由表中路由的来源 PAGEREF _Toc344987401 h 4 HYPERLINK l _Toc344987403 3.2.1通过RIP（路由信息协议）来实现路由选择 PAGEREF _Toc344987403 h 4 HYPERLINK l _Toc344987404 3.2.2通过OSPF（开放最短路径优先）来实现路由选择 PAGEREF _Toc

5、344987404 h 6 HYPERLINK l _Toc344987405 3.2.3 Dijkstra算法 PAGEREF _Toc344987405 h 7 HYPERLINK l _Toc344987408 4.1.1RIP PAGEREF _Toc344987408 h 8 HYPERLINK l _Toc344987409 4.1.2 OSPF PAGEREF _Toc344987409 h 121引言随着计算机信息技术的发展，大规模的互联网逐渐流行起来，也为路由器的发展提供了良好的基础和平台。作为不同网络之间互相连接的枢纽，路由器系统构成了基于TCP/IP 的国际互联网络Int

6、ernet 的主体脉络。然而如何准确的发送并接受信息，则需要通过路由表的准确查找，路由表存储着指向特定网络地址的路径（在有些情况下，还记录有路径的路由度量值）。通过路由表查找过程的设计与模拟可以更好的体现路由的选择，帮助我们准确的理解路由的选择过程。2需求分析2.1设计题目路由器查表过程模拟2.2设计目的该程序主要是用来模拟路由器中路由查找的过程。当主机向目的网络发送一个数据包时，对每一个IP包，当发送到一个网络拓扑中的时候，可以分别使用RIP或OSPF协议，来决定数据包通过互联网络的路径。通过模拟算法的实现，我们可以模拟一个简单的路由查找过程，进而找出最优路径，实现路由的查找。2.3设计主要

7、内容及要求2.3.1 设计内容1rip：距离向量路由协议，距离向量路由协议的特征是它在进行路由更新时，会发送路由表的全部或一部分给邻居路由器（这台邻居路由器也必须运行rip协议），当路由信息通过这种方式扩散到整个自治系统时，每个路由器会根据Dijkstra算法计算出到达每个网段的最优路径，rip选择到达某个网络的最优路径根据跳数。数据包经过一个路由器就是一跳。2 ospf：路由器的路由选择是基于链路状态，通过Dijkastra算法建立起来最短路径树，用该树跟踪系统中的每个目标的最短路径。最后再通过计算域间路由、自治系统外部路由确定完整的路由表。与此同时，OSPF动态监视网络状态，一旦发生变化则

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

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

10、路径算法计算出网络中各目的地址的最优路由。2.3.3使用环境及语言编程环境：Microsoft Visual C+6.0编写语言：C+语言3概要设计3.1基本功能描述3.1.1路由表的结构标准的路由表表目是一个二维组（目的网络地址，下一站地址），其中不携带子网信息，不能满足子网寻径。引入子网编址以后，路由表的每一表目中加入子网掩码，于是路由表表目变为三维组：子网掩码、目的网络地址、下一站地址。表1 路由表结构及使用目的地址掩码下一跳地址路由器依据路由表来为报文寻径，路由表由路由协议建立和维护。路由协议的设计则是依据某种路由算法。路由器提供了将异构网互联的机制，实现将一个数据包从一个网络发送到另

11、一个网络。路由就是指导IP数据包发送的路径信息。3.1.2路由表的作用路由器的主要工作就是为经过路由器的每个数据帧寻找一条最佳传输路径，并将该数据有效地传送到目的站点。由此可见，选择最佳路径的策略即路由算法是路由器的关键所在。为了完成这项工作，在路由器中保存着各种传输路径的相关数据路由表（Routing Table），供路由选择时使用。打个比方，路由表就像我们平时使用的地图一样，标识着各种路线，路由表中保存着子网的标志信息、网上路由器的个数和下一个路由器的名字等内容。路由表可以是由系统管理员固定设置好的，也可以由系统动态修改，可以由路由器自动调整，也可以由主机控制。3.1.3路由表中路由的来源

12、在路由表中有一个Protocol字段，指明了路由的来源，即路由是如何生成的。 = 1 * GB2 链路层协议发现的路由（Direct）它的特点是开销小，配置简单，无需人工维护，只能发现本接口所属网段拓扑的路由。 = 2 * GB2 手工配置的静态路由（Static）静态路由是一种特殊的路由，它由管理员手工配置而成。通过静态路由的配置可建立一个互通的网络，但这种配置问题在于：当一个网络故障发生后，静态路由不会自动修正，必须有管理员的介入。静态路由无开销，配置简单，适合简单拓扑结构的网络。 = 3 * GB2 动态路由协议发现的路由（RIP、OSPF等）当网络拓扑结构十分复杂时，手工配置静态路由工

13、作量大而且容易出现错误，这时就可用动态路由协议，动态（Dynamic）路由表是路由器根据网络系统的运行情况而自动调整的路由表。路由器根据路由选择协议（Routing Protocol）提供的功能，自动学习和记忆网络运行情况，在需要时自动计算数据传输的最佳路径。让其自动发现和修改路由，无需人工维护，但动态路由协议开销大，配置复杂。3.2IP路由选择路由器通常依靠所建立及维护的路由表来决定如何转发。路由表能力是指路由表内所容纳路由表项数量的极限。3.2.1通过RIP（路由信息协议）来实现路由选择RIP（Routing information Protocol，路由信息协议）是应用较早、使用较普遍的

14、内部网关协议（Interior Gateway Protocol，IGP），适用于小型同类网络的一个自治系统（AS）内的路由信息的传递。RIP协议是基于距离矢量算法（Distance Vector Algorithms，DVA）的。它使用“跳数”，即metric来衡量到达目标地址的路由距离。它是一个用于路由器和主机间交换路由信息的距离向量协议，目前最新的版本为v4，也就是RIPv4。 1.RIP的工作原理RIP是一种距离矢量路由协议RIP使用跳数作为路由选择的度量。当在进行路由选择是，路由表会根据最小跳数来决定转发的路径RIP用“路程段数”（即“跳数”）作为网络距离的尺度。每个路由器在给相邻路

15、由器发出路由信息时，都会给每个路径加上内部距离。在如图3-1中，路由器3直接和网络C相连。当它向路由器2通告网络的路径时，它把跳数增加1。与之相似，路由器2把跳数增加到“2”，且通告路径给路由器1，则Route1和Route0与Route2所在网络的距离分别是1跳、2跳。图3-1 rip的工作原理事例2.RIP报文的格式对于RIP报文有两种版本的格式，Version 1和Version 2。两种报文稍有不同，如图3-2所示：图3-2 rip报文的两种版本格式在一开始，所有路由器中的路由表只有路由器所接入的网络（共有两个网络）的情况。现在的路由表增加了一列，这就是从该路由表到目的网络上的路由器的

16、“距离”。在图中“下一站路由器”项目中有符号“”，表示直接交付。这是因为路由器和同一网络上的主机可直接通信而不需要再经过别的路由器进行转发。同理，到目的网络的距离也都是零，因为需要经过的路由器数为零。图中粗的空心箭头表示路由表的更新，细的箭头表示更新路由表要用到相邻路由表传送过来的信息。接着，各路由器都向其相邻路由器广播RIP报文，这实际上就是广播路由表中的信息。假定路由器R2先收到了路由器R1和R3的路由信息，然后就更新自己的路由表。更新后的路由表再发送给路由器R1和R3。路由器R1和R3分别再进行更新。3.2.2通过OSPF（开放最短路径优先）来实现路由选择OSPF是一种分层次的路由协议，

17、其层次中最大的实体是AS（自治系统），即遵循共同路由策略管理下的一部分网络实体。在每个AS中，将网络划分为不同的区域。每个区域都有自己特定的标识号。对于主干（backbone）区域，负责在区域之间分发链路状态信息。这种分层次的网络结构是根据OSPF的实际提出来的。当网络中自治系统非常大时，网络拓扑数据库的内容就更多，所以如果不分层次的话，一方面容易造成数据库溢出，另一方面当网络中某一链路状态发生变化时，会引起整个网络中每个节点都重新计算一遍自己的路由表，既浪费资源与时间，又会影响路由协议的性能（如聚合速度、稳定性、灵活性等）。因此，需要把自治系统划分为多个域，每个域内部维持本域一张唯一的拓扑结

18、构图，且各域根据自己的拓扑图各自计算路由，域边界路由器把各个域的内部路由总结后在域间扩散。这样，当网络中的某条链路状态发生变化时，此链路所在的域中的每个路由器重新计算本域路由表，而其它域中路由器只需修改其路由表中的相应条目而无须重新计算整个路由表，节省了计算路由表的时间。OSPF的设计实现要涉及到指定路由器、备份指定路由器的选举、协议包的接收、发送、泛洪机制、路由表计算等一系列问题。本文仅就Dijkstra算法与路由表的计算进行讨论。3.2.3 Dijkstra算法Dijkstra算法是路由表计算的依据，通过Dijkstra算法可以得到有关网络节点的最短路径树，然后由最短路径优先树得到路由表。

19、1.Dijkstra算法的描述 = 1 * GB2 初始化集合E，使之只包含源节点S，并初始化集合R，使之包含所有其它节点。初始化路径列O，使其包含一段从S起始的路径。这些路径的长度值等于相应链路的量度值，并以递增顺序排列列表O. = 2 * GB2 若列表O为空，或者O中第1个路径长度为无穷大，则将R中所有剩余节点标注为不可达，并终止算法。 = 3 * GB2 首先寻找列表O中的最短路径P，从O中删除P.设V为P的最终节点。若V已在集合E中，继续执行步骤2.否则，P为通往V的最短路径。将V从R移至E. = 4 * GB2 建立一个与P相连并从V开始的所有链路构成的侯选路径集合。这些路径的长度

20、是P的长度加上与P相连的长度。将这些新的链路插入有序表O中，并放置在其长度所对应的等级上。继续执行步骤2.2.Dijkstra算法举例以路由器A为例，来说明最短路径树的建立过程：1）路由器A找到了路由器B、C，将它们列入候选列表.（2）从候选列表中找出最小代价项B，将B加入最短路径树并从候选列表中删除。接着从B开始寻找，找到了D，将其放入候选列表.（3）从列表中找出C，再由C又找到了D.但此时D的代价为4，所以不再加入候选列表。最后将D加入到最短路径树。此时候选列表为空，完成了最短路径树的计算。3.OSPF路由表的计算与实现有关路由表的计算是OSPF的核心内容，它是动态生成路由器内核路由表的基

21、础。在路由表条目中，应包括有目标地址、目标地址类型、链路的代价、链路的存活时间、链路的类型以及下一跳等内容。关于整个计算的过程，主要由以下五个步骤来完成 = 1 * GB2 保存当前路由表，当前存在的路由表为无效的，必须从头开始重新建立路由表； = 2 * GB2 域内路由的计算，通过Dijkstra算法建立最短路径树，从而计算域内路由； = 3 * GB2 域间路由的计算，通过检查Summary-LSA来计算域间路由，若该路由器连到多个域，则只检查主干域的Summary-LSA； = 4 * GB2 查看Summary-LSA：在连到一个或多个传输域的域边界路由器中，通过检查该域内的Summ

22、ary-LSA来检查是否有比第（2）（3）步更好的路径； = 5 * GB2 AS外部路由的计算，通过查看AS-External-LSA来计算目的地在AS外的路由。通过以上步骤，OSPF生成了路由表。但这里的路由表还不同于路由器中实现路由转发功能时用到的内核路由表，它只是OSPF本身的内部路由表。因此，完成上述工作后，往往还要通过路由增强功能与内核路由表交互，从而实现多种路由协议的学习。OPSF作为一种重要的内部网关协协议的普遍应用，极大地增强了网络的可扩展性和稳定性，同时也反映出了动态路由协议的强大功能。4详细设计4.1各模块的伪码算法4.1.1RIP1.定义存储类型的三个类：(1)网段类，

23、包含相邻弧的信息（不用route_f，用next）,也可用于存储文件读入信息（用route_f，不用next） public:string net_id;string route_f;string route_n;Net_sec* next;(2)路由类相当于头结点class Routepublic:string route;Net_sec *next;class Net_sec(3)路由表内容类class Contentspublic:string net_id;int diatance;string next_stop;2.路由表和网段类在路由表网段类中定义了多个函数。void open_

24、file(ifstream& infile)打开文件函数。Route_net()类的构造函数用来表示网络拓扑的邻接状况，bool judge(string str)函数判断一个路由是否已为其添加了路由表，void Init_routes()初始化路由表，void show()显示各路由表，void change(int i) 对相邻路由表change一下，距离加1，下一跳变为该路由名字，void update(int i) 对一个路由进行更新操作，void UPDATE()对所有路由进行更新路由表操作，bool neighbor(int i,int j) 判断两路由是否相邻。在类中还定义了一些

25、私有的成员变量。（1）Route_net类的伪码段：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; /存储图的信息，即各路由的邻接表lis

26、t routesMAX; /存储各路由路由表list temp; /用于存储处理后的临时路由表string flectionMAX; /用于对应路由器与存储序列标号int sum; /用于统计路由个数;（2）构造函数Route_net:Route_net()ifstream infile;istringstream strm;string a_line;Net_sec t1;open_file(infile);while(getline(infile,a_line)strm.str(a_line);strm_idt1.route_ft1.route_n;li.push_back(t1);str

27、m.clear(); （3）判断一个路由是否已为其添加了路由表bool Route_net:judge(string str)int i=0;while(flectioni!=&inext) p.diatance=1; _id=t-net_id; p.next_stop=直接交付; routesi.push_back(p);（5）显示各路由表void Route_net:show()int i=0;list:iterator p;for(;isum;i+)cout This is the table of flectioniendl;for(p=routesi.begin();p!=route

28、si.end();p+)cout(*p).net_id (*p).diatance (*p).next_stopendl;（6）对相邻路由表change一下，距离加1，下一跳变为该路由名字void Route_net:change(int i)Contents 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.pu

29、sh_back(co);（7）对一个路由进行更新操作void Route_net:update(int i)int count=0;list:iterator it1=routesi.begin();list:iterator it2=temp.begin();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=(*i

30、t2).diatance; (*it1).next_stop=(*it2).next_stop;if(*it1).next_stop!=(*it2).next_stop)&(*it1).diatance(*it2).diatance) (*it1).diatance=(*it2).diatance; (*it1).next_stop=(*it2).next_stop; if(count=0) routesi.push_back(*it2); count=0;（8）对所有路由进行更新路由表操作void Route_net:UPDATE()int j=0,i=0,I;for(I=0;Isum;I+

31、)for(j=0;jsum;j+)for(i=0;isum;i+)if(neighbor(j,i)change(i);update(j); coutThis is the I+1 runningnext)if(flectionj=p-route_n) return true;return false;4.1.2 OSPFOSPF路由协议是基于链路状态的一种路由协议，通过带宽大小来决定路径，带宽大者优先。1.包含的头文件#include #include #include #include #include #include2.结构体定义（1）将每个路由器看成一个节点，用结构体VEXTYPE来定

32、义。结构体内包含变量时名字name，ip地址，路由器的序号num。typedef struct /图中顶点表示点，存放点名称 char name30;char ip12;int num; VEXTYPE;（2）网络拓扑图用无向图来表示，定义一个无向图的结构体MGraph，包含VEXTYPE类型的数组变量，ADJTYPE型的矩阵，int型变量来记录顶点数和边数。 typedef struct VEXTYPE vexsMAXLEN; /顶点的信息 ADJTYPE arcsMAXLENMAXLEN; /邻接矩阵 int vexnum,arcnum ; /顶点数和边数 MGraph; /无向图3.建立

33、无向网的邻接矩阵结构MGraph InitGraph() /*建立无向网的邻接矩阵结构*/ int i, j; MGraph G; G.vexnum =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)

34、;strcpy(G.vexs3.ip,); strcpy(G.,r4);strcpy(G.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.操作函数输出每个顶点的信息：void PutOutVex(MGraph *

35、G)，输出每条边的信息：void PutOutArc(MGraph *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) coutv

36、0; coutv1; 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=w;min

37、=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; 5调试与结果说明5.1 RIP的调试结果图5-1 RIP调试结果图5-1 RIP调试结果（续）5.2 OSPF的调试结果1.运行OSPF的时候，首先会有个选择菜单，按0时会

38、输出网络拓扑中节点的信息，本实验中有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所示图5-3OSPF输出边的信息3.当按2的时候可以更改节点间边上权值及带宽的信息如是更改(r1,r3)=78,调试结果如图5-4所示：图5-4OSPF边更改后的信息4.当按3的时候显示源节点到目的的最短路径及,如r0到r4,调试结果如图5-5所示图5-5OSPF输出

39、最短路径信息5.当按4的时候显示删除某个节点，如删除r4后显示的节点信息，调试结果如图5-6所示：图5-6 OSPF删除顶点后输出信息6.当按5的时候显示删除某个边，如删除(r2，r3)后显示的边信息，调试结果如图5-7所示：图5-7 OSPF删除边后输出信息7.当按6的时候显示插入某个边，如插入(r2,r3)后显示的边信息，调试结果如图5-8所示图5-8 OSPF删除边后输出信息6.课程设计总结与体会本次课程设计主要是通过设计一个简单的路由表查找过程的模拟来模拟实际网络中路由变化的过程，以掌握这种有用的技术。要求通过距离矢量的rip协议和链路状态的ospf协议来分别实现路由表的查找过程。在使

40、用rip和ospf协议的时候都是用到了数据结构中图的邻接矩阵的存储，带权无向网的建立及Dijkstra算法的使用。在使用rip协议的网络拓扑中，程序是根据两个节点中的跳数来计算最优路径的。在ospf协议的网络拓扑中，是根据带宽即图中边的权值来计算最优路径的。在课程设计报告的撰写过程中，遇到了格式，字体等的不正确在老师的指导下都一一解决。通过实验使得小组各个成员对路由表的查找过程有了更清楚的认识和理解。在实验过程中，通过对系统模拟算法的实现以及使用rip和ospf时的实现过程，加深对路由查找的了解。并在实验中懂得无论多复杂的问题，都可以转化为简单的算法模拟实现，使之更形象更具体。总之，此次课程设

41、计既让该小组成员掌握了路由表查找过程原理，还提高了自身的动手能力和团队合作能力。参考文献胡学钢.数据结构(C语言版)M.北京:高等教育出版社,20082 严蔚敏,吴伟民.数据结构(C语言版)M.北京:高等教育出版社,20033 谢希仁.计算机网络M.北京:电子工业出版社,19994 陆姚远.计算机网络技术M.北京:高等教育出版社,2000致谢首先我们要感谢张巧云老师在这次课程设计对我们的指导，张老师在我们遇到难题的过程中给予我们帮助，致使我们的这次课程设计得以顺利完成。在此我们这一小组对张老师表示感谢！其次，我们还要感谢在设计中给予我们帮助的同学，他们的宝贵意见让这次课程设计更加完善。最后还要

42、感谢我们的学校给予我们良好的的设计环境，良好的学习环境，以及优秀的教师资源等等！在此我们该小组表示感谢！附录RIP/以下是模拟RIP协议实现的C+代码#include#include#include#include#includeusing namespace std;#define MAX 100 /最大路由数/*下面是存储类型的三个类*/class Net_sec;/网段类/路由类相当于头结点class Routepublic:string route;Net_sec *next;/网段类，包含相邻弧的信息（不用route_f，用next）,也可用于存储文件读入信息（用route_f，不用

43、next）class 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;/*上面是存储类型的三个类*/路由表和网段类class Route_netpublic:void open_file(ifstream& infile);Route_net();/ 构造函数bool judge(string str);void Init_routes();void sh

44、ow();void change(int i);void update(int i);void UPDATE();bool neighbor(int i,int j);/j和i相邻吗private:list li; /读取信息存储在这Route routeMAX; /存储图的信息，即各路由的邻接表list routesMAX; /存储各路由路由表list temp; /用于存储处理后的临时路由表string flectionMAX; /用于对应路由器与存储序列标号int sum; /用于统计路由个数;/打开文件函数void Route_net:open_file(ifstream& infil

45、e)string filename;coutfilename;infile.open(filename+.txt).c_str();if(!infile) cerrfile open error!_idt1.route_ft1.route_n; li.push_back(t1); 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

46、_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=(*it2).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

47、_f; t3=t2; t2-next=new Net_sec(); t2=t2-next; t3-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=(*it2).route_f) t2-net_id=(*it2).net_id; t2-route_n=(*it2).route_n; t3=t2; t2-

48、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; t3-next=NULL;i+;sum=i;routei.next=NULL;/网络拓扑图的邻接表表示法/判断一个路由是否已为其添加了路由表bool Route_net:judge(string str)int i=0;while(flectioni!=&inext)p.diatance=1;

49、_id=t-net_id; p.next_stop=直接交付;routesi.push_back(p);/显示各路由表void Route_net:show()int 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; /对相邻路由表change一下，距离加1，下一跳变为该路由名字void Route_net:chang

50、e(int i)Contents 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);/对一个路由进行更新操作void Route_net:update(int i)int count=0;list:iterator it1=routesi.begin();list:iterator it

51、2=temp.begin();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).diata

52、nce)(*it1).diatance=(*it2).diatance;(*it1).next_stop=(*it2).next_stop; if(count=0)routesi.push_back(*it2);count=0;/对所有路由进行更新路由表操作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 runningnext)if(flectionj=

53、p-route_n)return true;return false;int main()Route_net route_net;route_net.Init_routes();route_net.show();route_net.UPDATE();route_net.show();return 0;/*运行程序时要在当前文件下创建一个txt文件用以输入网络拓扑结构。举例如下：文件名为net_route.txt存储信息如下： R0 R1 R1 R2 R1 R3 R3 R4 R2 R4分别表示网段与连接此网段的两个路由。运行程序输入.txt文件名：net_route即可完成功能。*/OSPF#i

54、nclude #include #include #include #include #include #define MAX 10000 #define MAXLEN 8 #define ADJTYPE int typedef struct /图中顶点表示点，存放点名称 char name30; char ip12; int num; VEXTYPE; typedef struct VEXTYPE vexsMAXLEN; /顶点的信息 ADJTYPE arcsMAXLENMAXLEN; /邻接矩阵 int vexnum,arcnum ; /顶点数和边数 MGraph; /无向图MGraph

55、b; MGraph InitGraph() /*建立无向网的邻接矩阵结构*/ int i, j; MGraph G; G.vexnum =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);strcp

56、y(G.vexs3.ip,); strcpy(G.,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=130;G.arcs12=80; G.arc

57、s13=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;void Menu() /输出菜单 cout需要输出顶点的信息请按0n; cout需要边的信息输出请按1n; cout需要修改请按2n; cout需要

58、求出最短路径请按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+) if(G-arcsijMAX) cout从 到vexs

59、 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; coutv1; if(v1G-vexnum) coutv1; for(v=0;vvexnum;v+) / 初始化f

60、inal20,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; for(w=0;wvexnum;w+) if(!finalw&(min+G-arcsvwa