（计算机科学与技术专业论文）网络拓扑发现技术的研究与实现.pdf

里堕型兰垫查奎兰堕窒生堕兰垡笙苎 摘要 计算机网络愈来愈复杂，对网络管理的要求也愈来愈高。作为网络管理最基本功 能之一的网络拓扑发现，其技术的研究与实现具有十分重要的意义。 本文重点研究了“系统管理与网络管理”系统中拓扑发现子系统的体系结构和功 能。文中描述了基于拓扑数据库的网络拓扑自动发现系统的总体结构，此结构具有良 好的伸缩性，有利于各种拓扑发现技术的综合利用。本文对该系统的实现技术进行了 细致的研究和分析，设计了一个易于存储、分析及显示的拓扑数据库，利于拓扑信息 的存储和分析处理。在研究网络拓扑发现的基本技术，分析当前常用的两种拓扑发现 算法的基础上，设计并实现了一种灵活的拓扑发现算法。该算法以当前广泛使用的 s n m p ( 简单网络管理协议) 为基础，同时利用了a r p ( 地址解析协议) 及i c m p ( i n t e r n e t 报文控制协议) 。将该算法应用于网络拓扑自动发现系统，在实际运行中取得了令人满 意的结果。 【关键字】拓扑发现，简单网络管理协议，管理信息库，拓扑数据库 国防科学技术大学研究生院学位论文 a b s t r a c t t h e c o m p l e x i t y o f c o m p u t e r n e t w o r k sa c c e l e r a t et h e i m p r o v e m e n t o fn e t w o r k m a n a g e m e n t ，t h u s i ti s n e c e s s a r ya n ds i g n i f i c a n tt o d or e s e a r c ha n di m p l e m e n t a t i o no f n e t w o r k t o p o l o g yd i s c o v e r i e sw h i c h a r et h ee s s e n t i a lf u n c t i o n si nn e t w o r k m a n a g e m e n t t h e p a p e rp r e s e n t sm y w o r ka n dc o n c l u s i o no nt h ep r o j e c to f s y s t e mm a n a g e m e n t a n d n e t w o r k m a n a g e m e n t m y r e s e a r c hf o c u s e so nt h ef r a m e w o r ka n df u n c t i o no ft h e s u b s y s t e m o fn e t w o r kt o p o l o g y d i s c o v e r y n t h i s p a p e r , t h es c a l a b l e f r a m e w o r ki s p r e s e n t e d w h i c hc a n i n t e g r a t em a n yk i n d s o ft e c h n o l o g i e sa b o u tn e t w o r k t o p o l o g y d i s c o v e r i e s ，a n dt h et o p o g r a p h yd a t a b a s ei sd e s i g n e db yw h i c ht o p o l o g yi n f o r m a t i o ni s e a s i l ys t o r e d ，a n a l y z e da n dv i s u a l i z e da f t e rt h ei n - d e p t hs t u d yo ft h ek e yt e c h n o l o g i e sa b o u t t h ei m p l e m e n t a t i o no ft h es u b - s y s t e m f u r t h e rm o r e ，a f t e rad i s c u s s i o na b o u tt h ef e a t u r e s a n dd r a w b a c k so ft h ec u r r e n tt e c h n o l o g yo fn e t w o r k t o p o l o g yd i s c o v e r i e s ，a na l g o r i t h mo f t o p o g r a p h y d a t a b a s eb a s e dw h i c hi n t e g r a t e s s n m p , a r pa n di c m pi s d e s i g n e d a n d i m p l e m e n t e d t h i sa l g o r i t h ms h o w s a g o o dp e r f o r m a n c ei nr u n t i m e k e y w o r d t o p o l o g yd i s c o v e r y , s i m p l en e t w o r km a n a g e m e n tp r o t o c o l ( s n m p ) m a n a g e m e n ti n f o r m a t i o nb a s e ( m i b ) ，t o p o g r a p h yd a t a b a s e i i 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含 其他人已经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示谢意 学位论文题目： 圆鳌堑盐蕴塑拉盎煎盈究生塞理 学位论文作者签名：盘盈垄日期：彻y 年，月哆日 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留、使用学位论文的规定。本人授权 国防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子 文档，允许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密学位论文在解密后适用本授权书) 学位论文题目： 圆鳖堑盐崖趣垫盔盟盈窥生塞理 学位论文作者签名：盘垫叁 日期：渺) ，年，f 月i 多日 作者指导教师签名 b 翔：z 年? ? a f ；b 国防科学技术大学研究生院学位论文 第1 章绪论 1 1 网络拓扑发现概述 随着计算机及通信技术的飞速发展，计算机网络已经渗透到社会经济生活的各个 方面，对社会进步与经济发展起着越来越重要的作用，也使人们的工作甚至生活方式 发生了巨大的变革。当我们对计算机网络的依赖越来越多时，我们自然关心如何保持 计算机网络良好的运行状态，如何对网络系统进行优化，如何增强管理者对网络容量 的了解和控制能力；如何及时发现网络运行过程中出现的故障、报告故障问题、判断 故障原因并尽快解决网络故障，这些就涉及到网络管理所研究的内容。随着网络 规模的激增，网络复杂性和异构性的焦点化，网络管理问题上升到了网络建设的战略 性位置。 一般说来，网络管理就是通过某种方式对网络状态进行调整，使网络能正常、高 效地运行。其目的很明确，就是使网络中的各种资源得到更加高效的利用，当网络出 现故障时能及时做出报告和处理，并协调、保持网络的高效运行等。早在八十年代， 国际标准化组织( i s o ) 定义了网络管理的五个功能域：故障管理：这是网络管理 的基本功能，其目的是保证网络能够提供连续可靠的服务，其内容包括对网络状态的 监视、检测，孤立和控制网络异常活动；配置管理：也是网络管理的基本功能，至 少包括识别被管网络的拓扑结构、标识网络中的各个对象、自动修正指定设备的配置、 动态维护网络配置数据库等；安全管理：保证网络用户和网络资源不被非法使用， 以及防止网络管理信息受到未经授权的访问；性能管理：通过收集和分析网络数据 辅助管理者优化网络性能；计费管理：收集和处理用户使用网络资源的统计信息。 其中，网络拓扑发现是网络管理系统最基本的功能和要求，是配置管理的核心，故障 管理的基础，在整个网络管理系统的开发中占有举足轻重的地位。 网络拓扑发现的主要目的是获取和维护网络元素的存在性信息以及它们之间的 连接关系信息，并在此基础上给出整个网络连接状态的图示。这里提及的网络元素通 常包括互联设备( 如：路由器、网关、网桥、交换机等) 、主机和子网。 由于网络规模日益庞大而且不断变化，手动获得网络拓扑信息很不现实，只有基 于主动探测的自动拓扑发现才能满足实际要求。此处的自动拓扑发现是指在无需用户、 网管人员介入的情况下自动获得网络拓扑结构的相关信息。 根据发现的层次，网络拓扑发现可分为三类： 1 三层拓扑发现 主要发现路由器、子网和主机所构成的网络，揭示其存在性，并给出它们之 间的连接关系。 2 二层拓扑发现 在三层拓扑发现的基础上，揭示交换机、v l a n 、l a n 所构成的网络或通信 网络，给出路由器之间的链路信息。 第1 页 国防科学技术大学研究生院学位论文 3 高层拓扑发现 在三层拓扑发现的基础上，揭示防火墙、v p n 网关、高层交换机、网络服务 器等应用设备所构成的网络，给出有关信息。 根据发现的范围，拓扑发现可分为：域内拓扑发现和域外拓扑发现( 骨干网的拓 扑发现) 。 好的网络自动拓扑发现软件要求做到对网络带来的额外负载和开销尽可能小；拓 扑发现速度快；能尽可能地发现完整的网络，做到最小遗漏；发现的网络结构准确无 误：拓扑发现自动化程度比较高。 1 2 网络拓扑发现的国内外发展现状 当前，商用的企业级网络和系统管理平台主要有：h p 的o p e n v i e w ，i b m 的t i v o l i ， c a 的u n i c e n t e rt n g ，s u ns o l s t i c ee n t e r p r i s em a n a g e r ，a d v e n t n e t 公司的a d v e n t n e t w e bn m s 等。这些产品在网络拓扑发现上存在如下的共性： 以s n m p 协议作为网络拓扑发现的基础 利用菜些特定的网络协议，对基于s n m p 协议的拓扑发现方法进行扩充 以三层拓扑发现为主，兼顾二层拓扑发现 域内的拓扑发现 这些产品的优势在于网络设备相关信息的搜集相当完备，能发现多种网络设备； 而其不足则在于拓扑发现速度较慢，且局限于小规模的环境，不能找出单个设备间的 物理连接关系。另外，还存在以下不足： 价格昂贵( 软件、专用硬件设备) 。首先是软件费用高。它们提供了丰富的功 能，因而开发成本高。但问题是这其中的许多功能并非所有用户都需要。其 次，要求运行于专用的高性能工作站上，需要额外的硬件开销。 安装、运行和维护困难。 由一个或少数几个节点收集数据，易产生瓶颈，对问题的反应不够灵敏，管 理规模上受到限制。 在网络拓扑发现的研究领域，出现了以下的成果： 互联网数据分析协会( c a i d a ) 以t r a c e r o u t e 为基础，综合b g p 表，开发了 s k i t t e r 系统，探测组成i n t e r n e t 的网络节点之闻的连接关系。 康奈尔( c o m e l l ) 大学开发的o c t o p u s 系统，综合s n m p 、t r a c e r o u t e 、启发式 猜想等拓扑发现方法，进行域内和骨干网的拓扑发现。 南加州大学工程学院信息科学研究所( t h eu n i v e r s i t yo fs o u t h e r nc a l i f o m i a s c h o o lo f e n g i n e e r i n g si n f o r m a t i o ns c i e n c e si n s t i t u t e ) 设计了一个拓扑发现原 型：m e r c a t o r ，利用t r a c e r o u t e 等工具提供的逐跳回馈( h o p - b y - h o p f e e d b a c k ) ， 发现网络拓扑中的i p 地址，构造网络拓扑图。尽管许多新的路由器不再响应 t r a c e r o u t e 报文，该方法仍在当前的i n t e r n e t 上取得了可喜的结果。 第2 页 国防科学技术大学研究生院学位论文 1 3 课题研究背景 本课题来源于项目“系统管理与网络管理”。 网络管理是计算机网络的三大经典问题( 路由，流控，网管) 之一。古老而永具 挑战性；网络的“可靠性、安全性”都与网络管理密切相关。 网络结构、规模和应用发生的巨大变化促进了网络管理技术的发展，八十年代国 际标准化组织( i s 0 ) 定义的网络管理的五个功能域已远远不能满足现代网络管理系 统的要求，网络管理功能的内涵需要增加以下方面： 网络管理向系统管理发展 故障管理包括应用系统的故障分析与定位 配置管理包括应用系统的资源动态配置 安全管理包括大部分网络安全功能，如i d s ，安全审计，防火墙，用户认证等 性能管理包括端端q o s 管理，性能测度，流量管理等 计费管理包括基于策略和s l a 的计费等 传统的网络管理模式已不能适应目前网络的分布性、可伸缩性、动态性和可扩展 性等特性，新一代的网络管理要求具有： 分布性：开放、灵活的网络环境，需要网络管理的可分布性和可扩充性以及 网管任务的灵活分布和自动执行。 基于策略和实时性：传统的网络管理以静态管理为主，网管操作通常须由操 作员人工进行，管理无实时性，对于大型网络很难有实时反应。现在的网管 产品普遍采用基于策略的网络管理，它以动态管理为主，根据预先定制的策 略自动进行网络管理，管理实时性强，能综合各种因素对全网进行及时有效 的反映。 拓扑发现的可伸缩性：面对当前日益纷繁复杂的网络，要在给网络带来最小 额外负载的前提下，自动、快速、完整、准确的发现各种网络的拓扑结构， 就需要充分发挥各种拓扑发现方法和技术的优势，实现多种方法和技术的配 合使用，并根据所要管理的网络或子网的特征，使用相应有效的算法。 可视化w e b 管理界面：基于w e b 的网络管理模式融合了w e b 功能和网络管理 技术，允许网络管理人员通过与w w w 同样的形式去监测、管理网络系统。 利用任一w 曲浏览器可在网络任何结点上方便、迅速地配置、控制及访问网 络。这种新的网络管理模式的魅力在于它是交叉平台，可以很好解决由于多 平台结构产生的互操作问题。它能提供比传统网管界面更直接、更易于使用 的图形界面，从而降低对网络管理操作和维护人员的特别要求。 综合管理性：研究综合性的网络管理。支持简单网络管理协议s n m p 、c m i p 、 t l i ( t r a n s a c t i o nl a n g u a g e1 ) 、c l i ( c o m m a n dl i n ei n t e r f a c e ) 等多种网管协 议能在很大程度扩展网络管理的范围和领域：另外，网络管理可广泛涉及各 种应用领域包括i d c 、企业网、社区网及接入网、企业e x t r a n e t 网、i s p ( 城 域网，骨干网) 、电信网等。 第3 页 国防科学技术大学研究生院学位论文 根据上述发展需求，“系统管理与网络管理”项目确立了研究目标：提出适应于 大型计算机网络和通信网络及应用系统的综合系统管理与网络管理体系结构，解决基 于大型数据库的分布网管结构、网络自动拓扑发现和可视化、数据采集、事件过滤与 关联性分析、资源依赖性分析、策略描述与策略服务等关键技术，建立一个综合系统 管理与网络管理的原型系统，为最终研制高性能、实用的系统管理与网络管理产品提 供强有力的技术支持。 1 4 课题研究内容 在拓扑发现子系统的开发过程中，根据“系统管理与网络管理”项目的方案设计 要求，参考国外的一些成功项目中取得的经验，同时也考虑到国内的实际情况，进行 基于大型拓扑数据库的拓扑自动发现系统的设计和实现。从理论研究和代码实现两个 方面开展工作，主要完成了以下的一些工作： 参加“系统管理与网络管理”项目方案的研制 研究了现有的网络拓扑发现技术 设计了基于单个探测点的网络拓扑自动发现系统和基于多个探测点的分布式 网络拓扑自动发现系统 参与网络拓扑数据库的设计，并实现了子网库和结点库 综合分析两种当前常用的拓扑发现算法，在这两种算法的基础上设计了一种 灵活的拓扑发现算法，实现了基于单个探测点的网络拓扑自动发现系统中的 拓扑发现模块以及基于多个探测点的分布式网络拓扑自动发现系统中的网元 服务器 第4 页 国防科学技术大学研究生院学位论文 第2 章网络拓扑发现技术 网络拓扑发现在“系统管理与网络管理”系统的开发中占有举足轻重的地位，其 技术的研究具有十分重要的意义。本章在简要介绍网络拓扑结构一般模型的基础上， 对现有的网络拓扑发现技术作了一个综述，并对拓扑发现的相关问题作了相应论述。 2 1 网络拓扑结构的一般模型及路由选择算法 口主机0 路由器。子网 图2 1 网络拓扑结构的一般模型 网络拓扑图的自动搜索实现，实际上是一个图的遍历过程。对于网络拓扑结构， 路由器、子网、主机等网络元素可以认为是图中的结点。路由器结点是与子网和其它 路由器结点相邻的结点，而子网结点可以认为只与路由器结点相邻，至少与它的缺省 路由器相邻。如上图所示，各子网通过各自相邻的路由器与其他子网通信，这些子网 可以是一个局域网，也可以是某个局域网的一个子网。它们都连接到路由器的某个端 口上。路由器的一个端口可以连接一个子网，也可以与其他路由器直接相连。一个子 网的某一机器发送数据时，数据包首先到达该子网的缺省路由器，缺省路由器检测数 据包中的目的地址，根据其路由表确定该目的地址是否在与自己相连的子网中，如果 是，则把数据包直接发给目的地，否则，转发给路由表中规定的下一跳路由器。这样， 下一个路由器再进行类似处理，依次类推，数据包将最终到达目的地。 路由表是网络管理信息的重要来源，一个理想的路由表如下表所示： l目的地址下一跳地址掩码 1 0 0 0 02 0 2 1 2 0 3 2 2 4 lo o 0 0 l 2 0 2 1 2 0 2 02 0 2 1 2 0 2 2 5 42 5 5 2 5 5 2 5 5 0 第5 页 国防科学技术大学研究生院学位论文 2 0 2 1 2 0 6 1 4 42 0 2 1 2 0 6 2 3 62 5 5 2 5 5 2 5 5 2 4 0 2 0 2 1 2 0 6 1 7 62 0 2 1 2 0 6 2 3 62 5 5 2 5 5 2 5 5 2 4 0 2 0 2 12 0 6 2 2 42 0 2 1 2 0 6 2 3 82 5 5 2 5 5 2 5 5 2 4 0 2 0 2 1 2 0 8 02 0 2 1 2 0 8 2 5 42 5 5 2 5 5 2 5 5 0 2 0 2 1 2 0 1 0 02 0 2 1 2 0 1 0 2 5 42 5 5 2 5 5 2 5 5 0 表2 1 典型的路由表结构 如上表所示，路由表中的每个条目都包含三个参量： 路由选择算法依据上述三个参量进行，算法如下 2 5 】 从数据报中提取目的i p 地址d ； 根据路由表，计算目的地网络的i p 地址n ： i f n 与任何直接相连的网络的地址匹配 t h e n 通过该网络把数据报交付到目的地d e l s ei f d 是特定主机寻径 t h e n 把数据报发送到表中指定的下一跳 e l s ei f 表中包含到网络n 的一个路由 t h e n 把数据报发送到表中指定的下跳 e l s ei f 表中包含一个默认路由 t h e n 把数据报发送到表中指定的默认路由器 e l s e 宣布选路出错 从路由表中可以得到网络拓扑的有关信息，至于如何访问以及分析路由表，这将 在后面介绍。 2 2 拓扑发现的基本方法 拓扑发现主要采用以下几种基本方法： 使用s n m p 协议查询临近路由器的m i b 信息：包括路由器中的路由表、地址表 信息以及其他路由协议的相关信息。 使用i c m p 的查询和差错报告报文：向网络上的所有设备发出i c m p 报文，根 据应答报文，判断目标网段中主机的活跃状态，并记录每个主机的i p 地址、 所属网段地址、状态等信息。 利用t r a c e r o u t e 命令，确定一个包从源地址到目的地址的路由，得到路由设 备间的连接关系。 处理本网段的a r p 应答报文，根据a r p 应答报文，确定本网段活跃主机的i p 地址，并记录该主机的m a c 地址、状态等信息。 第6 页 国防科学技术大学研究生院学位论文 利用d n $ “z o r l et r a n s f e r ”：大多数域名服务器通过“z o n e t r a n s f e r ”命 令返回含有域内名字到其i p 地址的绑定的列表文件的副本，可以发现域内的 所有主机和路由器。 侦听、接收网络上的r i p 路由广播信息，分析r i p l 、r i p 2 中的路由可达性信 息，从而决定哪些主机是路由器，以及该路由器连接的网段信息。对于r i p l 协议，可直接在5 2 0 端口侦听接收；r i p 2 路由协议中增加了对组播的支持， 故先将管理站加入组播组中后，再接收r i p 报文。 模拟o s p f 和b g p 协议的简单功能，向o s p f 和b g p 的路由器主动建立链接， 获取路由信息。 2 2 1 简单网络管理协议( s n m p ) s n m p 是适用于互联网络设备的网络管理框架，已经被广泛的应用于商业产品中， 并成为网络管理的事实上的标准【2 ”。s n m p 主要基于i p 协议栈，也可以在其它协议栈 上运行。它提供了一种从网络上的设备收集网络管理信息的方法，也为设备向网络管 理工作站报告问题和错误提供了一种方法。s n m p 采用管理站代理的体系结构，一个 s n m p 代理能够回答来自s n m p 管理站关于m i b 中定义信息的各种查询。每个提供 m i b 信息给管理站的网络设备都有一个s n m p 代理。基于s n m p 的网络管理层次结构 如下图所示。 管理系统被管系统 图2 2 基于s n m p 的网络管理层次结构 s n m p 规定了网络管理工作站与被管理设备进行通信时的语法和规则，它是一系 列协议组和规范，包含三个组成部分一一s m i ( 管理信息结构) 、m i b ( 管理信息库) 第7 页 国防科学技术大学研究生院学位论文 和协议。其中，管理信息结构是管理信息库中的对象定义和编码( 以便通过协议传输) 的基础；管理信息库定义了可以通过网络管理协议进行访问的管理对象的集合，为每 个对象说明了具体的对象实例，并为每个实例绑定了一个值：s n m p 协议是为网络管 理服务而定义的应用协议，网络管理站和代理进程间的管理信息的交换就是通过 s n m p 协议进行的。利用s n m p 协议，对网络设备状态的监视主要通过查询代理m i b 中相应对象的值来完成。代理也会发出一些陷阱( t r a p ) 来通知管理站。 在m i b 的i n t e r f a c e 组中，提供了网络实体的物理层接口信息( 如：接口类型、 接口描述等) ，每个接口被认为是附属于一个子网，当然一个接口对应个点到点的 链路也是存在的。 在m i b 的i p 组中包含了： i p f o r w a r d i n g 一表示网络设备是否具有i p 报文转发功能。 设备的i p 路由表。在具有路由功能的主要网络设备中，保存有网络路由功能 所必需的路由表。路由表的基本表项包括路由的目的网络地址、目的网络的 网络掩码、该路由的下一跳的i p 地址、对应的端口、所使用的路由协议等。 其中，下一跳的i p 地址信息可以用于网络的拓扑发现。由于路由器的下一跳 i p 地址所标识的必然是具有路由功能的网络结点，因此，从管理工作站的缺 省路由器开始，通过读取路由表，可以逐步向下发现网络中的所有具有路由 功能的网络结点。 设备的i p 地址表。此表提供了设备各接口的i p 地址、与该i p 地址相关联的 子网掩码。 i p 地址转换表，用于从i p 地址到物理地址的转换。此表提供了与本设备相连 的其它设备的i p 地址和物理地址的映射以及映射方式，由此可以发现设备之 间的一些连接情况。 对于网络拓扑发现而言，s n m p 是最有效的工具。利用s n m p 进行拓扑发现，其 基本要求是每一个被管设备( 如路由器、主机、交换机等等) 都具有一个存放了足够 信息的管理信息库，而且实现了s n m p 协议。 利用s n m p 进行拓扑发现的优势在于：1 ) 当网络发生变化时，设备m i b 中的信息 也会自动更新：2 ) 可以快速的从m i b 中获取信息，从而加速拓扑发现过程；3 ) s n m p 可用于非i p 网络。 利用s n m p 进行拓扑发现的局限性在于：1 ) 并非所有的设备实现了这个协议； 2 ) m i b 中的信息对于拓扑发现而言存在冗余以及不规范性；3 ) 标准m i b 中存放了设备 的基本信息，各个厂商所定义的私有m i b 中则存放了其产品的详细功能特性，对于自 动拓扑发现而言，必须找到简洁有效的方式在算法中充分利用私有m i b 中的有利信 息；4 ) 管理代理能够限制只有被授权的管理站才能访问它的m i b ，这就给跨多个认证 范围的拓扑发现带来许多问题。 2 2 2i n t e r n e t 控制报文协议( i e m p ) i c m ? 报文可分为两大类：差错报告报文和查询报文。差错报文报告路由器或主机 第8 页 国防科学技术大学研究生院学位论文 ( 目的站) 在处理一个i p 数据报时可能遇到的一些问题( 如：目的站不可达等) 。查 询报文是成对出现的，它帮助主机或网络管理员从一个路由器或另一个主机得到特定 的信息，如：某结点的邻站，网络的地址掩码等。 i c m p 中常用的命令是p i n g 命令和t r a c e r o u t e 命令。这两个命令用于网络拓扑发 现，其最大的优点就在于：每个支持t c p i p 的设备中都能使用p i n g 和t r a c e r o u t e ， 这使得拓扑发现进程对网络的假设要求降至最低。另外，使用p i n g 和t r a c e r o u t e 进 行拓扑发现，在一定程度上可以得到相当完整、准确的拓扑信息。 p i n g 通常可用于每个支持t c p i p 的设备，并且在许多操作系统和其他网络设备 上都是可用的。p i n g 工具仅是一个客户端应用程序，不需要额外软件来使它可用，它 是通过直接与远程系统的协议层交互来完成它的任务。 拓扑发现中，p i n g 命令主要用于检测目的主机是否可达。它实际上是对主机的 i p 地址发一个i c m p 回应请求包( e c h or e q u e s t ) ，用异步的方式接收i c m p 回应应答 ( e c h or e p l y ) 包。若收到应答，则报告目的主机运行正常。 广播p i n g 是指发送一个p i n g 报文给整个子网，如：发广播报文至子网 1 7 2 2 6 1 2 0 中的所有结点，只需：p i n g1 7 2 2 6 1 2 0 或者p i n g1 1 7 2 2 6 1 2 2 5 5 。 子网内接收到广播p i n g 报文的主机，将会发送应答报文至最初发送端。广播p i n g 的 作用在于发现子网内的所有活跃主机。 由于广播p i n g 可能造成拒绝服务性攻击，有一些网络不支持广播p i n g ，有的根 本不回复广播p i n g ，这样就限制了广播p i n g 的使用。 另外，如果p i n g 的目标不存在或没有正常工作，则会造成长时间的等待。解决 的方法是修改ti m e o u t 计时器。 t r a c e r o u t e 检测并记录到达某个指定网络目标的路径。它使用i p 报文中包含的 生存期( t t l ) 字段，并试图从沿路由到达目标的每个主机处获得一个i c m p 的t i m e e x c e e d e d 消息。随着试图连接目标的二个不可达端口，将导致沿路由到达最终目标期 间从每个路由器获得一个系统的响应。其工作过程“1 描述如下： 1 发送4 0 字节的u d p 报文( t t l = i ) 至探测目标点 2 第一个接收该报文的路由器丢弃该报文，发送e r r o r 报文至源结点 3 源结点接收e r r o r 报文，并记下e r r o r 报文的发源地，将之作为通向探测目标 点的第一站路由器 4 再次发送4 0 字节的u d p 报文( t t l = 2 ) 至探测目标点 5 第二个接收该报文的路由器丢弃该报文，发送e r r o r 报文至源结点 6 源结点接收e r r o r 报文，并记下e r r o r 报文的发源地，将之作为通向探测目标 第9 页 国防科学技术大学研究生院学位论文 点的第二站路由器 7 t t l 每次加l ，重复上述步骤，直至目标点有回应，或者未成功到达目标点但 已经过了最大跳数。如果报文到达目标点，则会有e r r o r 报文发送至源结点一一 因为报文的目的端i z i 对于t c p i p 系统来说正常情况下是不使用的。源结点根据 e r r o r 报文来判别与目标点的连接是否成功。 在拓扑发现中，t r a c e r o u t e 用于发现路由器的i p 地址及路由器间的连接关系。 跟p i n g 一样，当目标结点不存在时，t r a c e r o u t e 会产生长时间等待的副效应。当路 由路径中的某个路由器不响应t r a c e r o u t e 报文时，t r a c e r o u t e 会产生错误结果。另 外，t r a c e r o u t e 的长距离运行，时间开销很大。 2 2 3 地址解析协议( a r p ) 地址解析协议( a r p ) 在i p 地址和数据链路( 物理) 地址之间做映射。a r p 协议 非常简单，有以下优点：第一，a r p 是动态的。第二，a r p 是一个标准并且对每个支 持t c p i p 的设备可用，与数据链路协议无关。第三，a r p 可用于i p 子网，提供在一 个路由i n t e r n e t 中设备间通信非常简单的方法。 任何有以太网接口的网络设备都必须支持地址解析协议，并在本机维持着一张 a r p 表地址解析协议表( 也称为a r p 缓存) ，包含一个本地网络上所有数据链路协 议到i p 地址映射的完整列表。 网络拓扑发现中，根据任何一台路由器或交换机的a r p 表，可以发现与各以太网 端口相连的以太局域网中的网络设备：再根据其它信息判别网络中的路由器和交换机， 并继续根据其a r p 表进行发现，就可以得出整个以太网的拓扑结构关系。 该拓扑发现方法具有以下特点。”： 发现效率非常高。a r p 表中的网络设备地址都是最近活动过的有效设备的i p 地址和以太网络地址，而且几乎没有冗余信息 可以基于s n m p 或公共管理信息协议( c m i p ) 获得a r p 表 适合于局域网的拓扑发现； 其局限性表现在”： 不能发现那些不支持a r p 协议的网络设备和连接 不是所有的路由器都支持使用s n m p 方法获得a r p 表 如果网络过大，a r p 表中可能无法包括网络中实际存在的所有网络设备 在大型的网络管理系统中，该方法可以用于局域网的拓扑发现，以弥补基于i c m p 的拓扑发现方法的不足。 2 2 4 域名系统( d n s ) 一个域的域名服务器( d n s ) 维持该域内的每个名字到其i p 地址的绑定。大多数 域名服务器通过“z o n et r a n s f e r ”命令返回该域内名字的列表。所以d n s 的区传送功 能可以发现域内的所有主机和路由器。这种技术快速、开销小。但是，发现并不完全 第1 0 页 国防科学技术大学研究生院学位论文 准确，因为用d h c p 获取i p 地址的主机并没有d n s 服务，而且，一些网管员因安全原 因关闭了d n s 的区传送服务。 2 2 5 其它方法 路由选择协议是一些规则和过程的组合，使得在互联网中的各路由器能够彼此互 相通告互联网的变化，共享它们知道的互联网的情况和邻站的情况。当前比较流行的 路由选择协议包括：内部路由选择协议r i p ( 路由选择信息协议) 和o s p f ( 开放最短 路径优先协议) ，外部路由选择协议b g p ( 边界网关协议) 。利用r i p 、o s p f 、b g p 等 提供的路由信息，可以快速发现网络中的子网信息和路由器信息。 对于非i p 网络，也有方法进行拓扑发现。如：i p x ，可以用s a p ( s e r v i c e a d v e r t i s e m e n tp r o t o c 0 1 ) 发现网络中的服务器及其位置。 2 3 启发和猜想 拓扑发现技术还包括：启发( h e u r i s t i c s ) 和猜想( g u e s s i n g ) 。其思想是通过已经 获取的i p 地址推测它们所属子网的地址、子网掩码以及路由器i p 地址，主要包括猜 测域中的有效i p 地址，根据已知地址集猜测子网地址、子网掩码等。下面具体介绍文 献 1 中提出的启发和猜想技术。 2 3 1 猜测域中的有效地址 对于一个子网地址空间，分析子网地址空间中主机地址的分布特征，如以观察某 校园网为基础，该校园网有如下特征： 对于每个p i n g 通的主机( i p 地址为a b c d ) 来说，它的子网地址形式是 a b c 0 ，相应网关地址为a b c 1 ，这与2 4 位长的子网掩码2 5 5 2 5 5 2 5 5 0 相符合。 大多数主机是相邻的，例如，如果1 7 6 4 2 4 1 i 0 存在，则1 7 6 4 2 4 1 1 i 存 在的可能性就很高。 一些主机的i p 地址以 1 2 9 结尾，它们通常是路由器，且其子网掩码为2 5 长。 一些主机的i p 地址以 6 5 和 1 9 3 结尾，它们通常是路由器，且其子网掩码 为2 6 位长。 基于上述观察，可用下面的启发式方法来扩充本域内的地址集合t e m p s e t 。用p i n g 确认t e m p s e t 中【p 地址的有效性。 f o r 每个p i n g 成功的i p 地址a d d r e s s 把紧接a d d r e s s 之后的n 个连续地址增加到t e m p s e t 中 i f ( a d d r e s s 以i ，6 3 ，1 2 9 或者1 9 3 结尾) 增加n 个带有相同前缀的随机地址到t e m p s e t 中； 1 1第页 国防科学技术大学研究生院学位论文 上述算法中，n 的选择决定了能够搜索到的地址数。若n 很大，它可以发现所有 主机，但有很多无效地址；若n 太小，大多数地址有效，但不能发现所有主机。 2 3 2 根据地址集猜测子网地址 已知：主机地址a l ，a 2 ，a 3 ，某个路由器的端口i p 地址为a 。如下图所示。 求：三主机所属子网地址，子网掩码 a i 2 0 2 1 3 6 8 1 9 5 1 1 0 00 0 1 1 a 2 2 0 2 1 3 6 8 2 1 6 1 1 0 01 1 1 0 a 3 2 0 2 1 3 6 8 2 2 8 1 1 0 11 0 1 0 图2 3 子网样例 方法：首先判断这四个地址属于a 类地址，b 类地址，还是属于c 类地址，获得 n e t i d ( i p 地址的网络部分) ；然后，四个i p 地址，均去掉n e t i d ，剩余部分分别按位 逻辑与，按位逻辑或。最后再作判断。 下面用一个样例加以说明。 假设：路由器的端口地址为：2 0 2 1 3 6 8 1 9 2 ，三个主机地址分别为： 2 0 2 1 3 6 8 1 9 、2 0 2 1 3 6 8 2 1 6 和2 0 2 1 3 6 8 2 2 8 。显然，它们都是c 类地址，其n e t i d 为2 0 2 1 3 6 8 。下面要分析获得s u b n e t i d ( i p 地址的子网部分) 。 用1 1 0 00 0 1 0 标识路由器，1 1 0 00 0 1 1 ，1 1 0 11 1 1 0 和1 1 0 11 0 1 0 分别标识三个主 机。这四个标识值按位逻辑“与”的结果是1 1 0 00 0 1 0 子网号初始猜测为儿0 ，1 l ， 1 或空；按位逻辑“或”的结果是1 1 0 ll l l l 可确定h o s t i d ( i p 的主机部分) 至 少是五位，子网号可能为：1 1 0 ，l l ，1 或空。由给定的条件，无法得出结果。这时若 存在a 4 = 2 0 2 1 3 6 8 2 ( 0 0 0 00 0 1 0 ) ，按位逻辑“与”的结果就是0 0 0 00 0 1 0 ，排除 了l l o ，1 l 和l 。最终得到子网地址1 2 8 8 4 1 5 5 ，子网掩码2 5 5 2 5 5 2 5 5 0 。 评价：该方法适用于所有域，没有额外的网络开销，具有快速的特点。如果子网 中的主机地址在子网的地址空间分布均匀，该方法的结果是精确的：但如果主机地址 过于集中，该方法就不能得到精确的子网地址和掩码。 第1 2 页 电警摊 、 加o 国防科学技术大学研究生院学位论文 2 4 拓扑发现的基本算法 对i p 网络进行三层拓扑发现，需要获得以下信息： 网络中存在的路由器以及路由器间的连接关系 网络中的子网以及子网与路由器的连接关系 子网中的主机及其它设备 子网类型 设备的信息，如设备名、设备类型、设备的接口数、设备的接口类型、设备的 物理地址等 对i p 网络进行三层拓扑发现，一般采用以下的基本方法： 利用s n m p ( 简单网络管理协议) 获取m i b ( 管理信息库) 中的拓扑信息 利用p i n g p i n gb r o a d c a s t 命令判断设备的存在性，检测目的设备是否活跃 利用d n s “z o n et r a n s f e r ”，获得域内的主机和路由器的相关信息 获取a r p 信息，从而获得同一以太网网段内的所有活动主机的地址信息 利用t r a c e r o u t e 命令，获得路由器及路由器间的连接关系 获取b g p ，o s p f ，r i p 等路由信息，从而快速获得路由器及路由器间的连接关 系以及子网信息 下面介绍文献 i 和文献 3 中提出的四种基本算法，前三种主要用于i p 网络中 单个管理域内的拓扑发现，最后一种主要用于i n t e r n e t 骨干网的拓扑发现。 2 4 1 基于区传送z o n et r a n s f e r 的算法 假设：本域支持d n s 的区传送z o n et r a n s f e r 。通过区传送获得域内主机和路由 器的i p 列表；d n s 服务器返回路由器的所有端口的i p 地址。 基本思想：同时使用d n sz o n et r a n s f e r ，t r a c e r o u t e 和p i n g 。用d n sz o n e t r a n s f e r 获得一个域中的主机和路由器的i p 地址列表，放入临时集合t e m p s e t 。然后， 用p i n g 判断这些i p 地址的有效性，用t r a c e r o u t e 发现测试源到这些有效i p 地址( 目 标结点) 经过的所有路由器，这样可以得到路由器间的连接关系。该算法利用有效的 启发猜测方法( 根据地址集猜测子网地址) 获得子网地址。 算法描述如下： 第1 3 页 国防科学技术大学研究生院学位论文 1 t e m p s e t = d n sz o n et r a n s f e r ( d o m a i n ) 2 将c u m u l a t i v e a n d 芹1 c u m u l a t i v e o r 置为空 两个h a s h 表c u m u l a t i v e a n d 和c u m u l a t i v e o r ，以路由器端口 地址为索引值，分别存放逻辑“与”和逻辑“或”的结果，用于子网地 址和子网掩码的推断 3 f o ra d d r i p t e m p s e td o a ) p i n g ( a d d r l p ) b ) i f ( a d d r l p 活跃结点) t h e np e r m s e t = p e r m s e t ua d d r l pe l s e c o n t i n u e c ) t r a c e r o u t e ( a d d r i p ) d ) r o u t e r = 距离a d d r i p 最近的路由器i p 地址 e ) 利用d n s 的l o o k u p 找到r o u t e r 的所有i p 地址，记为i p ( r o u t e r ) di p ( r o u t e r ) q b 的每一项x o ra