IP网络拓扑结构自动搜索算法的研究与实现

IP网络拓扑结构自动搜索算法的研究与实现 I P 网络拓扑结构自动搜索算法的研究与实现 1 2颜晓蔚,王志明 ()11 南京邮电学院 计算机科学与技术系 ,江苏 南京 210003 ; 21 南京工程学院 通信工程系 ,江苏 南京 210013 摘要 : IP 网络拓扑结构的自动搜索与构造是实现一个 IP 网络管理系统的基础 ,它的目的是为了自动发 现 IP 网络中的所有设备和整个网络的拓扑结构 。论文首先简单介绍了 SN M P 和 ICM P 协议 离婚协议模板下载合伙人协议 下载渠道分销协议免费下载敬业协议下载授课协议下载 ,然后详 细描述了如何利用这两种协议来实现自动搜索算法 ,并提出了在算法中需要注意的问 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 。 关键词 :网络管理 ; IP 网络 ;拓扑自动搜索 ;路由表 () 中图分类号 : TP393102 文献标识码 :A文章编号 :1005 - 7641 200403 - 0025 - 03 的改进意见 。0 概述 1 和 ICM P 协议简介S NM P 随着 IP 网络规模的日益底大和拓扑结构的日益 复杂 ,网络管理系统的地位变得越来越重要 ,它已经成 111 SNM P 协议 为保障整个 IP 网络能够正常运行的一个重要组成部 ( 简 单 网 络 管 理 协 议 SN M P : Simple Net wo r k分 ,而拓扑结构的自动搜索与构造是实现一个 IP 网络 ) Management Protocol是一种基于 TCP/ IP 的 网 络 管 管理系统的基础 ,在整个 IP 网络管理系统中占有非常 重要的地位 ,也是评价一个网络管理系统性能的一个 ( )理协议 。该协议主要用于计算机互连网络 IP 网络 重要方面 。 的管理 ,它是当前在 IP 网络管理中应用最广泛的协 拓扑结构的自动搜索是根据一定的算法 ,并采用 议 。到目前为止 ,SN M P 协议共有 3 个版本 ,它们所定 ICM P 和 SN M P 协议来自动搜索和发现所要管理的 ( ) 义的协议数据单元 PDU : Protocol Data U nit 也有些 ( IP 网络 中 的 所 有 节 点 包 括 路 由 设 备 、子 网 和 主 机 不同 ,但和本算法有关的 3 个 PDU 是每个版本都定义 ) 等,以及它们之间的连接关系 ,从而构造出整个网络 的拓扑结构 ,并且把构造出的拓扑结构保存在定义好 的 ,分 别 是 : Get2Request 、Get Next2Request 和 Get2Re2 的数据库中 ,以备其他部分使用 。 spo nse 。 1 拓扑结构的自动搜索的算法可以分为两个部分 ,R FC 1157 描述了 SN M P 的体系结构模型。该 一是骨干网络的搜索 ,主要是用于搜索整个网络中的 模型是一种代理 —管理者模型 ,它从信息处理的角度 所有路由设备和子网 ,以及它们之间的连接关系 。该 规定了 SN M P 网络管理系统的结构 ,描述了管理者和部分的实现以 SN M P 协议为主 , 辅助以 ICM P 协议 ; 代理角色以及它们之间的相互关系 ,如图 1 所示 。管 另一部分是子网内主机的搜索 ,主要是用于发现子网 () 理者的任务是发送管理命令 如查询命令和设置命令 ( 内的所有主机设备 ,以及该子网的拓扑形式 总线型 、 并接收代理回送的数据 ,代理的任务是直接管理有关 ) 令牌环型等。该部分的实现以 ICM P 协议为主 ,辅助 ( 的网 元 、维 护 本 地 的 管 理 信 息 库 M IB : Management以 SN M P 协议 。 ) Info r matio n Base 、响 应 管 理 者 发 来 的 查 询 或 修 改 本文首先简单介绍了 SN M P 和 ICM P 协议 ,然后 ( ) M IB 中的对象实例命令 ,并可以通过陷阱 Trap 来把 详细描述了如何利用这两种协议来实现自动搜索算 网元所发生的特定的事件通知管理者 。M IB 中存放 法 ,包括骨干网络的搜索过程和子网内主机的搜索过 了各种被管对象的管理参数 ,其中的信息组织为树型 程 ,并分别给出了在实现时需要注意的问题和对算法结构 。 收稿日期 : 2003 - 08 - 12 ; 修回日期 : 2003 - 09 - 23 ( ) 作者简介 : 颜晓蔚 1976 - ,女 ,江苏如东人 ,硕士研究生 , 研究方向为计算机通信与网间互联 ; 1 SNM P 的体系结构模型图 () 王志明 1967 - ,女 ,江苏苏州人 ,硕士 ,讲师 ,从 事电力通信的教学和科研工作 。 112 ICM P 协议 S YN TA X Ip Ro ute Ent ry ( 网际控制报文协议 ICM P , Inter net Co nt rol Mes2 : : = { ip Ro ute Table 1 } ) sage Protocol是一个不携带用户数据的网络层协议 , 2 Ip Ro ute Ent ry : : = 它的消息封装在 IP 数据报中。ICM P 协议有两个 SEQ U EN C E { 功能 :一是报告错误的功能 ,如将数据不能到达目的地 ip Ro uteDest IpAddress ,该路由的目的子网地 的消息通知发送端 ; 另一个是为诊断程序携带查询和 址 。( ) 应答消息 ,如使用 ICM P 回应 echo 消息来确定网络 ip Ro ute If Index IN T E GER ,该路由的本地接 上的另一台设备是否可以到达 。 ( 本算法中用到了两种报文即 ,回应请求 echo re2 口索引 。 () ) quest报文和回应应答 echo respo nse报文 ,其报文格 ip Ro uteNext Hop IpAddress ,该路由的下一个 式如图 2 所示 。其中的“标识符”与“序号”用于匹配特 路由器地址 。 定的请求和应答 ,因此允许同一设备同时向多个 IP 地 ip Ro ute Type IN T E GER ,该路由的类型 。址发出请求 。回应请求/ 应答报文用来检测目的 IP 地 ( ) ip Ro uteMask IpAddress , 目的子网地址的掩 址的可到达性 。请求者 一般是一台主机向特定的 IP 地址发送一个回应请求报文 ,其中包含一个可选的 码 。 ( ) 数据区 。目的 IP 地址所表示的设备 回应者发回响 应的回应应答 ,应答中包含了该请求中的可选数据区 } 的拷贝 。 每一台路由设备都包含有多个接口 ,用于连接不 同的子网 。接口表用于描述路由设备中各个接口的基 本信息 ,其结构和本算法中所要用到的变量定义如下 (())类型 8 或 0 代码 0 校验和 所示 : 标识符 序号 if Table OBJ EC T2T YP E 可选数据 S YN TA X SEQ U EN C E O F If Ent ry : : = { interf aces 2 } 图 2 回应请求/ 应答报文格式if Ent ry OBJ EC T2T YP E 回应请求和回应应答均以 IP 数据报的形式在互S YN TA X If Ent ry 连网中传送 ,如果请求者成功收到了一个应答 ,则说明 该目的 IP 地址可到达 ,而且请求者和回应者之间的路 : : = { if Table 1 } 由器也能正常寻址 。在一个 IP 网络中 ,用户命令 Ping If Ent ry : : = 就是利用 ICM P 回应请求/ 应答报文来测试目的 IP 地 SEQ U EN C E { 址是否可以到达 。在本算法中 ,也是用 ICM P 报文来 if Index IN T E GER ,接口索引 ,同路由表中的实现 Ping 功能 。 ip Ro ute If Index 。 if Type IN T E GER ,接口类型 ,如总线或令牌 2 路由表和接口表的结构 环等 。 在讨论算法的实现之前 ,我们首先要介绍一下路 由设备中路由表和接口表的结构 ,骨干网络的搜索主 } 要就是根据这两个表来实现的 。路由表和接口表在 3 为了 使 算 法 更 加 准 确 , 在 实 现 过 程 中 还 用 到 了R FC 1213中定义 ,并位于 M IB 树中的 M IB2 ?分支 之下 。 M IB 库中的其他对象 ,如 ip Fo rwarding ,用于判断一个 设备是否具有路由转发功能 ; 以及 IpAddr Table ,设备 路由表用于存储路由设备中各条路由的信息 ,其 的地址表 ,可以读出一台设备中的所有 IP 地址 ,从而 结构和本算法中所要用到的变量定义如下所示 : 避免把一台具有多个 IP 地址的路由设备当作一台设 ip Ro ute Table OBJ EC T2T YP E 备处理 。S YN TA X SEQ U EN C E O F Ip Ro ute Ent ry 3 算法描述 : : = { ip 21 } 当前常见的网络拓扑发现算法的基本原理都是运 ip Ro ute Ent ry OBJ EC T2T YP E 用协议特性来获取路由器的路由表信息 ,并由这些信 eDest 所表示的子网中 。如果 ip RouteNext Hop 在 ip Rout2 息用来构造网络的拓扑图 。但这些算法在实现时往往 存在一定的缺陷 ,如无法识别具有“双重身份”的路由 eDest 所表示的子网中 ,则该节点与 ip RouteDest 子网直接 () 器 、没有区分骨干网络的搜索和子网内主机的搜索等 , 相连 ,并可以根据接口表 if Table 中 的 接 口 类 型 变 量 这些缺陷使得算法在实现时无法得到正确的网络拓扑if Type 来判断该子网的类型 ; () ( ) 图 。本文所描述的算法中提出了这些问题 ,并给出了 4把第 3步中的得到的路由设备的地址不重 ( ) 解决问题的 方法 快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载 。 复地加入到待搜索节点队列中 ,重复第 3步 ,进一步 IP 网络的一般拓扑结构模型如图 3 所示 。子网搜索与之相连的路由设备和子网 ,就可以得出整个骨 通过各自的出口路由器与其他子网通信 ,它们都连接 干网络的拓扑结构 。 以上所描述的是算法的一般实到出口路由器的一个接口上 。路由器的其他接口可以 现过程 ,这种算法 连接一个子网 ,也可以同其他路由器的接口相连 。当 过程易于理解 ,但在实际的实现过程中 ,需要注意到以 一个子网中的某一台主机发送数据时 ,数据包首先到 下几点 ,否则可能无法得到准确的网络拓扑图 。 ) 1有些设备具有“双重身份”,既是一台主机 ,也达该子网的出口路由器的接口 ,路由器再检测数据包 () 具有路由转发功能 ip Fo rwarding = 1,此时我们往往 中的目的地址 ,并根据自己所保存的路由表来确定把 该数据包转发到哪一个路由器或子网 。下一个路由器 需要把它们作为路由设备来看待 。 ) 再进行类似的处理 ,依此类推 ,数据包就可以最终到达 2一般来说 ,一台路由设备有多个接口 ,而每个 目的地 。 接口可能有多个 IP 地址 。在算法实现时 ,如果简单地 把它作为多个路由器来对待 ,就无法得到准确的网络 (拓扑图 。此时 ,我们需要根据该路由设备的地址表 ip ) Addr Table,读出一台设备的所有 IP 地址 , 从而确定 多个 IP 地址是否属于同一台设备 。 ) 3 在 遍 历 一 个 网 络 的 过 程 中 , 有 些 目 的 子 网 () ip Ro uteDest,包括在它前面的一些路由设备 ,可能距 离起始节点很远 ,它们也许根本就不是我们所要管理 图 3 IP 网络的一般拓扑结构 的节点 ,此时搜索如果无限制地进行下去 ,只有白白浪 费网络资源 。所以在搜索算法中 ,需要根据所要管理 根据 IP 网络的一般拓扑结构 ,我们可以把它分为 ( 两个主 要 的 部 分 : 一 部 分 是 骨 干 网 络 backbo ne net2 的网络规模设置一个“搜索深度”,在搜索过程到达这 ) wo r k,主要节点包括各个路由设备 、子网等 ; 另一部 个深度以后 ,就不再进行下去 。也就是说 ,只要把我们 分是子网内主机 。 所要管理的节点搜索出来就可以了 。 311 骨干网络的搜索( ) ) 4在到达一个目的子网 ip Ro uteDest 或搜索深 对于骨干网络的搜索是要发现整个网络中的所有 度之前 ,如果在某个网络分支上遇到不支持 SN M P ,或 路由设备 、子网以及它们之间的连接关系 。骨干网络 ( ) 者不知道 SN M P 的团体名 Co mmunit y的设备 ,则该 的搜索主要是根据骨干网络中路由设备的路由表来实 分支上的搜索就不再继续进行下去 。 现的 ,搜索步骤如下 : 312 子网内主机的搜索() 1给出一个搜索的起始节点 。起始节点最好是 子网内主机的搜索是根据上一步中得到的子网地 一台路由设备 ,如果给出的是主机 ,则需要找出该主机 址和子网掩码 ,确定子网内存在哪些主机 ,以及这些主 所在的子网的出口路由器作为起始节点 。起始节点可 机的状态 、类型及网络接口 。以有多个 ; () 1取出一个子网的地址和掩码 ,可以计算出子 () 2建立一个待搜索节点的队列 ,把起始节点作 网内各主机的 IP 地址 。用 Ping 功能依次检测各个 IP 为待搜索节点加入到该队列 ; 地址 ,察看主机是否存在 。 () 3从队列中取出一个待搜索节点 ,用 SNMP 协议 () 2用 SN M P 协议读取各主机的基本信息 ,如果 ( ) 查询 它 的 路 由 表 ip Route Table , 根 据 路 由 表 中 的 设备不支持 SN M P 协议 ,则该 IP 地址表示一般的主 ip RouteNext Hop 变量可以找到与该节点直接相连的路由 机 。否则 ,把读出的基本信息保存起来 。设备 的 IP 地 址 , 并 可 以 根 据 本 地 接 口 索 引 变 量 () 3如果设备支持 SN M P 协议 ,再察看它是否具 () ip Route If Index 和接口表 if Table 中的接口索引变量 if Ind2 () 有路由转发功能 ip Fo rwarding = 1,如果有 ,则把它不 ex 来确定它们之间的连接关系 。同时根据 ip RouteDest 以 重复地加入到待搜索的路由设备中 。及 ip RouteMask 可以判断 ip RouteNext Hop 是否在 ip Rout2 () 下转第 48 页 程序中 ,设置信息帧的结束标志 。当主程序检测到一Mo dbus 协议适信号进行实时数据采集与传输 。由于 用范围广 ,因此 ,本系统也可广泛地用于任何具有 RS2个信息帧的结束标志时 ,调用 CRC 校验子程序 ,并检 验设备地址是否正确和接收字节数目是否大于或等于 232 接口 、遵循 Mo dbus 通信协议 标准 excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载 的系统之间 。 最小值 ,以此来判断接收到的信息帧的有效性 。参考文献 : 3 结束语1 Modico n1Modbus Protocol Reference Guide Z 120001 赖麒 文 18051 单片机 C 语言开发环境实务与 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 M 1 北2 本系统已应用于保定市领新科技有限公司开发的 京 :科学出版社 ,20021 蓄电池在线监测装置中 ,可以对遥测 、遥信 、遥控 、遥调 Modbus protocol a ppl ied in on2l ine supervision product of accumula tor Z HA O J i a2y u , B A O Hui ()Dep t1 of Elect ro nic and Co mmunicatio n Engineering ,Nort h China Elect ric Power U niversity ,Baoding 071003 ,China Abstract : This paper mainly deals wit h how to use Modbus p rotocol to implement serial co mmunicatio n o n t he base of o n2line supervisio n p roduct of accumulator ,and it simply int roduces t he f rame st ruct ure of Modbus p rotocol1 Key words : o n2line supervisio n ; Modbus p rotocol ; serial co mmunicatio n () 上接第 27 页 () ( 4如果设备不具备路由转发功能 ip Fo rwarding,也是评价一个网络管理系统性能的一个重要的地位 ) = 0,还需要用 SN M P 协议读出该设备的所有 IP 地 重要方面 。 事实上 ,在此我们给出了一种 IP 网络拓扑结构自 址 ,以免把具有多个 IP 地址的主机当做多个主机来处 理 。动搜索的算法 ,本文首先简单介绍了算法中所用到的 () ( ) 5取出下一个子网的地址和掩码 , 重复第 1SN M P 和 ICM P 协议 ,然后不仅详细描述了如何利用 步 。这两种协议来实现自动搜索算法 ,包括骨干网络的搜 在用 Ping 功能依次检测子网中的 IP 地址时 ,为 索过程和子网内主机的搜索过程 ,而且给出了在实现 了提高检测速度和避免网络阻塞 ,可以用异步的方式 时需要注意的问题和对算法的改进意见 。用该算法能 发送和接收 ICM P 数据包 ,这样可以同时对多台主机 够得到一个 IP 网络准确的拓扑结构 。进行检测 。一般来说 ,采用异步方式检测 IP 地址 ,一 参考文献 : 个 C 类网可以在几秒钟内检测完毕 ,而且不会造成网 ( ) RFC 11571 The Simple Network Management Protocol SNMP1 络阻塞 ,可以极大地提高算法的性能和效率 。 S 1May 19901 4 结束语2 RFC 12131Management Information Base for Network Man2 agement of TCP/ IP2based Internet s : M IB2?S 1March 19911拓扑结构的自动搜索与构造是实现一个 IP 网络 3 R FC 7921 Internet Co nt rol Message Protocol S 119811 管理系统的基础 ,在整个 IP 网络管理系统中占有非常 The analysis and implementation of a utomatic topology discovery of IP net works 1 2Y A N X i ao2w ei, W A N G Zhi2m i n g (11Dep t1 of Co mp uter Science & Technolege ,Nanjing U niversit y of Post and Teleco mmunicatio ns ,Nanjing 210003 ,China ; )21Dep t1 of Co mmunicatio n Engineering ,Nanjing Instit ute of Technology ,Nanjing 210013 ,China Abstract : Auto matic topology discovery is t he base of a management system of IP net wor k ,it is to discover all t he devices and t he topology of t he whole IP net wor k1 In t his article ,SNM P and ICM P p rotocols are int roduced first1 Then we describe how to implement t he algorit hm of auto matic topology discovery in detail ,and t he issues t hat must be noticed in t he implementatio n of t he algorit hm are p resented too1 Key words : net wor k management ; IP net wor k ;auto matic topology discovery ; route table