（通信与信息系统专业论文）基于宽带网络的网络拓扑发现的研究与实现.pdf

东北大学硕士学位论文摘要 摘要 随着网络技术的迅速发展，网络管理已成为网络系统性能的关键，而网络的拓 扑结构是网络管理的一个重要组成部分，准确的网络拓扑图在现代的网络管理中起 到至关重要的作用。由于网络设备的不断增加，规模的不断扩大，网络结构也越来 越复杂，因此，过去那种仅凭记忆或通过a u t oc a d 等软件手工绘制拓扑图的方法已 不能适应网络发展的需求，网络拓扑的自动发现技术势在必行。 本文结合网络配置管理的需求特征，研究t c p i p 网络拓扑发现技术。论文首先 介绍网络管理的基本原理，描述网络的体系结构。进而阐述网络拓扑发现理论和常 用的实现方法，通过重点分析三种常用的网络拓扑发现方法，评价其各自的特点和 关键问题所在。在此基础上，针对上述方法存在的问题，在不增大算法复杂度的前 提下，提出了一种层次化的网络拓扑发现算法，该算法的核心思想是：根据目前i p 网络层次化的特点，采用分级搜索的策略，将网络拓扑发现分成两级进行。一级拓 扑发现主要发现路由器( 网关) 设备和子网；二级拓扑发现主要发现予网内的主机以及 子网类型等一些信息。一级拓扑发现采用s n m p 和i c m p 协议对路由器的路由表的 进行探测来发现路由器之间的连接关系。二级拓扑发现采用a r p 协议和s n m p 协议 来发现子网以及子网内的主机。接着，本论文还对该算法进行了详细设计和c + + 编 码实现。该算法的研究和实现对网络管理、网络配置和规划、网络评估等都具有实 用价值。 关键词：网络管理拓扑发现s n m pm i bi c m p i i 东北大学硕士学位论文a b s t r a c t a b s t r a c t n e t w o r km a n a g e m e n ti s b e c o m i n g a k e yo fn e t w o r kp e r f o r m a n c e n e t w o r k t o p o l o g y ，ai m p o r t a n tp a r to fn e t w o r km a n a g e m e n t ，i sp l a y i n gak e yr o l ei nm o d e m n e t w o r km a n a g e m e n t w i t ht h ei n c r e a s eo fn e t w o r ke q u i p m e n t ，n e t w o r kt o p o l o g yi s b e c o m i n gc o m p l e x i ti sd i f f i c u l tt or e c o r dn e t w o r kt o p o l o g yw i mm e m o r ya n da u t o c a d m a n u a l l y n e t w o r kt o p o l o g ya u t od i s c o v e r yi san e ww a y t h i st h e s i sf o c u s e so i lr e s e a r c h i n gt c p i p b a s e dn a t d a c c o r d i n gt oc m n e e d s f i r s t o fa l l 。t h eb a s i cn e t w o r km a n a g e m e n tt h e o r i e sa r ei n 打o d u c e db r i e f l y , a n dt h ef u n c t i o n s r e q u e s ti sa l s od e s c r i b e d t h e n ，i ts t u d i e sf o u n d a t i o n a lk n o w l e d g ea n dc o m m o nr e a l i z a t i o n o f n a t d a f t e rp l a c i n gs t r e s so ne x p l o r i n gt h ew a yo fn e t w o r kt o p o l o g yd i s c o v e r y ，w h i c h l e v e ld e l e g a t e db yt h r e ei n s t i t u t i o n ，i te v a l u a t e st h ea d v a n t a g ea n di n s u f f i c i e n tr e s p e e t i v e l y m o r e o v e r , al a y e r i n gw a yo f t o p o l o g yd i s c o v e r yi sb r o u g h tf o r w a r d ，w h i c ht h i n k i n gi st o s e a r c hn e t w o r ki nt w od e g r e e si nt e r m so ft h el a y e r i n go fn e t w o r kw i t h o u ti n c r e a s i n g a r i t h m e t i cc o m p l i c a t i o n t h ea i mo f f i r s tp h a s ei st od e t e c tr o u t e r sa n ds u b n e t s t h es e c o n d i st og e ts o m ei n f o r m a t i o n , s u c ha s ，t h eh o s t si ns u b n e t s ，t h et y p eo fs u b n e t s ，e t c t h e p r i n c i p l eo ff i r s tp h a s ei s t oa d o p ts n m p b a s e dr o u t i n gt a b l em e t h o d w h i l e ，t od e t e c t h o s t si ns u b n e t sb ym e a n so f a r p - b a s e da n ds n m p - b a s e dw a y w i t ht h i su n d e r s t a n d i n g ，i t d e s i g n sa na l g o r i t h ma n dg i v e si t sc + + r e a l i z a t i o n k e yw o r d s ：n e t w o r km a n a g e m e n tt o p o l o g yd i s c o v e r y s n m pm mi c m p i 独创性声明 本人声明所呈交的学位论文是在导师的指导下完成的。论文中取 得的研究成果除加以标注和致谢的地方外，不包含其他人己经发表或 撰写过的研究成果，也不包括本人为获得其他学位而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均己在论文中作了明确 的说明并表示谢意。 学位论文作者签名：三亟如芗 f 日期：凇喀2 b 学位论文版权使用授权书 本学位论文作者和指导教师完全了解东北大学有关保留、使用 学位论文的规定：即学校有权保留并向国家有关部门或机构送交论 文的复印件和磁盘，允许论文被查阅和借阅。本人同意东北大学可 以将学位论文的全部或部分内容编入有关数据库进行检索、交流。 ( 如作者和导师同意网上交流，请在下方签名；否则视为不同意。) 学位论文作者签名：导师签名： 签字日期：签字日期： 东北大学硕士学位论文第一章绪论 1 - 1 研究背景及意义 第一章绪论 随着计算机网络的迅猛发展，特别是随着i n t e m e t 的不断推广应用，计算机网络 越来越成为人们所关注的全球性热点之一。计算机网络的使用越来越广泛，用户对 网络的依赖也越来越大，而且网络广泛地用于银行、工业、国防等重要领域。因此， 网络的可靠性成为越来越重要的问题。网络管理i l j 是一个解决方案，它寻求最大限度 地利用现有的网络资源，增加网络的可用时间，提高网络设备的利用率、网络性能、 服务质量和安全性，提高网络的运行质量和效率【2 1 。因此，研究网络管理具有重要 的意义。 另外，随着网络技术的迅速发展，网络规模的不断扩大，结构也越来越复杂， 其功能也越来越强。网络管理已成为网络系统运行好坏的关键，网络的拓扑结构发 现是其它网络管理如配置管理、性能管理、故障管理的基础。网络拓扑结构的灵活 多样及虚拟网技术的应用，使得多层网络拓扑发现及虚拟网拓扑发现成为必要。网 络拓扑图和故障管理功能相结合，有助于实现网络故障的识别和定位。因此，实现 网络拓扑图，对于监视整个网络获取完整的网络信息以保证网络高效、稳定的运行 是非常重要的。 除此之外，拓扑发现可以用于大型网络的可视化。可视化不仅对于网络管理来 说很重要，它对于从各个不同角度观察网络及其运行以及基于这些观测的决策制定 也都有着十分熏要的意义。拓扑发现的一个比较新的应用领域是i n t e m e t 实际拓扑的 模型化研究。这一领域的主要目的是找出主宰i n t e m e t 建立和运转的模式及规则。除 此之外，它还旨在研究i n t e m e t 的结构问匝。这一领域的研究是十分有意义的，因为 我们可以利用其研究结果建立模拟i n t e m e t 的人工网络，用来测试新的协议和路由算 法。此时，拓扑发现作为工具不仅仅用于发现网络的实际拓扑，还用来从网络中提 取所需的网络信息。和这一应用比较相近的一个研究领域是对大型网络( 如i n t e m e t ) 演化方式的研究。此时，我们感兴趣的不是网络的实际拓扑，而是在两个连续的时 间点网络拓扑所发生的变化，最终找出网络拓扑的变化规律。这个规律可以用来测 试网络的未来变化。 1 2 国内外研究现状 国外早期的i p 网络自动拓扑发现工作【6 - 8 1 均是利用s n m p 等协议发现管理域内的 逻辑拓扑，即描述路由器与路由器，路由器与子网以及子网内部主机相互连接关系 的i p 层拓扑。另外，许多商业网络管理系统，如惠普公司的o p e n v i e w 、i b m 公司 1 东北大学硕士学位论文 第一章绪论 的t i v o l i 、达特茅斯的i n t e r m a p p e r 等，其拓扑发现也都是采用基于s n m p t 5 】协议的网 络层自动拓扑发现算法。 近期，国外的研究工作在物理拓扑自动发现”和广域网f 如i n t e m e t ) 的拓扑发现 方面已经开展了一些。最近，i e t f 在意识到物理拓扑发现的重要性后，指定了物理 拓扑s n m pm m 库”4 1 ，但是并没有定义任何通用的协议和算法用于获得物理拓扑信 息。一些硬件制造商，如c i s c o 公司，开发了用于发现物理拓扑的私有协议c d p ( c i s e o d i s c o v e r yp r o t o c 0 1 ) 以及相关工具，但是c d p 只适用于t l 动发现c i s c o 公司的网络设 备，不具有通用性。p e r e g r i n e 公司的i a f r a t o o l s 软件和m i c r o i t i u s e 公司的n e t c o o l 据 称可以支持物理拓扑的自动发现，但这些公司的独有技术是我们不可得知的。 相比较而言，i n t e m e t 拓扑发现研究的相对滞后已经对几乎所有的广域网应用、 服务器选择和定位造成了瓶颈。这使得i n t e r n e t 的拓扑发现和性能衡量日益受到重视。 确定广域网拓扑结构常用的方法是使用b e n c h m a r k s 测量通过网络拓扑的带宽。 t o p o l o g y d 是一个早期的使用这种方法进行拓扑发现的项目，生成了网络的最小生成 树视图【1 5 】。最近，项目i d m m a p s t l 6 , 1 7 】以及t h e i l m a n n 和r o t h e r m e l ”1 等人致力于生成 网络的距离图( n e t w o r kd i s t a n c em a p ) ，它是i n t e r n e t 网络拓扑的一种更加灵活的表示。 一种更加常用的方法是使用底层工具t r a c e r o u t e 进行i n t e r n e t 拓扑发现。美国康奈尔 大学网络研究组( c n r g ) 、南加州大学信息科学学院s c a n 研究组，加州柏克莱大学 计算机系、卡内基梅隆计算机学院以及朗讯贝尔实验室均进行了部分这方面的研究。 互联网数据分析协作联盟c a i d a 自1 9 9 8 年起开始了它的宏观拓扑项目( m a c r o s c o p i c t o p o l o g y d i s c o v e r y p r o j e m ，s k i t t e r 是c a i d a 开发的这方面的主要工具，用于i m e m e t 拓扑信息和往返传输时问( 1 a t e n c y r t y ) 数据的收集。 在国内，许多高校都有网络自动拓扑发现方面的研究，主要有华中科技大学f “、 上海交通大学弘”1 、西安交通大学1 2 7 。1 、中国科技大学等 3 1 - 3 2 】。但是，这些研究主要 集中于发现i p 网络管理域内的逻辑拓扑。文献【1 9 】虽然对虚网( v l a n ) 的拓扑发现算 法进行了一些探索，有定的借鉴性，但是该算法针对c i s c o 公司网络设备( 如 c i s c 0 7 2 0 4 ，c a t a l y s t 3 0 0 0 ) 的m i b 库，通用性显得不够。郑海川等人的物理拓扑发现 算法需要通过在网络中产生额外流量来保证网络中每一个节点地址转发表的完整。 鉴于网络拓扑的自动发现技术是网络管理的基础，我国已将该技术列为“8 6 3 ” 计划的研究内容之一。 早期的网络拓扑自动发现主要着眼于网络层i p 设备的拓扑结构，忽略掉集线器， 网桥和链路的细节。其算法主要基于以下三种工具p 1 ： ( 1 ) p i n g ( 2 ) t r a c e r o u t e ( 3 ) d n sz o n et r a n s f e r 随着网络技术的发展。交换机日益成为局域网中的重要设备。但是交换机是工 2 东北大学硕士学位论文第一章绪论 作在数据链路层的设备，而以上的三种工具无法发现交换机与主机的拓扑连接，这 不能不说是很大的缺陷。 随着网络管理协议的发展，基于网络管理协议的网络拓扑自动发现技术日益成 为主流。这种技术的核心是使用适当的网络管理协议获取远程设备上的相关数据， 并使用适当算法发现设备之问的连接情况。 1 - 3 课题的提出 网络拓扑发现通常利用网络协议搜索网络设备，并搜集其中的配置信息以生 成拓扑连接。传统的拓扑发现算法主要反映的是网络层设备的连接关系( 如路由器 与路由器、路由器端口与子网之间的连接关系，图1 1 所示) 而不提供物理网络拓 扑( 如交换机与交换机、交换机与网桥之间的连接关系，图1 2 ) 发现。自动发现网 络层拓扑相对简单，对于基于s n m p 的第3 层设备拓扑发现算法，所有的这些信息都 可以从每个路由器的m i b i i 库的i p r o u t e r t a b l e 中获取。随着网络规模的不断扩大， 网络层拓扑结构已经不能准确反映网络设备之间的连接关系。因此，本文依据标准 的s n m p 和i c n p 等协议和相关的m i b 信息，提出了一个新的物理拓扑自动发现算法。 子网：i p 子网r ：路由器 图1 1 网络层拓扑图 f i g 1 1t o p o l o g y o f n e t w o r k l a y e r 3 东北是学硕士学位论文 第一章绪论 作在数据链路层的设备，而以上的三种工具无法发现交换机与主机的拓扑连接，这 不能不说是很大的缺陷。 随着嘲络管理协议的发展，基于网络管理协议的网络拓扑自动发现技术日益成 为主流。这种技术的核心是使用适当的网络管理协议获取远程设备上的相关数据， 并使用适当算法发现设备之问的连接情况。 1 - 3 课题的提出 网络拓扑发现通常利用网络协议”搜索网络设备并搜集其中的配置信息以生 成拓扑连接。传统的拓扑发现算法主要反映的是网络层设备的连接关系( 如路由器 与路由器、路由器端口与子网之间的连接关系，图1 1 所示) 而不提供物理网络拓 扑( 如交换机与交换机、交换机与网桥之间的连接关系。图1 2 ) 发现。自动发现网 络层拓扑相对简单，对于基于s n m p 的第3 层设备拓扑发现算法，所有的这些信息都 可以从每个路由器的m i b i i 库的j p r o u t e r t a b l e 中获取。随着网络规模的不断扩大， 网络层拓扑结构已经不能准确反映网络设备之间的连接关系。因此，本文依据标准 的s n h l p 和i c 冲等协议和相关的m i b 信息，提出了一个新的物理拓扑自动发现算法。 的s p 和i c m p 等协议和相关的m i b 信息，提出了一个新的物理拓扑自动发现算法。 子网ti p 予网r ：路由器 图l + 1 网络层拓扑图 f i g 1 1t o p o l o g y o f n e t w o r k l a y e r 3 东北大学硕士学位论文第一章绪论 眦主机r 路由器s ：交抉机 图1 2 物理网络拓扑图 f i g 1 2t o p o l o g yo f p h y s i c a ll a y e r 1 4 论文结构 本文主要是结合宽带网络管理系统，对网络拓扑自动发现技术进行了阐述。论 文共分六章：第一至三章主要提供了课题研究的理论依据，包括国内外网络管理技 术的发展现状、网络管理的体系结构；系统中用到的技术，如s m i 、m i b 、s n m p 、 i c m p 等相关技术的阐述。第四章讲述了网络拓扑发现算法的研究与设计。第五章结 合实践对网络拓扑发现技术的设计与实现作了详细的阐述。第六章是对系统进一步 扩展的展望，并对整个系统作一个总结。 4 东北大学硕士学位论文g - 章网络管理的体系结构 第二章网络管理的体系结构 2 1 网络管理的一般模型结构 网络管理本质上是一个监视和控制网络的过程，其目的是尽可能地保证网络的 正常运作。因此网络管理系统的重要任务就是收集其所管理的网络中各种网络设备 及系统的数据，包括工作参数、运行状态等信息，在进行简单加工或高级处理后， 以数字或图表等可视化形式提供给网络管理人员，在紧急情况下甚至可以通过声音 警报或电子邮件等形式来通知网络管理人员对此及时进行处理。 图2 1 网络管理系统和网络管理人员的关系 f i g 2 1t h er e l a t i o n s h i pb e t w e e nn e t w o r km a n a g e m e n ts y s t e ma n dn e t w o r km a n a g e r 网络管理的体系结构主要涉及网络管理系统的组成部件和结构，各部件之间的 关系，网络管理应该包括的功能以及这些功能的划分。 从系统组成的角度来看，现代网络管理系统由四部分组成：一个或多个网络管 理系统n m s 烈e 铆o r km a n a g e m e n ts y s t e m ) 、多个被管代理( m a n a g e da g e n t ) 、与被管 代理对应的管理信息库m i b ( 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 一起驻留在被称为被管设备的网络设备上。说明如下： ( 1 ) 网络管理系统：网络管理的实体( e n t i t y ) ，处于网络中一个主机节点( 管理工作 站) 上，是整个网络系统的核心，实施各项网络管理功能，如配置网络、监视 网络性能、排除网络故障等。 ( 2 ) 被管代理：是一种软件，驻留在被管理的网络设备( 如路由器和寻径服务器、 交换机和网桥、集线器、计算机主机、或网络打印机等) 上，负责向管理系统 提供各种该网络设备的信息和根据管理系统的请求设置相应的信息。 ( 3 ) 管理信息库：是一种动态刷新的数据库，存储被管理设备的各种信息，如配 置信息、通信统计信息、安全信息及该设备生产厂商的特有信息等，负责向 被管代理提供数据和存储被管代理设置的数据。 ( 4 ) 网络管理协议：描述网络管理系统和被管代理之间的数据通信机制，既定义 了网络管理的通信报文格式和管理信息库的数据库格式。它的定义决定了网 络管理系统的主要功能。 它们的关系图如图2 2 所示： 5 型 图2 2 网络管理基本组成部分之间的关系 f i g 2 2t h er e l a t i o n s h i pa m o n gt h ep a r t so f t h en e t w o r km a n a g e m e n ts y s t e m 管理域a 管理域b ii 系统a 管理系统 ii 系统b 管理系统 被管 操作 被管 对象 - 一j 鼻件+ 对煮 通信 f = 二二= a 管理管理 l s t r u c ts u b n e t l t e m l o n gt u o p o i n d e x ；，拓扑对象索引，用于拓扑生成 i p a d d rs u b n e t i p ；子网地址 i p a d d rs u b n e t m a s k ；子网掩码 i n ts u b n e t t y p e ；h 子网类型 ) s t r u c ts u b n e t q u e u e n o d e s u b n e t l t e m s u b n 吼：，一个子网的有关信息 l o n gg a t e w a y m d e x ；，与该予网相连路由器的索引 s t r u e ts u b n e t q u e u e n o d e + n e x t ； ) ( 2 ) 算法详细描述 算法流程图如图4 4 所示： 4 1 - 查! ! 垄堂堡主兰堡垒墨苎里主璺丝塑! ! 查墨簦鲞塑堑壅圭竺盐 ( 2 ) ( 1 ) 4 2 c 3 ) 东北大学硕士学位论文 第四章网络拓扑发现算法的研究与设计 图4 4 一级拓扑算法流程 f i g 4 4f l o wd i a g r a mo f f i r s tc l a s st o p o l o g y a l g o r i t h m 初始化最大i p 路由器队列，路由器队列，子网队列，全局拓扑索引值s t a t i c - 4 3 东北大学硕士学位论文第四章网络拓扑发现算法的研究与设计 i n d e x = l 。 ( 2 ) 用g e t h o s t n a m e 0 取回主机名，再用g e t h o s t b y n a m e 0 取回主机i p 等信息。 ( 3 ) 读取系统文件e t c s y s c o n f i g n e t w o r k ，取得默认网关的i p 地址。 ( 4 ) 令当前网关的值为默认网关，并计时开始。 ( 5 ) 读取当前网关的i p a d d r t a b l e 表，取出i p a d e n t a d d r 的最大值t e m p m a x i p 。 ( 6 ) 构建一个g a t e w a y i t e m ，其t u o p o i n d e x 值为i n d e x + + ；其m a x i p 的值为取得的 最大值：其上一级路由器的值记为管理站的i p 地址。 ( 7 ) 根据上面的g a t e w a y i t e m 构建一个g a t e w a y q u e u e n o d e 添加到最大路由器队 列中和路由器队列中。 ( 8 ) 现在超时没有? 如果没有执行( 9 ) ，否则执行( 1 8 ) 。 f 9 ) 绑定对象i p r o u t e n e x t h o p ，采用s n m p 协议中的g e t n e x t r e q u e s t 操作，读取 当前网关的i p r o u t e t a b l e 一行中的i p r o u t e n e x t h o p 的值。 ( 1 0 ) 分析取回的值，如果不等于t e m p m a x i p ，并且路由器队列中没有重复，构建 一个g a t e w a y q u e u e n o d e ，其中其t u o p u i n d e x - - i n d e x + + ，m a x i p d 的值暂时记 录为i p r o u t e n e x t h o p 的值，上一级路由器为当前网关的值，添加到路由器队 列中。 ( 1 1 ) 否则不记录任何值，而是绑定取回的对象的值，再次用g e t n e x t r e q u e s t 操作 取表中的下一行的值，直到表访问完。 ( 1 2 ) 绑定对象i p r o u t e d e s t ，i p r o u t e m a s k ，i p r o u t e t y p o ，用s n m p 办议中的 g e t n e x t r e q u e s t 操作，读取当前网关的i p r o u t e t a b l e 表的一行，取出其中的 i p r o u t e d e s t ，i p r o u t e m a s k ，i p r o u t e t y p e 值。 ( 1 3 1 如果取回的i p r o u t e t y p e 的值为3 ，并且子网队列中没有该子网，则构建一个 s u b n e t l t e m ，其中t u o p u i n d e x = i n d e x + + ，子网地址等于取回的i r i r o u t e d e s t 的 值，子网掩码等于取回的i p r o u t e m a s k 的值。 ( 1 4 ) 构建一个s u b n e t q u e u e n 0 d e ，其中网关的索引为当前网关的索引，将该结点 加入子网队列。 ( 1 5 1 绑定取回的对象的结果，再次调用g e t n e x t r e q u e s t ，再取一行值如此循环直 到表访问完。 ( 1 6 ) p n 果队列没有访问完，读取路由器队列的下一个作为当前网关，将前面暂时 记录的m a x i p 作为当前网关的i p 地址再取最大i p 标识，如果取回的最大i p 值与记录的值不等，替换之。如果表已经访问完执行0 8 ) 。 ( 1 7 ) 在最大1 p 队列中是否有该路由器，没有则添加，否则超时没有，如果没有， 重复( 1 6 ) i 如果超时了，执行0 8 ) 。 ( 1 8 ) 这时是已经超时或者队列已经访问完成。释放掉g a t e w a y q u e u e 中没有访问 到的结点。 4 4 东北大学硕士学位论文 第四章网络拓扑发现算法的研究与设计 ( 1 9 ) 将g a t e w a y q u e u e 中的m a x i p 和p a r e n tg a t e w a y i n d e x 相同的结点只保留个， 其余删除释放掉。 ( 2 0 ) 结束。 这样一级拓扑发现结束，得到在g a t e w a y q u e u e 中记录的发现的路由器及相关信 息，以及在s u b n e t q u e u e 中记录的发现的子网及相关信息。 4 1 2 二级拓扑发现方法分析与算法设计 4 1 2 1 算发分析 在完成一级拓扑搜索之后，已经搜索出了路由器( 网关) 和与相应的路由器相连的 予网，但是子网内的主机的情况并没有得到。如果需要知道某个子网的主机的活动 情况，可以选中某个子网，再进行二级子网主机的搜索。 ( 1 1 子网内主机的发现 在前面的分析中已经提到过，对于子网主机的发现采用基于i c m p 协议的“p i n g ” 和基于a r p 协议的方法，这两种方法都有比较高的发现率。迸一步分析，当前的实 际情况往往是子网内的主机数远小于一个子网所可以拥有的主机数，这样如果采用 “p i n g ”，如果某个堙不存在，则需要等到响应超时达到规定最大的次数，这样会浪 费许多的时间，并且即使是“p i n g ”通了，也只是知道该主机是活动的，而其他的信 息却得不到，还需要再用其他的办法来得到诸如主机物理地址，接口类型等信息。 在分析m i b 提供的所有对象信息后发现，发现在路由器的m i b 库中有一个表， 即i p n e t t o m e d i a t a b l e 表，它一记录了从i p 地址到物理地址的映射，记录的是当前活 动的主机的映射，通过检查设备的i p n e t t o m e d i a t a b l e 表，可以发现与该设备相连的 其他设备的i p 地址和物理地址的映射以及映射方式，由此可以发现设备之间的一些 连接情况。内容如表4 2 所示。 表4 2j p n e t t o m e d i e t a b l e 的对象 t a b l e 4 2t h eo b j e c to f i p n e t t o m e d i e t a b l e 对象说明 i p n e t t o m e d i a l f l n d e x 该记录对应的接口索引 i p n e t t o m e d i a p h y s a d d r e s c , 介质依赖的物理地址 i p n e t t o m e d i a n e t a d d r e s s 与介质依赖的物理地址想对应的i p 地址 i p n e t t o m e d i a t y p e 地址影射的类型；1 其他；2 无效；3 动态；4 - 静态 它的机制实质上就是a r p 协议实现的口地址与物理地址的映射。考虑子网内的 4 5 东北大学硕士学位论文 第四章网络拓扑发现算法的研究与设计 主机如果是活动状态，则一定在表中有一条映射，在一级拓扑搜索时已经提取了子 网地址以及子网掩码，这样如果利用提取的子网掩码，在相应的路由器中的 i p n e t t o m e d i a t a b l e 表中与i p n e t t o m e d i a n e t a d d r e s s 一一进行“与”操作，得到属于 这个予网的所有主机i p 。同时判断，如果某个i p 对应的i p n e t t o m e d i a p h ? ，s a d d r e s s 为“f f ：f f ：f f ：f f ：f f ：f f ”则该i p 地址或者是网络地址，或者是广播地址，不记录该 1 p 地址和物理地址以及i p n e t t o m e d i a i f l n d e x 。这样所有该子网内在当时活动的主机 就都发现了。子网中对应路由器的端口也看成是活动的主机设各。 ( 2 ) 子网类型的确定 在上面的表4 2 中有一个对象i p n e t t o m e d i a l f l n d e x ，它的值与在i n t e r f a c e s 组接 口表i t t a b l e 对象中的一项i f l n d e x 值相对应，接口表中的有关对象见前图3 - 4 所示， 根据i f i n d e x 和i f r y p e 的值的对应关系可以得到子网的类型。例如，如果i f r y p e 的值 为6 ，则子网类型为总线型；若为8 ，子网类型为令牌总线型；为9 则是令牌环等等。 下面是m i b i i 中i f t y p e 的定义： o t h e r o ) ，表示不属于下面的任何一类 r e g u l a r l 8 2 2 ( 2 ) ， h d h l 8 2 2 ( 3 ) ， d d n 1 ( 2 5 ( 4 ) ， r f c 8 7 7 2 5 ( 5 ) ， e t h e m e t l s m a c d ( 6 ) ， i s 0 8 8 0 2 3 - - - - - - - - e s m a c d ( 7 ) ， i s 0 8 8 0 2 4 - - - - - - t o k e n b u s ( 8 ) ， i s 0 8 8 0 2 5 - - - - - - - t o k e n r i n g ( 9 ) ， i s 0 8 8 0 2 6 - - - - - - - m a n ( 1 0 ) ， s t a r l a n ( 1 1 ) ， p r o t e o n - - 1 0 m b i t ( 1 2 ) , p r o t e o n - - 8 0 m b i t ( 1 3 ) ， h y p e r c h a n n e l ( 1 钔， f d d i ( 1 5 ) ， l a p b ( 1 6 ) ， s d l c ( 1 7 ) ， d s l ( 1 8 ) ，卜一l e l ( 1 9 ) ，_ e u r o p e a ne q u i v o f t - - 1 b a s i c l s d n ( 2 0 ) ， p d m a r y i s d n ( 2 1 ) ，1 ) r o p n e t a r ys e r i a l 4 6 东北大学硕士学位论文第四章网络拓扑发现算法的研究与设计 p r o p p o i n t t o p o i n t s e r i a l ( 2 2 ) ， p p p ( 2 3 ) ， s o i t w a r e l o o p b a c k ( 2 4 ) ， e o n ( 2 5 ) ，c l n p o v e ri p e t h e r n e t 一3 m b i t ( 2 6 、， n s i p ( 2 7 ) ，涮so v e ri p s l i p ( 2 8 ) ，g e n e r i cs l i p u l t r a ( 2 9 ) ，u i j r at e c h n o l o g i e s d s 3 ( 3 0 ) ，。卜3 s i p ( 3 1 ) ，s m d s f r a m e - r e l a y ( 3 2 ) 根据选出的子网的i p n e t t o m e d i a l f i n d e x ，查接口表i t t a b l e ，从而可以接口索弓 所对应接口类型得到该子网的类型，这个信息对于拓扑生成时很有用。 4 1 2 2 算法设计 ( 1 ) 算法数据结构 s t r u e th o s t q u e u e i p a d d rh o s t i p ； i p a d d rh o s t m a c ； s t r u c th o s t q u e u e + n e x t ； ) ( 2 ) 算法详细描述 ( 1 ) 选定要进一步进行主机发现的子网。初始化主机队列，子网类型确定标志 t y p e f l a g = 0 。 ( 2 ) 绑定对象i p n e t t o m e d i a n e t a d d r e s s 、i p n e t t o m e d i a p h y s a d d r e s s 以及 i p n e t t o m e d i a i f l n d e x 。 ( 3 ) 利用s n m p 协议的g e t n e x t r e q u e s t 操作取表i p n e t t o m e d i a t a b l e 的一行中的 相应的值。 ( 4 ) 分析取回的i p n e t t o m o d i a p h y s a d d r e s s 的值是否为“f f ：f f ：f f ：f f ：f f ：f f ”，如 果是，相应的i p n e t t o m e d i a n e t a d d r e s s 是子网地址或者是广播地址，不是主 机地址，执行( 7 ) ；如果不是，则认为取回的值是活动主机的砰地址、物理 地址以及子网接口索引，执行( 5 ) 进一步进行判断。 ( 5 ) 将取回的i p n e t t o m e d i a n e t a d d r e s s 的值与选定子网的掩码相“与”，结果与 选定子网地址比较，如果相同，则主机是选定子网内的主机，取回的 4 7 东北大学硕士学位论文 第四章网络拓扑发现算法的研究与设计 i p n e t t o m e d i a p h y s a d d r e s s ，i p n e t t o m e d i a n e t a d d r e s s 是该主机的i p 地址和物 理地址。将确定是该子网内的主机连接到队列中。 ( 6 ) 如果分析取回的i p n e t t o m e d i a i f l n d e x 的值，为6 则是总线型子网，为9 则是 令牌环型子网，等等。从而确定了子网的类型，并将t y p e f l a g 的值置为1 。 若t y p e f l a g = l 则不进行分析。 ( 7 ) 将取回的i p n e t t o m e d i a p h $ r s a d d r e s s 和i p n e t t o m e d i a n e t a d d r e s s 以及 i p n e t t o m e d i a l f l n d e x 绑定，再用o e t n e x t r e q u e s t 操作取值。重复( 3 ) 到( 7 ) 直到 表访问完。 ( 8 ) 结束。 这样，所有搜索到的活动主机都在队列中了。 ( 3 ) 算法流程图 图4 5 子网主机发现流程图 f i g 4 5f l o wd i a g r m - no f s u b n e th o s tm a c h i n e - 4 8 东北大学硕士学位论文 第四章网络拓扑发现算法的研究与设计 4 2 与已知网络拓扑发现算法的比较 国内十分重视网络拓扑发现算法的研究，对网络拓扑发现算法研究一直在进行， 其中一些研究结果代表当前网络拓扑发现方法研究的水平，本小节列举了其中的三 个有代表性的方法：基于s n m p 协议路由表的发现算法是上海交大学报发表的上 海交通大学孙德文等老师的研究结果；基于i p 协议订l 的网络拓扑搜索算法是 西安交通大学新型计算机研究所徐斌博士等在得到国家8 6 3 高技术项目资助下得到 的研究结果；基于i c m p 和s n m p 的网络拓扑搜索算法是华中理工大学网络中心 李佳博等得到国家“九五”重点科技攻关资助的研究结果。在研究分析三种方法 并与本文提出的算法进行了比较。结论是：本文提出的算法在没有增大算法复杂度 的前提下，避免了三种算法中的一些缺陷，而且实现更合理，容易。因此，本文提 出的算法具有实用价值和推广价值。 4 2 1 基于s n m p 协议路由表的发现算法 4 2 1 1 算法描述 初始化路由器队列，子网队列，连接队列； 把默认路由器放入路由器队列中； w h i l e ( 路由器队列非空) 从路由器队列中取出一个路由器，为c u r r e n t r o u t e r ； 访问c u r r e n t r o u t e r 路由表； 把路由表中的各i p r o u t e n e x t h o p 不重复地放到路由器队列中； 把各i p r o u t e d e s t 不重复地放到子网队列中； 把c u r r e n t r o u t e r 与各i p r o u t e n e x t h o p 的连接不重复地放到连接队列中； i f ( i p r o u t e n e x t h o p 属于i p r o u t e d e s t 子网) 把i p r o u t e n e x t h o p 与i p r o u t e d e s t 的连接不重复地放到连接队列中 i f ( i p r o u t e r n e x t h o p 与c u t r e n t r o u t e r 地址相同1 把c u r r c n t r o u t c r 与i p r o u t e r d e s t 的连接不重复地放到连接队列中； 4 2 1 2 算法分析 由于没有进行路由器多个口地址的分析，接个算法对路由器的识别是根据l p 地 址的不同，这样显然得到的结果不准确。因为一个路由器在网络中可能是有多个i p 地址，如果对于路由器的每个m 地址都访问一遍路由器的路由表，假设每个路由器 4 9 东北大学硕士学位论文第四章网络拓扑发现算法的研究与设计 所拥有的i p 数为r ( 数量级为1 0 ) ，那么此算法一个路由器路由表将会重复访问r 次， 而本人所设计的算法只需访问1 次路由表。由此本算法的时间复杂度将大大减少。 其次是对于连接关系的处理，算法中是记录路由器的下一跳路由器与当前路 由器的连接关系，算法中和是记录路由器与予网的连接关系。根据算法它是将 网络中路由器之间的连接与路由器与子网的连接分离开来。按照算法的思想对连接 进行抽象，如图4 6 所示，设网络中有5 个路由器分别用r 1 。r 5 表示，路由器之间的 连接为一条直线，为了说明分别用数字1 8 标识，对于烈和r 3 之间的连接1 号连接， 由于砒和r 3 连接l 的端口分别处于同一个子网内，这样砒连接了子网1 ，而r 2 同样有一个连接予网1 。其