基于SNMP协议的网络拓扑发现算法.pdf

《基于SNMP协议的网络拓扑发现算法.pdf》由会员分享，可在线阅读，更多相关《基于SNMP协议的网络拓扑发现算法.pdf（5页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第 4 卷第4 期2 0 0 7 年 1 2 月长 沙 理 工 大 学 学 报(自然 科 学 版)J o u r n a l o f C h a n g s h a U n i v e r s i t y o f S c i e n c e a n d T e c h n o l o g y(N a t u r a l S c i e n c e)Vo l.4 No.4 De c.2 0 0 7文章编号:1 6 7 2-9 3 3 1(2 0 0 7)0 4-0 0 6 8-0 5基于S N MP协议的网络拓扑发现算法邓泽林，张立芳，刘翌南，傅明(长沙理工大学 计算机与通信工程学院，湖南 长沙

2、4 1 0 0 7 6)摘要:网络拓扑发现对于现代网络管理是一个重要的课题，尤其是第 2 层网络拓扑发现是一个难题。针对这一难题，基于大多数网络设备都支持的S N MP 协议，提出了一个快捷、高效的算法，并对该算法进行了详细的描述，用该算法进行了真实环境的测试，测试结果和真实网络情况完全吻合，说明了此算法是一个有效的拓扑发现算法.关键词:网络;拓扑发现;简单网络管理协议;第 2 层中图分类号:T P 3 9 3.0 7文献标识码:AN e t w o r k t o p o l o g y d i s c o v e r y a l g o r i t h m b a s e d o n S

3、N MPD E N G Z e-l i n，Z HA N G L i-f a n g，L I U Y i-n a n，(C o l l e g e o f C o m p u t e r a n d C o m m u n i c a t i o n E n g i n e e r i n g,C h a n g s h a S c i e n c e a n d T e c h n o l o g y,C h a n g s h a 4 1 0 0 7 6,C h i n a)F U Mi n gUn i v e r s i t y o fA b s t r a c t:N e t w o

4、r k t o p o l o g y d i s c o v e r y i s v e r y i mp o r t a n t f o r t o d a y s n e t w o r k ma n a g m e n t,t h e 2-l a y e 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 i s d i f f i c u l t e s p e c i a l l y.A f a s t a n d e f f e c t i v e n e t w o r kt o p o l o g y d i s c o v e

5、 r y a l g o r i t h m b a s e d o n S N MP f o r l a y e r 2 o f n e t w o r k i s p r o v i d e d，w e a l s o a p-p l y t h i s a l g o r i t h m t o r u n o n a n e t w o r k,t h e r e s u l t s h o w s t h a t t h i s a l g o r i t h m i s v e r y g o o d f o rn e t w o r k t o p o l o g y d i s

6、 c o v e r y.K e y w o r d s;n e t w o r k;t o p o l o g y d i s c o v e r y;s i m p l e n e t w o r k m a n a g e m e n t p r o t o c o l;l a y e r-2 拓扑发现是指确定网络元素之间的互连关系.由于网络的连接会经常变换，所以通过手工操作了解最新的网络连接就成了一件很繁琐的工作.随着 I P网络自动拓扑发现技术的开发，网络层(第3 层)的发现技术已渐趋成熟，文献 1,2 介绍了网络层拓扑发现算法.相对于网路层(第 3层)拓扑发现而言，实现链路层(第

7、2 层)拓扑发现则变得相当困 难.著名的硬件提供商，如:C i s c。已开发出针对各自产品的拓扑发现协议，但对于异构的网络拓扑发现却还没有成熟的技术和方法.目 前市场上流行的网管产品基本上是基于S N MP 协议实现的.简单网络管理协议(S i m p l eN e t w o r k Ma n a g e m e n t P r o t o c o l，简称 S N MP)是一种基于 T C P/I P协议的互联网的管理协议标准，是互联网工程任务组 I E T F(I n t e r n e t E n g i-n e e r i n g T a s k F o r c e)以简单网关监控

