路由器查表课程设计报告

1 滁州学院 课程设计报告 课程名称 课程名称 计算机网络 设计题目设计题目 路由表查找过程模拟 院院 部 部 计算机与信息工程学院 专专 业 业 网络工程 无线传感器网络方向 组组 别 别 第 二 组 起止日期起止日期 2012 年 12 月 29 日 2012 年 12 月 30 日 指导教师指导教师 张 老师 2 计算机与信息工程学院二计算机与信息工程学院二 一二年制一二年制 3 课程设计任务书课程设计任务书 课程设计题目路由器查表过程模拟 组长曹学号班级网工 113 班 院部 计算机与信息 工程学院 专业网络工程 无线传感器网络方向 组员 指导教师张 课程设计目的 通过课程设计 加深对路由表的理解 掌握路由表查找 的基本原理及功能 具有初步分析实际路由表的组成 构 造 并具备准确查找路由表的能力 课程设计所需环境Windows XP VC 6 0 课程设计任务要求 编程模拟路由器查找路由表的过程 用 目的地址 掩码 下一跳 的 IP 路由表以及目的地址作为输入 为目 的地址查找路由表 找出正确的下一跳并输出结果 课程设计工作进度计划 序号起止日期工 作 内 容分工情况 12012 12 29分析讨论 进行相关的分 工以及查阅相关的资料 曹对组员进行分工 每个组员查阅资 料 摘取相关的信息 22012 12 29编写源代码 对源程序进 行调试 编写源代码 对程序代码进行调试 32012 12 30撰写课程设计报告 与老 师进行交流 对报告进行 相关的修改 并打印 根据课程设计报告模板 组员在一起 撰写实验报告 并和老师在一起交流 进行报告的相关修改 最后打印实验 报告 指导教师签字 年 月 日 系 教研室 审核意见 系 教研室 主任签字 年 月 日 4 1 目 录 1 引言 1 2 需求分析 2 2 1 设计题目 2 2 2 设计目的 2 2 3 设计主要内容及要求 2 2 3 1 设计内容 2 2 3 2 设计要求 2 2 3 3 使用环境及语言 3 3 概要设计 3 3 1 基本功能描述 3 3 1 1 路由表的结构 3 3 1 2 路由表的作用 4 3 1 3 路由表中路由的来源 4 3 2IP 路由选择 4 3 2 1 通过 RIP 路由信息协议 来实现路由选择 4 3 2 2 通过 OSPF 开放最短路径优先 来实现路由选择 6 3 2 3 Dijkstra 算法 7 4 详细设计 8 4 1 各模块的伪码算法 8 4 1 1RIP 8 4 1 2 OSPF 12 5 调试与结果说明 15 5 1 RIP 的调试结果 15 5 2 OSPF 的调试结果 16 6 课程设计总结与体会 19 参考文献 19 致谢 20 附录 21 2 1 1 引言引言 随着计算机信息技术的发展 大规模的互联网逐渐流行起来 也为路由器的发展提供 了良好的基础和平台 作为不同网络之间互相连接的枢纽 路由器系统构成了基于 TCP IP 的国际互联网络 Internet 的主体脉络 然而如何准确的发送并接受信息 则需要通过路由 表的准确查找 路由表存储着指向特定网络地址的路径 在有些情况下 还记录有路径的 路由度量值 通过路由表查找过程的设计与模拟可以更好的体现路由的选择 帮助我们准 确的理解路由的选择过程 2 2 需求分析需求分析 2 12 1 设计设计题目题目 路由器查表过程模拟 2 22 2 设计目的设计目的 该程序主要是用来模拟路由器中路由查找的过程 当主机向目的网络发送一个数据包 时 对每一个 IP 包 当发送到一个网络拓扑中的时候 可以分别使用 RIP 或 OSPF 协议 来决定数据包通过互联网络的路径 通过模拟算法的实现 我们可以模拟一个简单的路由 查找过程 进而找出最优路径 实现路由的查找 2 32 3 设计主要内容及要求设计主要内容及要求 2 3 12 3 1 设计内容设计内容 1 rip 距离向量路由协议 距离向量路由协议的特征是它在进行路由更新时 会发 送路由表的全部或一部分给邻居路由器 这台邻居路由器也必须运行 rip 协议 当路由信 息通过这种方式扩散到整个自治系统时 每个路由器会根据 Dijkstra 算法计算出到达每个 网段的最优路径 rip 选择到达某个网络的最优路径根据跳数 数据包经过一个路由器就是 一跳 2 ospf 路由器的路由选择是基于链路状态 通过 Dijkastra 算法建立起来最短路径 树 用该树跟踪系统中的每个目标的最短路径 最后再通过计算域间路由 自治系统外部 路由确定完整的路由表 与此同时 OSPF 动态监视网络状态 一旦发生变化则迅速扩散 达到对网络拓扑的快速聚合 从而确定出新的网络路由表 因此 需要把自治系统划分为 多个域 每个域内部维持本域一张唯一的拓扑结构图 且各域根据自己的拓扑图各自计算 3 路由 域边界路由器把各个域的内部路由总结后在域间扩散 这样 当网络中的某条链路 状态发生变化时 此链路所在的域中的每个路由器重新计算本域路由表 而其它域中路由 器只需修改其路由表中的相应条目而无须重新计算整个路由表 节省了计算路由表的时间 2 3 22 3 2 设计要求设计要求 任意两个节点 分别在 rip 和 ospf 协议的前提条件下 根据相应的算法找出最优路径 在 rip 协议中 所有的路由都由跳数来描述 到达目的地的路由最大不超过 16 跳 且只保 留唯一的一条路由 这就限制了 RIP 的服务半径 即其只适用于小型的简单网络 同时 运行 RIP 的路由器需要定期地 一般 30s 将自己的路由表广播到网络当中 达到对网络 拓扑的聚合 这样不但聚合的速度慢而且极容易引起广播风暴 累加到无穷 路由环致命 等问题 为此 OSPF 应运而生 OSPF 是基于链路状态的路由协议 它克服了 RIP 的许多缺陷 第一 OSPF 不再采用跳数的概念 第二 OSPF 支持不同服务类型的不同代价 从而实现 不同 QoS 的路由服务 第三 OSPF 路由器不再交换路由表 而是同步各路由器对网络状 态的认识 即链路状态数据库 然后通过 Dijkstra 最短路径算法计算出网络中各目的地址 的最优路由 2 3 32 3 3 使用环境及语言使用环境及语言 编程环境 Microsoft Visual C 6 0 编写语言 C 语言 3 3 概要设计概要设计 3 13 1 基本功能描述基本功能描述 3 1 13 1 1 路由表的结构路由表的结构 标准的路由表表目是一个二维组 目的网络地址 下一站地址 其中不携带子网信息 不能满足子网寻径 引入子网编址以后 路由表的每一表目中加入子网掩码 于是路由表 表目变为三维组 子网掩码 目的网络地址 下一站地址 4 表 1 路由表结构及使用 目的地址掩码下一跳地址 0 0 0 00 0 0 010 0 0 1 100 0 0 0255 255 255 020 0 0 1 200 0 0 0255 255 255 030 0 0 1 路由器依据路由表来为报文寻径 路由表由路由协议建立和维护 路由协议的设计则 是依据某种路由算法 路由器提供了将异构网互联的机制 实现将一个数据包从一个网络 发送到另一个网络 路由就是指导 IP 数据包发送的路径信息 3 1 23 1 2 路由表的作用路由表的作用 路由器的主要工作就是为经过路由器的每个数据帧寻找一条最佳传输路径 并将该数 据有效地传送到目的站点 由此可见 选择最佳路径的策略即路由算法是路由器的关键所 在 为了完成这项工作 在路由器中保存着各种传输路径的相关数据 路由表 Routing Table 供路由选择时使用 打个比方 路由表就像我们平时使用的地图一样 标识着各 种路线 路由表中保存着子网的标志信息 网上路由器的个数和下一个路由器的名字等内 容 路由表可以是由系统管理员固定设置好的 也可以由系统动态修改 可以由路由器自 动调整 也可以由主机控制 3 1 33 1 3 路由表中路由的来源路由表中路由的来源 在路由表中有一个 Protocol 字段 指明了路由的来源 即路由是如何生成的 链路层协议发现的路由 Direct 它的特点是开销小 配置简单 无需人工维护 只能发现本接口所属网段拓扑的路由 手工配置的静态路由 Static 静态路由是一种特殊的路由 它由管理员手工配置而 成 通过静态路由的配置可建立一个互通的网络 但这种配置问题在于 当一个网络故障 发生后 静态路由不会自动修正 必须有管理员的介入 静态路由无开销 配置简单 适 合简单拓扑结构的网络 动态路由协议发现的路由 RIP OSPF 等 当网络拓扑结构十分复杂时 手工配置 静态路由工作量大而且容易出现错误 这时就可用动态路由协议 动态 Dynamic 路 由表是路由器根据网络系统的运行情况而自动调整的路由表 路由器根据路由选择协议 Routing Protocol 提供的功能 自动学习和记忆网络运行情况 在需要时自动计算数据 传输的最佳路径 让其自动发现和修改路由 无需人工维护 但动态路由协议开销大 配 5 置复杂 3 2IP3 2IP 路由选择路由选择 路由器通常依靠所建立及维护的路由表来决定如何转发 路由表能力是指路由表内所 容纳路由表项数量的极限 3 2 13 2 1 通过通过 RIPRIP 路由信息协议 来实现路由选择 路由信息协议 来实现路由选择 RIP Routing information Protocol 路由信息协议 是应用较早 使用较普遍的内部网 关协议 Interior Gateway Protocol IGP 适用于小型同类网络的一个自治系统 AS 内 的路由信息的传递 RIP 协议是基于距离矢量算法 Distance Vector Algorithms DVA 的 它使用 跳数 即 metric 来衡量到达目标地址的路由距离 它是一个用于路由器和主机间 交换路由信息的距离向量协议 目前最新的版本为 v4 也就是 RIPv4 1 RIP 的工作原理 RIP 是一种距离矢量路由协议 RIP 使用跳数作为路由选择的度量 当在进行路由选择 是 路由表会根据最小跳数来决定转发的路径 RIP 用 路程段数 即 跳数 作为网络距 离的尺度 每个路由器在给相邻路由器发出路由信息时 都会给每个路径加上内部距离 在如图 3 1 中 路由器 3 直接和网络 C 相连 当它向路由器 2 通告网络 142 10 0 0 的 路径时 它把跳数增加 1 与之相似 路由器 2 把跳数增加到 2 且通告路径给路由器 1 则 Route1 和 Route0 与 Route2 所在网络 172 16 0 0 的距离分别是 1 跳 2 跳 图 3 1 rip 的工作原理事例 2 RIP 报文的格式 对于 RIP 报文有两种版本的格式 Version 1 和 Version 2 两种报文稍有不同 如图 3 6 2 所示 命令 版本 路由选择 地址族 路径标签 IP 地址 子网掩码 下一个站点的 IP 地址 度量值 前 20 个字节的重复 命令 版本 全零 地址族 全零 IP 地址 全零 全零 度量值 前 20 个字节的重复 a Version 1 b Version 2 0 31 0 31 图 3 2 rip 报文的两种版本格式 在一开始 所有路由器中的路由表只有路由器所接入的网络 共有两个网络 的情况 现在的路由表增加了一列 这就是从该路由表到目的网络上的路由器的 距离 在图中 下一站路由器 项目中有符号 表示直接交付 这是因为路由器和同一网络上的主 机可直接通信而不需要再经过别的路由器进行转发 同理 到目的网络的距离也都是零 因为需要经过的路由器数为零 图中粗的空心箭头表示路由表的更新 细的箭头表示更新 路由表要用到相邻路由表传送过来的信息 接着 各路由器都向其相邻路由器广播 RIP 报文 这实际上就是广播路由表中的信息 假定路由器 R2 先收到了路由器 R1 和 R3 的路由信息 然后就更新自己的路由表 更 新后的路由表再发送给路由器 R1 和 R3 路由器 R1 和 R3 分别再进行更新 3 2 23 2 2 通过通过 OSPFOSPF 开放最短路径优先 来实现路由选择 开放最短路径优先 来实现路由选择 OSPF 是一种分层次的路由协议 其层次中最大的实体是 AS 自治系统 即遵循共 同路由策略管理下的一部分网络实体 在每个 AS 中 将网络划分为不同的区域 每个区 域都有自己特定的标识号 对于主干 backbone 区域 负责在区域之间分发链路状态信 息 这种分层次的网络结构是根据 OSPF 的实际提出来的 当网络中自治系统非常大时 网络拓扑数据库的内容就更多 所以如果不分层次的话 一方面容易造成数据库溢出 另 一方面当网络中某一链路状态发生变化时 会引起整个网络中每个节点都重新计算一遍自 己的路由表 既浪费资源与时间 又会影响路由协议的性能 如聚合速度 稳定性 灵活 性等 因此 需要把自治系统划分为多个域 每个域内部维持本域一张唯一的拓扑结构图 7 且各域根据自己的拓扑图各自计算路由 域边界路由器把各个域的内部路由总结后在域间 扩散 这样 当网络中的某条链路状态发生变化时 此链路所在的域中的每个路由器重新 计算本域路由表 而其它域中路由器只需修改其路由表中的相应条目而无须重新计算整个 路由表 节省了计算路由表的时间 OSPF 的设计实现要涉及到指定路由器 备份指定路由器的选举 协议包的接收 发 送 泛洪机制 路由表计算等一系列问题 本文仅就 Dijkstra 算法与路由表的计算进行讨 论 3 2 33 2 3 DijkstraDijkstra 算法算法 Dijkstra 算法是路由表计算的依据 通过 Dijkstra 算法可以得到有关网络节点的最短路 径树 然后由最短路径优先树得到路由表 1 Dijkstra 算法的描述 初始化集合 E 使之只包含源节点 S 并初始化集合 R 使之包含所有其它节点 初始化路径列 O 使其包含一段从 S 起始的路径 这些路径的长度值等于相应链路的量度 值 并以递增顺序排列列表 O 若列表 O 为空 或者 O 中第 1 个路径长度为无穷大 则将 R 中所有剩余节点标注 为不可达 并终止算法 首先寻找列表 O 中的最短路径 P 从 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 开始寻找 找到了 D 将其放入候选列表 3 从列表中找出 C 再由 C 又找到了 D 但此时 D 的代价为 4 所以不再加入候选列表 最后将 D 加入到最 短路径树 此时候选列表为空 完成了最短路径树的计算 3 OSPF 路由表的计算与实现 有关路由表的计算是 OSPF 的核心内容 它是动态生成路由器内核路由表的基础 在 路由表条目中 应包括有目标地址 目标地址类型 链路的代价 链路的存活时间 链路 的类型以及下一跳等内容 关于整个计算的过程 主要由以下五个步骤来完成 保存当前路由表 当前存在的路由表为无效的 必须从头开始重新建立路由表 域内路由的计算 通过 Dijkstra 算法建立最短路径树 从而计算域内路由 8 域间路由的计算 通过检查 Summary LSA 来计算域间路由 若该路由器连到多个 域 则只检查主干域的 Summary LSA 查看 Summary LSA 在连到一个或多个传输域的域边界路由器中 通过检查该域内 的 Summary LSA 来检查是否有比第 2 3 步更好的路径 AS 外部路由的计算 通过查看 AS External LSA 来计算目的地在 AS 外的路由 通过以上步骤 OSPF 生成了路由表 但这里的路由表还不同于路由器中实现路由转 发功能时用到的内核路由表 它只是 OSPF 本身的内部路由表 因此 完成上述工作后 往往还要通过路由增强功能与内核路由表交互 从而实现多种路由协议的学习 OPSF 作 为一种重要的内部网关协协议的普遍应用 极大地增强了网络的可扩展性和稳定性 同时 也反映出了动态路由协议的强大功能 4 4 详细设计详细设计 4 14 1 各模块的伪码算法各模块的伪码算法 4 1 1RIP4 1 1RIP 1 定义存储类型的三个类 1 网段类 包含相邻弧的信息 不用 route f 用 next 也可用于存储文件读入信息 用 route f 不用 next public string net id string route f string route n Net sec next 2 路由类相当于头结点 class Route public string route Net sec next class Net sec 3 路由表内容类 class Contents public string net id int diatance string next stop 2 路由表和网段类 9 在路由表网段类中定义了多个函数 void open file ifstream 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 route MAX 存储图的信息 即各路由的邻接表 list routes MAX 存储各路由路由表 list temp 用于存储处理后的临时路由表 string flection MAX 用于对应路由器与存储序列标号 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 id t1 route f t1 route n li push back t1 strm clear 3 判断一个路由是否已为其添加了路由表 bool Route net judge string str int i 0 10 while flection i id t net id p next stop 直接交付 routes i push back p 5 显示各路由表 void Route net show int i 0 list iterator p for i sum i cout This is the table of flection i endl for p routes i begin p routes i end p cout p net id p diatance p next stop endl 6 对相邻路由表 change 一下 距离加 1 下一跳变为该路由名字 void Route net change int i Contents co temp erase temp begin temp end list iterator p routes i begin for p routes i end p co diatance p diatance 1 id p net id co next stop flection i temp push back co 11 7 对一个路由进行更新操作 void Route net update int i int count 0 list iterator it1 routes i begin list iterator it2 temp begin for it2 temp end it2 for it1 routes i begin it1 routes i 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 next stop it2 next stop if count 0 routes i push back it2 count 0 8 对所有路由进行更新路由表操作 void Route net UPDATE int j 0 i 0 I for I 0 I sum I for j 0 j sum j for i 0 i sum i if neighbor j i change i update j cout This is the I 1 running next if flection j p route n 12 return true return false 4 1 24 1 2 OSPFOSPF OSPF 路由协议是基于链路状态的一种路由协议 通过带宽大小来决定路径 带宽大 者优先 1 包含的头文件 include include include include include include 2 结构体定义 1 将每个路由器看成一个节点 用结构体 VEXTYPE 来定义 结构体内包含变量时名 字 name ip 地址 路由器的序号 num typedef struct 图中顶点表示点 存放点名称 char name 30 char ip 12 int num VEXTYPE 2 网络拓扑图用无向图来表示 定义一个无向图的结构体 MGraph 包含 VEXTYPE 类 型的数组变量 ADJTYPE 型的矩阵 int 型变量来记录顶点数和边数 typedef struct VEXTYPE vexs MAXLEN 顶点的信息 ADJTYPE arcs MAXLEN MAXLEN 邻接矩阵 int vexnum arcnum 顶点数和边数 MGraph 无向图 3 建立无向网的邻接矩阵结构 MGraph InitGraph 建立无向网的邻接矩阵结构 int i j MGraph G G vexnum 5 存放顶点数 G arcnum 7 存放边点数 for i 0 i G vexnum i G vexs i num i strcpy G vexs 0 name r0 13 strcpy G vexs 0 ip 192 168 0 1 strcpy G vexs 1 name r1 strcpy G vexs 1 ip 192 168 1 1 strcpy G vexs 2 name r2 strcpy G vexs 2 ip 192 168 2 1 strcpy G vexs 3 name r3 strcpy G vexs 3 ip 192 168 3 1 strcpy G vexs 4 name r4 strcpy G vexs 4 ip 192 168 4 1 for i 0 i G vexnum i for j 0 j G vexnum j G arcs i j MAX G arcs 0 1 130 G arcs 1 2 80 G arcs 1 3 110 G arcs 3 4 75 G arcs 2 4 50 for i 0 i G vexnum i for j 0 j G vexnum j G arcs j i G arcs i j return G 4 操作函数 输出每个顶点的信息 void PutOutVex MGraph 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 final 20 D 20 p 20 20 cout v0 if v0G vexnum cout v0 cout v1 if v1G vexnum 14 cout v1 for v 0 vvexnum v 初始化 final 20 p 20 20 final v 1 即已经求得 v0 到 v 的最短路径 p v w 1 则是 w 从 v0 到 v 当前求得最短路径上的顶点 D v 带权长度 final v 0 D v G arcs v0 v for w 0 wvexnum w p v w 0 if D v MAX p v v0 1 p v v 1 D v0 0 final v0 1 for i 1 ivexnum i min MAX for w 0 wvexnum w if final w if D w min v w min D w final v 1 for w 0 wvexnum w if final w for x 0 xvexnum x p w x p v x p w w 1 cout 从 vexs v0 name 到 vexs v1 name 的最短路径长度为 D v1 endl cout 路径为 for int j 0 jvexnum j if p v1 j 1 cout vexs j name endl 15 5 5 调试与结果说明调试与结果说明 5 15 1 RIPRIP 的调试结果的调试结果 图 5 1 RIP 调试结果 图 5 1 RIP 调试结果 续 16 5 25 2 OSPFOSPF 的调试结果的调试结果 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 所示 图 5 3OSPF 输出边的信息 3 当按 2 的时候可以更改节点间边上权值及带宽的信息如是更改 r1 r3 78 调试结果如图 5 4 所示 17 图 5 4OSPF 边更改后的信息 4 当按 3 的时候显示源节点到目的的最短路径及 如 r0 到 r4 调试结果如图 5 5 所示 图 5 5OSPF 输出最短路径信息 18 5 当按 4 的时候显示删除某个节点 如删除 r4 后显示的节点信息 调试结果如图 5 6 所示 图 5 6 OSPF 删除顶点后输出信息 6 当按 5 的时候显示删除某个边 如删除 r2 r3 后显示的边信息 调试结果如图 5 7 所示 图 5 7 OSPF 删除边后输出信息 19 7 当按 6 的时候显示插入某个边 如插入 r2 r3 后显示的边信息 调试结果如图 5 8 所示 图 5 8 OSPF 删除边后输出信息 6 6 课程设计总结与体会课程设计总结与体会 本次课程设计主要是通过设计一个简单的路由表查找过程的模拟来模拟实际网络中路 由变化的过程 以掌握这种有用的技术 要求通过距离矢量的 rip 协议和链路状态的 ospf 协议来分别实现路由表的查找过程 在使用 rip 和 ospf 协议的时候都是用到了数据结构中 图的邻接矩阵的存储 带权无向网的建立及 Dijkstra 算法的使用 在使用 rip 协议的网络拓 扑中 程序是根据两个节点中的跳数来计算最优路径的 在 ospf 协议的网络拓扑中 是根 据带宽即图中边的权值来计算最优路径的 在课程设计报告的撰写过程中 遇到了格式 字体等的不正确在老师的指导下都一一解决 通过实验使得小组各个成员对路由表的查找过程有了更清楚的认识和理解 在实验过 程中 通过对系统模拟算法的实现以及使用 rip 和 ospf 时的实现过程 加深对路由查找的 了解 并在实验中懂得无论多复杂的问题 都可以转化为简单的算法模拟实现 使之更形 象更具体 总之 此次课程设计既让该小组成员掌握了路由表查找过程原理 还提高了自 身的动手能力和团队合作能力 参考文献参考文献 1 胡学钢 数据结构 C 语言版 M 北京 高等教育出版社 2008 20 2 严蔚敏 吴伟民 数据结构 C 语言版 M 北京 高等教育出版社 2003 3 谢希仁 计算机网络 M 北京 电子工业出版社 1999 4 陆姚远 计算机网络技术 M 北京 高等教育出版社 2000 致谢致谢 首先我们要感谢张巧云老师在这次课程设计对我们的指导 张老师在我们遇到难题的 过程中给予我们帮助 致使我们的这次课程设计得以顺利完成 在此我们这一小组对张老 师表示感谢 其次 我们还要感谢在设计中给予我们帮助的同学 他们的宝贵意见让这次 课程设计更加完善 最后还要感谢我们的学校给予我们良好的的设计环境 良好的学习环 境 以及优秀的教师资源等等 在此我们该小组表示感谢 21 附录附录 RIP 以下是模拟 RIP 协议实现的 C 代码 include include include include include using namespace std define MAX 100 最大路由数 下面是存储类型的三个类 class Net sec 网段类 路由类相当于头结点 class Route public string route Net sec next 网段类 包含相邻弧的信息 不用 route f 用 next 也可用于存储文件读入信息 用 route f 不用 next class Net sec public string net id string route f string route n Net sec next 路由表内容类 class Contents public string net id int diatance string next stop 上面是存储类型的三个类 22 路由表和网段类 class Route net public void open file ifstream 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 route MAX 存储图的信息 即各路由的邻接表 list routes MAX 存储各路由路由表 list temp 用于存储处理后的临时路由表 string flection MAX 用于对应路由器与存储序列标号 int sum 用于统计路由个数 打开文件函数 void Route net open file ifstream cout filename infile open filename txt c str if infile cerr file open error id t1 route f t1 route n li push back t1 strm clear 23 以上把文件内容存入了类属性 li 中 list iterator it1 li begin it2 int i 0 Net sec t2 t3 for it1 li end it1 if judge it1 route f flection i it1 route f route i route flection i t3 t2 route i next new Net sec for it2 li begin it2 li end it2 if flection i 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 flection i 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 if judge it1 route n flection i it1 route n route i route flection i t3 t2 route i next new Net sec for it2 li begin it2 li end it2 if flection i 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 flection i it2 route n t2 net id it2 net id t2 route n it2 route f 24 t3 t2 t2 next new Net sec t2 t2 next t3 next NULL i sum i route i next NULL 网络拓扑图的邻接表表示法 判断一个路由是否已为其添加了路由表 bool Route net judge string str int i 0 while flection i id t net id p next stop 直接交付 routes i push back p 显示各路由表 void Route net show int i 0 list iterator p for i sum i cout This is the table of flection i endl for p routes i begin p routes i end p cout p net id p diatance 25 p next stop endl 对相邻路由表 change 一下 距离加 1 下一跳变为该路由名字 void Route net change int i Contents co temp erase temp begin temp end list iterator p routes i begin for p routes i end p co diatance p diatance 1 id p net id co next stop flection i temp push back co 对一个路由进行更新操作 void Route net update int i int count 0 list iterator it1 routes i begin list iterator it2 temp begin for it2 temp end it2 for it1 routes i begin it1 routes i 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 next stop it2 next stop if count 0 routes i push back it2 count 0 对所有路由进行更新路由表操作 void Route net UPDATE int j 0 i 0 I for I 0 I sum I for j 0 j sum j 26 for i 0 i sum i if neighbor j i change i update j cout This is the I 1 running next if flection j 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 存储信息如下 192 168 0 0 R0 R1 192 168 1 0 R1 R2 192 168 2 0 R1 R3 192 168 3 0 R3 R4 192 168 4 0 R2 R4 分别表示网段与连接此网段的两个路由 运行程序输入 txt 文件名 net route 即可完成功能 OSPF include include include include include include define MAX 10000 27 define MAXLEN 8 define ADJTYPE int typedef struct 图中顶点表示点 存放点名称 char name 30 char ip 12 int num VEXTYPE typedef struct VEXTYPE vexs MAXLEN 顶点的信息 ADJTYPE arcs MAXLEN MAXLEN 邻接矩阵 int vexnum arcnum 顶点数和边数 MGraph 无向图 MGraph b MGraph InitGraph 建立无向网的邻接矩阵结构 int i j MGraph G G vexnum 5 存放顶点数 G arcnum 7 存放边点数 for i 0 i G vexnum i G vexs i num i strcpy G vexs 0 name r0 strcpy G vexs 0 ip 192 168 0 1 strcpy G vexs 1 name r1 strcpy G vexs 1 ip 192 168 1 1 strcpy G vexs 2 name r2 strcpy G vexs 2 ip 192 168 2 1 strcpy G vexs 3 name r3 strcpy G vexs 3 ip 192 168 3 1 strcpy G vexs 4 name r4 strcpy G vexs 4 ip 192 168 4 1 strcpy G vexs 5 name 超市 r5 strcpy G vexs 5 ip 192 168 5 1 strcpy G vexs 6 name 综合实验楼 r6 strcpy G vexs 6 ip 192 168 6 1 strcpy G vexs 7 name 校医院 r7 strcpy G vexs 7 ip 192 168 7 1 for i 0 i G vexnum i for j 0 j G vexnum j G arcs i j MAX G arcs 0 1 130 28 G arcs 1 2 80 G arcs 1 3 110 G arcs 3 4 75 G arcs 2 4 50 G arcs 3 4 120 G arcs 2 3 265 G arcs 3 5 85 G arcs 3 6 400 G arcs 4 6 350 G arcs 5 6 120 G arcs 4 7 200 G arcs 6 7 150 for i 0 i G vexnum i for j 0 j G vexnum j G arcs j i G arcs i j return G void Menu 输出菜单 cout 需要输出顶点的信息请按 0 n co