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

摘要 摘要 随着网络规模的进一步扩大和网络软硬件设施的日益复杂，得到一个完整、 准确的网络拓扑结构图对于网络管理、网络优化、故障定位等应用越来越重要。 目前，对网络拓扑发现技术的研究主要集中在i p 层，且还不够成熟和系统化，因 而其必要性和紧迫性不容忽视。该论文来源于国家自然重点基金项目“基于网络 探测的i p 网络拓扑发现和性能分析的研究”，拓扑发现部分是该项目的重要内容和 基础。作者通过对于一些文献资料的研读和总结，提出了新的思想和方法，并做 出了大量的实践工作，在该项研究上取褥了一定的进展。 论文的主要内容包括：首先，系统地总结、分析、比较了现有主要的网络拓 扑发现算法：其次，通过对比单点式拓扑发现和分布式拓扑发现方法的优劣，提 出了一种基于d o u b l e t r e e 分布式拓扑发现改进算法，并通过分析证明了它可以有 效地降低链路冗余，提高发现速度和准确性；接着，介绍了s n m p 协议的特点， 然后提出了一种基于s n m p 协议的拓扑发现算法以及针对它的改进算法，并进行 了比较；最后提出了一种有效提高网络探测速度和准确性的拓扑发现思想，其优 越性得到了证明。 关键词：拓扑发现分布式d o u b l e t r e es n m p a b s t r a c t a b s t r a c t w i t ht h ee x p l o d i n gs c a l ea n dc o m p l e x i t yo fi n t e m e ti nt h e s ey e a r s i t sm o r ea n d m o r ei m p o r t a n tt og e tac o m p l e t ea n dc o r r e c ti n t e r a c tt o p o l o g y , w h i c hc a nb eu s e di n t h e s ef i e l d ss u c h 雒n 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 df a u l tl o c a t i o n n o w , t h er e s e a r c ho nn e t w o r kt o p o l o g yd i s c o v e r yt e c h n i q u ei sf o c u s e do ni pl a y e rm a i n l y , a n dt h ed i s c o v e r yt e c h n i q u ei ss t i l li m m a t u r ea n dn o n s y s t e m a t i c ，s om u c hm o r e a t t e n t i o ns h o u l db ep a i du r g e n t l yt ot h ei s s u e a so n eo ft h em o s ti m p o r t a n tt a s k s ，t h i s p a p e ri sf r o mt h en a t i o n a lk e yp r o j e c t s t u d yo fi pn e t w o r kt o p o l o g yd i s c o v e r ya n d p e r f o r m a n c ea n a l y s i sb a s e do nn e t w o r kp r o b i n g w h i c hi ss u p p o r t e db yn s f c n e w i d e a sa n dm e t h o d sh a v e b e e ng i v e na n dl a r g ea m o u n to fm a t e r i a l sa n dc e r t a i n i m p r o v e m e n t h a sb e e no b t a i n e do nt h i sp r o j e c t t h i sp a p e ri so r g a n i z e da sf o l l o w s ：f i r s t l y ，t h em a j o re x i s t i n gn 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 e s a r es u m m a r i z e d ，a n a l y z e da n dc o m p a r e dw i t he a c ho t h e r ； s e c o n d l y , b yc o n t r a s t i n gt o p o l o g yd i s c o v e r yp r o b e db ys i n g l e - p o i n tw i t hd i s t r i b u t e d t o p o l o g yd i s c o v e r ym e t h o d ，ad o u b l e t r e e ，b a s e di m p r o v e da l g o r i t h mo fd i s t r i b u t e d t o p o l o g yd i s c o v e r yi sp r o p o s e d ，w h i c hi sp r o v e db ya n a l y s i st or e d u c et h er e d u n d a n c y o fl i n ke f f e c t i v e l ya n dt oe n h a n c ed i s c o v e r i n gv e l o c i t ya n dv e r a c i t y t h i r d l y , as n m p p r o t o c o lb a s e dt o p o l o g yd i s c o v e r ya l g o r i t h ma n d i t si m p r o v e m e n ti sp r e s e n t e d f i n a l l y , an e wt o p o l o g yd i s c o v e r ym e t h o d , w h i c hc a ne f f e c t i v e l yi m p r o v ep r o b ev e l o c i t ya n d v e r a c i t y , i sp r o p o s e da n d t e s t e df o ri t ss u p e r i o r i t y k e y w o r d s ：t o p o l o g yd i s c o v e r y , d i s t r i b u t e d ，d o u b l e t r e e 。s n m p 创新性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学或 其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做 的任何贡献均已在论文中作了明确的说明并表示谢意。 本人签名：剑菲盘 一1 日期：汐r 关于论文使用授权的说明 j 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究生 在校攻读学位期间论文工作的知识产权单位属于西安电子科技大学。本人保证毕 业离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科技大学。 学校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全 部或部分内容，可以允许采用影印、缩印或其它复制手段保存论文。 本人签名l 兰 4 7 哇l 导师醚塑塾支 日期：聊彳 日期：丑幻多，。子 第一章绪论 第一章绪论 本章主要介绍了本论文的研究背景和意义，说明了本文的主要研究任务，给 出了论文的章节安排 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 ) 并确定网元之间 的互连关系，包括互连设备( 如路由器、网桥、交换机等) 、主机和子网。网络拓 扑图是拓扑结构的可视化表现形式。网络拓扑连接图为网络管理人员提供了一个 了解全局网络连接情况的直观手段通过网络拓扑图，网络管理人员可以对整个 网络的情况进行总体上的把握，从而对部件进行重新安装和重新配置，并对问题 进行诊断，网络拓扑连接图还是网络管理人员实施管理功能的一个很好的入口。 网络拓扑发现主要应用于以下各个方面： ( 1 ) 模拟网络：为了模拟实际网络分析网络性能，对网络进行合理扩容和优 化，必须先得到该网络的拓扑结构； ( 2 ) 网络优化：网络拓扑信息可帮助网络管理者确定是否需要增加新的路由 器，当前硬件是否正确配置，并发现网络中的瓶颈位置和失败的链路，进行网络 优化： ( 3 ) 用户接入方式的选择：网络拓扑信息可帮助用户确定自身处于网络的什么 位置，从而确定服务器的位置以及选择哪一个网络服务提供商能够将时延最小化、 可用带宽最大化； “) 研究拓扑敏感算法：一些新的协议和算法可以在得到网络拓扑信息的基础 上改善网络性能t 例如：基于拓扑敏感信息策略和q o s 的路由选择算法和基于拓 扑敏感进程组选项的组通信算法： ( 5 ) 确定镜像服务器的位置：根据拓扑信息合理配置镜像服务器的位置，以最 大可能减少时延，解决瓶颈问题： 2 网络拓扑发现的研究和实现 ( 6 ) 实行网络服务管理：例如：m a i l ，f i p ，w e b ，s n m p ，d n s ； ( 7 ) 统计数据的采集及关联分析； ( 8 ) 网络战。 1 2 网络拓扑发现概述 网络拓扑发现涉及到的问题比较多，但是总的来说，要对一个网络进行拓扑 发现，主要有五个方面的问题需要明确： ( 1 ) 确定这个技术针对的是网络的哪一层、什么协议只有确定网络的层次和 协议，才能明确到底需要采集什么样的信息，才能使这项技术具有比较好的适应 性。 ( 2 ) 确定是采用被动探测技术还是主动探测技术来实现网络拓扑信息的采集。 这两项技术相比：被动探测技术是通过给所有观测的网络都加入一个探测器，由 它来采集信息，并发送到网络管理主机来形成网络的拓扑结构其优点是除了探 测器向管理主机递交各个网络的拓扑信息，不产生额外的流量，所以网络负担小。 缺点是由于是各个探测器被动地收集各自网络中交换的信息，所以需要花费较长 的时间才能收集到足够的网络拓扑信息，并且将探测器安装在所有的网络中也是 不实际的。主动探测技术是通过网络管理主机主动向所有管理网络发送探测包， 并采集返回信息，进行分析最终形成网络的拓扑。这种技术的优点是能比较快地 获得网络拓扑。缺点是需要产生的流量比较大，并且对于一个十分慢的网络不太 合适。 ( 3 ) 确定采用何种方式收集信息。一种是采用简单网络管理协议( s n m p ) 来 收集网络的信息。但是不是所有的网络的设备都支持这些管理协议，而且需要对 涉及到的网络逐个进行配置；一种方式就是采用一种通用的协议来实现对于网络 信息进行采集，这样局限性小，如基于i c m p 等协议来实现的，它们是建立在i p 层的基础上，被所有的i p 网络和设备支持，可靠性比较高，且省去了大量的手工 配置。但是得到的信息又是有限的 ( 4 ) 确定网络拓扑发现的目标及发现的程度这两方面均与实际网络业务需求 紧密相关，但不管采用哪种协议和工具，网络拓扑发现的最终目标是得到一个快 速、完整、正确和高效的网络拓扑发现算法或拓扑发现工具。所谓快速即能够实 时地发现网络拓扑的结构和变化情况，且保持数据内部的一致，一个不能跟上网 络实时变化的拓扑发现算法适用范围也是受限的完整性指的是在出现最少错误 概率的情况下有效地、尽可能多地正确发现一个特定网络内部的结构。正确性即 算法应尽力保证拓扑发现结果正确，尽量不出或少出错误。高效性是指算法不应 消耗过多的网络资源，仅仅是给网络增加尽可能小的负载 ( 5 ) 采用单点式的拓扑发现还是分布式的拓扑发现分布式拓扑发现是通过建 第一章绪论 立服务器和客户机之间的连接，在服务器端启动拓扑发现过程，将在各个探测点 处收集到的拓扑信息发送到客户端，然后在客户端对这些信息进行收集和整理 最后得到整个网络完整的拓扑结构。 拓扑算法有两个重要指标，一是性能，就是拓扑发现的速度；二是获得网络拓 扑结构的完备性，完备性就是指拓扑发现得到的网络拓扑结构是否能真实反映网 络结构的实际情况，但由于可获得的信息本身不完备等其他原因，拓扑发现算法 很难的得到真实的拓扑结构。这两个问题恰恰是拓扑发现中的难点。 1 3 网络拓扑发现技术的发展现状 有许多研究机构和公司着力于发现i p 层网络拓扑发现结构的研究，如 c a i d a t t l ，n l a n r p l ，j a s p v i ”，g e o b o y ”，o t t e 一，s k i a e r 【“，m i n c 3 1 ，h p 的i n t e m e t m a p p i n g s l 项且。大多数网络管理工具都具有拓扑发现的功能，如h po p e n v i e w ， i b m st i v o l i 等，它们大都依赖于简单网络管理协议( s n m p ) 这一标准协议。而 s n m p 并不是一种通用协议，基于它的拓扑发现受到权限的限制，没有权限便不 能访问其支持的m i b i i 信息，也就无法进行拓扑发现。 、 以太网的规模越来越大，发现物理层网络拓扑也引起一些公司的注意，如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 ) 、b a y 的( n e t w o r k 。o 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 l 、c a r n e g i em e l l o n 大学【6 l 以及我国的研究人员 】都在研究物理网络拓扑发现方法。同时i e t f ( i n t e r n e te n g i n e e r i n g t a s i cf o r c e ) 也制定了物理网络拓扑的管理信息库( b r i d g em i b ) 【7 1 【射 1 4 论文承担任务及贡献 此课题来源于国家自然科学基金重点项目“基于网络探测的i p 网络拓扑发现 和性能分析的研究”( 项目编号：6 0 1 3 2 0 3 0 )，基金项目中最重要、最基础的 部分就是网络拓扑发现。得到一个完整、准确的网络拓扑结构图可以使网络探测、 性能分析及安全性分析等工作更加简单、高效地进行。 本论文的主要工作及贡献为： 1 系统地总结、分析、比较了各种主要的网络拓扑的发现方法； 2 分析了网络层的特点，在以往单点拓扑发现算法的基础上，提出了一种新 颖的分布式拓扑发现算法，并与原有算法进行了比较，证实了改进算法的 优越性： 3 系统总结了大量实际的网络特性，分析了s n m p 协议在网络拓扑发现方面 的作用，并提出了一种基于s n m p 协议的拓扑发现算法，分析了其优越性， 最后提出了一种有效提高拓扑发现速度的拓扑发现算法思想： 4 通过实践总结了大量的实际网络特性，对从事网络管理、安全分析、性能 网络拓扑发现的研究和实现 分析等工作的人员都有很大的价值。 本论文内容安排如下：第二章详细介绍网络拓扑发现技术可采用的协议、工 具等，系统地总结了基于不同协议或工具的拓扑发现算法、物理层拓扑发现算法、 无线网络的拓扑发现算法；第三章介绍分布式拓扑发现改进算法的主要思想、对 算法关键部分进行描述以及对算法结果进行详细分析；第四章介绍了s n m p 协议 的基本概念和基本功能，并提出了一种基于s n m p 协议的拓扑发现算法，分析了 其优越性，最后提出了一种能够提高拓扑发现速度的算法；第五章对全文进行总 结。 第二章网络拓扑发现技术综述 第二章网络拓扑发现技术综述 本章首先全面介绍网络拓扑发现可采用的协议和工具；其次介绍i p 层网络拓 扑发现技术，物理层网络拓扑发现技术；然后分析了网络拓扑发现面临的问题， 可能解决的方案及未来的研究方向 2 1 拓扑发现技术可采用的协议和工具 网络拓扑发现可采用多种工具和协议，归纳起来有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 p i n g p i n g 工具主要用于检测目的主机是否在网络中存活，每一个被p i n g 的主机向 源主机发一个i c m p 回显应答包( e c h or e p l y ) ，该数据包中包含了应答和时延等信 息。p i n g 一个存活的主机回应的时间一般是微秒级或毫秒级，而对一个关机的主 机和不存在的主机回应时间为2 0 秒，这样就影响了p i n g 工具的效率。所以可用异 步的方式发送和接收i c m p 回显应答包，这样既可以提高检测的速度，又不会导 致阻塞。 此外，还可用“d i r e c t e db r o a d c a s tp i n g ”直接p i n g 子网内所有主机。这样可快 速有效地发现一个子网内所有的主机，但不是所有网络都支持这种方式。在有些 网络中仅路由器对b r o a d c a s tp i n g 响应。丽有些网络中所有主机和路由器均不给予 响应。 2 t t a e c r o n t e t r a c e r o u t e 的功能是发现一条主机到目的主机的路径，它利用的是i p 头中的 t 1 l 字段。开始时信源设置i p 头的t t l 值为l ，发送报文给信宿，第一个路由器 收到此报文后，将r r l 的值减去l ，丢弃此报文，并发送一个类型为“超时”的 i c m p 报文给信源，信源接收到此报文后对它进行解析，这样就得到了该路径中的 第一个路由器地址。然后信源发送t 1 乙为2 的报文给信宿，第一个路由器把它的 r r l 值减去l 后转发给第二个路由器，第二个路由器收到后再减1 ，报文的t t l 值变为0 ，该路由器丢弃此报文并发送一个类型为“超时”的i c m p 报文给信源。 这样就得到了路由中的第二个路由器地址。如次循环下去，直到报文正确到达， 信源就得到了通往信宿的路由。 这种发送不同的r 几值在信源与信宿之间发现路由的方法，除了网络管理者 刻意要隐藏网络内部拓扑信息外，t l a c e r o u t e 均可正确发现路径，其中使用的是 i c m pt t le x p i r e dp a c k e t 响应 6 网络拓扑发现的研究和实现 3 s n m p s n m p 即简单网络管理协议，规范了以下几方面的功能，一个或多个管理系统 和一组代理之间交换信息的协议，格式化和存储管理信息的架构。定义了一组通 用目的的管理参数，或称被管对象。其管理信息库( m i b ) 定义了网络管理的具体 对象，是代表各种被管对象的网络管理数据库。该数据库包括了对于网络拓扑发 现来说最有益的节点及路由信息，因而基于s n m p 的网络拓扑发现效率较高，但 通常情况下没有权限直接访问该数据库的信息，所以基于它的网络拓扑算法常受 到限制 4 d n s 服务器的域转换 一个域的域名服务器( d n s ) 维持该域内的每个名字到其i p 地址的绑定。大 多数域名服务器通过“z o n c t r a n s f e r 命令返回该域内名字的列表。所以d n s 的域 转换可以发现域内的所有主机和路由器这种技术快速、准确、开销小，但是发 现并不完全准确，因为用d h c p 获取i p 地址的主机并没有d n s 服务，而且。一 些网管员因安全原因关闭了d n s 域转换服务。 5 d n s i s 快速而且准确，但它的使用常常被限制，因而使用受到限制。 6 i ci n f o r m a t i o n ( 网络接口卡信息) 该信息的使用需要一定的网络管理员权限，否则不能得到，因而使用受到限 制。 7 i g m p 协议 基于组播可以推算时延、丢包率等网络性能参数，采用这些参数可以推算出 网络逻辑拓扑结构。 2 2 网络拓扑发现技术的研究 i p 层的网络拓扑描述的是第三层网络设备( 如路由器，网关，主机等) 、子网 之间的连接关系。即逻辑上各个i p 地址的连接情况。 目前常用的i p 层网络拓扑方法主要有：基于s n m p 路由表的网络拓扑方法， 基于a r p 协议的网络拓扑发现方法。基于d n s 、o s p f 、r i p 等协议的网络拓扑发 现算法，基于i c m p 、u d p 等协议的网络拓扑发现方法。基于主动性能探测的拓 扑发现等下面对这几个方面进行简要介绍 2 2 1 基于s n m p 路由表的i p 层网络拓扑发现 s n m pm i b 库的i p 组记录了有关i p 实现和操作的信息。网络拓扑发现需要用 到的对象主要有：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 ( 目的l p 地址) 、 i p r o u t c n e x t h o p ( f - - 跳路由器的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 u t e m a s k ( 掩码) 、i p r o u t c l f l n d c x ( 路由的接口索引) ； 第二章网络拓扑发现技术综述 i p f o r w a r d i n g 1 代表可转发数据( 具网关功能) ，2 代表不转发数据( 不具有 网关功能) 。 由于路由表的下一跳地址所标识的必然是具有路由功能的网络节点，因此从 网络工作站的默认路由开始，通过读取路由器的路由表可以逐步向下发现网络中 所有具有路由器功能的网络节点 一种可能的算法如下： 初始化网关队列，子网队列，连接队列： 把缺省网关放入网关队列中； w h i l e ( 网关队列非空) f 从网关队列中取出一个网关，为c u r r e n t g a t 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 的地址相同) 把c u r r e n t c j a t e w a y 与i p r o u t e d e s t 的连接放到连接队列中： 这种基于s n m p 协议的拓扑发现算法的优点【1 0 l 有以下几个方面：基于标准的 s n m p 协议实现；发现过程和算法简单；目标明确，发现效率高，系统和网络开 销4 - 由于从路由表可以获得下一站地址信息，因此对于受到访问限制的网络仍 然可以发现其第一级路由器，得到比较完整的拓扑关系。 但是它的缺点【1 0 1 也有以下几个方面：网络设备必须支持s n m p 协议而且需要 有访问权限：无法发现网络中无路由功能的网络设备。包括交换机和主机设备； 对于只使用静态路由配置的路由器，其发现效果将受到很大约束：路由表中包含 了大量对于拓扑发现来说冗余的信息。 因此，该方法主要用于大型骨干网络的拓扑发现，得到网络的整体拓扑情况。 2 2 2 基于交换表信息的链路层拓扑发现 大多数网络管理工具仅提供口层的拓扑发现( 路由器之间及主机之间的连接 关系) ，第二层的设备( 如网桥、交换机) 需要网管人员手工录入。c i s c o ( c i s c o d i s c o v e r yp r o t o c o l ，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 ) 等公司设计了针对特定设备的第二层拓扑发现协议，但在复杂的 t n t e m e t 环境中，使用范围受到限制。i e t f 定义了描述局部网拓扑的m i b i 引，但没 有给出如何发现物理拓扑( 第二层拓扑) 的方法。局域网规模的逐渐庞大使得如 网络拓扑发现的研究和实现 何发现物理拓扑越来越引起人们的关注【5 1 【6 】【l l l ，这些方法都基于网桥( 多端1 3 网桥 即交换机，以下对网桥和交换机不加区分) m i b 数据( 分组转发表信息) 来推算 网桥之间的连接关系，即发现物理拓扑。b r i d g em i b 中可能包含所有可达节点的 交换表，也可能仅包含部分可达节点的交换表，针对这两种情况分别说明。这里 的前提是每个交换机都采用逆向学习算法，并运行了生成树协议( s p a n n i n gt r e e ， r f c l 4 9 3 ) ，因此无环路。 1 基于完全交换表信息的拓扑发现1 5 l 【6 l 这时，令s i j 为交换机s i 的第j 个端e l ，a b 为s i j 收到的数据帧的源m a c 地址 集( s i 转发表的子集) 。又令a ( b ) 为交换机a 中节点b 的转发端口。相互连接的交 换机网络中，各交换机可能属于同一子网，也可能属于不同子网。 y u r ib r e i b a r t 等提出的算法1 2 9 1 基于以下引理： 引理l 如果a 。u a n = ( 指子网内所有交换机的集合) 且a 。n 山= m ， 则端口屯与端口直接相连接 定义l 若s 的端口s , j 的a f t 中未包含其它交换机m a c 地址，则称瓯为叶端 口。 引理2 若路由器r 与交换机s 的岛端口直接相连当且仅当是叶端口且 a 。中包含路由器r 的m a c 地址 算法步骤： b e g a i n ( 1 ) f o re a c hs w i t c hs d o ( 2 ) f o re a c hi n t e r f a c e jo f 墨d o ( 3 ) ( i f ( 瓯i sm a t c h e d ) t h e nc o n t i n u e ( 4 ) e l s e i f ( a fu a = p a n d a fn 如= t d ) t h e n m a t c h 岛w i t h ) ( 5 ) f o re a c hr o u t e rr i 。s w i t c hs jd o ( 6 ) f o re a c hi n t e r f a e e jo f 墨d o i f ( s 。i s n o t m a t c h e d a n d a f e e o n t a i n sr k ) t h e n m a t c h s , w i t h r t 第二章网络拓扑发现技术综述 9 e n d 为了保证每台交换机的地址转发表完整( 也就是每台交换机的地址转发表中均 包含子网内其它交换机的m a c 地址) ，两个算法分别采用如下两种方法： 方法l 子网内所有节点都向每台交换机做p i n g 操作，目的是使子网内每台交 换机均获取子网内每个节点的信息。 方法2 对原有的p i n g 程序进行修正，将管理节点发出的i c m p 响应请求包中 的源i p 地址改为给定的且标交换机的i p 地址，目的i p 地址依次为网络中其它交 换机的i p 地址当目的交换机接到i c m p 查询请求包之后，将向给定的目标交换 机发回i c m p 查询响应包，则给定目标交换机地址转发表中就会出现目的交换机 的m a c 地址。 但上述两种方法均存在问题，方法1 只能适用于某些特殊环境，对一般实际网 络环境不大可能实现。对于方法2 ，当目的交抉机收到i c m p 查询请求包后不进行 a r p 操作，而是简单地将接到的数据帧中的源m a c 地址与目的m a c 地址互换。 然后发出i c m p 查询回应包，这样给定目标交换机就不能获取到目的交换机的准 确信息，所以这两种方法的可行性受到一定限制。而且如果网络中有不可网管的 元素，算法就更无能为力了 2 基于不完全交换表信息的拓扑发现 郑海掣2 9 1 提出了一种当a f t 不完整时，基于以下引理的算法： 定义2 上行端口：指端口对应的a f t 中出现控制节点m a c 地址的端口。 定义3 下行端口：指端口对应的a f t 中没有出现控制节点m a c 地址的端口。 在控制节点肘，依次向子网中的各元素进行p i n g 操作：完成此过程后，经过 分析发现，每个下行端口的信息都是完整的，但是每个上行端口的信息不能保证 完整。 引理3 如果某一个交换机端口的地址转发表中的元素，刚好是另一个交换机所 有下行端口地址转发表中的元素，再加上交换机自己本身的m a c 地址，则此端口 与对方交换机的上行端口相连。即：若交换机置与足满足：4 = 如u 溉 n _ 0 ( 甩= 1 , 2 ，n 为交换机墨的端口数，且n 不等于上行端口集合中端口的编 号) ，则& 与盈的上行端口直接相连。 算法步骤： ( 1 ) 获取子网内所有的交换机的列表： ( 2 ) p i n g 子网内所有交换机：。 1 3 ) ，依次读取每台交换机的地址转发表； 1 0 网络拓扑发现的研究和实现 ( 4 ) 从各交换机地址转发表中构造每台交换机的上行端口与下行端口集合。同时将千网内 一 所有交换机节点放入待检测队列h 一 ( 5 ) 将州j 交换机节点依次压入待生成队列( 此队列为先进先出队| 列) 。同时把n i 交换机从待 i 检测队列移去：0 。： ， 。 ( 6 ) 从待生成队列中取山一个节点使其成为待检测节点 赢茚譬r 滢- t 球：卵，警 ( 7 ) 在其它节点的下行蛸口集合中的各端口的地址转发表中查询是否包含待检测帮点 m a c 地址若出现但是表中：仃点个数大弧1 、则删除此表项。若仅出现检测节点i 、则 此项所对应的端口号与待检测的节点上行端口直接连接，j 同时将此端口从当前：l ，点的 下行端口集合中移去p ： ( 8 ) 每遍历完一个1 ，点。若此：1 7 点的下行端口集合为空则将此交换机：1 l 点压入待生成带点 队列中同时从待监溯队列中移老 ( 9 ) 若待生成队列不空。重复6 9 ： 这种方法在判断上运算量大，而且也要求每个交换机都支持s n m p ，而实际的 底层网络元素经常不会统一地支持地s n m p 例如，对于网络中存在h u b 或哑交 换机的情况，算法就不能顺利进行。 任何一个交换机都是基于a f t 而进行数据转发的，因此基于a f t 拓扑发现算 法要求所需要的a f t 是可访问的，即支持s n m p 的。这在一定程度上限制了其普 适性。 2 2 3 基于a r p 协议的网络拓扑发现 任何有以太网接口的网络设备都必须支持地址解析协议( a r p ) ，并在本机 维护着一张a r p 表，用于i p 地址和m a c 地址的解析和转换。a r f 表中的网络设 备地址都是最近活动过的有效设备的i p 地址和以太网地址，而且几乎没有冗余信 息。 方法原理：根据任何一台交换机或路由器的a r f 表，就可以发现与其它各以 太网端口相连的以太网中的所有网络设备，再根据其它信息判断网络中的路由器 和交换机，并继续根据a r p 表进行发现 需要用到的对象主要有： i p n e t t o m e d i a t a b l e ：描述物理地址和i p 地址进行映射的表，即a r p 表 s y s s e r v i c e s ：指示节点所提供的服务，若主机在第i 层提供了服务，则l i 对应 相应的层数，则s y s s e r v i c e s 的值为：肌= 2 ( 4 - 。i - l ，2 ，3 4 ，5 分别对应物理层， i 链路层，网络层，传输层。应用层例如，若s y s s c r v i c c s 的值为7 。则它是路由器 该拓扑发现方法的优点：发现效率高，特别适合局域网的拓扑发现。 第二章网络拓扑发现技术综述 该拓扑发现方法的不足：不适用于不支持a r p 的网络设备，因此一般只适用 于局域网：对a r p 表的访问需要通过s n m p 或c m i p 协议的支持，因此对特定设 备的依赖性较大；如果网络过大，a r p 表就无法包括所有的网络设备【j 。 2 , 2 4 基于主动探测的拓扑发现 一、基于i c m p u d p 主动探测 基于主动探测构造网络拓扑，一方面可以利用网络上用来对i n t c r n e t 控制和管 理的协议( 如i c m p ，i n t e r a c t 控制报文协议) 以及其他服务( 如d n s 域名服务) 提供的信息，另一方面可以通过测量网络端到端的性能( 其中包含了内部网络结 构，即拓扑的信息) 所蕴涵的信息来构造。 网络操作系统提供的工具，如p i n g 、t r a c e r o u t e ，为网络拓扑构造提供了可能。 但单纯的i c m p 网络拓扑发现方法受到较多限制，因此，经常需要和其它的拓扑 发现方法综合使用，例如： 美国南加利福尼亚大学信息科学研究所s c a n 研究组研究得到一个探测工具 m e r c a t o r i 屹】，该工具采用类似于w a c ：e r o u t e 用跳数受限的路径探测( p a t hp 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 ei c m p 分组的源地址与探测 的地址不同则认为是多端口路由器。 美国康奈尔大学的c n r g ( c o m e l ln e t w o r kr e s e a r c hg r o u p ) 也开发了网络拓 扑的探测方法i - 1 5 l ，和m e r c a t o r 类似。也利用了类似于t r a c e r o u t e 的方法。国内 也做了大量工作【1 6 h 2 3 1 。 这种方法能粗略的发现第三层拓扑，但是一方面受网管人员干预，获得的信 息很有限。另一方面搜索的时间太长，可是这种具有一定的普遍性，能在一定的 程度上发现网络拓扑 二、基于性能主动探测 通过测量掌握网络性能，考查服务协议( 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 m 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 ) 1 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 ) f 2 】。i p m a ( i n t e r a c tp e r f o r m a n c em e a s u r e m e n ta n d a n a l y s i s ) 2 4 1 等。通过测量不但可以获得端 到端的性能( 如时延、丢包) ，而且能够推算网络内部的性能，甚至网络内部拓扑 结构。相比于单播测试而言，多播测试能够推算更多的内部关联信息。通过端到 端组播测量得到丢包率、时延可以推算出组播拓扑。目前有不少基于性能的拓扑 网络拓扑发现的研究和实现 发现方法【2 5 h 2 。i ，比如： 夺基于端到端丢包的组播拓扑推算 基于时延的组播拓扑推算 自适应组播拓扑推算 基于性能主动探测的i p 层网络拓扑发现需要发送大量的数据，并进行数据运 算，所以应用还是受到了一些限制。 2 2 5 基于d n s 、o s p f 、r i p 的网络拓扑发现 l ，基于d n s 的拓扑发现 d n s 协议用于完成域名地址和i p 地址的转换。i n t e r a c t 中的d n s 系统是一个 存储域名和i p 地址映射关系的分布式数据库，数据库中保留着域中所有主机和路 由器的域名信息 利用d n s 的区域传输机制可以查询域名服务器。从而得到域内每个名字到i p 地址的绑定，就可以发现域内主机和路由器。 利用d n s 进行拓扑发现快速、开销小。但是，d n s 数据库中的信息可能和实 际不一致，另外，某些d n s 服务器不允许区域传输。 2 基于o s p f 的拓扑发现 o s p f 中链路状态数据库存有的信息可以用来计算网络路由，计算过程是从不 同的链路状态记录中概括出一个代表网络的图。图中的内部端点是o s p f 路由器和 中转网络，外围端点是末梢网络、汇总网络以及外部目的节点，连接的弧线是具 有不同t o s 度量制式的各种链路。因此，网络管理系统可以访问自治系统每个区 域中某一个路由器存有的相关的o s p f 路由表信息，就可以构造出整个自治系统的 网络拓扑图。 实际运行的企业网管一般不会超出一个自治系统的范围，因此基于o s p f 构造 网管系统具有较大的适用性，该技术的效率和速度也比较高。但此技术不能发现 那些不支持o s p f 协议的网络设备和连接。另外，o s p f 中涉及的路由部分比较复 杂，算法上的理解和实现都有一定的困难 3 基于r i p 的拓扑发现 类似o s p f ，利用r i p 协议，也可以从路由器中提取其i p 地址或i p 子网的路 出信息表，进而发现网络拓扑r i p 协议本身的缺陷( 例如，没有子网概念、容易 受到攻击、收敛慢) 限制了r i p 佛议的普及，也就限制了基于r i p 的拓扑发现的 应用。 2 2 网络拓扑面临的问题和未来的工作 2 3 1 网络拓扑发现面l 晦的问题 第二章网络拓扑发现技术综述 采用探测工具逐个探测每一个子网和主机，所花费的时间太久，此时若采用 分布式探钡4 的方式，可同时探测多个目标，就可以缩短探铡拓扑的时间提高探测 效率。也可以采用m 地址分类的方法进一步缩短时间。另外采用基于v l a n 或者 移动代理进行分布式拓扑发现也可以缩短拓扑发现的时间 利用网络工具发现网络拓扑，往往受到限制，如i c m p 常常被路由器禁用或 低优先级，而由s n m p 访问m i b 库，m i b 库更新需要一定的周期，并不是每个节 点都支持s n m p 协议，因此它的使用受限。后面将详细讨论s n m p 协议在拓扑发 现方面的应用 2 3 2i p v 6 中的拓扑发现技术 由于i p v 6 地址从i p v 4 的3 2 位发展到1 2 8 位，有大量的i p 地址存在，这使得 网络需要分层管理或者分布式管理，而且一些针对i p v 6 的分层拓扑发现算法已经 在研究。 2 3 3 基于移动代理的拓扑发现技术 移动代理的一般定义为：具有跨地址空间持续运行机制的a g e m 。此定义突出 三个特征：( 1 ) 首先要是一个代理，满足代理的目标驱动特征；( 2 ) 能够转移到不同 的地址空间中执行；( 3 ) 转移后其执行是持续的，即从转移的下一条指令继续执行， 转移过程中保持自身状态。 r r o yc h o u d h u r y 等人提出了基于移动代理的分布式拓扑发现策略，每个节点 运行一个代理，周期性的收集拓扑信息，并将其分发到网络中的其他节点。这种 方法不能提供瞬时的网络拓扑，发现完整的网络拓扑需要较长的时间。并且需要 分发很多消息，因而效率不商且消耗带宽。 2 4 小结 本章讨论了不同层面、不同类型的网络拓扑发现技术，它们各有优缺点，实