8、协议S G MP(S i m p l e G a t e w a y Mo n i t o r i n g P r o t o c o l)为基准改造而成，具有较强的扩展性，允许为厂商的特定要求增强扩展MI B(管理信息库)，从而方便扩展管理能力.目 前，国内 外关于网络拓扑发现已进行了大量的研究，并取得了一定的研究成果.文献 3,习论述了利用S N MP 协议进行网络拓扑发现的步骤和方法，能基本发现第 2 层、第 3 层网络的结构，但文献并没有讨论针对网络中普遍存在的不收稿日 期:2 0 0 6-1 2-2 9-基金项目:湖南省自 然科学基金资助项目(O T J J 3 1 2 0);湖南省

9、教育厅科研资助项目(0 7 C O 8 1).作者简介:邓泽林(1 9 7 7-)，男，湖南常德人，长沙理工大学讲师，主要从事计算机网络与安全、算法方面的研究.万方数据第4 卷第4 期邓泽林，等:基于S N MP协议的网络拓扑发现算法可网管的设备，如:H u b 等设备的发现方法，因而其发现的结果与实际网络是有一定误差的.随着网络技术的飞速发展，网络结构也变得越来越复杂，特别是一个交换域内多子网的出现，以及虚拟局域网V L A N技术的广泛使用，向网络拓扑的自动发现提出了新的挑战 5.6 1 本研究在网络拓扑发现研究 3.4 的基础上，利用网络设备广泛支持的S N M P协议(文献 7,8 提

10、供了S N MP 协议以及网桥可管理对象的定义)提出了一种针对交换机一交换机、交换机一H u b 等第 2层设备连接关系的快速、准确的拓扑发现算法.1 基本理论1.1 网络基本概念 计算机网络可以用无向图G=(V,E)表示.V表示网络中的节点，如:交换机、路由器和主机等;E表示V中元素的连接关系.为了减少网络阻塞，I P网络被划分为多个子网或逻辑网段.子网间以路由器连接，子网内以交换机等网络元素连接.真实网络环境的物理链路可能由于存在回路(备份链路)而导致网络风暴，致使整个网络瘫痪.为了防止网络风暴，可以通过运行“生成树协议”(S T P)来破除网络中的环，使某些交换机间的连接逻辑上断开以有效

11、防止网络风暴.运行 S T P协议的网络构成了树状结构，如图 1 所示.1.2 拓扑发现信息源MI B库 目 前大多数商业化的网管软件都是基于S N M P，借助网络设备中的网管代理，通过访问或配置MI B中的变量来实现网络管理功能(包括性能、故障、计费、配置和安全管理五个功能域).MI B含有对路由表、转发表及接口的描述，因此使得拓扑构造成为可能.它不仅可以构造出网络层设备(路由器、网关)的连接关系，而且也可以构造出链路层设备(网桥、交换机)的连接关系.基于网络管理协议进行拓扑发现用到 MI B库中的变量:I P路由表(i p R o u t i n g T a b l e).路由表中主要信

12、息有:目的 I P地址、下一跳路由器的I P地址、路由类型、路由协议、掩码和路由的接口索引;接口表(i f T a b l e).接口表中主要信息有:接口索引、接 口描述、接口类型和接口的物理地址;i p F o r w a r d i n g.1 代表可转发数据(具网关功能),2代表不转发数据(不具有网关功能);s y s S e r v i c e s.可用于判断设备类型.若主机在第 i层提供了服务，则L 对应相应的层数，s y s S e r v i c e s的值为:m=s u m 2-(L*一1),i=1,2,3,4,7 分别对应物理层、链路层、网络层、传输层和应用层(如图2 所示)

