（通信与信息系统专业论文）ip网络拓扑发现技术：研究与实践.pdf

摘要 摘要 随着网络规模的日益膨胀，普及范围的进一步扩大，得到一个完整准确的网 络拓扑结构图对于网络管理、网络优化、定位故障等应用越来越重要。国内在网 络拓扑发现技术方面的研究仍处于初级阶段，因而其必要性和紧迫性不容忽视。 该论文来源于国家自然科学基金重点项目“基于网络探测的i p 网络拓扑发现和性 能分析”。通过对于一些文献资料的研读，分析和总结，提出了新的思想和方法， 并进行了大量的实践工作，在该项研究取得了一定的进展。 论文的主要内容包括：系统地总结、分析并比较了各种网络拓扑发现算法； 总结了各种组播网络的拓扑发现算法，在b l t 算法的基础上提出了h b l t 算法， 该算法结合接收节点和源节点之间的跳数及接收节点处的丢包分布，通过仿真汪 明了该算法能有效改善原算法的效率和准确率。接着，提出了分布式拓扑发现的 框架和分布式的探测过程，该探测框架是建立在分布式网络探测d n m a i 的基础之 上，采用服务器一客户机模型。最后，总结了两类a dh o c 网络的路由协议体系， 论述了两种a dh o c 网络拓扑发现算法。 关键词：拓扑发现组播网络分布式a dh o c 网络 a b s t r a c t a b s t r a c t w i t ht h es c a l eo fi n t e m e t se x p l o d i n gi nt h e s ey e a r s ，t h e r e f o r ei t sm o r ea n dm o r e i m p o r t a n t t og e tac o m p l e t ea n da c c u r a t et o p o l o g ys t r u c t u r em a p ，w h i c hi su s e di nt h e s e f i e l d ss u c ha sn e t w o r km a n a g e m e n t ，n e t w o r ko p t i m i z a t i o na n dt r o u b l es h o o t i n g t h e r e s e a r c ho nt o p o l o g y d i s c o v e r yt e c h n i q u e i si ni t s i n f a n c y i n h o m e ，s o i t s v e r y n e c e s s a r yt oc o n s i d e ri t sn e c e s s i t ya n du r g e n cy t h i sp a p e rs t e m sf r o m t h en a t i o n a lk e y p r o j e c t “s t u d yo f i pn e t w o r k t o p o l o g yd i s c o v e r ya n dp e r f o r n l a n c ea n a l y s i sb a s e do n n e t w o r kp r o b i n g w h i c hi s s p o n s o r e db yn s f c ，n e w i d e a sa n dm e t h o d sh a v eb e e n p r e s e n t e da n dl a r g e a m o u n to fw o r kh a sb e e np r a c t i c e d t h r o u g hr e f e r r i n g t o l a r g e a m o u n to fm a t e r i a l sa n dc e r t a i ni m p r o v e m e n th a sb e e no b t a i n e do nt h i sp r o j e c t f i r s t l y , a l l - a r o u n dc o m p r e h e n s i o na n ds y s t e m i c c o n c l u s i o no fn e t w o r kt o p o l o g y d i s c o v e r yt e c h n i q u ei sg i v e n s e c o n d l ys e v e r a lk i n d so ft o p o l o g yd i s c o v e r ym e t h o d s o n m u l t i c a s tn e t w o r kh a v eb e e na n n y z e d h b l ta l g o r i t h mi s p r e s e n t e db a s e do nb l t a l g o r i t h m i tc o m b i n e st h eh o p - c o u n tb e t w e e nt h es o u r c ea n dt h ed e s t i n a t i o n sw i t ht h e p a c k e t s l o s sd i s t r i b u t i o n i tp r o v e st h a t t h e a l g o r i t h mc a ne f f e c t i v e l yi m p r o v et h e p r o f i c i e n c ya n dt h ea c c u r a c yo f t h eo r i g i n a la l g o r i t h mt h r o u g hs i m u l a t i o n t h i r d l yt h e d i s t r i b u t e dt o p o l o g yd i s c o v e r yf r a m e w o r ka n dt h el a y e r e dp r o b i n gp r o c e s sa r ep r e s e n t e d ， w h i c ha r eb a s e do nt h ed i s t r i b u t e dp r o b i n gf r a m e w o r kd n m a iu s i n gt h em o d e lo f s e r v e r c l i e n t f i n a l l y , i td e a l sw i t ht w ok i n d so fa dh o cn e t w o r kr o u t i n gp r o t o c o l sa n d t w o t o p o l o g yd i s c o v e r ya l g o r i t h m s o na dh o cn e t w o r k k e y w o r d s ：t o p o l o g yd i s c o v e r y m u l t i c a s tn e t w o r kd i s t r i b u t e da dh o cn e t w o r k 创新性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的 研究成果。尽我所知，除了文中特i i i i 以标注和致谢中所罗列的内容以外，论 文中不包含其他人已经发表落撰写过的研究成果；也不包含为获得西安电子科 技大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对 本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 本人签名 篁垦笪 日期：卯d 印， 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研 究生在校攻读学位期间论文工作的知识产权单位属于西安电子科技大学。本人 保证毕业离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科 技大学。学校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以 公布论文的全部或部分内容，可以允许采用影印、缩印或其它复制手段保存论 文。 本人虢塑墨笪 导师签名 日期：! ! 竺! ! 日期：乡一f ，j 第一章引言 第一章引言 随着网络规模的膨胀和复杂度的增加，网络管理在今天的网络环境中起着愈 发重要的作用了。网络测量是现有网络管理技术的有力补充。如通过网络测量建 立网络的业务模型( s e r v i c em o d e l s ) 管理网络，也可提供对s l a ( s e r v i c el e v e l a g r e e m e n t ，服务等级协议) 的管理。又如通过测量发现并改正病态路由，对网络 选路制定策略，在网络破坏后的网络资源自组织等。检测网络是否被他方探测、 识别探测者身份和探测意图( 即是入侵探测，i n t r u s i o nd e t e c t i o n ) 的网络安全 管理领域的重要问题之一，实际上是网络测量( 探测) 与反测量( 探测) 的斗争 过程。一个好的网络管理系统首先就是要掌握整个管理网络的拓扑结构，因此作 为网络管理的重要组成部分的网络拓扑发现对于异构的、多样的、和多变的网络 来说日益显示出其重要性。通常网络的拓扑是通过工具由网络管理员输入到网络 管理系统中的，这对于一个规模小且变化少的网络还是可以的。但是对于一个规 模较大的网络，网络的拓扑结构经常在发生一些变化。这时还采用手工的方法已 经不太现实了，所以迫切需要一个方法能够自动生成网络的拓扑结构并且动态的 反映网络的拓扑变化情况。 本章概述了网络拓扑发现技术的概念、特点、目标及其应用。 1 1 网络拓扑发现概述 计算机网络是由各种各样不同的实体组成，这些实体相互作用得以给终端用 户提供各类服务。实体可以用软件或者硬件来实现，在实际网络中这些实体指： 调制解调器，路由器，应用服务器，网桥，交换机，传输链路及相关协议等。任 何一个实体都会影响到所提供的业务是否正常运行，进而对终端用户造成直接的 影响。 拓扑发现( t o p o l o g yd i s c o v e r y ) 是指发现网元( n e t w o r ke l e m e n t ) 并确定网元之 间的互连关系，包括互连设各( 如路由器、网桥、交换机等) 、主机和子网。网络拓 扑图是拓扑结构的可视化表现形式。拓扑发现作为配置管理和故障管理中的一项 重要功能，是网络管理的一个重要组成部分。拓扑发现生成的网络拓扑图 ( n e t w o r k t o p o l o g y m a p ) 可以帮助网络管理员掌握网络拓扑结构，迅速定位故障发生 地点，确定故障影响的范围，还可以成为发现网元并调用其它管理功能模块的共 同出发点。拓扑发现同时也是衡量一个商业网络管理系统成败的重要尺度，在整 个网络管理系统的开发中占有相当重要的地位。 网络拓扑发现涉及到的问题比较多，但是总的来说，要对一个网络实现拓扑 发现，主要有四方面问题需要明确： i p 网络拓扑发现技术：研究与实践 ( 1 ) 确定这个技术针对网络层次的哪一层及什么协议。这是因为只有确定了网 络的层次和协议，才能明确到底什么样的信息要被采集，才能使这项技术具有比 较好的适应性。因而有第二层( m a c ) 物理拓扑发现和第三层拓扑发现之分。目 前随着i n t e r n e t 的普及，大多数的网络都采用t c p i p 协议，几乎所有的设备都支 持i p 协议，所以这里针对冲层相对较好。 ( 2 ) 确定是采用被动监测技术还是主动探测技术来实现网络拓扑信息的采集。 这两项技术相比较：被动监测技术是通过在所有观测的网络都加入一个探测器， 由它来采集信息，并发送到网络管理主机来形成网络的拓扑结构。这种技术的优 点是本身除了向管理主机递交各个网络的拓扑信息，不产生额外的流量。所以产 生的网络流量比较小，网络负担小。缺点是由于是各个探测器被动地通过收集各 自网络中交换的信息。所以需要花费长的时间才能收集到足够的信息来形成最后 的网络拓扑。并且由于要将探测器安装在所有涉及的网络中，这是对于一个大的 网络来说是不太实际的。主动探测技术是通过网络管理主机主动向所有管理网络 发送探测包。并采集返回的信息，进行分析最终形成网络的拓扑。这种技术的优 点是：能够比较快的形成整个网络的拓扑。缺点是需要产生的流量比较大，并且 对于一个十分慢的网络不太适合。 ( 3 ) 确定采用何种方式收集信息一种是采用网络管理信息协议( 如s n m p ) 来收 集网络的信息。但是网络上的设备十分繁杂，不是所有的设备都支持这些管理协 议而且需要对涉及到的网络逐个进行配置。一种方式就是采用一种通用的协议 来实现对于网络信息进行采集，这样局限性较小，如基于i c m p 等协议来实现的。 它们是建立在i p 层的基础上的，被所有的i p 网络和设备支持，可靠性比较高，且 省去了大量的手工配置。 ( 4 ) 确定网络拓扑发现的目标及发现程度。这两点均跟实际网络业务需求息息 相关，但不管采用哪种协议和工具，网络拓扑发现的最终目标是得到一个快速、 完整、正确和高效的网络拓扑发现算法或拓扑发现工具。所谓快速即能够实时地 发现网络拓扑的结构和变化情况，且保持数据的内部致性。一个不能跟上网络 实时变化的拓扑发现算法适用范围是受限的；而完整性指的是在出现最少错误概 率的情况下有效、尽可能多地正确发现一个特定网络内的大部分主机和路由器： 正确性即算法应尽力保证拓扑发现结果正确，尽量不出或少出错误：高效性即算 法不应消耗过多的网络资源，仅给网络增加尽可能小的负载。对网络拓扑结构的 发现程度可根据具体的需求定，对一个无特殊要求的网络进行拓扑发现，发现路 由器和主机级即可。 ( 5 ) 采用单点式的拓扑发现还是分布式的拓扑发现。分布式拓扑发现是通过建 立服务器和客户机之间的连接，在服务器端起动拓扑发现过程，将各个探测点处 收集到的拓扑信息发送到客户端，然后在客户端对这些信息进行收集和整理，最 第一章引言 后得到整个网络完整的拓扑结构。 拓扑算法有两个重要的指标，一是性能，就是拓扑搜索的速度；二是获得网 络拓扑结构的完备性，完备性就是指拓扑搜索得到的网络拓扑结构是否能真实反 映网络结构的实际情况，但由于路由信息本身的不完备性等其它原因，拓扑搜索 算法很难得到真实的拓扑结构。这两个问题恰恰是拓扑搜索算法中的难点。 1 2 网络拓扑发现技术的应用 拓扑发现主要应用于以下各个方面： 1 ) 模拟网络为了模拟实际网络，分析网络性能、合理扩容和优化网络，必 须先得到该网络的拓扑结构： 2 ) 网络优化网络拓扑信息可以帮助网络管理者确定是否需要增加新的路由 器，当前硬件是否配置正确，并发现网络中的瓶颈所作和失败的链路，进行网络 优化。 3 ) 用户接入方式的选择网络拓扑信息可以帮助用户确定自身处于网络中的 位置，从而决定服务器的位置以及选择哪一个网络服务提供商可以将网络时延最 小化、可用带宽最大化； 4 ) 研究拓扑敏感算法一些新的协议和算法可以在得到网络拓扑信息的基础 上改善网络性能，例如：基于拓扑敏感策略和q o s 的路由选择算法与基于拓扑敏 感进程组选项和组通信算法： 5 ) 确定镜像服务器的位置根据拓扑信息合理配置镜像服务器的位置以最大 可能减少时延，解决瓶颈问题； 6 ) 实行网络服务管理例如：m a i l ，f c d ，w e b ，s n m p ，d n s ： 7 ) 统计数据的采集及关联分析； 8 ) 网络战对于信息作战而言，获得敌方的网络拓扑及与拓扑相关的信息可 以灵活有效地组织攻击。 1 3 网络拓扑发现技术的发展现状 有许多研究机构和公司着力于发现网络拓扑结构的研究，如c a i d a ”， r 4 l a n r t 2 1 ，j a s p v i ! ”，g e o b o y “，o t t e r i ”，s k i t t e r ”，m 1 n c 0 1 。m 的i n t e m e tm a p p i n g c 4 】 项目。大多数网络管理工具都具有拓扑发现的功能，如h p o p e n v i e w i b m s t i v o l i 等，它们大都依赖于简单网络管理协议( s n m p ) 这一标准协议。而s n m p 并不 是一种通用的协议，基于其的拓扑发现受到权限的限制，没有权限便不能访问其 支持的m i b i i 信息，也便无法进行拓扑发现。 i p 网络拓扑发现技术：研究与实践 以太网的规模越来越大，发现物理拓扑( 即第二层拓扑，交换机、路由器与 主机之间的连接关系) 引起一些公司的注意，如c i s c o 开发的c d p ( c i s c od i s c o v e r p r o t o c o l y 、b a y 的( n e t w o r k so p t i v i t ye n t e r p r i s e ) 、i n t e l 、f l u k e ( l a n m a p s h o t ) 等， b e l l 实验室【5 】、c a r n e g i em e l l o n 大学1 以及我国的研究人a t 1 都在研究物理拓扑发 现方法。同时i e t f ( i n t e m e te n g i n e e r i n gt a s kf o r c e ) 也制定了物理拓扑的管理信 息库( b r i d g e m i b ) 7 1 1 8 】 1 4 论文承担任务及贡献 该论文题目属于国家自然科学基金重点项目“基于网络探测的i p 网络拓扑发 现和性能分析的研究”，为三所高校联合申请的项目，预期四年完成。该项目主要 的内容为：研究碑网络探测及性能分析技术包括网络性能、拓扑、无线i p 的探 测和分析原理及技术、网络性能评价及分析预测技术，探讨基于网络探测的新技 术和新应用，研究大规模数据中解析网络和业务特性、网络和信息安全的理论及 方法，架构以探测测量监控为一体的综合网管体系，保证i p 网络安全有效运行， 为发展有自主知识产权的网络探测体系及网络新方法奠定基础。我校负责i p 网络 探测的体系结构、i p 网络探测的原理及方法、i p 网络流及安全性分析、i p 网络拓 扑发现、无线i p 探测方法和技术的研究五部分。 i p 网络拓扑发现是该项目最基础和最重要的部分，得到一个完整准确的网络 拓扑结构图可以使网络探测、性能分析、网络流及安全性分析等工作更加容易、 高效地进行。该部分计划完成以下的内容：通过p i n g 发送i c m p 分组，并用 t r a c e r o u t e r 跟踪路由，获得i p 地址集，判断相应的设备，并由路由器的接口地址 和网络掩码，可得网络地址及其范围，同时可由d n s 判断多目主机地址，进而形 成拓扑：也可通过访问m m 中的路由表信息实现网络拓扑自动搜索：选择构造依 据时还可以选用网络性能参数如链路时延、丢包率等，采用某种算法推算网络拓 扑结构；进一步探讨分布式网络拓扑发现和物理层的拓扑发现：最后讨论无线网 络的拓扑发现。 本论文主要的工作及贡献为： 1 系统地总结、分析并比较了各种网络拓扑的发现算法： 2 分析了组播网络的特点，在总结以往的组播网络推算算法的基础上提出 了一种新的基于丢包的拓扑发现算法( h b l t ) ，并分别利用o p n e t 和 n s 对该算法进行了仿真。建立了组播树模型，利用该算法得到了该组 播树的拓扑结构。 3 基于单点式的拓扑发现算法，构造了分布式拓扑发现的框架结构，并用 一个实例说明了其工作过程，得到了分布式网络的拓扑结构。 第一章引言 4 分析了a dh o e 网络的特点，给出两类路由算法的体系框架，详细论述了 两种拓扑推算算法。 本论文的内容是这样安排的：第二章介绍了网络拓扑发现技术可采用的协议、 工具等，系统地总结了基于不同协议或工具的拓扑发现算法、物理层拓扑发现算 法、无线网络的拓扑发现算法；第三章详细论述了组播网络的拓扑发现。首先总 结了已有的拓扑发现算法，并将其进行了初步的比较，然后提出了一种新的组播 网络的拓扑发现算法( h b l t ) ，接着介绍了两种仿真软件，给出了各自的仿真结 果和推算结果，本章最后改进型的算法和以往的算法进行了比较；第四章首先提 出了分布式拓扑发现的思想，进而给出了分布式拓扑发现的整体的软件框架，然 后论述了用w i n d o w s 下的网络编程实现该分布式拓扑发现的步骤并给出实例；第 五章论述a dh o e 网络的拓扑发现算法：第六章总结全文。 6 l p 网络拓扑发现技术：研究与实践 第二章网络拓1 1 、发现技术综述 网络拓扑结构反映了网络中各个设备的连接关系，获得网络拓扑使网络管理 人员能够优化网络、找出网络瓶颈和拥塞点，对网络升级、定位故障发生位置等 许多方面具有重要作用。同时，发现网络拓扑为网络仿真提供真实依据，并有助 于开发拓扑敏感的算法，提高网络的性能。 发现网络拓扑是一项挑战性的工作，因为互联网是各种网络的集合体，这些 网络不但设备、软件差异很大，而且可能被不同的组织所管理，他们的组织、运 营、安全等措施互不相同。另外网络规模越来越大，而且变化非常快( 特别是无 线网络) ，更增加了拓扑发现的难度。大多数网络管理工具都具有拓扑发现的功能， 如h po p e n v i e w ，i b m st i v o l i 等，它们大都依赖于简单网络管理协议( s n m p ) 这一标准协议。 但是互联网络的异构性、协议的多样性及快变性使得纯粹依靠网络管理协议 构造网络拓扑有些力不从心，而网络上提供的一些工具( 如p i n g ，t m c e r o u t e ) 可用 来辅助构造网络拓扑，另外从端到端性能测量的角度来也可分析和推算网络拓扑， 还有发现无线网络的拓扑是研究者感兴趣的另一个方向，本文就这几个方面研究。 有许多研究机构和公司着力于发现网络拓扑结构的研究，如c a i d a ”， n l a n r 2 ，j a s p v i 1 1 ，g e o b o y ”，o t i e 一，s k i t t e r ”，m i n c 3 h p 的i n t e r n e tm a p p i n g 【们 项目。以太网的规模越来越大，发现物理拓扑( 即第二层拓扑，交换机、路由器 与主机之间的连接关系) 引起些公司的注意，如c i s c o 开发的c d p ( c i s e od i s c o v e r p r o t o c 0 1 ) 、b a y 的( n e t w o r k so p t i v i t ye n t e r p r i s e ) 、i n t e l 、f i u k e ( l a n m a p s h o t ) 等， b e l l 实验室1 5 】、c a r n e g i em e l l o n 大学1 6 j 以及我国的研究人员【1 l l 都在研究物理拓扑发 现方法。同时i e t f ( i n t e m e t e n g i n e e r i n gt a s kf o r c e ) 也制定了物理拓扑的管理信 息库( b r i d g em i b ) v “5 1 。 本文集中研究不同网络、不同类型的网络拓扑发现问题，从以下几个方面来 探讨：基于网络管理协议的拓扑发现，包括第三层和第二层拓扑发现；基于网络 主动探测和测量的拓扑发现，包括基于网络常用工具的方法( 如p i n g t r a c e r o u t e 等) 、基于端到端组播测量的推算方法：无线网络的拓扑发现方法。然后分析了网 络拓扑发现面临的问题、可能的解决方案及下一步需要研究的问题。最后总结全 文。 2 1 基于网络管理协议的拓扑发现 目前大多数商业化的网管软件都是基于s n m p ，借助网络设备中的代理，通 第二章网络拓扑发现技术综述 过访问或配置m i b ( 管理信息库) 中的变量来实现网络管理功能( 包括性能、故 障、计费、配簧、安全管理五个功能域) 。这些m i b 含有对路由表和转发表及接1 3 的描述，因此使得拓扑构造成为可能，不但可以构造出网络层设备( 路山器、网 关) 的连接关系，而且也可构造出链路层设备( 网桥、交换机) 的连接关系，下 面分别描述。 2 1 1 基于s n m p 的网络层拓扑发现 基于网络管理协议进行i p 层的拓扑发现是网络管理工具的一个巫要功能，需 要用到m i b 库中的变量有 i p r o u t i n g t a b l e i p 路由表，其中i p r o u t e d e s t ( 目的i p 地址) 、i p r o u t e n e x t h o p ( 下跳路出器的i p 地址) 、i p r o u t e t y p e ( 路由类型) 、i p r o u t e p r o t o ( 路由防议) 、 i p r o m e m a s k ( 掩码) 、i p r o u t e l f l n d e x ( 路由的接口索引) 可用来搜索拓扑； i f i a b l e 接口表，其中i f i n d e x ( 接口索引) 、i f d e s c ( 接口描述) 、i f i y p e ( 接 几类型) 、i f p h y s a d d r e s s ( 接口的物理地址) ，可用来构造拓扑： i p f o r w a r d i n g l 代表可转发数捌( 贝网关功能) ，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 = 2 u r “，滓1 ，2 3 ，4 7 分别对应物理 层，链路层，网络层，传输层应用层。例如若s y s s e r v i c e s 的值为6 ，则它是路山 器： i p n e t t o m e d i a t a b l e - - - - - 可以访问相连的终端设备的i p 地址。 基于这些变量并辅之以p i n g ，采用广度优先遍历算法即可构造出刚络拓扑图， 一利算法实现如下”0 1 ： 初始化网关队列，子网队列，连接队列： 把缺省网关放入网关队列中； w h i l e ( 网关队列非空) f 从网关队列中取出一个网关，为c u r r e n t g a e w a y ： 访问c u r r e n t g a t e w a y 路由表； 把路由表中的各i p r o u t e n e x t h o p 不重复地放到网关队列中： 把各i p r o u t e d e s t 不重复地放到子网队列中： 把c u r r e n t g a t e w a y 与各i p r o u t e n e x t h o p 的连接不重复地放到连接队列中； i f ( i p r o u t e n e x t h o p 属于i p r o u t e d e s t 予网) 把i p r o u t e n e x t h o p 与i p r o u t e d e s t 的连接放到连接队列中； i f ( i p r o u t e n e x t h o p 与c u r r e n t g a t e w a y 的地址相同) i p 网络拓扑发现技术e 研究与实践 把c u r r e n t g a t e w a y 与i p r 0 u t e d e s t 的连接放到连接队列中； 子网内部的搜索可结合p i n g 工具、m i b 变量s y s s e r v i c e s 和i f f y p e ( 6 表示以太 网，7 表示8 0 2 3 以太网。9 表示8 0 2 5 令牌环，1 5 表示f d d i ，2 3 表示p p p 2 8 表 示s l i p 等) 来确定。 2 i 2 基于交换袭信息的链路层拓扑发现 大多数网络管理工具仅提供i p 层的拓扑发现( 路由器之州及与l j l l 之f l q ( , j 连 接关系) ，第一二层的设备( 如网桥、交换机) 需要网管人员手工录入。c i s c o ( c i s c o d i s c o v e r p r o t o c 0 1 c d p ) 、b a y ( n e t w o r k so p t i v i t ye n t e r p r i s e ) 、i n t e l 、f l u k e ( l a n m a p s h o t ) 等公司设计了针对特定设备的第二层拓扑发现m 议，但在复杂的 i n t e m e t 环境中，使用范围受到限制。i e t f 定义了描述局域网拓扑的m i b f 8 1 ，但没 有给出如何发现物理拓扑( 第二层拓扑) 。局域网规模的逐渐庞火使得如何发现物 理拓扑越来越引起了研究人员的注意【5 】【川i i1 1 ，这些方法都基于网桥( 多端厂l 网桥| _ ! | j 交换机，以下对网桥和交换机不加区分) m i b 数据( 分组转发表信息) 来推算嘲 矫之m 的连接关系，即发现物理拓扑。b r i d g em i b 中可能包含何所有可达节点的 交换表，也可能仪包含部分可达廿点的交换表，针对这蹲种情况分别泌明。这+ 杠 的6 u 提是每个交换机都采用逆向学习算法，并运行了生成树协 义( s p a n n i n gt r c c r f c l 4 9 3 ) ，因此无环路。 一、 基于完全交换表信息的拓扑发现1 5 1 【6 1 ： 这时，令s u 为交换机s i 的第j 个端口，a u 为s 收到的数据帧的源m a c 地 址集( s i 转发表的子集) 。又令a ( b ) 为交换机a 中节点b 的转发端口。相互连接 的交换机网络中，各交换机可能属于同一予网，也可能属于不同子网。1 j f - 种情 况，构造拓扑容易些，算法如下： 1 发现节点：由i p a d d r t a b l e 发现子网，由i p r o u t e t a b l e 发现路由器，i t i i p f o r w a r d i n g 及有无b r i d g em i b 判断交换机。 l i 发现边： 若a ，u a 。，= u ( u 是所有节点集合) 且a 。n 以= 中 ( 审集) ，则s u 与s u 相连。 若s i 足叶子端口( 不与任何交换相连) 且a i i 包含路出器r 的m a c 地川：，则s i 与路由器r 相连。 若存在变换机集s b ，节点集s e ，令s = 以u s f ，有：v a s v b f s ， 有a ( b ) = a ( c ) ，则s 中在s b 当中包含一个j e 享网段( 集线器) ，使sc 1 各节点互联。 第二章两络拓扑发现技术综述 9 后一种情况，含有多个子网的交换机网络拓扑构造算法如下： i 产生有效并集( u n i o n ，u 删= a 。ua 。) 的集合u ，其中各并集应满足： a s n 如= 中 ： 对每个子网t ，a ou 如要么包含t 中所有节点，要么一个都不包含； 若s i i ，s u 属于同一子网，则不存在另外一个子网中的交换机s p ，使得 c ，0 = u , j r 。，且彳，n a = m ： i i 重复以下步骤直到没有更多的有效并集从u 中删除： 如果s k i 出仪出现在一个有效并集中，则： 除了u i 叫外删掉所有包含s “的有效并集 删掉所有有效的u i 。b ，x j ，y ，： i i i 对任一有效的u i 得出结论：s i i 与s k l 相连。 注意上述方法需要每个交换机的交换表t i j 与其他节点相连的信息要完整，实 际上生成树自学习的机制使得交换表要定期更新，交换机难免出现故障或其他原 因使得孩条件难以满足，因此产生下述方法。 二、基于不完全交换表信息的拓扑发现 该方法不需要每个交换机获得全部其他交换机的所有转发表信息，通过考查 每i 】i i 个变换机的端口的转发表来判断其是否相连。令b 是交换机集合，a b 是其 l t 任意两个交换机，a x 是交换机a x 端口，b 。是交换机b 的第y 端口，a 。为交 换机a 在端口x 收到的数据帧的源m a c 地址集，a b v 同样。t 。是a 的转发表中除 a 。外其余m a c 地址集，即除x 端口外其他端口收到的数据帧的源m a c 集之和， 同理t b y 是b 的转发表中除a b y 外其余m a c 地址集。此时如采f 。n 瓦，= m ，则 a 、和b 。足连通的，反之亦然。依据这个定理可以有三种依据判断交换机a 的x 端 i _ ：= l 与交换机b 的y 端口相连( 至少一个满足，并且此时的连通不定是直接相连。 中间可能包含其它节点) 【6 j - i ) 每一交换机在其地址表中都有一项表明另一个的地址( 不包含带外端口， 如控制端口) ； i i ) 交换机a 在其a 。中含有b ，并f 1 3 k x ，使得a h n a 。k m ； i i ij f ，- ，i ，有( a 。n ，中) n 如中j 且j k x ，a b yn a o , 中。 如果局域网络运行了生成树协议，通过这两种方法发现的网络拓扑可能隐藏 了一些连接，这一点可以根据生成树| 办议自身的特点米判断，因为每一个网段的 局域网交换机之问的连接存在一个指定的桥( d e s i g n e db r i d g e ，d b ) ，每个交换机 的端口都知道这个d b 的i d 号，通过比较可以发现隐藏的链路。另外在构造物列! 拓扑酬也可考虑a r p ( 地址解析侨议) 和p i n g 操作的作用。 1 0 i p 网络拓扑发现技术：研究与实践 2 3 基于主动探测或测量的拓扑发现 基于主动测量或探测构造网络拓扑，一方面可以利用网络上用来对i n t e m e t 控 制和管理的协议( 如i c n i p , i n t e m e t 控制消息协议) 以及其它服务( 如d n s ，域名 服务) 提供的信息，另一方面可以通过测试网络端到端的性能( 其中包含了内部 网络结构，即拓扑的信息) 所蕴涵的信息来构造。 2 3 1 基于网络工具( p i n g 、t r a c e r o u t e ) 的拓扑发现： 网络操作系统提供的工具，如p i n g , t r a c e r o u t e 和网络服务，如d n s ，为网络 拓扑构造提供了可能。美国南加利福尼亚大学信息科学研究所s c a n 研究组研究 得到一个探测工具m e r c a t o r t l 2 1 ，该工具采用类似于t r a c e r o u t e 用跳数受限的路径探 测( p a t h p r o b i n g ) u d p 分组进行拓扑构造，为确保m e r c a t o r 高效灵活，做了三方 面的考虑：( 1 ) 初始集的选择：根据一个主机的地址来判断有效的网络地址，并 假定相邻的网绍地址有效，而且从测试主机自身开始，这样不需要预先构造探测 地址集；( 2 ) 单点探测可能会漏掉交叉链路( c r o s s l i n k s ) ，因此采用源选路的路由 器，使得探测分组从每个相邻的路由器都进行探测：( 3 ) 由于路由器可能会有多 个接口，因此给路由器的无效端口发送u d p 分组，如果返回的p o r tu n r e a c h a b l e i c m p 分组的源地址与探测的地址不同则认为是多端口路由器。 美国康奈尔大学的c n r g ( c o m e un e t w o r k r e s e a r c hg r o u p ) 也开发了网络拓 扑的探测方法【1 3 h 仔j ，和m e r c a t o r 类似，也利用了类似于t r a c e r o u t e 的方法。国内 也做了大量工作【1 6 】叶“。 利用网络工具和服务进行网络拓扑发现的步骤如下： ( 1 ) 确定探测点，在每个探测点确定临时地址组，选择时可根据已有的积累 及网络地址分配的预先知识； ( 2 ) 在每一探测点用p i n g 逐个探测临对组中地址的存活性( 如存活加入永久 组) ，并用t r a c e r o u t e 跟踪中间路由器，利用d n s 的z o n e 咖s f e r 、l s 及向无效端口 发送u d p 分组发现多端口路由器，由网络地址划分子网，相应信息存入对应链表 中，同时根据子网地址扩充临时地址组。重复执行直至遍历完毕： ( 3 ) 将各探测点的获得的链表进行综合，构造主干拓扑； ( 4 在子网内搜索可能存活的主机。构造子网拓扑。 这种方法能粗略的发现第三层拓扑，但是一方面受网管人员干预，获得的信 息很有限，另一方面搜索的时间太长，可是这种具有一定的普遍性，能在一定的 程度上发现网络拓扑。 第二章网络拓扑发现技术综述 2 3 2 基于端到端性能测试的拓扑推算 通过测量掌握网络性能，考查服务协议( s l a ，s e r v i c el e v e la g r e e m e n t ) 越 来越引起人们的重视，建立了许多测量的基础结构，如n i m i ( n a t i o n a li n t e r n e t m e a s u r e m e n ti n f r a s t r u c t u r e ) 2 4 1 ，n a i ( n e t w o r ka n a l y s i si n f r a s t r u c t u r e ) 1 2 1 ，i p m a ( i n t e m e tp e r f o r m a n c em e a s u r e m e n t a n d a n a l y s i s ) 【2 4 1 等。通过测量不但呵以获得端 到端的性能( 如时延、丢包) ，而且能够推算出网络内部的性能，甚至恻络内部拓 扑结构。相比于单播测试而言，多播测试能够推算更多的内部关联信息。通过端 到端组播测量得到丢包率、时延可以推算出组播拓扑，下面分别讲述。 一、基于端到端丢包的组播拓扑推算【2 5 l f 2 s l 设逻辑组播树r ( z l ) ，节点为v ，边的集合为l 。r ( k ) 是以k 为根结点的f 树 包含的叶予节点的集合。定义随机过程x = ( 也) 。，当探测分组能到达节点k ， 则x k = 1 ，否则为o 。殴分组成功穿越链路k ( 节点k 及其父节点之问的边) 的概率 为吼，口2 慨kr 。除根结点外若0 嘶 1 则树为诈规树。苗a ( k ) 是探测分组到 达k 的概率，则彳( 七) = 兀口( j 为k 与根结点之间的探测包成功穿越的节点) ， 对于uc v 令 “= j f ) h ，劬】= l j 则 1 一，o z ：兀( 1 一，彤) oq ，( 己d ； ( i i )令 b ，( ，那么当且仅当 b b ( 有 ( 1 一z ( u ) b = i l 。u ( 1 一r ( d b ) ( i i i ) 如果u 是兄弟节点的集合，则b ( u ) = 爿( 口( ) 。如果有相同的父节 点，所以的兄弟节点集合具有相同的曰( 值。 ( i v )u 是兄弟节点的集合，假设ev 满足a ( u u n ) - 口( 同时 a ( u u j j ) ) - k 。那么b ( u u 七) ) b ( c ，) 。 命题中的( i v ) 表明在兄弟节点集合中增加一个非兄弟非祖先的节点后将增加 函数b 的值，如图2 1 所示。于是我们就可以直接从 r ( u ) ：ucv 1 重建逻辑树。 r 接收节点集 图3 2 当u = u u k ) 时b ( u ) b ( u ) 用( x 。) 毖。表示在接收节点处观察到的来自于n 个探测分组中每一个分组被 接收到的分布。解命题1 ( i ) 时用户( 尼) 来代替y ( ) ，见( 3 - 3 ) 式。对于u c v 我 4 j j 定3 ( 2 ( u ) = n - i ：u 。骞“e 宣可由式( 3 4 ) ，( 3 5 ) 得到。尹( u ) 表示节点 集u 中某个节点的子孙接收到的探测分组的比例。这样我们就可以得到b ( u )