（计算机应用技术专业论文）基于snmp的ip网络拓扑信息的发现与应用.pdf

基rs n m p 的i p 州络抖1 扑信息的发现与麻用 摘要 随着对网络需求的不断增强，必须要求一个可信、可靠、安全、稳定的网络 平台。网络管理已成为网络系统运行好坏的关键。如何发现网络拓扑结构，建立 有效的网络拓扑模型，对于网络管理是十分重要的。 本文讨论了在研究i p 网络拓扑发现时所需要考虑的问题，在分析了以前的 拓扑发现算法的基础上，提出了一种有效的针对管理域内网络自动拓扑发现算 法。本算法使用s n m p 协议采集管理域内各种网络设备中m i b 库保存的信息， 采用本文提出的设备连接关系判定规则处理获取的拓扑信息，确定路由器、交换 机和主机之间的连接关系，构造网络第二层和第三层的拓扑结构图。实验结果表 明，大部分支持网管的设备中包含了算法所要求的数据。在与以前的自动拓扑发 现算法做了比较以后，本算法具有稳定性好、运算简单、获得的网络拓扑构图更 准确且可操作性强的优点。 在分析基于s n m p 拓扑发现算法性能的基础上，本文介绍了一个自主开发的 拓扑发现子系统原型。该系统由数据采集和网络拓扑图生成两部分组成，分别实 现了m i b 数据的获取和网络拓扑结构图生成功能。 网络拓扑发现需要发送大量的探测包来收集拓扑信息，使得完成次拓扑发 现需要很长的时间，并且占用大量的网络带宽。为了提高拓扑发现的性能，本文 介绍了系统原型在减少探测包数量，加快探测过程等方面采用的一些关键技术， 使其具有更强的实用性。 关键词：网络管理，网络拓扑发现，路由表，生成树，简单网络管理协议 基rs n m p 的i p 嘲络* 扑信息的发现与应用 a b s t r a c t i nl a 曜ea n dc o n s t a n t l ye v o l v i n gn e t w o r k s ，i ti sd i f f i c u l tt od e t e r m i n eh o wt h e n e t w o r ki s a c t u a l l yl a i do u t y e tk n o w l e d g eo ft h eu p t o d a t et o p o l o g yo fa ni p n e t w o r ki sc r u c i a lt oan u m b e ro f c r i t i c a ln e t w o r km a n a g e m e n tt a s k s b a s e do nt h ea n a l y s i so ft h ee x i s t i n ga u t o m a t i ct o p o l o g yd i s c o v e r yt e c h n i q u e s ， t h i sp a p e rp r e s e n t san e wt o p o l o g yd i s c o v e r ya l g o r i t h mf o rh e t e r o g e n e o u si pn e t w o r k s u s i n gs t a n d a r ds n m pm i b s o u ra l g o r i t h mm a k e su s eo ft h et o p o l o g yc o n f i g u r a t i o n i n f o r m a t i o ni nr o u t e r s ，s w i t c h e sa n dh o s t su n d e rt h es i t u a t i o nt h a td on o tg e n e r a t e t r a f f i ci nt h en e t w o r ki na d v a n c e ，t od e t e r m i n et h ei n t e r c o n n e c t i o nb e t w e e nd i r e c t l y c o n n e c t e dp e e r si nan e t w o r k ，t op r o d u c et h ei p l e v e la n dl i n k l e v e lt o p o l o g ym a p w eh a v et e s t e do u ra p p r o a c hi no u ri n t e r n a ln e t w o r ka n dw ev e r i f i e dt h er e s u l t ，i th a s a c c u r a t e l yd e t e r m i n e dt h et o p o l o g yo fs e v e r a ld i f f e r e n tn e t w o r k su s i n gav a r i e t yo f h a r d w a r ea n dn e t w o r kc o n f i g u r a t i o n s w ep r e s e n tt h ed e s i g no fn e t w o r km a n a g e m e n tp m t o t y p e w eh a v ei m p l e m e n t e d t h cp r o p o s e dt o p o l o g yd i s c o v e r ya l g o r i t h mb a s e do nt h ev i s u a lc + + a n dw i n s n m p a p i d e t a i l e di m p l e m e n t a t i o nt e c h n i q u e sa r eg i v e nf o rd e c r e a s i n gt h en u m b e ro f s n m p r e q u e s tp a c k e t sa n dt h ec o s to f t o p o l o g yd i s c o v e r y k e y w o r d s ：n e t w o r km a n a g e m e n t ，t o p o l o g yd i s c o v e r y ，r o u t i n gt a b l e ，s p a n n i n gt r e e s n m p 基rs n m p 的l p m 络拓扑信包的发现与府用 第一章绪论 在网络规模不断扩大的今天，伴随着复杂性的持续增加，网络的异构性也日 趋提高，加以充斥其中的众多不同网络操作系统、：_ 1 i 同厂家的网络通信设备、多 种多样的网络服务软件和水平相差甚大的使用者与潜在的攻击者，网络已相当复 杂。与此同时，层出不穷的应用也使得用户对网络性能的要求越来越高。网络管 理成了网络系统正常运行的关键，而网络拓扑发现是网络管理的基础。同时，要 对网络性能及流量进行分析，首先也必须得到正确的网络拓扑结构和相关信息。 1 1 网络结构概述 图1 1 ( a ) 描述了网络端用户所感觉到的网络结构视图，大部分应用程序也 足保存这种网络视图。图1 ，1 ( b ) 描述了所有的机器足通过路由器连接在网络上 的。这也是网络中最容易探测到的设备。一般我们能用t r a c e r o u t e 程序来探测主 杌之间的路由器。 图1 1 ( c ) 被用来说明网络第二层( 链路层) 的透明性。这一层包括了连接 主机构成以太局域网的主要网络部件( 设备) 网桥，以太网是目前使用最广泛的 局域网柴构，也是网络中最难扶取其网络拓扑的一层。这种困难来源丁网桥协议 的透明性。采用网桥构造局域网和转发数据包所使用的算法不需要知道网络全局 的信息，也不需要主机直接告诉网桥，也就是说网桥不需要知道主机的存在。冈 此，网桥的这种透明性是第二层网络设备非常有效的一个特点，但足它却使得扶 得第二层网络拓扑变得很困难了。随着网络技术的发展，现在第二层网络设备中 最常见的是交换机( 它可以认为是有更多端口的网桥) 。在本文中术语“网桥” 和“交换机”是同一个意思。 ( c ) 口士机。路由器变换机 图1 1 ：不同层次的网络视图。( a ) 用户所感觉到的网络结构视图。( b ) i p 路由层的网络视 图。每个主机和路由器明确地沿着路径向相邻设箭转发数据包。( c ) 增加了以太网交换机的 网络视图。每个交换机学习到主机和路由器的连接位置，然后透明地向目的设各转发数据帧。 基rs n m p 的pm 络拓扑信息的发现与麻用 虽然狱得以太网的拓扑结构是困难的，但足随着以太网在网络中使用得越来 越广泛，获得其拓扑结构也变得越来越重要。图1 2 描述了。个冈为没有发现网 桥之m 的 | 塞链路，使得有效带宽预测的结果无效的例子”。 图1 2 ：一个忽略了删桥导致无效的结果的嘲络配置例子。如图所示，如果不能发现连接a 和b 之州的刚桥有可能产生的拥塞链路，将会过高的估计两者之问的有效带宽 1 1 1 f p 路由 确定i p 路由层( 网络层) 的拓扑结构比较容易，因为每个主机和路由器都 保存并维持一张路由表“。路由表中的每一条记录标识着到达每个日标i p 地址 的包所需转发的下一跳( h o p ) 的路由设备。因此，记录从源i p 到月的i p 所经 过的每一跳的路由设备，就可以构造出i p 网络路由层( 网络层) 的拓扑结构图。 1 1 2 交换以太网 以太嘲( e t h e m e t ) 是世界范围内最流行的网络类型，困为它实旋起来很容 易，成本比其他技术相对较低。而且很容易管理，以太网产品可以随处获得。以 太网技术已经从传统的1 0 m b p s 网络发展到1 0 0 m b p s 快速以太网，现在已达到 1 g b p s 网络，或者是更好的g i g a b i te t h e m e t 网络【2 】【3 】f 4 。 以太网所使用的接入机制叫做具有冲突检测的载波监听多点接入 ( c s m a j c d ) 。采用以太网技术构建的一个共享网段时，距离和数量都有特定的 限制。随着网络规模的增加，每个设备实际获得的带宽将越来越少，必须使用一 些设备把网段分成微网段，使得每个微网段的设备使用整个带宽。网桥和交换机 注：术语相同，交换机可视为多端口网桥 是o s i 第二层的网络连接设备。这种 使用网桥的以太网常称为交换以太网p 1 。 桥接以太网必须t 作在一个无环路或者树状的网络拓扑结构上。这个条件即 保证了到网络中的每一个设备只有一条路径，又简化了网桥转发包的工作。如果 一个由交换机构建的网络存在环，交换机将使用以太网网桥生成树算法使得环中 基j ：s n m p 的i p | i 畸络拓扑信息的发现与应用 的某条链路失效( 不t 作) ，从而保证网络处丁一种无环路的拓扑结构。 网桥采用了一种比网络层路由更复杂的数据帧转发箅法。网桥通过对每个端 口的流量的学习来决定如何转发数据帧。只要网桥在任一端口获得一个数据帧， 它就保存该帧的源地址和网桥端口号。网桥一直维持这样一张地址转发表 ( f o r w a r d i n gd a t a b a s e ，f d b ) ，表中的每条记录表明网桥在某个端口上发现了一 台发出数据流的主机。网桥在转发数据帧时，将该帧的日的地址提取出来，然后 查找地址转发表以决定如何处理该帧。这种网桥成为自适应( a d a p t i v e ) 或学习 ( 1 e a r n i n g ) 网桥。 在记录了一帧的源地址后，自适应网桥根据帧的目的地址决定是否继续转发 该帧。如果从地址表中看出该帧的目的地址就在本以太网中，网桥不再转发该帧： 如果在其他端口学习到该帧，那么网桥仅仅向该端口转发帧：如果目的地址不在 地址转发表中( 目的地址是个广播或组播地址，或者网桥还没有学习到该目的 地址) ，则网桥采用“洪泛”的方式，向其他所有的端口转发该帧。 自适应网桥的优点非常明显。因为网桥使用正常通信量中发现的地址，所以 它是完全自动的，不需要人为地以特定地址配置网桥。所以我们常称网桥是即插 即用i 殳各。 采用上述方法的网桥构成的网络可以认为是透明的，冈为计算机不知道有多 少个网桥连接着并个嘲段，并个主机连接在哪个网桥上。这使得研究准确发现和 构造交换以太网的拓扑发现算法很困难。 1 1 3 虚拟局域网 与传统的共享网段相比，局域网在采用交换技术以后，每个节点的吞吐量不 会随着节点的增多而下降，网络的性能大大提高。但对丁所有处丁- 一个i p 网段 的网络设备来说，却同在一个广播域中。当t 作站数量较多和信息流较大时，容 易形成广播风暴，严重影响了网络运行速度，甚至容易造成网络瘫痪。为解决这 问题，引入了虚拟局域网的概念。 v l a n ( v i r t u a ll o c a la r e an e t w o r k ) 即虚拟局域网，是一种通过将局域网内 的设备逻辑地而不是物理地划分成一个个网段从而实现虚拟t 作组的新兴技术。 i e e e 于1 9 9 9 年颁布了用以标准化v l a n 实现方案的8 0 2 1 q 阱议标准草案 4 1 。 v l a n 具有如下特点： 分段性：可根据部门，功能和项目来划分成不同的网段； 灵活性：组成v l a n 的用户不用考虑物理位嚣，同一个v l a n 也可以跨越 多个交换机； 幕rs n m p 的l p 酬络拓扑信息的发现与应用 安全性：通过广播域的分隔，使每个逻辑的v l a n 就像一个独立的物理桥， 控制网络的广播风暴，提高了网络的性能和安全，但不同的v l a n 间的通 讯需要经过路由器来连接。 v l a n 在交换机匕的实现方法，可以大致划分为四类：基丁端口划分的 v l a n 、基丁m a c 地址划分v l a n 、基丁网络层划分v l a n 、根据i p 组播划分 v l a n 。其中基二j i 端口的v l a n 是划分虚拟局域网最简单也是最有效的方法。 1 2 网络拓扑概述 i p 网络( 简称刚络) 拓扑是指包括网络设备及其连接关系的网络图。刚络 拓扑是一种表示网络中自接相连的设祷之间互连关系的方法。网络抓扑图包括网 络对象的信息，网关、路由器、桥接器、端客户机、接口等甚至网络本身部属丁 网络对象。在拓扑图中，各种网络设备之间的互连关系是最基本的信息，符设备 和链路的属性( 例如速度、负荷、协议、o s 等) 和功能也可以显示出来，功能 包括网络元件提供的服务，其他一些信息元素还包括与策略( p o l i c y ) 有关的信 息、与网络名字和地址有关的信息、与网络管理机构和管理有关的信息口i 。 传统的网络拓扑发现以手j r 添加为主，然而随着网络技术的迅速发展，网络 规模不断扩大，网络结构日益复杂，使得手丁方法已不能满足人们的要求。 网络拓扑发现( n e t w o r k t o p o l o g y d i s c o v e r y ) 是。个识别所有向用户传送满 意的服务中所涉及的实体的过程。该过程不仅要能汉别实体，还要发现它们在网 络中担任的角色，即它们之间是如何交互的，是如何被使用的、它们提供的服务 以及服务质量。 准确有效地完成网络拓扑发现有极大地需求和应用前景，这主要体现在以下 儿方面7 】 8 】f 9 】【i o 】= 1 网络管理：网管系统的基本功能足以图形方式直观地将被管对象显示出 来。冈而拓扑发现足不可或缺地部分。作为网络管理系统的一个重要组成部分， 抓扑发现是配置管理的核心、故障管理的基础，同时它也是衡量一个商业网管系 统成败的重要尺度。因此拓扑发现算法的设计在整个网管系统的丌发中占有举足 轻重的地位。 2 模拟( s i m u l a t i o n ) ：为了模拟实际的网络，网络的拓扑必须首先获得。 大规模网络实际拓扑的建模( 例如i n t e m e t ) 是个相当新的研究领域。利用拓 扑发现工具不仅可以发现网络的实际拓扑结构，还可以从中抽取信息，以了解网 络拓扑的特征。例如，计算每个结点的平均出度和入度：两个结点间的平均跳 基卜s n m p 的】p 州络拓扑信息的发现与应用 ( h o p ) 数；路径上流量的分布等等。可以利用建模的结果产生人造( 模拟) 网 络( 对真实的模拟) ，来测试新的协议和想法。 3 服务器选址和定位：根据拓扑信息，合理配置镜像服务器的位置，最大 可能减少响应时延，解决瓶颈问题：另一方面，网络捕扑信息可帮助用户测定自 身在网络中的位置，由此决定加入哪里的站点服务器，接入哪个网络服务提供商 ( i s p ) 以挟得最小的延迟和最大的有效带宽。 4 拓扑敏感算法( t o p o l o g y - a w a r ea l g o r i t h m s ) ：一些新的协议和算法利用网 络拓扑信息来提高算法的性能。例如：基丁拓扑敏感策略和服务质量( q o s ) 的 路由算法，基t 打i ? b 敏感的处理器组( 路由器) 选抒的组播算法【9 i 。 5 网络发展变化的研究：对大型网络( 例如i n t e r n e t ) 发展变化的研究也 与拓扑发现有关。这时候不仅要了解实际的网络拓扑，更关心网络随着时间的变 化是如何发展的，以及支配这些变化的规则。利用这些规则可以预测网络将来的 变化】。 6 大型复杂网络拓扑的可视化”。 综上所述，在网络日益发展的今天，网络拓扑发现已成为一项非常重要的工 作。 1 3 网络拓扑发现概述 1 3 1 网络拓扑发现基本协议 在t c p i p 最初发展的阶段，还很少考虑到网络管理的问题。直到2 0 世纪 7 0 年代后期，仍然没有网络管理协议。当时的一个有效管理t 具是i n t e r n e t 控制 报文协议i c m p ”1 。i c m p 提供了从一个网络设备( 如路由器或主机) 到另一 个网络设备传输控制报文的手段。i c m p 在所有支持i p 协议的设备上都足可行 的。到8 0 年代秀u 期，i n t e r n e t 的不断发展更促使人们进一步意识到网络管理的重 要性。1 9 9 0 年i e t f 在r f c1 1 5 7 中正式公布了s n m p 【l ，由于s n m p 的普遍使 用，针对s n m p 的丌发和研究成果不断出现，s n m p 已经成为了网络管理领域 中事实上的工业标准【l “。 目前，在自动网络拓扑发现算法研究和产品开发中，绝大多数都是基于上述 两种协议来收集网络中的拓扑信息，然后加以分析处理，构造网络拓扑图以及对 i ； 络结构的更进一步的研究。 i c m p 通过发送e c h or e q u e s t 和e c h or e p l y 报文对，提供一种测试网络实体之 基rs n m p 的i p 刚络拓扑信息的发现与应用 问通信可能性的机制。利用这种机制而开发出来的最有名的管理t 具就是p i n g 。 它可以用来测试某个设备是否可达”1 。为了防止避免路由器中的选路表出现选 路循环，每个i p 数据报都包含一个寿命计时器( t i m et ol i v e ，t t l ) ，有时称为 下一跳计数( h o pc o t i n t ) 。一日路由器冈为某个数据报的下一跳计数为0 就丢弁 它，而且向数据报的源站发回一个i c m p 超时( t i m ee x c e e d e d ) 报文。利用这种 机制而开发出来的最有名的管理 二具就是t r a c e r o u t e 。他可以用来测试两个网络 设备之问的路由设备“1 。利用i c m p 协议的这些特征，开发拓扑发现算法的研究 丁作主要是针对大型的i p 网络，如i n t e r n e t 。 近来，i e t f1 | l 易【1 人阻刮网络打i 扑的重要性，提m 卜个s n m pm i b ( r f c 2 9 2 2 ) 来描述拓扑，但是它只定义一种描述和存储拓扑图的数掘结构，并没 有提出扶得拓扑图的协泌或方法。但是，利用s n m p 管理叻，议获取目前大多数 网络设备已经支持的m i b 数据，通过对这些数据的分析处理，构造管理域内的 网络拓扑结构的研究和算法很多。由丁利用s n m p 协议开发的自动拓扑发现算 法简单，发现的网络拓扑图完整、准确，所以被很多商业管理软件所采用。 1 3 2 网络拓扑发现算法 1 网络i p 层拓扑发现算法 h w a c h u nl i n t ”、石冰心【”埂出了基于s n m p 的拓扑发现算法，算法的基 本思想是使用s n m p 协议访问网络设备的m i b s ，然后根据m i b 数据构造网络 的拓扑图。具体实现是采用s n m p 访问m i b i i ( r f c1 2 1 3 ) 1 9 1 ，利用其中接v 1 组、i p 路由组和i p 地址映射组等m i b 数据构造i p 网络层拓扑图。这种方法的 主要的优点是算法的效率高。 但是基y - s n m p 的拓扑发现算法必须要求系统具有访问网络设备的管理权 限，所以这些算法不适用于跨越多个管理域的网络( 例如i n t e r n e t ) 的拓扑发现。 要推断路由的邻接关系使用限跳探测( h o p 1 i m i t e dp r o b e ) 足最简单和唯一有效 的方法口】。这种探测包括发送一个限跳的i p 包，和与之相应的i c m p 回应包指 示i p 包寿命( t t l s ) 过期或发生其它错误。t r a e e r o u t e 工具就是采用这种方法 来获得到给定的日标的路径。 早期获得拓扑图的方法【9 ”】 2 0 1 就是向i n t e m e t 中不同的目的结点发送一系列 的t r a c e r o u t e s 来计算路由器的邻接关系。目的结点的i p 地址通常来自一个或多 个数据源( 例如，任何的路由表，d n s ，预先计算好的主机地址) 。而且，许多 早期的工作都试图在网络的一个源点发送限跳包以获得i n t e r n e t 的拓扑图。 r a m e s h g o v i n d a n t t 描述了推导i n t e m e t 路由层拓扑程序m e r c a t o r 中使用的一 基s n m p 的i p | 叫络拓扑俯息的发现与麻用 组启发式方法。该程序发送限跳探测包的目的i p 不需要外部数据源来提供，而 足使用基 。知识的随机地址探测的启发式方法，以及i p 地址分配政策。这种不 需要外部信息源来控制探测的技术使得m e r c a t o r 可以运行丁网络的任何地方。 m e r c a t o r 除了在安装站点以发射状向外发生限跳探测包以外，还利用源路由技术 ( s o u r c e r o u t i n g ) 控制探测包的方向以发现交义链路( c r o s s l i n k s ) 一一种限跳 探测不能发现的路由器邻接方式。这些启发式探测方法必然会导致一个路由器有 多个别名( a l i a s ，接口i p 地址) 的情况。m e r c a t o r 也采用了一些识别这些别名 的启发式方法。 p a u l b a r f o r d ”讨沦了在发现i n t e r n e t 拓扑图的过程中，被测点和测量源的数 量的增加对拓扑图的有效覆盖率的影响，以更加量化的方法来研究发现i n t e r n e t 拓扑而进行的大范1 4 4 1 n 量的边际效用( m a r g i n a lu t i l i t y ) 。使用信息与统计学方法 对获得的拓扑图的顶点、边( 链路) 、结点度的分布、端到端数据流的分布等特 征进行研究。由此得出结论，在大范俐网络拓扑发现中，增加被测量点比增加测 量源更有效。 基丁限跳探测方法的拓扑发现算法，由丁其采用i p 和i c m p 这些底层通用 胁泌，所以这类算法可以很好的挟得跨越多个自治系统( 如i n t e m e t ) 的打i 扑图， 算法实现简单、可操作性强。但是限跳探测方法足一种很赞时的方式【9 l ，而且为 了提高拓扑图的覆盖率，必须探测大量的目的地址刚，所以探测网络拓扑的时 间很长。 徐大海等口2 】提出了一种基于o s p f 协议的网络拓扑搜索算法。o s p f 协议采 用的s p f ( s h o r t e s tp a t hf i r s t ) 算法要求每个参与工作的路由器都要具有全部的 拓扑结构信息，即每个路由器拥有一张标出所有路由器及其所连接的网络的图。 该网络拓扑搜索算法就是利用o s p f 协议的特性，采用实现o s p f 叻，议并安装到 一台主机，然后让它与路由设备通信，利用它从路由设备得到的路由信息来提取 网络拓扑连接信息：或者直接获取某一个采用o s p f 协议的路由器中的m i b 数 据，就可阱计算出整个网络i p 层拓扑。该算法性能高、速度快，但实现难度大， 而且由于o s p f 足种内部网关协议，所以搜索只能限某个自治系统内进行，并 且要求该范闱内的所有路由设备都支持o s p f 协议。 2 网络链路层拓扑发现算法 y u r ib r e i t b a r t 等队b r u c el o w e k a m p 等与郑海等分别提出了符白基于 地址转发表的以太网链路层拓扑发现算法。 y u r ib r e i t b a r t 提出了一种在异构i p 网络中的物理拓扑发现算法。利用 b r i d g em i b 2 5 1 的转发表中的数据和网桥生成树协议，提出了一个判断两设备直 基j ：s n m p 的i p 嘲络拓扑信息的发现与应用 连的引理。该方法通用( ：包含多个i p 子网的桥接以太网的拓扑发现。但是这个 算：法要求完全的m a c 地址转发表的条件在实际网络中很难实现。 b r u c el o w e k a m p 在r e m o s 项目中采用了一种改进的算法，提出了判断两 设备连通的引理以及最小必要条件引理，它不需要转发表是完全的，而且这个算 法可以处理共享网段，这些特点使该系统更适合于实际网络，而f l 对于大规模网 络的拓扑发现的效率也很高。 郑海提出的算法，通过端口地址转发表是否保存了一个特殊的标志记录，把 交换机的端口分为上行和下行两类端口，提出了一种判定上行端h l 利下行端口直 连的引理。从而解决了上行端口的地址转发表的记录不完整问题。 因为交换机的地址转发表中的记录是通过逆向学习的方式动态扶取的，而 且，每条记录都有超时控制，超过一定时间，交换机会将其丢弃。那么，地址转 发表具有不完整性和动态性。为了保证每台交换机的地址转发表的记录能满足判 定连接关系算法的要求，上述的拓扑发现算法在进行打i 手h 发现之前都采用了一些 注入附加流量的方法2 ”【2 4 】，使得地址转发表中的记录有效。但是这些方法不仅 增加了网络的负荷，而且均存在一些问题 2 4 】，影响了算法的可操作性。 而且上述三种算法为了简化问题，都假设地址转发表中只包含路由器与交换 机的m a c 地址。而实际网络中的交换机设备的地址转发表还包含了主机的m a c 地址。这大大增加了级联端口的地址转发表中的记录数，从而增加了歌取( 筛选 出) 有效m a c 地址记录的难度，使得算法的可行性受到一定限制，这就要求找 到另一种新的算法解决上面的问题。 1 3 3 网络拓扑发现产品 1 商业产品 c i s c o 公司： c i s c o w o r k s 2 0 0 0 系列1 2 6 c i s c o w o r k s 2 0 0 0 是一基于互联网标准的用于管理c i s c o 的企业网和设备的产 品系列。c i s c o 开发了c i s c o d i s c o v e r y p r o t o c o l ( c d p ) 来用于其自家产品的通信和 拓扑发现。在异构的网络环境中，c i s c o w o r k s 2 0 0 0 无用武之地。 h p ：o p e n v i e w 系列t 2 7 】 h po p e n v i e wn e t w o r kn o d em a n a g e r 它以直观的图形方式提供了深入的网 络视图。n e t w o r kn o d em a n a g e r 能够发现网络设备，并提供显示网络实际状况的 视图。 初始化时提供一些支持s n m p 的结点：使用s n m p 访问a r p 表以构建网络 拓扑；利用i c m p 动态发现设备的存在性，改变拓扑：利用s a p 发现i p x 网络。 基下s n m p 的i p 删络拓扑信息的发现与应用 i b m t i v o lin e t ve w 2 8 】 t i v o l in e t v i e w 采用的足c m i p 管理协 义，只能用丁二s n a 架构的网络的拓扑 发现。n e t v i e w 是i b m 公司在h po p e n v i e w 的基础之上发展起来的。它的核一1 1 , 代码没有改动，但加入了大量的应用，特别是s n a ( s y s t e m sn e t w o r k a r c h i t e c t u r e ) 网络的支持。 2 研究成果或原型 o c t o p u s 和a r g u s 项目9 1 该项目由c o r n e l l 执行的。采用p e r l 语亩实现了3 种算法：一个使用s n m p 查找路由器的a r p 表；第二个使用d n s 的z o n et r a n s f e r 和v a c e r o u t e ；第三个 是先猜。些地址，然后使用t r a c e r o u t e 来找拓扑。而且还通过修改p i n g 和 t r a c e r o u t e 提高算法执行速度。其最大的问题足内存消耗大。因为所有的信息都 保存在内存中，直到算法结束。 s k it t e r f 2 0 1 由c a i d a 丌发。使用t r a c e r o u t e 查找两结点的连接路径，同时收集性能信 息。这个方法的特点：使用一组主机是一个分布式的应用( 多主机收集数据再向 中央服务器报告) ：利用t r a c e r o u t e 测量性能也是其特点。 r e m o s 2 9 3 0 】 b r u c el o w e k a m p 等在项日中采用m a c 地址转发表的数据，实现了一种发 现以太网物理层网络拓扑的算法，并且在此基础上开发了一组a p i ，使上层应用 程序能够获得网络路径的结构以及路径上的一些网络资源特性。 1 4 本文的主要工作与意义 随着对网络需求的不断增强，必须要求一个可信、可靠、安全、稳定的网络 平台。网络管理已成为网络系统的运行好坏的关键。如何发现网络拓扑结构，建 立有效的网络拓扑模型以便了二网络管理和研究是十分重要的。 网络的拓扑结构发现是网络管理的基础。网络拓扑是网络管理的重要组成部 分，网络管理员在安装或配置网络部件时需要网络拓扑结构。它也是网络监视的 一个基础工具。每个网络管理工具在初始化阶段都要进行拓扑发现。 目前比较成熟的网络管理系统主要集中在国外，不仅价格昂贵，而且对异构 网络的支持不够，没有提供协议分析、网络性能分析等功能。冈此，开发商业化 的智能在线网络监控系统有很大的市场价值。 本文在分析和研究现有的网络拓扑发现算法的基础上，提出种基于s n m p 基：s n m p 的1 p 叫络拓扑信息的发现与府用 的i p 网络拓扑发现算法，并在网络管理系统中丌发了拓扑发现模块。本文的主 要t 作包括： 1 在分析前人提出的多种网络层拓扑发现算法的基础上，提出了基丁路由 表的发现算法，这是在管理城内获得路由器之间连接关系的最有效的方 法。 2 以前的网络链路层拓扑发现算法都足基于m a c 地址转发表的，本文提出 了一一利- 拙y - 例桥生成树的算法，这个簧法的土要特点在j ：彳；需要任何的 准备 _ 作，只需扶取标准m i b 中生成树协议组中的数据，做简单的杏找 比较操作就可以准确的推导出网络设备( 链路层设备) 之间的连接关系。 算法简单有效，有更好的可操作性。 3 在分析有关m i b 文档( r f c ) 的基础上，实验验证了本文提出的网络层和 链路层拓扑发现算法的正确性。 4 利用上述的网络拓扑发现算法，本人利用v c + + 开发语言，在w ir l d o w s 平台上实现了1 个网络拓扑发现子系统原型。利用本人开发的基y - s n m p 的m i b 数据获取类，根据网络拓扑发现算法的要求，获取网络设备中的 有关m i l 3 值，然后根据算法中提出的连接关系判定算法，推导出网络的 拓扑结构。 1 5 文章的组织 本文共七章，第一章介绍网络拓t b a c n 拓扑发现的概念、麻用以及当前国内外 拓扑发现算法的研究现状，并简单介绍了用于拓扑发现的基本协议。网络拓扑发 现涉及到的问题比较多，在第二章讨论了研究网络拓扑发现算法要考虑的问题。 第三章描述了利用s n m p 西议获取路由表和利用i c m p 发现网络层拓扑的算法， 而利用s n m p 协议软取的m a c 地址转发表和生成树表构建链路层( 第二层) 拓 扑的算法将在第四章介绍。第五章介绍了通过对实际网络设备m i b 值的采集和 分析，验证了本文提出的拓扑发现算法的正确性和可行性。第六章介绍了拓扑发 现子系统的设计和编程实现中的关键技术。第七章是全文的总结和下一步工作的 展望。 - l o 基j 。s n m p 的i p 删络拓扑信息的发现与席用 第二章网络拓扑发现 网络规模越来越大，目，网络技术不断发展。发现网络的实际布局、人t 描绘 网络 千l 扑结构变得越来越困难。然而，网络拓扑信息在网络管理、模拟和服务器 定位等庸用领域十分重要。对网络拓扑自动发现算法的研究是网络拓扑中最关键 的1 ：作。网络拓扑发现涉及到的问题比较多，下面将对其巾主要的问题进行讨论。 2 1 引言 由于结点和链路不断的加入网络，结点的迁移，网络容量的增加导致流量不 断增大，这些因素使得网络拓扑在不断变化。用手工的方法来跟踪网络拓扑是不 可能的。而且研究自动网络拓扑发现方法也是很困难的。 没有使拓扑发现这项t 作变容易的实现机制或设计规范【9 】 一个有紧密关系的问题是缺乏知道网络( 如i n t e r n e t ) 的细节以及对如何设 计和实施网络提出一些强制性的规则的中央管理机构。缺乏管理是i n t e r n e t 发展 迅猛的一个原冈，但这对管理和跟踪网络变化来说却是一个不利的冈素。由于与 网络管理有关的协议和标准的缺乏，造成了在发现网络打f 扑时，缺乏合适、有效 的专用工具而只能使用一些基础工具，如p i n g 、t r a c e r o u t e 。 自动拓扑发现必须解决由不同机构管理各自子网的闽题 以i n t e r n e t 为例，网络由多个被不同机构管理的自治系统( a u t o n o m o u s s y s t e m ，a s ，由个i s p 运营的网络称为一个自治系统) 组成。自动拓扑发现 t 具必须能够发现由多个自治系统组成的网络的精确的拓扑结构，但是由丁安全 方面的要求使得算法采用的技术受到限制，使得拓扑发现过程更加难以实现。例 如，在拓扑发现方法中经常采用的s n m p 协议、d n s 的z o n e t r a n s f e r 、广播p i n g 方法就不能获得其他a s 的信息。即使只要求荻得与其它a s 的连接、a s 边际设 备等这些少量的信息，由于当前网络运行的策略的限制使得实际操作时会遇到困 难。 即使在由同一个机构管理的自治系统中，拓扑发现面临的问题也相当困难。 因为现在的网络采用多种不同的技术来提供服务。例如在实现底层网络时可以采 用a t m 或以太网技术( i e e e8 0 2 x ) ，在网络层可以使用i p 协议或其他非t c p i p 协议。要求拓扑发现算法能识别出各种设备一般说来是困难的。如果要求拓扑发 现算法能识别运行其它网络协议( 非t c p i p 协议) 的网络，将使算法的实现更 基r ，s n m p 的】pm 络拓扑信息的垃现畸麻用 加困难。 实现通用型的第二层网络拓扑结构发现方法是很困难的2 3 1 构造第三层的网络拓扑图要相对容易一些，因为路由器为了执行它们的基本 功能必须清楚的知道与其邻接的设备。所以利用标准的路由信息就足以获取并描 绘出第三层的连接关系。然而，在整个i p 网络的连接关系中，第三层的拓扑关 系只足一小部分，而在子网中第二层网络元件( 交换机和网桥) 构成的复杂的连 接关系是大部分。 为摊t 缸予州巾件个小，l 享刚段之问的带宽，使用交换机f 1 ：为筇一j 。：例络连 接设备的情况越来越多，也就是说在第三层刚络拓扑图中不能描述的网络设备 ( 及其之间的关系) 在整个i p 网络中的比例在不断增大。与之相应的是，网络 管理员在进行端到端故障定位或评价交换网中链路( 或设备) 失效造成的影响时 的能力将严重减弱。 综合这些| 天f 素，我们在提出有实用性的i p 拓扑发现算法时，必然会遇到下 面三个基本困难f 8 。 1 设备信息的有限性 算法对设备能提供有效信息的假设越少越好；也就是说，只利用大多数可管 设备都维护的信息。 2 设备跨协议层的透明性 算法要能正确的构造工作在i s om 议不同层上的物理设备之间的互联关系。 这很重要，冈为在交换子网中第二层设备对于位于i s o 协议第三层的负责子网 之间流量转发的路由器来说是完全透明的。 3 网络设备的异构性 算法能够收集异构网络元件的拓扑信息。而且要确保不同厂商的设备中相关 的数据要可以访问且能正确解释。 网络拓扑发现涉及到的问题比较多，但是总的来说，主要有三方面问题需要 明确( o l 【3 j 】 32 1 。 1 首先，要明确拓扑发现程序的目的一关心哪一层的网络结构，因为只有 确定了网络的层次协议，才能明确到底什么样的信息要被采集，才能使这项技术 具有比较好的适应性。对目标的理解得越清楚，在设计好的发现程序时就越容易。 目前随着i n t e m e t 的普及，大多数的网络都采用t c p f l p 协议。儿乎所有的 设备都支持i p 协议，所以( 大多) 网络拓扑发现将以i p 网络为主。 2 决定拓扑信息的获取方式，即决定使用被动监测技术还足主动探测技术 来收集包含了网络结构信息的数据。 基- j 。s n m p 的i p 刚络拓扑信息的发现与戍用 被动监测技术( p a s s i v em o n i t o r i n gt e c h n i q u e s ) 是通过在所有观测的网络都 加入一个探测器。由它来采集信息，并发送到网络管理主机来形成网络的拓扑结 构。最大的优点是不会给网络带来额外的负担。同时，因为只能观察当前交换的 包( 流过本共享网段的包) 来收集网络数据，所以不能主动的控制发现进程。因 此，采用该方法必须花费很长的时间才能收集到能构造出完整网络图的足够的数 据，另一个问题是由于网络设备( 如路由器) 对数据包流向的控制，所以要获得 整个网络的信息，必须在每一个子网段( 共享网段) 设置监测设备，这对丁一个 火的网络来说是不太实际的。 主动探测技术( a c t i v e l yp r o b i n gt e c h n i q u e s ) 是通过网络管理主机向所有管理 网络发送探测包，并采集返叫的信息，进行分析最终形成网络的拓扑。所以其特 点与被动监测技术相反。该方法将造成额外的网络流量，将对收集的信息和对负 载敏感的网络都有一定的影响。另一方面这种技术的优点足：由丁主动探测过程 可以控制，状得网络拓扑图的时间丌销可能足最小的。 3 决定发现程序的数据源，即决定要收集什么数据，从哪里能得到以及荻 得的方法。 确定采用何种方式收集信息。这里有两种可选择的方案。一种是可以使用网 络管理协议( 如s n m p ) 或者利用一些协议( 如i c m p ) 的特点和功能( 甚至可 以开发自己的协议，但要能安装到网络的每个设备上) 能够提取出拓扑信息。如 果网络中的设备能够响应网管协议的请求，那么使用网络管理协议是一个好方 法。但是网络上的设备十分繁杂，不是所有的设备都支持这些管理协议，而且需 要对涉及到的网络逐个进行配置。而基于i c m p 协议的拓扑发现方法，他们是建 立在i p 层的基础上的，被所有的i p 网络和设备支持，在采集网络信息时局限性 较小，可靠性比较高，且省去了大量的手工配置，该方法只能收集i p 层的信息。 另一种方式是很多不同的设备协同工作，但分析获得的数据将变得困难。 2 2 网络拓扑发现算法 2 2 1 网络拓扑发现的基本算法 获得网络拓扑图最简单精确的办法是询问管理员扶得各个实体及其使用的 信息，然后手t 画出一张精确的网络。但实际上是不可能的。这有儿方面的原因： 网络实体数量指数增长；它们提供的服务也在增多且越来越复杂：网络由不同机 构管理。 基】s n m p 的1 rm 络拓扑侍息的发现与戍斤) 而自动拓扑发现算法可以克服这些困难。要注意的是现在一般的自动拓扑发 现算法仍然需要人的参与，一是进行一些启动算法的初始化操作，如提供一些关 键实体作为种子、搜索地址范吲等一些参数：二是在算法执行结束后，加入没有 被发现的设备、功能或服务。 最基本的算法： 1 把所有可能与实际主机、交换机和路由器等网络设备相关的l p 地址存入一个临时 地址集合( t e m p o r a r ys e t ) 2 f o r 临时地址集合巾的每一个地址： a 进行验证 b 如果有效，发现其与同定地扑集合( p e r m a n e n ts e t ) 叶1 的地址的关系，并加入 该地址到周定地址集合中 c 利用该地址产生更多的i p 地址并加入到临时地址集合中 这足对拓扑发现算法最一般的描述9 】，后续章节将描述系列的发现算法部 是在此基础上衍生出来的。 2 2 2 网络拓扑发现算法的分类 按拓扑图的范俐： ( 1 ) w a n 拓扑：i n t e r n e t 是拓扑发现算法研究的最主要的f | 标。i n