13、.如:若 s y s S e r v i c e s 的值为 4，则该设备是路由器;)I p N e t T o Me d i a T a b l e.可以访问相连的终端设备的 I P地址;地址转发表.以太网交换机通过读取传送帧的源 MA C地址和记录该帧进人交换机的端口号来学习网络上每个设备和交换机之间的连接情况，交换机把(设备 MA C地址和进人的端口号)这样的信息加到交换机的地址转发表，同时对存储的信息设置新的时间标记，对一段时间内没有被引用的信息进行淘汰.应用层表示层会话层传枪层网络层链路层物理层=7拓:5拼:3=2:l瓜吞及几寿瓜吞狐气“、-，.橇萝图 1 网络无向图图2 服务与L

14、对应关系图万方数据长 沙 理 工 大 学 学报(自然科 学 版)2 0 0 7年 1 2月2 网络拓扑发现的基本原理 网络拓扑发现的难点在于第 2 层的拓扑发现，第 2 层的主要设备是交换机、网桥及 H u b 等.交换机的主要功能是自动学习通过自 身各个端口数据帧的源MA C地址，并将其与对应的端口号一起存人本交换机的地址转发表A F T中，成为与本交换机相连的交换机、网桥或其他网络设备的物理地址，交换机的工作原理就是将 A F T表中MA C地址作为目的地址来作出转发帧或过滤帧的决定的.图3 表示运行 S T P协议后的网络拓扑图，主要包括交换机一交换机、交换机一H u b 连接关系.定理

15、1 在同一子网内，交换机端口S,;与S,直连，当 且仅当A,n A,=0 且A,U A,=M，其中，M为子网内 所有设备的物理地址集合1 8 1 实际中，条件A ij UA,=M很难得到满足.因为算法只在一台主机上运行，可以通过p i n g 每个子网内交换机使各交换机的下行端口完整，但上行端口很难达到完整.如:用主机 H o s t 上的拓扑发现程序逐一p i n g 交换机，根据交换机工作原理，交换机端口会记下数据帧的源 MA C地址，当P i n g 完成后，A 1 2=S 2 9 S 4 f S 5 f S 6 ,A 1 3=l S 3,S,，S 8 ,A Z:二 S 4 P S 5，

16、S 6 f A 4 3=S 6 ，A 4 2=(S 5)，A 3 2=(S 7 f S 8 1.由此可见，通过 P i n g 操作后，交换机的下行端口 都达到了完整。但在P i n g的过程中，只能保证每个交换机的下行端口记住了 H的MA C地址，因而不能保证上行端口的完整性.因此，不宜直接运用定理 1 发现交换机的连接.M P 请求路径M P 应答路径交换机H u b 运行算法的主机图3 运行 S T P协议的生成树 定义1 S。表示生成树中 第i 台交换机的第i 个端口，A。表示A F T中 对应S，端口 所学习到的M A C 地址，即端口S。接收的数据帧的源M A C 地址的集合.如果

17、一台交换机的地址转发表包含了所有其他交换机的MA C地址，则称此交换机的地址转发表是完整的.定义2 标志结点:当算法运行的主机在待处理子网中时，将此主机命名为标志结点;若不在，则将目 标子网中能转发算法运行的主机发出的数据包的 路由器结点定为标志结点.图3 中H o s t 为运行算法的主机，则 H o s t 为标志节点.定义3 上行端口、下行端口:如果交换机的某个端口对应的地址转发表中出现标志结点的MA C地址，则把这个交换机端口称为上行端口;如果交换机的 某个端口 对应的地址转发表中 不出现标志结点的MA C地址，则称为下行端口.3 网络拓扑发现算法描述 通过分析生成树可以发现叶节点是一

18、类特殊的节点，如果从叶节点开始分析拓扑关系，则发现的过程会变得方便、快捷.如图3 所示，可以确定 S s 为叶节点，因为交换机S。仅有上行端口 所对应的地址转发表中包含本子网内其他交换机的MA C地址，其余的下行端口只能和主机或者路由器直接相连，由 S 4 2=1 S 6 分析出S。的上行端口和S 4:直接相连，然后剪掉叶节点 S 6，继续确定下一对交换机的连接关系.依此类推，可以逐步发现整棵树的连接关系 9 .3.1 基本拓扑发现算法 拓扑发现算法 N T D描述如下:步骤1:获取子网内活动的网络元素，并根据相应的i p F o r w a r d i n g 及s y s S e r v

19、i c e s 的值判断出子网内所有的交换机，并保存至交换机队列s w i t c h L i s t 中;步骤 2:获取 s w i t c h L i s t 中每个交换机的A F T表，并确定每个交换机的上行端口号;万方数据第4 卷第4 期邓泽林，等:基于S N MP协议的网络拓扑发现算法 步骤3:若 s w i t c h L i s t 争，则转步骤 4;否则，转步骤 5;步骤 4:查找 s w i t c h L i s t中每个交换机的A F T表，找出 A 二1(j笋S 的上行端口，I A i;表示A。中表项的个数)的交换机端口，如A。二 S k)，则确定S;为当前树的叶节点，

