（计算机系统结构专业论文）计算机网络自动拓扑发现的研究.pdf

重庆大学硕士学位论文 中文摘要 摘要 随着计算机网络技术的飞速发展，各组织机构对计算机网络的高度依赖性使得 网络运行的可靠性变得至关重要。因此，就对网络管理提出了更高的要求。在网 络管理中，网络拓扑信息是其它所有管理功能的基础。只有在掌握了被管理网络 正确、完整的拓扑结构之后，才能对网络进行正确、有效的管理操作。如何快速、 高效并准确地发现网络拓扑信息是当前网络管理领域关注的重要问题。 计算机网络领域中，拓扑反映的是网络设备的分布及连接情况。本文主要是 研究管理域内的拓扑结构，分为两个层次来进行讨论。其一是网络层拓扑结构， 即网络骨干层次的拓扑结构，主要描述路由器、子网及其它们之间的连接关系： 其二是数据链路层拓扑结构，即一个子网内的拓扑结构，主要描述交换机、主机 及其它们之间的连接关系。 为了获得网络拓扑信息，必须要借助一定的协议和工具，本文对目前使用较 多的拓扑发现技术和工具进行了介绍，并分析了它们各自适用的情形和优缺点。 针对网络层拓扑发现，本文介绍了两种常用的发现算法，第一种是基于s n m p 协议的算法，其优点是实现简单，发现速度快，缺点是通用性不强；第二种是基 于通用协议的算法，其优点是通用性强，缺点是实现复杂，发现速度慢。本文在 此基础上提出了一种综合以上两种算法的改进算法，使得发现过程即具有简单、 高效性，又具有很强的通用性。同时解决了在发现过程中遇到的子网判定，多址 路由器身份确定等问题。 在数据链路层拓扑发现中，重点是要发现交换设备之间的级连关系，本文采 用依靠地址转发表来发现连接关系。目前的算法对地址转发表的完备程度要求较 高，而且实现复杂。为了克服这些不足，本文也提出了一种改进算法，降低了对 地址转发表是否完备的依赖程度，并使得算法执行过程更加简洁，同时也设计了 一种解决发现过程中出现不支持s n m p 协议设备的方案。 最后，基于提出的改进算法，本文实现了一个原型系统，介绍了原型系统的 结构组成，对设计中的关键问题作了说明。并在实际的网络环境中进行了测试， 经过对测试结果的分析以及与其它算法的比较，验证了改进算法的正确性和可行 性。 关键词：网络管理，拓扑发现，s n m p ，f d b 重庆大学硕士学位论文英文摘要 a b s t r a c t w i t ht h er a p i dd e v e l o p m e n to fc o m p u t e rn e t w o r kt e c h n o l o g y , e v e r yo r g a n i z a t i o n s d e p e n d so nc o m p u t e rn e t w o r ks om u c ht h a tn e t w o r km a n a g e m e n th a sb e c o m em o l ea n d m o l e 啊t a l t h e r e f o r e i tl e a d st oah i g h e rr e q u e s tt on e t w o r km a n a g e m e n ts y s t e m 。i nt h e n e t w o r km a n a g e m e n ts y s t e m , n e t w o r kt o p o l o g yi n f o r m a t i o ni st h ef o u n d a t i o no fo t h e r f u n c t i o n s o n l yw h e nt h es t r u c t u r eo fn e t w o r kt o p o l o g yi sm a s t e r c d ，c a l lc o r r e c ta n d e f f e c t i v ea d m i n i s t r a d o no p e r a t i o nb ei m p l e m e n t e d a tp r e s e n t , h o wt od i s c o v e rn e t w o r k t o p o l o g yf a s t , e f f i c i e n t l ya n da c c u r a t e l yi sam a j o rc o i i c e i t i - i nn e t w o r km a n a g e m e n t f i e l d i nt h ef i e l do fc o m p u t e rn e t w o r k , t o p o l o g yi sar e f l e e t i o no ft h ed i s t r i b u t i o no f n e t w o r kd e v i c e sa n dc o n n e c t i o n sa m o n gt h e m t o p o l o g yi na d m i n i s t r a t i v ed o m a i ni s m a i n l ys t u d i e di nt h ep a p e r , a n dt h e r el i f et w ol e v e l so ft o p o l o g yf o rd i s c u s s i o n o n e l e v e li st o p o l o g yo fn e t w o r kl a y e rw h i c hi st h es t r u c t u r eo fn e t w o r kb a c k b o n e , w h i e l a d e s c r i b e sl o u t e r s ，s u b n e t sa n dc o n n e c t i o n sa m o n gt h e m t h eo t h e ro n ei st o p o l o g yo f d a t al i n kl a y e rw h i c hi st h es t r u c t u r ei no n es u b n e t , w h i c hd e s c r i b e ss w i t c h e s ，h o s t sa n d e o n n e , c t i o n sa m o n gt h e m t oo b t a i nn e t w o r kt o p o l o g yi n f o r m a t i o n , i ti sn e c e s s a r yt ou s ef l o m ep r o t o c o l sa n d t o o l s s o m et e c h n o l o g i e sa n dt o o l sw h i c hh a v eb e e nw i d e l yu s e di nt o p o l o g yd i s c o v e r y a l l 。i n t r o d u c e di nt h ep a p e r , a n dt h e i rm e r i t s , s h o r t c o m i n g sa n ds i t u a t i o no fb e i n g s u i t a b l ef o r 哪峨a l s od i s e u s s e d a tt h en e t w o r kl a y e rt o p o l o g yd i s c o v e r y , t w oa l g o r i t h m si nc o m m o n 啪e l l - e i n t r o d u c e d t h ef i r s ti sb a s e do i ls n m p p r o t o c o l ，w h o s em e r i t si ss i m p l ea n dd i s c o v e r e d q u i c k l yw h i l et h es h o r t c o m i n gi sn o ts u i t a b l ef o rw i d eu t h es e c o n di sb a s e do n u n i v e r s a lp r o t o c o l s ，w h o s em e r i t sl l l * es u p p o r t e di nm o s ts i t u a t i o n s , a n ds h o r t c o m i n g s 眦t o oc o m p l i c a t e da n dd i s c o v e r e ds l o w l y a ni m p r o v e da l g o r i t h mw h i c hs y n t h e s i z e s t h et w oa l g o r i t h m si n t r o d u c e db e f o r ei sp r e s e n t e di nt h ep a p e r t h r o u g ht h i sa l g o r i t h m , d i s c o v e r yp r o c e s sw i l lb es i m p l e , l a i g h - e f f e e t i v e , a n dh a v ee x c e l l e n ta p p l i c a b i l i t y m e a n w h i l e , t h ep r o b l e mo fs u b n e td i s c o v e r i n ga n dh o wt oi d e n t i f yam u l t i a d d r e s s r o u t e ri sa l s os o l v e d a tt h ed a t al i n kl a y e rt o p o l o g yd i s c o v e r y , c o n n e c t i o n sa m o n gs w i t c h e sa , l et h em o s t i m p o r t a n t t h ed i s c o v e r ym e t h o do fu s i n gf d b ( f o r w a r d i n gd a t a b a s e ) i sm a i n l y s t u d i e di nt h ep a p e r a tp r e s e n t , t h ea l g o r i t h mr e q u i r e sf d bs h o u l db em o r ec o m p l e t e , 重庆大学硕士学位论文英文摘要 a n dt oi m p l e m e n ti st o oc o m p l i c a t e d t h e r e f o r e ，t oo v e r c o f f l et h e s es h o r t c o m i n g s ，a n i m p r o v e da l g o r i t h mi sp r e s e n t e d t h ei m p r o v e da l g o r i t h mc a nr e d u c er e l i a n c et of d b c o m p l e t i o na n dm a k ei m p l e m e n ts i m p l e r m e a n t i m e , t h ei m p r o v e da l g o r i t h md e s i g n sa s c h e m et os o l v et h es i t u a t i o nt h a tt h e r ea r e8 0 h l ed e v i c e sn o ts u p p o r t i n gs n m p p r o t o c o l d u r i n gd i s c o v e r i n g f i n a l l y , ap r o t o t y p es y s t e mb a s e do i lt h e s ei m p r o v e da l g o r i t h r a sh a sb e e nd e s i g n e d a n di m p l e m e n t e di nt h ep a p e r , i nw h i c hs y s t e ms t r u c t u r ea n dk e ys o l u t i o no f p r o t o t y p e s y s t e mh a sa l s ob e e nd i s c u s s e d i nr e a lc o m p u t e rn e t w o r ke n v i r o n m e n t , t h ep r o t o t y p e s y s t e mh a sb e e nt e s t e d b ya n a l y z i n gt h et e s tr e s u l ta n dc o m p a r i n gw i t ho t h e r a l g o r i t h m s ，t h ec o r r e c t i o na n df e a s i b i l i t yh a v eb e e np r o v e d k e y w o r d e ：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 , s n m p , f d b l l i 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取 得的研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文 中不包含其他人已经发表或撰写过的研究成果，也不包含为获得重废太堂 或其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本 研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 ， ， 、 学位论文作者签名：与杀定签字日期：20 0 ，年月ie l 学位论文版权使用授权书 本学位论文作者完全了解重废太堂有关保留、使用学位论文的 规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许 论文被查阅和借阅。本人授权 重庆太堂可以将学位论文的全部或部 分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段 保存、汇编学位论文。 保密() ，在年解密后适用本授权书。 本学位论文属于 不保密( ) 。 ( 请只在上述一个括号内打“”) 学位论文作者签名：与拿爱 签字日期：2 0 。7 年6 月e t 导师签名： 签字日期：沙可年6 月e t ， 重庆大学硕士学位论文 1 绪论 1 绪论 1 1 引言 随着计算机及通信技术的飞速发展，计算机网络已经渗透到社会经济生活的 各个方面，对社会进步与经济发展起着越来越重要的作用，也使人们的工作甚至 生活方式发生了巨大的变革。信息社会对计算机网络的依赖，使得计算机网络本 身运行的可靠性变得至关重要。我们需要掌握网络系统的工作状况，及时发现运 行中出现的故障，找出性能瓶颈，对网络系统做出优化，这些都涉及到网络系统 管理所研究的内容。随着网络规模的激增，网络复杂性和异构性的增大，网络管 理问题上升到了网络建设的战略性位置。 按照o s i 的定义，网络管理主要包括五个功能域：故障管理、配置管理、性 能管理、安全管理和计费管理。五大功能域之间既相对独立，又存在着联系。在 五大功能域中，配置管理是基础，它的主要功能包括发现网络的拓扑结构、监视 和管理网络设备的配置情况。而监视和管理网络设备的基础是已知网络的拓扑结 构，所以，网络拓扑发现是网络管理的基础。 网络拓扑展现网络中设备的存在性以及它们之间的连接关系。网络管理员通 过网络拓扑结构信息可以对网络故障进行定位，发现网络瓶颈，更加清楚地了解 网络的当前状况等等，从而更好地管理并优化整个网络。 对于小型网络，网络管理员可以手工绘制网络的拓扑。但是大型网络，可能 包含成千上万的设备，它们之间的连接关系非常复杂，手工绘制网络拓扑就成了 一件非常繁琐甚至不可能完成的任务。而且因为网络具有层次性的特点，不同的 管理者关注网络层面是不相同的，有的需要分析网络骨干设备之间的连接状况， 而其他人可能只对他自身所在的子网感兴趣。所以开发一种具有多层次的拓扑发 现算法具有重要的现实意义。 1 2 研究意义 网络拓扑发现是为了获取网络中存在的各个节点以及它们之间连接关系信 息，并在此基础上绘制出网络拓扑图。网络拓扑发现作为网络管理系统的一个重 要组成部分，同时也是衡量一个网管软件优劣的重要尺度，网络拓扑图为网络管 理人员提供了了解全局网络连接情况的直观方式，只有掌握了网络的拓扑结构， 才能有效地对网络设备进行监控、配置、故障诊断和优化。 很多重要的网络管理任务，如网络资源管理、服务器部署、事件关联以及故 障分析等都是以网络的拓扑结构为前提的。一个典型的例子是，当网络中发生一 重庆大学硕士学位论文 1 绪论 个故障时，该故障可能使相关的网络设备发出大量的告警信息，使网络管理员无 从得知故障的真正位置。如果知道了网络拓扑结构，就可以过滤掉派生的告警， 从而定位故障的原始位置。拓扑结构还可以使网络管理员预先发现那些容易引发 单点故障的不合理结构，防止故障的发生。在网络规划中，网络拓扑信息还可以 用于服务器定位，帮助用户确定自身在网络中的位置，从而决定服务器的位置以 及选择可以将时延最小化、可用带宽最大化的网络服务提供商。在网络优化中， 拓扑信息可以帮组管理员查找网络性能瓶颈，进而采取相应的措施来调整网络配 置。另外拓扑信息还能用于拓扑敏感算法( t o p o l o g y - a w a r ea l g o r i t h m s ) 中，使得一些 新的协议和算法能够在得到网络拓扑信息的基础上改善网络性能。比如，现在流 行的p t p ，网格计算等都是对网络拓扑比较敏感的应用，强烈需要拓扑信息来对 他们的内部算法给予支持。 网络拓扑为网络管理人员提供了从全局上把握网络状况的途径，使得网络管 理的部署等更为有效和合理，并使得网络管理的效率大为提高，故设计好的拓扑 发现算法是一个很有意义的研究方向。 1 3 国内外研究现状 最初的计算机网络规模比较小，通常在网络建设之初，由网络管理员手工绘 制网络拓扑图，由于网络的变动不大，所以该方式还能满足当时的需要。随着计 算机网络的飞速发展，手工绘制网络拓扑图已经成为一件非常烦琐的工作，有时 候甚至是不可能的。于是，人们开始了网络拓扑的自动发现的研究。在网络层， 人们从路由表中提取拓扑信息；在链路层，人们利用a r p 协议和i c m p 协议来发 现局域网中的设备。1 9 9 0 年，j d c a s e 等人提交了名为“一种简单网络管理协议” ( s n m p ) 的r f c l l 5 7 2 ，之后一年k m c c l o g h r i e 和m r o s e 在r f c l 2 1 3 刚中提出 了基于t c p i p 协议的因特网管理信息库m m i i ，这些都充分考虑了网络管理中的 拓扑发现需要，从此，拓扑发现的主要工具成为s n m p 。1 9 9 6 年，g l e n nm a n s f i e l d 等人在参考文献 1 3 仲提出了一种基于s n m p 的网络层拓扑发现算法，之后有许多 相关的拓扑发现软件产品问世，比如h p 公司的o p e a v i 部v 和i b m 公司的t i v o l i 等。然后，又有不同的人开始对拓扑发现算法在效率和适用性上作了改进。目前， 人们又开始利用路由协议来发现网络层拓扑。a m a ns h a i k h 等人在参考文献 1 2 1 中 提出了一种通过监听网络中的o s p f 数据包来获得网络拓扑的方法。这种方法的优 点是可以绕过设备不支持s n m p 带来的麻烦，同时可以避免向网络中注入大量数 据包，从而减轻了网络的负担。 s n m p 的出现也为数据链路层的拓扑发现算法提供了有力的工具，h w a - c h u n l i n 等人在参考文献【1 4 】中开始利用b r i d g em i b ( r f c l 4 9 3 ) t g l 来获取交换机的连接 2 重庆大学硕士学位论文1 绪论 信息，但是该方法的准确性不高。y b r c i t b a r t 等人在参考文献 1 5 e e 提出了一种基 于b r i d g em i b 的一种拓扑发现算法，并给出了严格的数学证明，但是该方法对网 络环境要求太高。之后，b m c el o w e k a m p 等人在参考文献【1 6 】中改进了y b r e i t b a r t 等人的算法，使的算法对网络环境的要求显著降低。 当前，随着对口v 6 网络研究的深入，人们开始关注i p v 6 网络的拓扑自动发现。 由于口v 6 协议中地址结构等方面的变化以及口v 6 网络中庞大的节点数量，适用于 i p v 4 网络的拓扑发现技术和方法必须做出相应地修改才能应用于i p v 6 网络环境 中。参考文献【1 7 】详细讨论了口v 6 网络给拓扑发现带来了一些新问题。 由于拓扑发现在网管系统中的重要性，目前大多数商用网管系统中都集成了 拓扑发现的功能。如惠普公司的o p e n v i e w 网管系统中的n n m 6 0 ，c a 的n e t w o r l d t 与f l u k e 公司的最新产品m a p s h o w ，都具有网络拓扑发现的功能。另外许多知 名的网络设备制造商也为自己的产品设计了功能强大的拓扑发现方案，c i s e o 制定 了专用于发现自家产品的c d p ( c i s c o d i s c o v e r y p r o t o c 0 1 ) 协议，b a y n e t w o r k s 公 司的网管系统o p t i v i t ye n t e r p r i s e ，但这两种方法均基于厂家自身的产品，不具有通 用性。 国内在网络拓扑发现领域起步相对较晚，但到现在为止，也取得了一些成果。 北京华信亿码科技发展有限公司开发了在w i n d o w sp c 平台上使用的网络管理软 件e a s y m a n a g c r 。该软件对t c p i p 网络实现拓扑发现，能对第三层设备及连接关 系较正确地发现并以逻辑的方式显示。华中理工大学对网络拓扑发现也有深入的 研究，但也只是完成对第三层设备及连接关系的发现并以逻辑图的方式显示发现 结果。包括西安交通大学在内的高校和研究所对网络拓扑发现也有较深入的研究。 1 4 研究目标和研究内容 本论文是以重庆大学校园网络作为实验环境，研究大型网络环境下不同层次 的网络拓扑自动发现方法。对现有的拓扑发现算法进行综合和比较，在此基础上 进行优化和改进，提出一种新的多层次的拓扑发现算法，该算法较已有算法有更 高的效率和准确度。在设计出改进算法的基础上，编程实现出原型系统，并测试 系统和算法的可行性。 本论文的主要研究内容包括以下几个方面： 仔细研究现有的拓扑发现算法，提出优化、改进方案。 在网络层上，主要有两类拓扑发现方法，一种是基于s n m p 协议，另一种是 利用i c m p 等通用性协议。基于s n m p 的拓扑发现算法已比较成熟，但因为实际 网络中还存在一些网络设备并不支持该协议，所以该方法存在一定的局限性。基 于通用性协议的方法虽然适用性强，但算法复杂度高，发现效率低。鉴于这些情 3 重庆大学硕士学位论文 l 绪论 况，设计一种既具有较高的发现效率，又兼具通用性的发现算法是本文的主要研 究方向。 研究子网内数据链路层拓扑的发现方式及连接定理，设计一个简单易行的 发现算法 目前对于数据链路层的拓扑发现还缺乏有效的机制，现有的数据链路层设备 连接定理对网络环境的要求过高，且算法实现复杂度大。数据链路层的拓扑信息 来源主要是交换设备的地址转发表，拓扑发现的任务是要基于地址转发表和连接 定理设计一个在实际网络中可行的算法。 根据设计的算法实现出原型系统，并在实验环境中进行测试。 根据以上研究所提出的拓扑发现算法，采用l i ps n m p + + 开发包，以v c6 0 为开发环境，以校园网络作为实验环境，实现出基于该算法的原型系统，并测试 算法的可行性、效率及准确性。 1 5 本文的组织结构 第一章，介绍了网络拓扑发现的研究意义，研究现状和本文的研究内容。 第二章，介绍网络拓扑发现所涉及到的相关技术和方法。 第三章，论述了目前网络层拓扑发现的各种方法和技术，分析各自的利弊和 适用环境，在此基础上提出综合几种技术的网络层拓扑发现改进算法，并对算法 中的关键环节进行说明。 第四章，对数据链路层的主要设备交换机的工作原理进行了论述，讨论 了数据链路层的拓扑发现方法，分析各种判断设备之间连接关系的连接定理，指 出了基于这些连接定理的发现算法的不足之处，提出了数据链路层拓扑发现改进 算法，并对算法中的实现细节作了说明。 第五章，拓扑发现原型系统的设计和实现。详细介绍了原型系统的模块组成 结构，然后论述了核心模块的设计和实现。最后基于校园网络对本原型系统进行 了测试，并将试验结果与实际网络情况进行了比较、分析，验证了改进算法的正 确性和可行性。 第六章，对本文的研究内容进行了总结，并对下一步将要进行的工作进行了 说明。 4 重庆大学硕士学位论文 2 计算机网络拓扑发现概述 2 计算机网络拓扑发现概述 2 1 网络拓扑结构 2 1 1 网络拓扑图的表现方式 拓扑学是数学的一个分支，研究几何图形在连续改变形状时还能保留不变的 一些特性。它只考虑物体之间的位置关系，不考虑它们的大小及距离。一个基本 的网络可以被看作由网络节点和链路组成。计算机网络领域中，拓扑反映了网络 节点的几何排列或布局以及网络节点之间的连接关系。网络节点是网络的基本互 连设备，知交换机、路由器、主机等，另外本文中在讨论网络层拓扑图时，我们 将子网也看作一个抽象的网络节点。链路将两个网络节点相连，提供它们之间信 息传递的通路。 网络拓扑图的表现形式通常用无向图g ( v ，e ) 来表示。网络节点表示为图 中的节点v ，链路表示为图中的无向边e 。这种表现方式将复杂的网络拓扑信息抽 象成点与边相结合的无向图，使得拓扑结构以简单、直观的形式呈现给管理者。 2 1 2 网络拓扑基本结构 主要的网络拓扑结构有树型、星型、总线型、环型以及它们的混合型结构【2 3 1 ， 如图2 1 所示。 峻 米 树型拓扑结构 星型拓扦结构 总线型拓扑结构环型拓扑结构 混合型拓扑结构 图2 1 基本网络拓扑结构 f i g2 1b a s i c & c h t c c t m eo f n e t w o r kt o p o l o g y 树型拓扑结构就像一棵“根”朝上的树，是分层的集中控制式网络，结点易于扩 5 重庆大学硕士学位论文2 计算机网络拓扑发现概述 充，寻找路径比较方便，但除了叶子结点及其相连的线路外，任意一个结点或其 相连的线路出现故障都会使系统受到不同程度的影响。 星型拓扑结构是一种以中央结点为中心，把若干外围结点连接起来的辐射式 互联结构。在星型网中，任何一个连接都只涉及到中央结点和一个外围结点。 总线型拓扑结构采用单根传输线作为介质，所有的站点都通过相应的硬件接 口直接连接到干线电缆即总线上。 环型拓扑结构中所有站点彼此串行连接，连成链一样，构成一个回路或称作 环。在环型拓扑网络中，数据是被单方向传输的，两个站点之间仅有唯一的通路。 在现实网络中通常采用以上多种拓扑结构的混合形式，即混合型拓扑结构。 2 1 3 多层网络拓扑结构 现在的大型的校园网、企业网等网络规模不断扩大，结构也更加复杂，将整 个网络作为一个整体来进行管理维护越来越困难。所以就有了将网络进行分层次 管理的思想，通常将整个网络按照不同的管理层次分为多级网络，不同层次的管 理者只负责管理本层次网络，而由上一级网络管理者负责各个下级网络之间的相 互协调工作。这样不同层次的网络管理者可以专注于本网络内的管理事务，而核 心的管理人员也不用再考虑琐碎的细节问题，而是从整个网络的层面上进行统筹 的安排和优化。通过这样的网络分层，提高了网络管理的效率，也使得网络管理 的成效更加明显。 另外计算机网络也具有层次性的特点，不同的网络设备工作在不同的层次， 比如路由器工作在网络层，交换机工作在数据链路层，h u b 工作在物理层。所以 这就导致了不同的管理需求，管理者有时需要在网络层上显示网络拓扑结构，有 时又需要在链路层上显示拓扑结构，所以拓扑发现需要探索不同层次的网络信息。 本文主要论述了两个层次的网络拓扑发现方法：其一是网络层，这个层次我 们主要是发现路由器，子网以及他们之间的连接关系；其二是链路层，这个层次 主要是发现子网中交换机，主机以及他们之间的连接关系。 2 2 网络拓扑发现的基本协议和工具 为了获得网络拓扑信息，必须要借助一定的协议和工具【1 8 1 【1 9 1 1 2 0 t 2 ”，下面我们 对获取网络拓扑信息的主要方法进行介绍，并对各自的适用环境及利弊进行分析。 s n m p 协议； i c m p 、# n g 、t r a c e r o u t e 方法； a r p 协议； d n sz o n et r a n s f e r 方法； 路由协议，如r i p , o s p f , b g p 等； 6 重庆大学硕士学位论文2 计算机网络拓扑发现概述 厂商专有的工具，如c i s c o 的c d p ( c i s c od i s c o v e r yp r o t o c 0 1 ) 协议。 2 2 1s n 伊 s n m p 的体系结构 s n m p ( 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 ，简单网络管理协议) 是一种基 于t c p i p 协议的互连网管理协议【2 l 【5 】【8 j 【2 2 】例。 s n m p 诞生于1 9 8 8 年，当时只想把它作为一个短期的网络管理框架，临时用 于管理连接到i n t c r n e t 上的设备。但随着s n m p 的发展和大量应用，其使用范围已 大为扩展，超出了i n t c m e t 的范围。s n m p 逐渐作为一种标准的协议在网络管理领 域得到了普遍的接受和支持，成为了事实上的国际标准。 应用进程对资 图2 2s n m p 体系结构 f 瑭2 2 a r d l i t e c 叫e o f s n m p s n m p 的体系结构( 见图2 2 ) 主要包括管理站( m a n a g e r ) ，代理( a g e n t ) ， 管理信息库( m i b ) ，网络管理协议( s n m p ) 。管理站一般是网络中的单机设备， 是管理员与网络管理系统的接口。代理是运行于各个被管网络节点中的进程，负 责收集本节点的相关信息，对来自管理站的查询进行响应，同时异步地向管理站 汇报本节点发生的重要事件。管理信息库包含代理进程的所有可被查询和修改的 参数集合。管理进程和代理进程之间的通讯协议使用s n m p 协议。用于管理进程 和代理进程之间的交互信息，s n m p 定义了五种报文，分别是：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 、g e t - r e s p o n s e 、h - a p 们。拓扑发现主要是通过前两种 操作来获取被管设备的信息，从而建立起拓扑关系图。 m m 信息库 7 重庆大学硕士学位论文 2 计算机网络拓扑发现概述 所谓管理信息库m i b 1 】f 3 】【_ 7 l ，就是所有代理进程包含的、并且能够被管理进程 进行查询和设置的信息的集合。它规定了网络代理必须保存的数据项目、类型及 允许的操作。网络管理系统中的每个结点都包括一个m i b ，它反映了该结点中被 管资源的状态。利用s n m p 协议访问网络设备的管理信息库，就可以得到网络设 备的所有相关信息，完成网络拓扑的构建。拓扑发现中需要访问的m m 库主要是 m i b i i ( r f c 1 2 1 3 ) 1 4 j ，b r i d g e m i b l 9 等。 使用s n m p 进行拓扑发现的优缺点 利用s n m p 进行拓扑发现的优势在于： i ) 可以快速地从m i b 信息库中获取拓扑信息，从而加快了发现的过程； 2 ) m i b 库中的信息会根据网络运行的状况自动更新； 3 ) s n m p 可适用于非口网络。 利用s n m p 进行拓扑发现的局限在于： 1 ) 并非所有的网络设备均支持s 旧协议； 2 ) 只有获得授权才能够访问m m 信息库； 3 ) m m 信息存在标准m m 和厂家自定义m i b 共存的局面，所以必须采用标 准的m m 信息进行拓扑发现。 因为s n m p 协议实际上已经成为国际上标准的网络管理协议，并被绝大多数 的网络设备所支持，并且发现管理域内的拓扑并不存在获得授权的问题，故本文 中的拓扑发现方法就大量采用了基于s n m p 获得m m 信息的技术。 2 2 2i c m 呼、p i n g 、t r a c e r o u t c i c m p 协议 差错与控制报文协议( i c m p ) 【l o 】是t c p i p 协议簇中通用的控制协议，主要 用于主机和路由器之间用来传达差错和控制信息。在拓扑发现中主要用到i c m p 协议中的可达性检测报文和获得子网掩码报文。 p i n g 操作 r i n g 操作主要检测目的主机是否处于活动状态，它实际上是对主机的口地址 发一个i c m p 回应请求数据包，并等待接受回应响应数据包。若收到应答，则报 告目的机运行正常。 t r a c c r o u t c 操作 t r a c e r o u t e 工具可以用来发现测试点和目标主机之间的路由器。路由器在转发 包之前总是将其1 r l 值减1 ，如果1 f r l 降为0 ，则路由器向源地址发送t t l - e x p i r e d i c m p 消息。嘶o u t e 实现的原理就是应用路由器的这个特性，通过发送r r l 逐 渐增大的探测包，由测试点到目标间这条路径上所有的路由器依次向测试点发送 t r l - e x p i r e di c m p 包，从而发现路径上所有的路由器。因为几乎所有支持t c p i p 重庆大学硕士学位论文2 计算机网络拓扑发现概述 的路由器设计时都实现了发送t r l - e x p i r e di c m p 消息的功能，所以大多数情况下 t r a c c r o u t e 的结果是准确可信的。由于采用逐渐增大r r l 值的方法，每探测一个目 标需要依次发送不同t t l 值的多个包，因此用t r a c e r o u t e 获取结果比p i n g 要慢得 多。 2 2 3 其它协议和工具 a r p 协议 球地址的分配是独立于机器的物理硬件地址的。为了在物理网络上把一个分 组从一台计算机发送到另一台上，网络软件必须把口地址映射到一个物理地址， 并用这个物理地址传送帧。地址解析协议( a r p ) 在口地址和物理地址之间做映射。 任何有以太网接口的网络设备都必须支持地址解析协议，并在本机维持着一张地 址解析表，包含一个本地网络上物理地址到口地址映射的完整列表。网络拓扑发 现中，根据任何一台路由器的a r p 表，可以发现与路由器相连的子网中的网络设 备。 d n sz o n et r a n s f e r 口地址是为网络上的主机、路由器等设备所设计的，它不符合人类的记忆习 惯，d n s ( d o m a i nn a m es y s t e m ) 就是为解决这个问题而开发的。d n s 系统主要 用于网络设备p 地址到名字的映射。使用d n $ 服务器所提供的区域传输功能可以 一次获取域内主机和路由器的域名和m 地址的映射关系，使用简单、快速。但出 于安全方面的考虑并不是所有的d n s 服务器都提供区域传输功能。而且，如果口 地址通过d h c p 服务器获得，那么聊q s 就无能为力了。 路由协议 网络中的路由器为了达成对网络连接状况的统一认识，必须通过路由协议来 交换网络可达性、网络状况等信息，通过获得路由协议中的网络连接信息就可以 探测出网络的拓扑结构。实际应用中常见的路由协议有r i p , o s p f ，b g p 等。我们 可以通过两种方式来访问路由协议的相关信息：其一是访问与特定的路由协议相 关的m i b 信息；其二可以监听网络中的路由协议数据包。利用路由协议可以发现 路由器、子网及它们之间的连接关系，利用b g p 协议还可以得到自治系统问的拓 扑结构。利用路由协议来进行拓扑发现的主要缺陷是路由协议的类型多，实际网 络中使用的路由协议各不相同，利用单一路由协议信息来进行拓扑发现受到很大 的局限。 厂商专属协议 基于网络拓扑在网管系统中的重要性，一些知名的网络设备制造厂商设计了 自己专有的协议来帮助网络拓扑的发现工作。比如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 i s c o 设备相关信息。使用这些协议 9 重庆大学硕士学位论文 2 计算机网络拓扑发现概述 来发现网络拓扑的优点是简单，快捷。但因为是厂商的专属协议，使用范围受到 很大的限制。 2 3 本章小结 本章首先介绍了网络拓扑的基本结构和层次化的思想。然后讨论了常用的拓 扑发现协议和工具，包括简单网络管理协议s n m p ，互联网控制报文协议i c m p ， 域名服务d n s 以及地址解析协议a r p 等其它工具。其中对各种工具的适用环境 和利弊进行了分析，最后得出了结论：网络自动拓扑发现的基本工具各有利弊， 在使用时，要根据网络的具体情况选择适当的发现工具，或者将多种工具结合起 来使用。 1 0 重庆大学硕士学位论文 3 网络层拓扑发现改进算法 3 网络层拓扑发现改进算法 网络层拓扑发现目前主要有以下两种算法：一是通过s n m p 获取路由器中的 路由表，采用广度优先遍历的方法；二是利用i c m p 协议实现基于p i n g 、t r a r 汜r o u t e 的深度优先遍历的方法。 3 1 基于s n m p 的网络层拓扑发现算法 3 1 1 拓扑发现过程中相关的m i b 变量 基于s n m p 的网络层拓扑发现算法主要是通过s n m p 协议来获得m i b 中与网 络拓扑相关的信息，然后对这些信息进行分析处理，从而得到拓扑结构。 m i b i i ( r f c l 2 1 3 ) 4 1 是标准的s n m pm i b ，所有的路由器都必须实现它。m i b i i 由 很多不同的组组成，基于s n m p 的拓扑发现算法用到的组包括：s y s t e m 组，i n t e r f a c e s 组和口组。下面详细介绍这三个组中包含的主要对象。 s y s t e m 组 该组内包含七个对象，分别为：s y s d e s e r 、s y s o b j e c t i d 、s y s u p t i m e 、s y s c o n t a c t 、 s y s n a m e 、s y s l o c a t i o n 和s y s s e r v i c 鸳s 。其中s y s d e s e r 描述了设备的相关信息，一般 包括厂商，型号等。s y s o b j e c t i d 唯一标识特定厂商的特定类型设备，比如 s y s o b j e c t i d 为1 3 6 1 4 9 5 4 5 ，则可以判断该设备为c i s c o 公司生产的型号为 c i s c 0 6 5 0 6 的交换机。s y s u p t i m e 表示设备从最近一次启动开始后正常运行的时间。 s y s c o n t a c t 由网络管理员设定，一般设为网络管理员的联系方式。s y s n a m e 也是由 网络管理员设定，表示设备的名字。s y s l o c a t i o n 由网络管理员设定，一般设为设 备所在地点。s y s s e r v i c 圮s 表示了该设备所能提供的服务层次。 i n t e r f a c e s 组 该组包含两个对象i f n u m b e r 和i l l ? a b l e 。i f n u m b e r 对象表示该设备所具有的接 口数量。i l l a b l e 是一张表，表内的每一个字段都是某一个接口的一个属性，包括 接口索引( i f i n d e x ) ，接口类型( i f t y p e ) ，接口速度( i f s p e e d ) 和接口物理地址 ( i f p h y s a d d r e s s ) 等。 p 组 该组的元素较多，其中有三个表对拓扑发现来说比较重要，分别是 i p a d d r t a b l e 、i p r o u t e t a b l e 和i p n e t t o m e d i a t a b l e 。 1 ) i p a d d r l i 曲l e 表 此表给出了结点自身所有接口的地址信息，同时结合i n t e r f a c e s 组的i f f a b l e 表，可以把接口和其口地址一一对应起来。该表中用于拓扑发现的相关m m 变量 重庆大学硕士学位论文3 网络层拓扑发现改进算法 列举如下： i p a d e n t a d d r ：