（计算机应用技术专业论文）网络自动拓扑发现算法研究.pdf

硕士学位论文 、”l r s + 1 j e s i s 摘要+ 目前的网络自动拓扑发现多采用s n m p 协议实现基于路由表的管理域内逻 辑拓扑发现算法。但是，交换机等二层设备越来越多地分布在i p 网络中形成微 子网段，使得越来越多的网络结构对于逻辑拓扑发现是不可见的。另外，i n t e m e l 拓扑发现研究的相对滞后已经对几乎所有的广域网应用、服务器选择和定位造 成了瓶颈，使得i n t e m e t 的拓扑发现和性能衡量日益受到重视。由此可见，现有 的管理域内逻辑拓扑发现算法远远不能满足实际需求。本文除提出了一种改进 的管理域内逻辑拓扑自动发现算法以外，还讨论了管理域内物理拓扑以及 i n t e r n e t 主干网拓扑的自动发现算法。 文中首先介绍了对算法设计比较重要的网络互连设备f 主要是网桥和路由 器) 功能以及局域网和广域网的常见拓扑结构。随后，通过对拓扑发现基本工具 利弊的比较分析，提出在实际使用这些工具时有必要针对拓扑发现目标网络的 具体情况，选用适当的工具或将多种工具结合使用。 针对传统的管理域内逻辑拓扑发现算法仅能发现网络中支持s n m p 协议设 备的这一不足，文中结合使用i c m p 协议实现基于p i n g 和t r a c e r o u t e 的算法。 拓扑发现的结果表明，该算法提高了管理域内逻辑拓扑发现结果的完整性。 现有的管理域内物理拓扑发现算法在发现了二层设备之后，大多尽力判断 设备端口之间的直接相连关系。这种方法需要在网络中产生额外流量用以保证 设备地址转发表的完整性。本文中的算法将直接判断端口相连的方法和从集合 中排除不可能相连端口对的间接方法相结合，在物理拓扑发现的高效性和准确 性方面更进了一步。 最后，本文在分析了以c n r g 算法为代表的i n t e m e t 拓扑发现基本算法的 局限性之后，对i n t e r n e t 的启发式拓扑发现算法进行了探讨，主要讨论了其采用 t r a c e r o u l e 的基本路径探测、启发式的随机地址选取、解决交叉连接问题的源路 由路径探测以及路由器别名判定四个机制。 关键词：网络自动拓扑发现，s n m p ，i c m p ，生成树协议，启发式算法 七本论文的研究工作受湖北省科技攻关重大项目“网络管理平台软件研究及产业化”( 2 0 0 1 a 1 0 5 a 0 4 ) 、湖北 省自然科学基金项目“智能拓扑发现算法的研究“( 2 0 0 1 a b b 0 1 3 ) 的资助 a b s t r a c t a td r e s e n t ，m o s to f t h en e t w o r ka u t o m a t i cd i s c o v e r ya l g o r i t h m s a r ed e v e l o p e dt o d i s c o v e rl o g i c a lt o p o l o g i e sw i t h i na d m i n i s t r a t i v ed o m a i n sb ya c c e s s i n gr o u t i n gt a b l e o fm 1 b si nm a n a g e do b j e c t su s i n gs n m p b u t a sm o r el a y e r - 2d e v i c e sa r ed e p l o y e d i n h e t e r o g e n e o u s i pn e t w o r k st o p r o v i d e m o r eb a n d w i d t h t h r o u g h s u b n e t m i c r o s e g m e n t a t i o n ，t h ep o r t i o n so f t h en e t w o r ki n f r a s t r u c t u r et h a ta r ei n v i s i b l et oa l a y e r 一3m a p p i n gw i l lc o n t i n u et og r o w b e s i d e s ，i n t e m e th a sb e e nt h en e w f o c u so f m u c hw o r ko n t o p o l o g yd i s c o v e r yb e c a u s ei th a sf o r m e d t h eb o a l e n e c kf o rn e a r l ya l l w i d e a r e aa p p l i c a t i o n s ，s e r v e rs e l e c t i o na n dp l a c e m e n t f r o ma b o v e ，w ec a ns e et h a tl o g i c a lt o p o l o g yd i s c o v e r yw i t h i na d m i n i s t r a t i v e d o m a i na l o n ei sf a ra w a yf r o mm e e t i n gt h en e e d so ft h e s ei s s u e s i nt h i sp a p e r ，a l l i m p r o v e dl o g i c a lt o p o l o g yd i s c o v e r ya l g o r i t h mf o ra d m i n i s t r a t i v ed o m a i n i sp r o p o s e d m o r e o v e r ，a u t o m a t i cd i s c o v e r ya l g o r i t h m sf o rp h y s i c a lt o p o l o g yo fa d m i n i s t r a t i v e d o m a i na n dt o p o l o g yo f i n t e m e ta r ed i s c u s s e dr e s p e c t i v e l y f i r s t l y ，t h ef u n c t i o n so f s e v e r a lm a i nn e t w o r kn o d e s ( s u c ha sb r i d g ea n dr o u t e r ) i m p o r t a n t t ot h ed e s i g no ft o p o l o g yd i s c o v e r y a l g o r i t h m s a r ei n t r o d u c e d t h e n c o n u n o nt o p o l o g i e so fn e t w o r k sa r ed e s c r i b e d f o u rt o p o l o g i e sa r ea s s o c i a t e dw i t h l a n s ：b u s ，r i n g ，s t a r ，a n dh y b r i d w a n s a r ec o n n e c t e di ne i t h e ram e s h t o p o l o g yo ra t r e et o p o l o g y a f t e rc o m p a r i n gt h ea d v a n t a g e sa n dd i s a d v a n t a g e so fb a s i ct o o l sf o r t o p o l o g yd i s c o v e r y ，t h e r ec o m e s t h ec o n c l u s i o n ：w es h o u l dc h o o s ea p p r o p r i a t et o o lo r c o m b i n e ss e v e r a lt o o l si nt h ep r o c e s so ft o p o l o g yd i s c o v e r ya c c o r d i n gt ot h er e a l c o n d i t i o no f o b j e c tn e t w o r k t r a d i t i o n a ll o g i c a lt o p o l o g yd i s c o v e r ya l g o r i t h m sw i t h i na d m i n i s t r a t i v ed o m a i n c a no n l yd i s c o v e rt h ed e v i c e st h a th a v ei m p l e m e n t e ds n m p w h i l ef o rt h o s ed e v i c e s t h a td on o ts u p p o r ts n m p ，t r a d i t i o n a la l g o r i t h m ss e e m i n c a p a b l e s ot h ea l g o r i t h m i n t h i sp a p e rc o m b i n et h et o o l so fs n m pa n dp i n g t r a c e r o u t eb a s e do ni c m p w h i c h m a k e st h er e s u l t so f i o g i c a lt o p o l o g yd i s c o v e r y m o r e c o m p l e t e a f t e r d i s c o v e r i n gl a y e r 一2d e v i c e s ，e x i s t i n gp h y s i c a l t o p o l o g yd i s c o v e r y a l g o r i t h m sf o ra d m i n i s t r a t i v ed o m a i nt r yt oi d e n t i f rd i r e c tc o n n e c t i o n sb e t w e e np o r t p e e r s o ft h e s e d e v i c e s ，w h i c hn e e d st o e n s u r et h e c o m p l e t i o no fa f t ( a d d r e s s f o r w a r d t a b l e ) i n f o r m a t i o n c o l l e c t e di n e v e r yn o d e s s n m pm i b st h r o u g h g e n e r a t i n ge x t r at r 墒l ci nn e t w o r k s t h ea l g o r i t h mp r e s e n t e di nt h i sp a p e rn o to n l y “ j u d g e sp h y s i c a lc o n n e c t i o n sb e t w e e np o r tp e e r sd i r e c t l y ，b u ta l s o t r i e st oe l i m i n a t e t h o s e p o r tp e e r s t h a tc a n n o th a v e s i m p l e c o n n e c t i o nr e l a t i o n s h i pf r o mt h es e t c o n s i s t i n go f a l lt h ep o s s i b l ep o r tp e e r s t h i sa l g o r i t h mi sm o r ee f f i c i e n ta n dg a i n s m o r ea c c u r a t er e s u l t s a tl a s t ，a f e ra n a l y z i n gt h es h o g c o m i n g so fb a s i ct o p o l o g yd i s c o v e r ya l g o r i t h m s f o ri n t e m e t ，s u c ha st h eb a c k b o n et o p o l o g yd i s c o v e r ya l g o r i t h md e v e l o p e db yc n r g ( c o r n e l ln e t w o r kr e s e a r c hg r o u p ) ，t h em a i np r o b l e m st h a t n e e dt ob es o l v e di n t o p o l o g yd i s c o v e r yo f i n t e r a c ta r ep r e s e n t e d a f t e r w a r d s ，h e u r i s t i c sf o ri n t e r a c tm a p d i s c o v e r yt h a tc a na d d r e s st h e s ep r o b l e m si nm u c hd e g r e ea r ed i s c u s s e d ，i n c l u d i n g b a s i cp a t hp r o b i n gu s i n gt r a c e r o u t e ，i n f o r m e dr a n d o ma d d r e s sp r o b i n g ，s o u r c e r o u t e d p a t hp r o b i n g f o rc r o s s l i n k sa n da l i a sr e s o l u t i o no fr o u t e r s k e y w o r d s ：a u t o m a t i ct o p o l o g yd i s c o v e r yo f n e t w o r k s ，s n m p ，i c m p s p a n n i n g t r e ep r o t o c o l ，h e u r i s t i c s 硕士学位论文 、1 、i l f r s1 i ! e s i s 第一章绪论 近几年来，计算机网络的发展十分迅速。特别是随着i n t e m e t i n t r a n e t 的快 速发展，网络不仅广泛地渗透到工业、银行、高等院校等各个领域，而且正在 迅速地走入家庭。截至今年一月，我国的上网计算机数约2 0 8 3 万台，上网用户 人数约5 9 1 0 万人，国际出口带宽的总量为9 3 8 0 m 。由此可见，中国计算机网 络的发展速度是惊人的。 当前计算机网络的发展特点是：网络规模不断扩大，复杂性不断增加，网络 的异构性也越来越高。一个网络往往由若干个大大小小的子网组成，并集成多 种o s 平台、包括多个厂家公司的网络和通信设备等。同时，网络中还有多种网 络软件提供各种服务。用户对网络性能及服务质量的要求也越来越高。如果没 有一个高效的网络管理系统对网络进行维护和管理，很难保证为广大用户提供 令人满意的服务。计算机网络管理技术的重要性正是在这种情况下为越来越多 的研究者所重视，并且日益发展成为计算机网络领域的研究热点和技术难点。 网络管理是关于规划、监督、设计和控制网络及网络资源使用的各种活动的 总称。网络管理的功能模型包括故障管理、性能管理、安全管理、配置管理和 计费管理五大模块1 2 , 3 】。一个好的网络管理系统首先需要掌握整个被管网络的拓 扑结构。网络的配置管理是发现和配置网络中对网络管理有意义的设备的过程， 而网络的自动拓扑发现则是配置管理的核心，故障和性能管理的基础，同时它 也是衡量一个商业网管系统成败的重要尺度。因此拓扑发现算法的设计在整个 网管系统的开发中有着举足轻重的地位【4 j 。 1 1 概述 网络的拓扑发现是将搜索到的网络设备及其之间的动态连接关系用图形方 式直观地显示出来，继而网络故障、设备流量以及其它重要的设备信息都可以 在拓扑图上直接反映，使网管人员或其他用户能够及时掌握网络的实时运行状 态。由于当前网络规模日趋扩大，动态性及异构性不断增强，手动输入这些信 息过于繁琐，几乎是一件不可能的事情。这就需要利用网络的一些协议特性自 动地获取网络的拓扑信息，生成网络拓扑图。 拓扑发现的目标，是在对网络本身所做假定尽量少的情况下自动地发现网 络的拓扑结构。具体而言，网络的自动拓扑发现算法应具有p ： 高效性：拓扑发现中的数据采集、获取拓扑信息等过程给网络带来的负 荷应当尽量小； 快速性：拓扑发现算法的设计应当力求最大限度地减少拓扑发现时问： 完整性：应当尽可能地发现网络中的所有设备及其连接关系； 准确性：要求生成的拓扑图与实际的网络拓扑相一致。 需要指出的点是，自动拓扑发现作为网络管理系统的一个基本组成部分 仅仅是其狭义的概念。本文的研究课题虽以网络管理为背景开展，但赋予拓扑 发现以更加广泛的含义：拓扑发现算法的研究并不仅仅局限于一个网络管理域 内，正如本文后面将要介绍的，文中也将讨论广域网( 如i n t e m e t ) 的自动拓扑发 现算法。 i 2 研究意义 准确有效地实现网络的自动拓扑发现有着很大的需求和应用前景。除应用 r 网络的管理和规划之外，网络拓扑信息还可以用于服务器定位：帮助用户确 定自身在网络中的位置，从而决定服务器的位置以及选择可以将时延最小化、 ，j 丁用带宽最大化的网络服务提供商。另外，拓扑信息可以被用于拓扑敏感算法 ( t o p o l o g y a w a r ea l g o d t h m s ) q b ，使得些新的协议和算法能够在得到网络拓扑信 息的基础上改善网络性能。例如，基于拓扑敏感策略和q o s 的路由选择算法， 基于拓扑敏感进程组选项的组通信算法等【5 j 。 除此之外，拓扑发现可以用于大型网络的可视化【6 1 。可视化不仅对于网络管 理来说很重要，它对于从各个不同角度观察网络及其行为以及基于这些观测的 决策制定也都有着十分重要的意义。拓扑发现的个比较新的应用领域是 i n t e r n e t 实际拓扑的模型化研究。这一领域的主要目的是找出主宰i n t e r n e t 建立 和运转的模式及规则【7 】。除此之外，它还旨在研究i n t e m e t 的结构问题。这一领 硕士学位论文 1 、1 2 2 r s 1 l l e s 【、 域的研究是十分有意义的，因为我们可以利用其研究结果建立模拟i n t e m e t 的人 ：网络【8 1 ，用来测试新的协议和路由算法。此时，拓扑发现作为工具不仅仅用于 发现网络的实际拓扑，还用来从网络中提取所需的网络信息。和这一应用比较 相近的一个研究领域是对大型网络( 如i n t e m e t ) 演化方式的研究。此时，我们感 兴趣的不是网络的实际拓扑，而是在两个连续的时间点网络拓扑所发生的变化， 最终找出网络拓扑的变化规律【9 i 。这个规律可以用来预测网络的未来变化。 1 3 面临的困难 至今，网络的自动拓扑发现仍是一个富有挑战性的研究课题，研究出符合 高效性、快速性、完整性及准确性四项目标的拓扑发现算法绝非易事。这是因 为，对用户的透明性( u s e r t r a n s p a r e n c y ) 是网络技术取得成功的一个重要因素， 网络本身没有已经实现的专门针对自动拓扑发现的任何机制。拓扑发现工具的 缺乏使得人们有时不得不采用网络的一些比较原始的工具，如p i n g 和t r a c e r o u t e 等。另外，随着网络规模的日益扩大，当前拓扑发现算法的执行可能要耗费几 天甚至几个月的c p u 时间，而网络实时动态性的增强可能使得一个算法执行若 干时间后产生的只是过时的拓扑图而已。 不同的管理机构管辖着网络的不同部分，例如i n t e m e t 就是由许多异构的自 治系统( a s ) 组成，这些异构网络内部的硬件类型和运行软件都有可能不同。并 且，不同的自治系统由不同的组织管理，它们有着各自的管理规则和安全策略， 有的过滤甚至屏蔽了一些拓扑发现工具的搜索，这给网络的自动拓扑发现造成 了一定的难度。同时，这也要求拓扑发现工具必须具有一定的通用性，能够发 现不同自治系统的拓扑结构。 即使在同一个自治系统中，同样有问题存在。如今，网络中提供服务的技 术多种多样，例如a t m 、i e e e8 0 2 协议等等。在这种情况下，采用通过简单网 络管理协议s n m p 对私有m i b 库进行访问的方法或许可行，但是这种方法不具 有通用性。另外，还有一些网络采用i p 协议以外的其它协议( 如n o v e l ln e t w a r e 的i p x s p x ) ，这使得网络的自动拓扑发现愈发显得困难。 硕士学位论文 、1 、x le r 5t i i e s l g 1 4 需要明确的问题 网络自动拓扑发现涉及到的问题比较多，但总的来说，主要有以下四个方 面的问题需要首先明确： 第一，确定拓扑发现的规模。计算机网络按照分布距离可以划分为局域网、 城域网、广域网等等。不同规模的网络，其互连设备、所需拓扑信息的详略、 搜索开销的大小、发现速度的快慢等都会有所不同。因此，网络的拓扑发现应 当针对不同规模的网络，采用不同的协议工具设计算法。本文将分别讨论网络 管理域内以及i n t e m e t 的自动拓扑发现方法。 第二，确定拓扑发现针对网络哪一层以及采用的什么网络协议。只有确定 了拓扑发现针对的网络层次和协议，才能明确到底哪些信息需要被采集。t c p i p 网络的i p 层。通常是拓扑发现的首选位置，绝大多数的网络都支持i p 协议，而 a 简单网络管理协议s n m p 已经成为事实上的工业标准，使用s n m p 的算法可实 现性较强，所以传统的算法基本上都是针对管理域内的i p 层发现网络的逻辑拓 扑。但是在异构网络中，二层设备( p u 交换机、网桥和h u b ) 越来越多的分布在 l p 网络中形成微子网段，以提供更多的带宽。因此，越来越多的拓扑信息对于 传统的逻辑拓扑发现是不可见的。网络层拓扑发现只能揭示i p 网络小部分的互 连关系，不能体现二层网络节点之间的复杂互连关系。为了发现网络更加详细 的拓扑结构( 如网络的物理拓扑) ，网络的多层自动拓扑发现是必不可少的，本文 将分别讨论i p 网络管理域内逻辑拓扑和物理拓扑的自动发现方法。 第三，就网络拓扑信息的采集而言。应当确定是采用被动监测技术还是主 动探测技术【1 0 1 。主动探测技术是通过网管工作站主动向所有管理网络发送探测 包，并采集返回的信息，进行分析最终形成网络拓扑。这种技术的优点是能够 比较快地形成整个网络的拓扑，但是会给网络增加额外的流量。被动监测技术 是通过在所有被观测的网络中都加入一个探测器，由它来采集信息，并发送到 网管工作站形成拓扑。这种技术的优点是除了其本身向网管工作站递交拓扑信 i p 层对应o s i 参考模型的网络层在本文中两种说法是通用的本文中的逻辑拓扑发现是针对于网络 的i p 层进行的 4 硕士学位论文 、1 、引e r sl l i e s i s 息以外，不产生额外的流量，网络负担小。但缺点是由于通过各个探测器被动 地监测网络上的分组交换信息，所以需要花费较长的时间才能收集到足够的信 息来形成最后的网络拓扑，而且由于要将探测器安装到所有涉及的网络中，这 对于一个大的网络来说是不太实际的。出于这方面考虑，本文所讨论的自动拓 扑发现方法采用主动探测技术。 第四，就拓扑信息的收集而言，应当确定采用何种工具收集信息( 基本工具 的详细介绍见第三章) 。目前，信息收集的方式大致可以分为两种：种采用简 单网络管理协议s n m p 来收集网络的拓扑信息，这种方式比较高效，但并不是 所有的网络设备均支持s n m p 协议，另一种信息收集方式采用比较通用的网络 协议，如基于网际控制报文协议i c m p 的p i n g 、t r a c e r o u t e 等。它们建立于i p 层的基础之上，被所有的i p 网络和设备所支持。由于当今网络情况比较复杂， 本文讨论的管理域内网络层发现算法将这两种方式结合使用。该算法在具有更 大适用性的同时，也可以发现更多的网络设备。另外，正如本文后面将要介绍 的，由于i n t e m e t 的复杂性与特殊性，i n t e m e t 的拓扑发现只能采用后一种方式 进行。 1 5 国内外研究现状 国外早期的i p 网络自动拓扑发现工作l i ”j 均是利用s n m p 等协议发现管 理域内的逻辑拓扑，即描述路由器与路由器。路由器与子网以及子网内部主机 相互连接关系的i p 层拓扑。另外，许多商业网络管理系统，如惠普公司的 o p e n v i e w 03 1 、i b m 公司的t i v o l i 】、达特茅斯的i n t e r m a p p e r l l 5 】等，其拓扑发现 也都是采用基于s n m p 协议的网络层自动拓扑发现算法。 近期，国外的研究工作在物理拓扑自动发现【l “2 0 】和广域网( 如i n t e m e t ) 的拓 扑发现方面已经开展了一些。最近，i e t f 在意识到物理拓扑发现的重要性后， 指定了物理拓扑s n m pm i b 库【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 ) z j 以及相关工具，但是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 软件1 2 3 1 5 1m i c m m u s e 公司的n e t c o o l l 2 4 1 据称可以支持物理拓扑的自动发现，但这 些公司的独有技术是我们不可得知的。 相比较而言，i n t e m e t 拓扑发现研究的相对滞后已经对几乎所有的广域阿应 用、服务器选择和定位造成了瓶颈。这使得i n t e m e t 的拓扑发现和性能衡量日益 受到重视。确定广域网拓扑结构常用的方法是使用b e n c h m a r k s 【2 ”测量通过网络 拓扑的带宽。t o p o l o g y d 是一个早期的使用这种方法进行拓扑发现的项目，生 成了网络的最小生成树视图f 2 6 j 。最近，项目i d m a p s l 2 7 ，2 ”以及t h e i l m a n n 和 r o t h e r m e l l 2 9 】等人致力于生成网络的距离图( n e t w o r kd i s t a n c em a p ) ，它是i n t e m e t 网络拓扑的一种更加灵活的表示。一种更加常用的方法是使用底层工具 t r a c e r o u t e 进行i n t e m e t 拓扑发现。美国康奈尔大学网络研究组( c n r g ) u ”j 、南 加州大学信息科学学院s c a n 研究组【3 2 】，加州柏克莱大学计算机系【3 3 】、卡内基 梅隆计算机学院以及朗讯贝尔实验室【3 4 - 3 6 1 均进行了部分这方面的研究。互联网 数据分析协作联盟c a i d a l 3 7 1 自1 9 9 8 年起开始了它的宏观拓扑项目( m a c r o s c o p i c t o p o l o g yd i s c o v e r yp r 0 3 i e c t ) t 3 ”，s k i t t e r l 3 9 ，4 0 】是c a i d a 开发的这方面的主要工具， 用于i n t e m e t 拓扑信息和往返传输时间( 1 a t e n c y r t t ) 数据的收集。 在国内，许多高校都有网络自动拓扑发现方面的研究，主要有华中科技大 学【4 4 3 1 、上海交通大学1 4 4 ，4 ”、西安交通大学4 6 4 ”、中国科技大学等5 0 1 。但 是这些研究主要集中于发现i p 网络管理域内的逻辑拓扑。文献【4 1 】虽然对虚 网( 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 库，通用性显得不够。 郑海【4 9 j 等人的物理拓扑发现算法需要通过在网络中产生额外流量来保证网络中 每一个节点地址转发表的完整。因此可以说，国内在网络物理拓扑发现方面的 研究还刚刚起步，而国内在广域网( 如i n t e m e t ) 拓扑发现方面的研究到目前为止 几乎还没有发现。本文在讨论网络管理域内逻辑拓扑发现算法的同时，也将对 管理域内的物理拓扑发现以及广域网i n t e m e t 的自动拓扑发现方法进行一些探 讨。 硕士学位论文 、1 、s le r s - i i e s p i 1 6 本文的主要工作及章节安排 本文在给出种改进的管理域内逻辑拓扑自动发现算法及其系统实现之 后，主要致力于解决管理域内物理拓扑自动发现的难题以及对i n t e m e t 的自动拓 扑发现方法进行探讨。 全文的章节安排如下： 第一章概述网络自动拓扑发现的相关理论。简述了网络自动拓扑发现的含 义及目标，阐明了网络拓扑发现的研究意义，指出目前网络拓扑发现技术面临 的困难和算法设计需要首先明确的问题。最后，在全面系统地总结现有成果的 基础上，说明了本文的主要工作和章节安排。 第二章主要介绍网络的拓扑结构。首先阐述网络互连设备网络节点( 重 点是网关和路由器) 的主要功能，然后介绍常见的局域网拓扑结构( 总线型、环形、 星型、混合型) 和广域网拓扑结构( 树形及网状) 。 第三章讲述拓扑发现常用的协议和工具：包括s n m p 、i c m p 、t r a c e r o u t e 、 d n s 、a r p 及其它工具。然后，对主要工具进行了比较分析，指出在实际使用 这些工具时应当注意的问题。 第四章主要描述一种改进的管理域内逻辑拓扑自动发现算法的详细设计。 讨论了算法的实现细节以及整个拓扑发现系统实现过程中的关键问题。 第五章主要讨论管理域内物理拓扑的自动发现算法。分别介绍了网络节点 的发现技术和设备端口连接的判定方法。最后，将该算法进一步扩展到对虚网 ( v l a n ) 进行处理。 第六章通过分析康奈尔大学c n r g 研究组主干网拓扑发现基本算法的不足 之处，指明广域网拓扑发现算法需要解决的主要问题，并对i n t e m e t 的启发式拓 扑发现算法进行了探讨。 第七章对全文进行总结，概括本文的主要工作及成果，并指出今后有待于 进一步开展的工作。 第二章网络的拓扑结构 拓扑学是数学的一个分支，研究几何图形在连续改变形状时还能保留不变 的一些特性。它只考虑物体之间的位置关系，不考虑它们的大小及距离。一个 基本的网络可以被看作由网络节点和链路组成。计算机网络领域中，拓扑反映 了网络节点的几何排列或布局以及网络节点之间的连接关系。网络节点是网络 的基本互连设备，如交换机，路由器等等。网络节点应区别于主机，主机通常 只是指网络中的计算机终端设备。链路将两个网络节点相连，提供它们之间信 息传递的通路。 网络拓扑代表网络中直连对等实体的相互连接关系，可以被划分为物理拓 扑和逻辑拓扑。对于物理拓扑，对等实体是指由物理传输链路连接的网络设备 端口。网络的物理拓扑在不同的网络抽象层上，对应于多个逻辑拓扑。例如， 对于o s i 参考模型的网络层，对等实体是指路由器或者主机。物理拓扑看起来 相似的网络，可能在逻辑拓扑上有很大的不同。 本章首先阐述网络基本互连设备的功能，重点介绍对后续章节的拓扑发现 算法有重要意义的二层设备网关和网络层设备路由器。随后，介绍几 种主要的局域网和广域网拓扑结构。 2 1 网络节点 网络节点是指网络中的互连设备。它可以是链路两端的设备，如集线器 ( h u b ) 、路由器( r o u t e r ) 等，也可以是连接网络的设备，如连接局域网的网桥 ( b r i d g e ) 、连接自治网络的网关( g a t e w a y ) 等。图2 1 是网络中不同网络节点的分 布情况及作用的示意图。 图2 1网络节点的分布示意图 集线器是用来构建局域网的网络设备。 交换枧( s w i t c h ) z 作在o s i 参考模型的物理层。它只将从一个端口进来的报 文分组传递到正确的端口输出，不对输入数据的格式做任何操作。其功i i i i 图 2 - 2 ( a ) 所示。 网桥。可以被看作工作在数据链路层的智能分组交换机，用来连接局域网。 其功能如图2 - 2 ( b ) 所示。它除了具有交换机的功能以外，还有过滤分组的功能。 智能网桥还有自学习的功能。它维护一张地址转发表，记录分组的源地址、目 的地址、接收端口和转发端口等信息。随着时间的增长，它获得某个分组应当 被转发到哪个特定端口的知识。如果这张表中没有存储某个分组的目的地址及 转发端口，网桥将其扩散到所有的端口，一旦发现某个目标节点对该分组做出 了回应，它立即将此新发现的转发项记录在地址转发表中。那些长期没有被使 用的转发项将会被定期清除掉。 桥接网络( b r i d g e dn e t w o r k ) 使用两种不同的路由算法：用于连接以太网的生 成树( s p a n n i n g t r e e ) 协议和用于连接令牌环网的源路由( s o u 础：r o u t i n g ) 算法。它们 分别对应两种不同的网桥和拓扑结构：透明网桥连接的树形结构和源路由网桥 连接的网状结构。 实际的网络主要由交换机组成，它是一种重要的有多个端日的网桥“交换机”和“网桥”在实际使用 中经常被互换，在本文的以下讨论中对它们也不加以区分 硕士学位论文 、1 、s ie r s 1 i i e s i 由于备用连接的存在，网络的两个节点之间可能存在多条路径，从而在物 理拓扑结构上产生环。环的产生可能导致报文分组的重复发送。生成树协议不 启用那些造成环的连接，从而维持整个拓扑的树状结构。透明网桥维护和存储 一张目的地址转发端口相对应的表。当收到一个分组，透明网桥只将其发送到 这个分组的目的地址所对应的转发端口。因此透明网桥不知道任何关于目的局 域网的信息，它只知道负责这个目的地址的转发端口和对应的相邻网络节点。 同样的，只有相邻节点知道其存在，对于其它网桥和局域网来说它是不可见的。 a t m a t ms w i t c h ( a ) s w i t c h a t m l o c a l l n 一r 一1 = = = = = = = = = = 。爿。* - r 二e 瓤e r r i a l l a i q e t h e r n 。e 。t 三哑止薹竽掣咖赠三e t h e z r 。a 。1 p 虻k e t s b r j d 零 r 脚估 ( b ) b r 姆 l o c a l n e t w o r k i pp a c h t s i p n e t w o r k p a c k e t s 匝e i 蓟三蜘制 r 。e t s 瞪 l 。 - “l j or m i o m e r ( c ) p o u t e r 匡i 重量强 g a t e w a y ( d ) g a t e w a y 图2 - 2 基本网络节点功能示意图 x2 5 n e t w o r k p a c k e t s 在源路由网桥连接的网络中，首先，为了获得到目的节点的路由信息，源 节点将广播分组扩散到整个网络，从而源节点知道通往目的节点的整条路径。 它将路径信息加入到传送的分组中，由分组自身携带路由信息。因此，分组的 选路无需任何中间节点的参与。 1 0 硕士学位论又 、1 刚f r s t l i e s i s 两种网桥比较起来，透明网桥更加健壮和可靠，源路由网桥速度更快。但 是源路由网桥连接的网络中，一旦网络结构发生了变化，整个网络的地址转发 表都需要被重新广播和发现一遍，因而处理起来比透明网桥复杂。 路由器和网关。是工作在网络层，执行路由功能的设备，主要用于构建主干 网，它们的功能分别如图2 - 2 ( c ) 和( d ) 所示。路由器除了有交换机和网桥的基本功 能以外，还有路由功能，可以将分组朝着其路由方向输出到恰当的端口。路由 器存储和维护一张定期更新的路由表，存放一个数据报由源节点到目的节点的 可能路由( 既包括完整路由，也包括路由的下一跳地址) 。单点传送0 3 n i c a s t ) 方式 f ，它将分组转发到通往目的地址的一个端口：广播( b r o a d c a s t ) 或多播( m u l t i c a s t ) 的方式下转发到多个端口。另外，路由器使用广播机制的地址解析协议 a r p 似d d r e s sr e s o l u t i o np r o t o c 0 1 ) 确定通往目的地址的本地端口。路由器连接的 网络允许拓扑结构中出现环，因而这种网络在路由器或其连接出现故障时，具 有一定的均衡流量和自恢复功能。不是所有的网络都采用相同的协议，网关除 有路由功能以外，还可以将一种协议格式转换为另一种协议格式，因此能够被 用来连接完全自治的两个网络( 可以有不同的路由算法、协议、管理策略等等) 。 2 2 局域网的拓扑结构 局域网( l a n ) 通常由一个管理域内距离比较近( 如一栋建筑内或者校园网内 数栋建筑之间) 的数据终端设备( d t e ) 连接而成的网络。它通常被定义为一个单 独的广播域，主要使用h u b ，网桥或交换机等连接同一个网段内的所有设备。处 于同一个局域网内的网络节点之间可以不通过路由器直接进行通信：而处于不 同局域网段内设备之间的通信常常需要通过路由器。局域网常有的拓扑结构有 四种：总线形、环形、星形和混合形( 通常是星形与总线形或者星型与环形相混 合) 。不同结构的网络采用不同的协议：总线形结构的局域网采用以太网协议， 网荚从学术上可指任意层的互连设备但通常情况下指代网络层互连设备本文将路由器和同关都看作 工作在网络层有路由功能的网络设备，并不考虑网关的协议转换功能，因此下文中对此也不加以区分 1 1 而令牌环和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 晌c e ) 是环形结构。集线器连接的局 域网一般是星形结构。 2 3 广域网的拓扑结构 广域网f w a n ) 与局域网相比组成网络在地理位置上通常相隔较远，如 i n t e m e t 就是全球范围的互联网络。广域网的一般拓扑结构是网状或者树形结构。 网状结构是i n t e m e t 最常见的拓扑形式，但是在网状结构的网络中，由某一网络 节点发出的广播消息，可能会被其所有相邻节点重新广播出去。以此类推，就 有可能造成网络中的洪泛( f l o o d i n g ) 和分组传送环路( l o o p i n g ) ，因此这种网络应 当小心编址。网状网络通常的互连设备是路由器。树形网络通常从一个头节点 月= 始，不断分支出其它网络节点，从而形成树形结构。这种网络结构中不允许 闭环的存在，实现起来比网状结构简单，通常由链路层设备网桥互连而成。 2 4 小结 在讨论网络的自动拓扑发现技术之前，本章介绍了基本网络节点的主要功 能，重点介绍对管理域内逻辑拓扑发现算法有重要意义的的网络层设备路 由器以及对物理拓扑发现算法很重要的链路层设备网桥。然后介绍了常见 的局域网拓扑结构：总线型、环形、星型和混合型，以及广域网拓扑结构：网 状和树形。 硕士学位论文 1 “f ：l t s “比s i s 第三章拓扑发现基本工具 获得网络拓扑最简单的办法可能莫过于让网络管理员根据实际网络手工绘 制出拓扑图。但是，现实生活中网络节点个数是动态增长的，而且网络的不同 部分可能由不同的管理机构掌管，其中某一机构多数情况下无法获悉其它机构 所管理网络的拓扑结构。因此，很有必要借助一定的协议和工具对网络的拓扑 结构进行自动发现。 本章首先介绍自动拓扑发现的基本工具，包括s n m p 协议、i c m p 协议、 t r a c e r o u t e 、d n s 以及a r p 等其它工具，然后通过对其中主要工具利弊的比较 分析，我们有理由认为在实际拓扑发现过程中应当根据待发现网络的具体情况， 选用恰当的拓扑发现工具，才能更大程度发挥它们的优势，获得更好的拓扑发 现效果。 3 1s n d p 简单网络管理协议s n m p 的协议规范设定了网络管理站( m a n a g e r ) 和代理 f a g e n t ) 之间交换管理信息的方式。s n m p 的体系结构1 5 i 】见图3 - 1 。s n m p 是基于 无连接通信子网的，底层的主要协议有用户数据报协议u d p 和网际协议i p ，因 此不能保证数据传递的可靠性，然而事实上大多数的信息都是传递无误的。 s n m p 中定义了5 种基本的协议数据单元( p d u ) ：g e t - r e q u e s t 。g e t - r e s p