20、S。和S km(m为S*的上行端口 号)直接相连，将连接信息放人连接队列 c o n n e c t i o n L i s t，从所有交换机的A F T中删除 S k，并从 s w i t c h L i s t 中删除 S k，转步骤 3;步骤 5:根据得到的连接队列 c o n n e c t i o n L i s t绘出拓扑图，退出程序.由算法描述可知，拓扑发现过程是通过不断剪切生成树的叶节点，优先确定叶节点的连接关系，通过有限步循环来完成的.如果子网内所有的连接都是以可网管的交换机作为节点，则用此算法能够发现整个子网.3.2 网络哑节点的发现 由于可网管的设备比较昂贵，通常在组网时

21、会使用一些不可网管的设备，如:H u b、不可网管的交换机等.这些设备便宜但不能运行S N MP协议，没有MI B表，因此发现算法无法感知这类设备的存在，这类设备被称为“哑”节点.哑节点的存在必然导致 N T D算法无法正确的执行.如图3 所示，S,通过一个H u b 连接S:和S 8 f由于 H u b 是哑节点，因而在 A F T中会出现和实际情况矛盾的情形(如图4 所示).图5 哑节点发现图 通过分析和实际情况不一致的A F T表，可以推知哑节点的存在，这样就可以比较准确地发现网络拓扑结构.3.3 拓扑发现改进算法 通过结合N T D和哑节点的发现算法，可以得出改进的拓扑发现算法E N

22、T D;步骤1:获取子网内活动的网络元素，并根据相应的i p F o r w a r d i n g 及s y s S e r v i c e 的值判断出所有的交换机并存于交换机队列s w i t c h L i s t 中;步骤 2:获取 s w i t c h L i s t中每个交换机的A F T表并确定每个交换机的上行端口号;步骤 3:若 s w i t c h L i s t:A$，则转步骤 4;否则，转步骤 5;步骤 4:查找 s w i t c h L i s t中每个交换机的A F T表，找出m i n(I A y I)(j 笋S 的上行端口，I A!表示A。中表项的个数)的交

