（通信与信息系统专业论文）网络拓扑发现算法研究.pdf

摘要 随着网络技术的飞速发展和广泛应用，网络规模越来越大，网络 结构也l d 趋复杂，网络管理已成为影响网络系统正常运行的关键因 素。网络拓扑自动发现作为网管系统的基本要求和重要功能，它可以 反映网络中的设备布局，可以提供可视化的管理界面，对保障网络系 统正常、安全运行具有重要意义。 本文联系甘肃省xxx 厅信息处计算机网管系统课题，对网络管 理中的拓扑发现算法进行了较深入的探讨。在分析现有拓扑发现算法 的基础上，提出了一种有效的针对管理域内网络自动拓扑发现算法。 本算法使用s n m p 协议采集管理域内各种网络设备m i b 库中保存的信 息，利用本文提出的设备连接判定规则确定路由器、交换机和主机之 间的连接关系，从而构造网络第二层和第三层的拓扑结构图。 实验结果表明，大部分支持网管的设备中包含了算法所要求的数 据。在与以前的自动拓扑发现算法比较后，本算法具有稳定性好、运 算简单、获得的网络拓扑构图准确且可操作性强的优点。使用本文中 的思想可以快速、细致和准确地发现全省xxx 机关计算机网络的拓 扑结构，为网络管理提供一个可靠的平台。 关键词：网络管理，拓扑发现，简单刚络管理协议 a b s t r a c t a i o n gw it ht h er a p i dd e v e l o p m e n ta n de x t e n s i v ea p p li c a t i o no ft h e n e t w o r kt e c h n o l o g y ，t h es c a lea n dc o m p l e x it yo fn e t w o r kb e c o m el a r g e r n e t w o r km a n a g e m e n th a sb e c o m et h ek e yf a c t o rt h a ta f f e c t st h en o r m a l m o v e m e n ti nn e t w o r k t h ea 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 ，w h i c h m i r r o rt h ed i s t r i b u t i o no ft h en e t w o r kf a c i l i t i e sa n de n a b l ev i s i b l e m a n a g e m e n ti n t e r f a e e ，a r ea m o n gt h ee s s e n c er e q u i r e m e n t sa n di m p o r t a n t f u n c t i o n st on e t w o r km a n a g e m e n ta n dn o r m a lm o v e m e n t s u p p o r t e db yxx o fg a n s up r o v i n c e ，t h i sp a p e rp r e s e n tat h o r o u g h a n a l y z i n go nan e wt o p o l o g yd i s c o v e r ya l g o r i t h m b a s e do nt h ea n a l y s i s o 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 ，w ep u tf o r w a r d anewt o p o i 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 su s i n g s t a n d a r ds n m pm i b s o u ra l g o r it h mm a k e suseo 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 e h e sa n dh o s t s u n d e rt h es it u a t i o nt h a td o n o tg e n e r a t et 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 e i n t e r c o n n e c t i o nb e t w e e nd i f e e t l yc 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 e t h ei p 一1 e v e la n dl i n k l e v e it o p o l o g ym a p w eh a v e t e s t e doura 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 d t h er e s u l t ，i th a sa 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 t n e t w o r k su s i n gav a t i e t yo fh 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 t h enew t o p o l o g yd i s c o v e r ya l g o r i t h mp r o v e dt ob ear e a s o n a b l ec h o i c et or e a c h ar a p i da n da c c u r a t ed e t e c t i o ni nt h ei n t e r n a ln e t w o r ko fx o fo u r p r o v i n c e ，t h u st op r o v i d ead e p e n d a b l et e r r a c ef o rn e t w o r km a n a g e m e n t 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 i o g yd i s c o v o f y ，s n m p 原创性声明 本人郑重声明：本人所呈交的学位论文，是在导师的指导下独立 进行研究所取得的成果。学位论文中凡引用他人已经发表或未发表的 成果、数据、观点等，均已明确注明出处。除文中已经注明引用的内 容外，不包含任何其他个人或集体已经发表或撰写过的科研成果。对 本文的研究成果做出重要贡献的个人和集体，均已在文中以明确方式 标明。 本声明的法律责任由本人承担。 ”论文作者签名： 日期： 关于学位论文使用授权的声明 本人在导师指导下所完成的论文及相关的职务作品，知识产权归 属兰州大学。本人完全厂解兰州大学有关保存、使用学位论文的规定， 同意学校保存或向国家有关部门或机构送交论文的纸质版和电子版， 允许论文被查阅和借阅；本人授权兰州大学可以将本学位论文的全部 或部分内容编入有关数据库进行检索，可以采用任何复制手段保存和 汇编本学位论文。本人离校后发表、使用学位论文或与该论文直接相 关的学术论文或成果时，第一署名单位仍然为兰州大学。 保密论文在解密后应遵守此规定。 论文作者签名：导师签名：日期： 嘲络拓扑发现算法研究 1 1 课题的提出 第一章绪论 在网络规模不断扩大的今天，伴随着复杂性的持续增加，网络的异构性也日 趋提高，网络中众多不同的网络操作系统、不同厂家的网络通信设备、多种多样 的网络服务软件和水平相差甚大的使用者与潜在的攻击者，使得用户对网络性能 的要求越来越高，网络管理也就成了网络系统正常运行的关键。 网络拓扑发现作为网络管理的基础，它是o s i 网络管理5 大基本功能域中配 置管理的功能之一，它为管理中心提供整个网络系统各子网间及子网内部网络设 备间的互连关系的信息。网络拓扑可以划分为逻辑拓扑和物理拓扑。逻辑拓扑是 指网络中从一个节点到另一个节点问传递信息的方法，与网络的外形无关，路由 器与子网的互连以及v l a n 的划分都属于逻辑拓扑范畴。物理拓扑是指网络节点 的地理分布与连接的几何构形，一个网络的物理拓扑可对应多个不同抽象级别的 逻辑拓扑。 甘肃省厅信息处为了研究在全省机关范围内，集中监控计算机 网络，实时掌握网络运行状态，检测网络性能可能出现的瓶颈，并进行自动处理 或告警显示，提出了建设与现行网络架构相适应的计算机网管系统的课题。本人 参与了整个系统的设计工作，并参与制订了系统的设计方案。本人在课题中的工 作重点是管理域内逻辑拓扑发现和物理拓扑发现的算法设计，本论文将就这一课 题进行研究和介绍。 i 2 需要明确的问题 网络拓扑发现涉及到的问题比较多，但是总的来说，主要有四方面的问题需 要明确。 第一，确定拓扑发现的规模。计算机网络按照分布距离可以划分为局域网、 城域网、广域网等等。不同规模的网络，其互连设备、所需拓扑信息的详略、搜 索”销的大小、发现速度的快慢等都会有所彳i 矧。因此，【嘲络的拓扑发珧心当针 网络拓扑发现算法研究 对不同规模的网络，采用不同的协议工具设计算法。本文仅讨论网络管理域内的 自动拓扑发现方法。 第二，确定拓扑发现针对网络哪一层以及采用什么网络协议。只有确定了拓 扑发现针对的网络层次和协议，才能明确到底哪些信息需要被采集，才能使这项 技术具有比较好的适应性。随着i n t e r n e t 的普及，绝大多数的网络都采用t c p i p 协议，大多数网络拓扑发现将以t c p i p 网络的i p 层为拓扑发现的首选位置。目 前，简单网络管理协议( 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 ) 己经成为 事实上的工业标准，使用s n m p 的算法可实现性较强，所以传统的算法基本上都 是针对管理域内的i p 层发现网络的逻辑拓扑。但是，在异构网络中，二层设备( 如 交换机、网桥和h u b ) 越来越多的分布在i p 网络中形成微子网段，以提供更多的 带宽。因此，越来越多的拓扑信息对于传统的逻辑拓扑发现是不可见的。为了发 现网络更加详细的拓扑结构( 如网络的物理拓扑) ，网络的多层自动拓扑发现是必 不可少的，本文将分别讨论管理域内逻辑拓扑和物理拓扑的自动发现方法。 第三，就网络拓扑信息的采集而言，应当确定是采用被动监测技术还是主动 探测技术”1 。 主动探测技术( a c t i v e l yp r o b i n gt e c h n i q u e s ) 是通过网管工作站主动向所 有管理网络发送探测包，并采集返回的信息，进行分析最终形成网络拓扑。这种 技术的优点是由于主动探测过程可以控制，获得网络拓扑图的时间开销可能是最 小，而且能够比较快地形成整个网络的拓扑，但是会给网络增加额外的流量。 被动监测技术( 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 ) 是通过在所有被观测的网 络中都加入一个探测器，由它来采集信息，并发送到网管工作站形成拓扑。这种 技术最大的优点是除了其本身向网管工作站递交拓扑信息以外，不产生额外的流 量，不会给网络带来额外的负担。但缺点是由于通过各个探测器被动地监测网络 上的分组交换信息，所以需要花费较长的时间才能收集到足够的信息来形成最后 的网络拓扑，而且由于要将探测器安装到所有涉及的网络中，这对于一个大的网 络来说是不太实际的。出于这方面考虑，本文所讨论的自动拓扑发现方法采用主 动探测技术。 第四，就拓扑信息的收集而言，应当确定采用何种工具收集信息( 基本工具 的详细介绍见第二市) 。目前，信息收集的方式大致可以分为两种：一种采用简单 第2 贝共6 2 且 阗络拓扑发现算法研究 网络管理协议s n m p 柬收集网络的拓扑信息，这种方式比较高效，但并不是所有 的网络设备都支持s n m p 协议；另一种信息收集方式采用比较通用的网络协议， 如基于网际控制报文协议( i n t e r n e c o n t r o lm e s s a g ep r o t o c o l ，i c m p ) 的p i n g 、 t r a c e r o u t e 等。它们建立于i p 层的基础之上，被所有的i p 网络和设备所支持。 由于当今网络情况比较复杂，本文讨论的管理域内逻辑拓扑发现算法将这两种方 式结合使用。该算法在具有更大适用性的同时，也可以发现更多的网络设备。 1 3 国内外研究现状 国外早期的i p 网络自动拓扑发现工作。“”均是利用s n m p 等协议发现管理域 内的逻辑拓扑，即描述路由器与路由器，路由器与子网以及子网内部主机相互连 接关系的i p 层拓扑。另外，许多商业网络管理系统，如惠普公司的o p e n v i e w 5 3 ， i b m 公司的t i v o l i “、达特茅斯的i n t e r m a p p e r ”1 等，其拓扑发现也都是采用基 于s n m p 协议的逻辑自动拓扑发现算法。 近期，国外在物理拓扑自动发现9 1 的研究工作已经开展了一些。i n t e r n e t 工程特别小组( i n t e r n e te n g i n e e r i n gt a s kf o r c e ，i e t f ) 在意识到物理拓扑发 现的重要性后，指定了s n m pm 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 ) 库“”，但是 并没有定义任何通用的协议和算法用于获得物理拓扑信息。一些硬件制造商，如 c i s c o 公司，开发了用于发现物理拓扑的私有协议c d p ( c i s c od i s c o v e r y p r o t o c 0 1 ) “”以及相关工具，但是c d p 只适用于自动发现c i s c o 公司的网络设备， 不具有通用性。p e r e g r i n e 公司的i n f r a t o o l s 软件“2 1 和m i c r o m u s e 公司的 n e t c o o l “3 1 据称可以支持物理拓扑的自动发现，但这些公司的独有技术是我们不 可得知的。 在国内，许多高校都有网络自动拓扑发现方面的研究，主要有华中科技大学 m m 、上海交通大学m 坩“、西安交通大学m 、中国科技大学等瑚1 。但是， 这些研究主要集中于发现i p 网络管理域内的逻辑拓扑。文献”虽然对虚网( 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 库，通用性显得不够。郑海1 等人的物理拓扑发现算法需要通过在网络中产生额外流量来保证网络中每一个 节点地址转发表的完整。因此t 叮以说，国内在网络物理拓扑发现方曲的研究还刚 第3 页共6 2 血 删络拓扑发现算法研究 刚起步。 1 4 本文的主要工作 本论文主要是基于甘肃省厅信息处计算机网管系统的设计及应用，所 做的 要工作包括以下几个方面： 1 _ 在分析前人提出的多种逻辑拓扑发现算法的基础上，提出了基rs n m p 和 i c i p 的管理域内逻辑拓扑发现算法。 2 吐前的网络物理拓扑发现算法都是基于m a c 地址转发表的，本文提出了一 种利用网桥生成树的算法，这个算法的主要特点在于不需要任何的准备工作，只 需获取标准m i b 中生成树协议组中的数据，做简单的查找比较操作就可阻准确的 推导出网络链路层设备之间的连接关系。算法简单有效，有更好的可操作性。 3 在分析有关b l i b 文档( r f c ) 的基础上，实验验证了本文提出的逻辑拓扑和 物理拓扑发现算法的正确性。 1 5 文章的组织 全文的章节安排如下： 第一章说明了课题的提出背景、拓扑发现需要明确的问题以及国内外研究现 状。然后总结了本论文所做的主要工作。 第二章介绍了与网络拓扑发现相关的知识和技术，包括网络的拓扑结构、网 络拓扑节点以及在网络拓扑发现中采用的基本协议和采集工具。 第三章介绍了一种利用s n m p 和i c m p 发现网络逻辑拓扑的算法，讨论了算法 的实现细节以及在整个拓扑发现过程中的关键问题。 第四章重点研究了利用s n m p 协议获耿m a c 地址转发表和生成树表构建嘲络 物理拓扑的算法，并描述了算法的细节。 第五章对实际网络设备m i b 值进行了采集和分机，验证了本文提出的拓扑发 现算法的正确性和可行性。 最后对全文进行了总结，概括了本文的主要工作及成果，并指出令后有待于 进一步丌展的上作。 进一步开展的工作。 | 埘络拓扑发现算法肼究 第二章网络拓扑发现相关知识和技术 2 1 网络拓扑结构 拓扑学是数学的一个分支，研究几何图形在连续改变形状时还能保留不变的 一些特性。它只考虑物体之间的位置关系，不考虑它们的大小及距离。一个基本 的网络可以被看作由网络节点和链路组成。 图2 1 ( a ) 描述了网络端用户所感觉到的网络结构视图，大部分应用程序也 是保存这种网络视图。图2 1 ( b ) 描述了所有的机器是通过路由器连接在网络上 的。这也是网络中最容易探测到的设备。一般我们能用t r a c e r o u t e 程序来探测 主机之间的路由器。图2 1 ( c ) 被用来说明网络第二层( 链路层) 的透明性。这一 层包括了连接主机构成以太网的主要网络部件( 设备) 网桥，以太网是目前使用最 广泛的局域网架构，也是网络中最难获取其网络拓扑的一层。这种困难来源于网 桥协议的透明性。采用网桥构造局域网和转发数据包所使用的算法不需要知道网 络全局的信息，也不需要主机直接告诉网桥，也就是说网桥不需要知道主机的存 在。因此，网桥的这种透明性是第二层网络设备非常有效的一个特点，但是它却 使得获得第二层网络拓扑变得很困难了。随着网络技术的发展，现在第二层网络 设备中最常见的是交换机( 它可以认为是有更多端口的网桥) 。在本文中术语“网 桥”和“交换机”是同一个意思。 刚络把扑笈现算法研究 圈2 1 ：不同层次的网络视图。( a ) 用户所感觉到的网络结构视图：( b ) i p 网络层的网络 视图。每个主机和路由器明确地沿着路径向相邻设备转发数据包；( c ) 以太网交换机的网络 视图。每个交换机学习到主机和路由器的连接位置，然后透明地向目的设备转发数据帧。 局域网常有的拓扑结构有四种：总线形、环形、星形和混合形( 通常是星形与 总线形或者星型与环形相混合) 。不同结构的网络采用不同的协议：总线形结构的 局域网采用以太网协议，而令牌环和f d d i ( f i b e rd i s t r i b u t e dd a t ai n t e r f a c e ) 是环形结构。集线器连接的局域网一般是星形结构。 广域网( w a n ) 与局域网相比，组成网络在地理位置上通常相隔较远，如 i n t e r n e t 就是全球范围的互联网络。广域网的一般拓扑结构是网状或者树形结 构。 2 2 网络拓扑节点 网络拓扑节点是指网络中的互连设备。它可以是链路两端的设备，如集线器 ( h u b ) 、路由器( r o u t e r ) 等，也可以是连接网络的设备，如连接局域网的网桥 ( b r i d g e ) 、连接自治网络的网关( g a t e w a y ) 等。 集线器是用来构建局域网的网络设备。 交换机( s w i t c h ) 工作在o s i 参考模型的物理层。它只将从个端口进来的报 文分组传递到正确的端口输出，不对输入数掘的格式做任何操作。 网桥可以被看作工作在数据链路层的智能分组交换机，用柬连接局域网。它 除了具有交换机的功能以外，还有过滤分组的功能。智能网桥还有自学习的功能。 第6 贸甚6 2 负 州络拓扑发现算法研究 它维护一张地址转发表，记录分组的源地址、目的地址、接收端口和转发端口等 信息。随着时间的增长，它获得某个分组应当被转发到哪个特定端口的知识。如 果这张表中没有存储某个分组的目的地址及转发端口，网桥将其扩散到所有的端 口，一旦发现某个目标节点对该分组做出了回应，它立即将此新发现的转发项记 录在地址转发表中。那些长期没有被使用的转发项将会被定期清除掉。 桥接网络( b r i d g e dn e t w o r k ) 使用两种不同的路由算法：用于连接以太网的 生成树( s p a n n i n gt r e e ) 协议和用于连接令牌环网的源路由( s o u r c e r o u t i n g ) 算 法。它们分别对应两种不同的网桥和拓扑结构：透明网桥连接的树形结构和源路 由网桥连接的网状结构。 由于备用连接的存在，网络的两个节点之间可能存在多条路径，从而在物理 拓扑结构上产生环。环的产生可能导致报文分组的重复发送。生成树协议不启用 那些造成环的连接，从而维持整个拓扑的树状结构。透明网桥维护和存储一张目 的地址转发端口相对应的表。当收到一个分组，透明网桥只将其发送到这个分 组的目的地址所对应的转发端口。因此透明网桥不知道任何关于目的局域网的信 息，它只知道负责这个目的地址的转发端口和对应的相邻网络节点。同样的，只 有相邻节点知道其存在，对于其它网桥和局域网来说它是不可见的。 在源路由网桥连接的网络中，首先，为了获得到目的节点的路由信息，源节 点将广播分组扩散到整个网络，从而源节点知道通往目的节点的整条路径。它将 路径信息加入到传送的分组中，由分组自身携带路由信息。因此，分组的选路无 需任何中间节点的参与。 两种网桥比较起来，透明网桥更加健壮和可靠，源路由网桥速度更快。但是 源路由网桥连接的网络中，一旦网络结构发生了变化，整个网络的地址转发表都 需要被重新广播和发现一遍，因而处理起来比透明网桥复杂。 路由器和网关是工作在网络层，执行路由功能的设备，主要用于构建主干网。 路由器除了有交换机和网桥的基本功能以外，还有路由功能，可以将分组朝着其 路由方向输出到恰当的端口。路由器存储和维护一张定期更新的路由表，存放 个数据报由源节点到目的节点的可能路由( 既包括完整路由，也包括路由的下 跳地址) 。单点传送( u n i c a s t ) 方式下，它将分组转发到通往目的地址的一个端口： 广播( b r o a d c a s t ) 或多播( m u l t ic a s t ) 的方式下转发到多个端口。另外，路t l 器使 第7 虹共6 2 贝 网络拓扑发现算法研究 用广播机制的地址解析协议a r p ( a d d r e s sr e s o l u t i o np r o t o c 0 1 ) 确定通往目的 地址的本地端口。路由器连接的网络允许拓扑结构中出现环，因而这种网络在路 由器或其连接出现故障时，具有一定的均衡流量和白恢复功能。不是所有的网络 都采用相同的协议，网关除有路由功能以外，还可以将一种协议格式转换为另一 种协议格式，因此能够被用来连接完全自治的两个网络( 可以有不同的路由算法、 协议、管理策略等等) 。 2 3 网络拓扑发现基本协议 在t c p i p 最初发展的阶段，还很少考虑到网络管理的问题。直到2 0 世纪 7 0 年代后期，仍然没有网络管理协议。当时的一个有效管理工具是i n t e r n e t 控 制报文协议i c m p ”。i c m p 提供了从一个网络设备( 如路由器或主机) 到另一个网 络设备传输控制报文的手段。i c m p 在所有支持i p 协议的设备上都是可行的。到 8 0 年代初期，i n t e r n e t 的不断发展更促使人们进一步意识到网络管理的重要性。 1 9 9 0 年5 月，i e t f 在r f c l l 5 7 中正式公布了s n m p ( 现在称之为s n m p v l ) ，由 于s n m p 的普遍使用，针对s n m p 的开发和研究成果不断出现，s n m p 已经成为了 网络管理领域中事实上的工业标准“。 目前，在自动网络拓扑发现算法研究和产品开发中，绝大多数都是基于上述 两种协议来收集网络中的拓扑信息，然后加以分析处理，构造网络拓扑图以及对 网络结构的更进一步的研究。 2 3 1 网际控制报文协议 在t c p 1 p 协议族中，i p 提供了不可靠的和无连接的数据报交付。i p 协议是 一种尽力服务( b e s t e f f o r t ) 的服务方式。当初这样设计是为了有效地利用网络 资源。但是，它有两个缺点：缺少差错控制和缺少辅助机制( 为主机和管理查询的 机制) 。网际控制报文协议i c m p 就是为了补偿上述两个缺点而设计的，它是i p 的一部分，并且在每个i p 实现中都必须包含它。 最初的设计是为了允讷：路由器向主机报告交付出错的原因，但是 c m p 并没 有限制仅在路由器上使用。尽管限制了某些i c m p 报文的使用，但是任何一台机 器一t 以向任何其他机器发送i c m p 报文。因此， 机可以用i c m p 与路器或蝎一 第8 负共6 261 嘲络拓扑发现算法研究 台主机通信。允许主机使用i c m p 的主要优点是：它为所有控制报文和信息报文提 供了统一的机制。 i c m p 报文的类型很多，总体上可分为2 种类型，即i c m p 差错报文和i c m p 询问报文。在网络拓扑发现中，我们将用到下列三种报文格式”2 1 ： ( 1 ) 回送请求和应答报文格式 表2 1 ：i c m p 回送请求或回送应答 o81 63 l 类型( 8 或o )|代码( o )校验和 标识符序号 可选数据 可选数据( o p t i o n a ld a t a ) 字段是一个可变长度字段，它包含要返回给发送 者的数据。回送应答通常返回与所收到的请求完全相同的数据。标识符 ( i d e n t i f i e r ) 字段和序号( s e q u e n c en u m b e r ) 字段由发送者用来匹配应答和请 求。类型( t y p e ) 字段的值指明报文是一个请求( 8 ) 还是一个应答( o ) 。 ( 2 ) 目的站不可达报告 当路由器无法转发或交付i p 数据报时，用如下图所示的格式向最初源站发 回一个目的站不可达报文。 表2 2 ：i c m p 目的站不可达报文格式 o81 63 l 类型( 3 ) i 代码( o 一1 2 ) l 校验和 未用( 必须为0 ) 互联网首部+ 数据报的前6 4 比特 目的站不可达报文中的代码( c o d e ) 字段包含了进一步描述问题的一个整数。 可能的值为： 表2 3 ：目的地不可达报文中代码取值 码值含义 0网络不可达 l主机不可达 j 2 协议不可达 3 端几不可达 第9 贞共6 2 贝 酬络拓扑发现算法研究 4需要分片并且d f 置位 5源路由失败 6目的网络未知 7目的主机未知 8 源主机被隔离 9 “于管理目的禁止了与目的网络的通信 1 0出丁管理目的禁止了与目的主机的通信 l i对所请求的服务类型，网络不可达 1 2对所请求的服务类型，主机不可达 ( 3 ) 地址掩码请求应答报文格式 为了得到网络的子网掩码，可以向路由器发送一个地址掩码请求( a d d r e s s m a s kr e q u e s t ) 报文并接收地址掩码应答( a d d r e s sm a s kr e p l y ) 报文。表2 4 表 示了地址掩码请求应答报文的格式。地址掩码请求应答报文中的类型字段指明 该报文是一个请求( 17 ) 还是一个应答( 1 8 ) 。应答在地址掩码字段( a d d r e s sm a s k ) 中包含了子网地址掩码。标识符( i d e n t i f i e r ) 和序号( s e q u e n c en u m b e r ) 字段使 主机可以把应答和请求联系起来。 表2 4 ：i c m p 地址掩码请求应答报文格式。 o81 63 l 类型( 1 7 或1 8 )代码( o 一1 )校验和 标识符序号 地址掩码 2 3 2 简单网络管理协议 简单网络管理协议s n m p 是目前t c p i p 网络中应用最为广泛的网络管理协 议。1 9 9 0 年i e t f 在r f c11 5 7 中正式公布了s n m p 的第一个版本s n m p v l 。s n m p 在9 0 年代初得到了迅猛发展，同时也暴露出了明显的不足，如，难以实现大量 的数据传输，缺少身份验证( a u t h e n t i c a t i o n ) 和加密( p r i v a c y ) 机制。冈此，1 9 9 3 年4 月又发布了s n m p v 2 ( r f c1 4 4 1 ) 。 但是，s n m p v 2 并没有完仝实现预期的目标，尤其是安全性能没有得到提高， 如：身份验证( 如用户衲始接入时的身份验证、信息完整性的分析、重复操作的预 防) 、加密、授权和访问控制、适当的远程安全配置和管理能力等都没有文观。 第1 0 页共6 2 姐 6 9 络拓扑发脱算法研究 1 9 9 6 年发布的s n m p v 2 c 是s n m p v 2 的修改版本，功能增强了，但是安全性能仍没 有得到改善，继续使用s n m p v l 的基于共同体( c o m m u n i t y ) 的一种明文密钥的身份 验证方式。i e t fs n m p v 3 工作组于1 9 9 8 年元月提出了互联网建议r f c 2 2 7 卜2 2 7 5 ， 正式形成s n m p v 3 。这一系列文件定义了包含s n m p v l 、$ n m p v 2 所有功能在内的体 系框架和包含验证服务和加密服务在内的全新的安全机制，同时还规定了一套专 门的网络安全和访问控制规则。可以说，s n m p v 3 是在s n m p v 2 基础之上增加了安 全和管理机制。 由于s n m p 的普遍使用，使得针对s n m p 的进一步开发不断加强。i e t f 于1 9 9 1 年1 1 月公布了远程网络监视协议( r m o n ) 来解决s n m p 在日益扩大的分布式网络 中所面临的局限性。r m o n 的目的在于使s n m p 更为有效、更为积极主动地监控远 程设备，提高传送管理信息的有效性、减少管理站的负担、满足网络管理员监控 网段性能的要求。 作为i e t f 定义的管理信息库，r m o n 是对s n m p 标准的扩展，它定义了标准 功能以及在基于s n t l p 管理站和远程监控者之间的接口，主要实现对一个网段乃 至整个网络的流量数据的监视功能。r m o n 的一个重要的优点还在于它与现存的 s n m p 框架相兼容，不需要对该协议进行任何修改。 在r m o n 基础上产生的r m o ni i 标准能将网管员对网络的监控层次提高到网络 协议栈的应用层。r m o n 在网络中查找物理故障，r m o ni i 进行的则是更高层次的 观察，它监控实际的网络使用模式。r m o ni i 没有取代r m o n ，而是它的补充技术。 r m o ni i 在r m o n 标准基础上提供一种新层次的诊断和监控功能。 s n m p 的网络管理模型有4 个组成部分1 ： 被管对象( m a n a g e do b j e c t s ) 管理站( m a n a g e m e n ts t a t io n ) 管理信息库( 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 ) 管理协议( m a n a g e m e n tp r o t o c 0 1 ) 图2 2 显示了上述四个部分的关系。 侧络拓扑发现算法研究 s n m p 管理站s n m p 代理告 图2 2 ：s n m p 网络管理模型( 注s n m p v l 版) 被管对象可以是主机、路由器、网桥和交换机等任何可以与外界交流状态信 息的硬件设备。网管代理( a g e n t ) 则是驻留在被管设备( 如路由器、交换机等) 上 的一个进程，负责接受、处理来自网管站的请求报文，然后将设备接口等特性管 理变量的数值形成响应报文，发送给管理站，并在一些紧急情况下，如接口状态 发生改变、呼叫成功等时候，通过发送陷阱( t r a p ) 报文主动通知管理站。 代理不断地收集统计数据，如所收到的字节数等，并把这些数据记录到一个 管理信息库m i b 中，管理站通过向代理的m i b 发出查询信号就可以得到这些信息， 这个过程就叫做轮询( p o l l i n g ) ，是s n m p 最基本的特点。网管站对网络设备发送 各种查询报文，并接收来自被管设备的响应及陷阱( t r a p ) 报文，将结果显示出来。 管理者既能从代理获得变量的值，也能设置代理中的变量。 网络的所有对象都存放在一个叫做管理信息库( m i r ) 的数据结构中。管理信 息库定义了一组被管对象的集合。每一个对象，代表了被管设备的某个特性的数 据变黾。在m i b 中，每个被管对象都有一个唯一的标识。这个标识的组成包括： 对象的类型、对象被访问的权限，对象的大小和范围。 网络拓扑发现算法研究 管理站和代理之间是通过s n m p 网络管理协议交互的，s n m p 管理者对m i b 中 的信息执行的操作如表2 5 所示。 表2 5 ：s n m p 管理者对m i b 中的信息执行的操作 操作说明 g e t r e q u e s t获取一个指定变量的值 g e t n e x t - r e q u e s t获取一个表中指定对象的f 一个对象的值 g e t b u 】k - r e q u e s t 获取一组指定的数据例如一个表中的多行数据 g e t r e s p o n s e对n m s 发送的g e t r e q u e s t ，g e t n e x t r e q u e s t ，s e t r e q u e s t 操作的同应 s e l - r e q u e s t设置一个指定变量的值 t r a p当一些事件发生后，代理向管理者主动发送消息 对于s n m p 协议，管理站和代理之间是以s n m p 报文的形式来交换信息的。每 一个报文包括一个s n m p 版本号，一个s n m pc o m m u n it y 和五种协议数据单元 ( p r o t o c o ld a t au n i t ，p d u ) 中的一种。表2 6 描述了s n m p 报文的结构。 表2 6 ：s n m p 报文的结构 v e r s i o nc o m m u n i t y l s t n 4 pp d o ( a ) s n m pm e s s a g e c o ) g e t r e q u e s t - p d u ，g e t n e x t r e q u e s t - p d u ，s e t r e q u e s t - p d u ( c ) r e s p o n s ep d u p d u 脚。| “p n 3 聊l _ a d 打 8 篓| ”鐾。m p 3 呷v a r i a b l e - b i n d i n g s ( e ) v a r i a b l e - b i n d i n g s 第13 负共6 2 贞 网络拓朴发现算法研究 表2 7 ：s n m p 消息字段 字段描述 v e r s l o ns n m p 版本 c o m m u n l t v共同体的名字用作s n l l p 认证消息的口令 r e q u e s t i d为每个请求赋予一个唯一的标识符 e r r o r s t a t u s n o e r r o r ( 0 ) ，t o o b i g ( 1 ) ，n o s u c h n a m e ( 2 ) ，b a d v a l u e ( 3 ) ，r e a d o n l y ( 4 ) ，g e n e r r ( 5 ) e r r o r 一1 n d e x当e r r o r s t a t u s 菲0 时，可以进一步提供信息指出哪个变量引起 的问题 v a r i a b l e b i n d i n g s 变量名及其对应值清单 e n t e r p r i s e生成t r a p 的对象的类型 a g e n t a d d r生成t r a p 的对象的地址 g e n e r l c - t r a p一般的t r a p 类型：c o l d s t a r t ( 0 ) ，w a r m s t a r t ( 1 ) ，l i n k d o w n ( 2 ) ， l i n k u p ( 3 ) ，u t h e n t i c a t i o n f a i l u r e ( 4 ) ，e g p n e i g h b o r l o s s ( 5 ) ， e n t e r p r i s e s p e c i f i c ( 6 ) s e c i f i c t r i a p特定的t r a p 代码 t i m e s t a m p网络实体从上次启动到本t r a p 生成所经历的时间 所有的s n m pp d u 都包括一个变量绑定( v a r i a b l e b i n d i n g s ) 的域。这个域由 一系列对象实例标识符和这些对象实例的值组成。其中的对象实例标识符就是 m i b 中定义的某个变量，其数据结构由s n m p 的管理信息结构( r f c1 1 5 5 ) ”具体 定义。s m i 采用了和d n s 中名字空间相类似的方式，是以树状的结构来表示管理 对象的名字。对象标识符有两种形式：名字形式和数字形式。例如m i b 对象 s y s d e s c r 具有如下的标识： 名字形式：i s o o r g d o d i n t e r n e t m g i n t m i b 一2 s y s t e m s y s d e s c r 数字形式：1 3 6 1 2 1 1 1 2 4 网络拓扑发现可采用的工具 网络拓扑发现可采用多种工具或协议，归纳起来有p i n g ，t r a c e r o u t e ，s n m p 和d n s 等，它们各具特点，但p i n g 和t r a c e r o u t e 应用范围最广，s n m p 最高效“1 。 1 d n s 一个管理域的域名服务器( d n s ) 维持该域内的每个域名到其i p 地址的映射。 大多数域名服务器通过“z o n et r a n s f e r ”命令返回该域内的所有映射。由此理 论卜d n s 的域转换町以发现域内的所有t 机和路由器，可以将其结果作为拓扑发 现算法的起始地址集。这种技术快速、准确、开销小，但是得到的映射1 j 能并不 网络拓扑发现算法研究 全，因为自的主机通过动态主机配置协议( d h c p ) 获得i p 地址，而且有些网络管 理员出于安全因素的考虑，关闭了d n s 域转换服务。 尽管有诸多缺点，d n s 在拓扑发现中还是很重要的，我们可以把d n s 返回的 信息作为其它算法的起点：我们还可以在不知道网络具体结构的情况下，使用不 同时间返回来的信息直接用来估算网络的增长速度。 2 a r p 地址解析协议( a r p ) 管理一张地址映射表，以动态更新的方式存放在c a c h e 里。这张表维护的是近期访问过的、与该设备直接相连的终端设备i p 地址与物 理地址的映射。拓扑发现并不关心这种映射关系，主要利用这张表取得与该设备 相连的终端设备i p 地址以及m a c 地址。 3 p i n g p i n g 命令是i p 网上最古老的一种工具，用来监测网络节点是否活着，或用 于监测到网络节点间的往返时延( r t t ) 。p i n g 命令使用的是网际控制报文协议 i c m p ，是i p 的一部分，并且在每个i p 实现中都必须包含它。i c m pe c h o r e q u e s t e c h or e p l y 报文被用于判定i p 地址的可达性。i c m pa d d r e s s m a s k r e q u e s t a d d r e s s m a s kr e p ly 报文可用于决定子网掩码。 使用p i n g 的最大问题是，当p i n g 一个活着的主机时，其往返时延往往在几 十毫秒左右，但p i n g 一个不存在的或宕着的主机，一般比较常用的超时通常为 2 秒，再加上为了减少丢包对测量结果的影响而采取发2 - 3 个p i n g 包，这样对 这类主机的监测代价就非常大。改进的办法，一是减小超时阀值。二是采用异步 方式发送和接受i c m p 包，从而可以并行的探测多个i p 。 使用p i n g 的另一种方式是广播p i n g ( d i r e c t e db r o a d c a s tp i n g ) 。其方法 是发送p i n g 包中的目的地址是一个子网的广播地址。而属于该子网中的结点都 会响应。这种方法不仅呵以快速的发现子网中的所有结点，而且能发现子网的广 播地址( 一般来说，这个地址也是子网的地址，子网号) 。广播p i n g 的功能由于 安全原因被限制了，以防拒绝服务攻击(