23、换机端口.如果A;=(5 k)，则确定S*为当前树的叶节点，S和S km(m为S*的上行端口 号)直接相连，将连接信息放人连接队列c o n n e c t i o n L i s t，并从s w i t c h L i s t中删除S k，从所有交换机的A F T中删除S k;如果 A;=(S k i I S k 2 I f S k n f，则用 H u b将 S k i rS k 2 I.I S 相连，将连接信息放人连接队列c o n n e c t i o n L i s t，从所有交换机的A F T中删除S k i,S k 2 I *t S 1.，并从 s w i t c h L i

24、s t中删除 S k i.S k 2 1*rS,.转步骤 3;步骤5:根据得到的连接队列c o n n e c t i o n L i s t绘出拓扑图，退出程序.图4 存在 Hu b的情形图4 测试结果 对应图 4的 A F T中的信息为 A 3 2=(S 7 fS 8)，根据A F T中数据可知，叶节点 S，和 S:直接连在S,的2 号端口上，这与一个端口只连一台交换机的实际情况矛盾.对于这种情况，可以推知S,S:与一个 H u b 直接相连，然后通过H u b 与S,相连(如图5 所示).应用E N T D算法测试一个真实网络，该网络由思科交换机、华为交换机以及 H u b等设备组成，得

25、到拓扑图6.整个发现过程耗时9.5 s.从图6可以看出，该算法成功地发现了 H u b 设备(以圆形标出).万方数据7 2长 沙 理 工 大 学 学报(自然 科 学 版)2 0 0 7 年 1 2月图6 自动发现网络拓扑图5 结论 本算法致力于第2 层的单子网网络拓扑发现算法.从实际测试的结果看，该算法是一个快捷、准确的拓扑发现算法.作为一个完整的网络拓扑发现算法，还应该要考虑网络中存在多子网 l o 和V L A N的情形，这些因素的介人使网络扑发现变为一个越来越复杂的问题，这些问题都是后续工作的主要内容.参考文献 1 刘海华，倪少权，王萍萍.一种基于 S N MP的网络层 拓扑发现算法 J

26、 .计算机安全，2 0 0 7,(9):5 2-5 3.2 尤澜涛，朱巧明，李培峰一 种快速网络拓扑发现算 法的设计与实现 J .计算机应用与软件，2 0 0 7,2 4 (9):1 8 1-1 8 3.3 刘玉华，余胜生，周敬利，等.基于A F T的链路层自 动拓扑发现算法 J .小型微型计算机系统，2 0 0 4,2 5 (1 2):2 2 1 1-2 2 1 4.4 蔡伟鸿，舒兆港，刘震.基于S N MP协议的以太网 拓扑自动发现算法研究 J .计算机工程与应用，2 0 0 5，(1 4):1 5 6-1 6 0.5 B r e i t b a r t,M i n o s G a r o

27、 f a l a k is,B e n J a i,e t a l.T o p o l o g y d i s c o v e r y i n h e t e r o g e r n e o u s I P n e t w o r k s:t h e N e t I n-v e r t o r y s y s t e m J .I E E E/A C M t r a n s a c t i o n s o n n e t-w o r k i n g,2 0 0 4,1 2(3):4 0 1-4 1 4.6 B r u c e L o w e k a m p,D a v i d R O H a

28、l l a r o n,T h o m a s G r o s s.T o p o l o g y d i s c o v e r y f o r l a r g e E t h e r n e t n e t-w o r k s J .I n p r o c e e d i n g o f A C M S I G C O MM,2 0 0 1，(8):2 3 7-2 4 8.7 Wi l l i a m S t a l l i n g s.S N MP,S N MP v 2，S N MP v 3，a n d R MO N 1 a n d 2 M.B o s t o n:A d d i s o

29、 n-We s l e y L o n g-m a n P u b l i s h i n g C O,I n c,1 9 9 9.8 D e c k e r E,L a n g i l l e P,e t a l.D e f i n i t i o n s o f m a n a g e d o b j e c t s f o r b r i d g e s S .I n t e r n e t R F C-1 4 9 3，J u l y 1 9 9 3.9 Z h e n g H a i,Z h a n g G u o-g i n g.A n a l g o r i t h m f o r

30、 p h y s i c a l n e t w o r k t o p o l o g y d i s c o v e r y J .J o u r a l o f C o m p u t e r R e s e a r c h a n d D e v e l o p m e n t,2 0 0 2,3 9(3):2 6 4-2 6 8.1 0 B e j e r a n o Y,B r e i t b a r t Y,G a r o f a l a k i s M,e t a l.P h y s-i e a l l o p o l o g y d i s c o v e r y f o r l a r g e mu l t i-s u b e n t n e t-w o r k s A .P r o c o f t h e I E E E I N F O C O M 2 0 0 3 C .Ne w Yo r k.I E E E P r e s s,2 0 0 3.3 4 2-3 5 2.万方数据