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

摘要 摘要 随着网络规模的日益膨胀、普及范围的进一步扩大，得到一个完整准确的网 络拓扑结构图对于网络管理、优化网络、定位故障等应用越来越重要。在国内对 网络拓扑发现技术的研究尚处于初级阶段，因而其迫切性和必要性不容忽视。该 论文内容来源于作者对于一些最新文献资料的系统研究和总结、大胆的创新思路 和大量的实践工作，取得了突破性的进展。 论文的主要内容如下：系统地总结、分析并比较了各种网络拓扑发现算法： 深入研究了基于f i n g 和t r l c e f o u t e r 的网络拓扑发现算法，在原算法的基础上 作了改进，大大提高了算法的效率；通过实践总结了大量实际网络特性，对从事 网络管理、安全分析、性能分析等工作的人员都有很大的实用价值；丌发了一种 全新的算法，即基于i c i p 和ud f ) 的网络拓扑发现算法，并实现了该算法，利用 它得到了实际网络的拓扑结构；提出了一种新的基于丢包率的组播拓扑推算算法 ( i t ) ，并在o p n e l 、中建立了组播树模型，利用该算法得到了该组播树的拓扑 结构。 关键词：拓扑发现i c m pu d p 组播网络 a b s t r a c t i n t e r n e tt e c h n i q u ed e v e l o p sr a p i d l yi no r d e rt om e e tt h es o c i e t y sn e e d t h es c a l e o fi n t e r n e te x p l o d e si nt h e s ey e a r s t h e r e f o r e ，i t sm o r ea n dn l o r ed i f f i c u l tt og e ta c 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 pw h i c hi s h o w e v e r v e r yu r g e n t n o w a d a y s t h u sr 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 eh a sb e c o m ea n i m p o r t a n tp r o j e c t i ti s i ni t si n t h n c yi nh o m e ，s om yr e s e a r c hw o r ks t e m sf r o n l s y s t e m i cs t u d yo ft h el a t e s tp a p e r s c r e a t i v et h o u g h t ，a n da l o to fp r a c t i c e 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 cc 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 y t h ei m p r o v e da l g o r i t h mb a s e do np i n ga n d t r a c e r o u t e ri sp r o p o s e d ，a n dm a n yc h a r a c t e r i s t i c so fr e a ln e t w o r ka r eo b t a i n e db y p r a c t i c e t h i r d l y , w i t hv i e wo ft h ea l g o r i t h m sl i m i t a t i o n ，an e wt o p o l o g ys o f t w a r e b a s e do ni c m pa n du d pi sd e v e l o p e da n dt h er e a lt o p o l o g yi sc o n s t r u c t e db yi t f i n a l l y an e wa l g o r i t h mo nm u l t i c a s tn e t w o r kt o p o l o g yi so b t a i n e d i nt h i sp a r t a l o s s b a s e di n f e r e n c ea l g o r i t h m sb l ti sd i s c u s s e d o nw h i c ht h en e wh b l ta l g o r i t h m i sd e s i g n e d i ti sp r o v e dt h a th b l t a l g o r i t h mi sm o r ea c c u r a t ea n de f f i c i e n t t h r o u g h c o l l e c t i n gd a t ab yo p n e t s i m u l a t i o na n dp r o g r a m m i n g ，m u l t i c a s tn e t w o r kt o p o l o g y i sr e c ) n s t r i l c t e d k e y w o r d s ：t o p o l o g yd i s c o v e r y i c m pu d pm u l t i c a s tn e t w o r k 第一章引言 第一耄雩l 言 随着网络规模的逐渐扩大，需求的日益增长，网络拓扑发现技术日盏显现出 其重要性，在网络领域有麓越来越广泛的应用。本章概述了网络拓扑发现技术的 概念、特点、臻稀及其应用，并用交通嘲形象地类比计算机网络，生动地揭示了 网络拓扑发现技术的概念及含义。 1 1 网络拓扑发现综述 互联网络是时代需求的产物，随着社会需求不断增长，互联网络技术飞速发 震，网络溪模惫囊澎获，懿侮褥戮宠整、准确静爨络拓羚结擒餮越来蘧爨难，毽 其必要性却日益增长，因而网络拓扑发现技术已经成为一个重要的研究课题。 计算辍网终惑壶各秘冬群不瓣戆实镕缀残，这些实体程互终翊褥蔽绘终装爝 户提供各类业务。实体可以用软件戚硬件来实现，在实际网络中这些实体指：调 测鳃调器、鼹喹嚣、应雳鞭务器、瓣捺、交换撬、簧辕链薅等。强鹰一令实髂都 会影响到所提供的业务是谮可以磁常运行，进而对终端用户造成赢接影响。网络 据羚发现露发璎袋鸯建络实体并确定各实体之阕纛连关系懿过程。该过纛不仅毯 括发现实体在网络中的作用、实体间的相艇作用、它们提供业务的方式，还包括 搜集设备蛇一些矬缝测量镶。即搜集实体淘网络提供鲍照务质量( q o s ) 售惠， 例如：某一设备是否可用，在某一时期可提供的最大用户数等。缀过以上的拓扑 发现过程，才得到完整的网络拓扑信息结构图。 以上定义指出了所有的网络设备都必须被发现，而在实际中这是不可能做到 的。发现网络拓扑是一项挑战性的工作，闲为互联网是各种网络的集合体，这些 网络不但设备、软件差异狠大，而且可能被不同的组织所管理，他们的组织、运 营、安全等措施互不相同。另外尉络规模越来越大，而且变化非鬻快( 特别是无 线黼络) ，更增加了拓矜发现的难痰。 一个简单的网络拓扑发现方法是请求网络管理员识别每一个实体，并描述这 些实体豹遮行方式。这样谯可以手正绘剜滋实际豹网络拓扑结构翻，虽然该拓扑 图可以非常准确，但在实际中由予网络实体的数目繁多以及其成搬数级增长的趋 势傻该方法不可麓实现。 掰且各弼络实体豹功毹随着需求不断增加，因而越来越 复杂。再加上网络被不同的组织机构管理，更限制了手工构造网络拓扑的可能性。 尧羧这些困难靛方法是耋动发瑗瓣络据羚，繇诺霸某静冀法或技术发现网络的实 网络拓扑发现技术研究及实现 体、功能、行为、相互作用及他们所提供的业务质量。该方法也须由管理员配置 一些信息，控制系统运行拓扑发现的进度和深度。这些信息可以是初始化信息( 例 如管理员可先发现网络的关键实体，再让该系统去发现网络的其他部分) ，或者算 法结束后请求某些未被发现的信息( 如未发现的设备、功能、及业务等) 。 本论文的研究工作主要集中在发现i p 网的拓扑结构。 发现网络的拓扑结构，首先须明确以下几个问题： 首先，确定这个技术针对网络的哪一层及什么协议，大多数网络采用t c p 1 p 协议，所以一般针对i p 层发现网络拓扑结构。 其次，确定是采用被动还是主动探测技术来实现网络拓扑信息的采集。被动 探测即在所有观测的网络都加入探测器，其优点是仅向网络管理主机递交各个网 络的拓扑信息，无额外流量，负担小，但花费时间长，对大网络安装探测器到所 涉及的各子网中不实际：主动探测即网络管理主机主动向所有管理网络发探测包， 采集返回信息，其优点为速度快，但产生流量大，对低速网络不太合适。 再次，确定采用何种方式收集信息，即采用s n m p 来收集网络信息：还是采 用一种通用的协议收集网络信息( 如使用d n s 、i c m p 等) 。 最后，确定网络拓扑发现的目标及发现程度。这两点均跟实际网络业务需求 息息相关，但不管采用哪种协议和工具，网络拓扑发现的最终目标都是得到一个 快速、完整、正确、高效的网络拓扑发现算法或拓扑工具。所谓快速即算法应能 够实时地发现网络拓扑，且确保数据的内部一致性。一个不能跟上网络实时变化 的拓扑算法适用范围是受限的：而完整性指的是在出现最少错误概率的情况下有 效、正确地发现一个特定网络内的大部分主机和路由器；正确性即算法应尽力保 证拓扑发现结果正确，尽量不出或少出错误；高效性即算法不应消耗过多的网络 资源，仅给网络增加尽可能小的负载。对网络拓扑结构的发现程度可根据具体的 需求决定，对一个无特殊要求的网络进行拓扑发现，发现到路由器和主机级即可。 1 2 网络拓扑发现技术的应用 计算机网络可以形象地类比为一个交通网络，其各种概念、性能分析、功能 配置等均可用交通网来理解，并从交通网络中得到有益的启示。本节从交通网络 模型的角度形象地解释网络拓扑发现的应用。 下表列出了交通网络与互联网络的类比项，从中可以看到两者的相似性。在 研究互联网络的问题时即可借用交通网络已有的模型，并从交通网的解决方法中 寻求解释和帮助。 第一章引言 表1 i 计算机网络与交通网络的类比 交通网互联网络类比项交通网互联网络类比项 交通网的地图拓扑结构图出租车、公共汽车等 网络中的各类不同业务 协议规定、队列管理 公路传输链路黄线、红绿灯 调度算法 路由器可提供的路 乘客发起业务的终端十字路口、丁字路口 由选择 不同干线所能提供不同链路可提供的 地名网络i p 地址 的最大车速最大传输速度 不同干线所能提供不同链路可提供的 上、下车的地点节点 的最大车流量最大带宽 让我们来想象一下交通网中的情况。 图1 i 交通网络 ( 1 ) 、某一市中心南北方向主干道车流量饱和，一乘客乘坐出租车急于从市南 郊到市北郊办理事务，从南郊的十字路口默认到北郊最近的路线便是从市中心穿 过直达北郊，但在该路线上行驶非常缓慢，车停停开开大部分时间处于等待状态： ( 2 ) 、于是在十字路口处选择左拐绕过市中心到达北郊，但左拐发现路况很糟， 路面不平整而且公路狭窄，影响了驾车速度： 网络拓扑发现技术研究及实现 ( 3 ) 、该出租车下次载客时选择右拐线路，在另一十字路1 2 1 等待红绿灯时发现 一个有趣的现象，从南至北红灯时间长，而从北至南红灯时间短，这是由车流量 的大小或为了分流某些路线流量过大而决定的。 交通网的情况简单列出以上几条，我们考虑互联网络中类似的情况： 圈1 ，2 计算机网络 ( 1 ) 、用户3 发起请求，比如说传递e m a i l 业务，该m a i l 要从该用户使用的西 电校园网邮箱传递到武汉大学校园网的用户7 邮箱中，装载此邮件信息的i p 包在 网络链路上传递，所有的路由器均设置了默认路由，但某一段默认路由中经过的 网络链路非常繁忙，等待队列很长，丢包率较大，大大影响了某些实时业务的传 输： ( 2 ) 、该中间路由器可为该i p 包选择另一中间路由。使该邮件尽早到达其目的 地，但在传递过程中又发现某一链路带宽较窄，而业务量较重，因此也影响了该 邮件的传输： ( 3 ) 、在下次选路时，避开这样的链路，选择另外的路由。此外在传递邮件业务 中有一点可以确定，从西电校园网传递业务到武汉大学校园网，和从武汉大学传 到西电选择的各路由一般会有所不同，甚至每一次邮件的传输选路也可能有所差 异，因而速度也有一些差异，当然这与路由器处理速度，链路带宽及自身选路的 智能程度等都有很大关系。 由以上的类比可以看出交通网络和互联网络在很大程度上有着相似性和可参 考性。形象的理解，交通图即包含了所有地名、公路以及各种行驶规定等在内的 拓扑结构图，而网络拓扑图即包含了所有网络中的路由器、主机及互连关系等信 第一章引言 息的结构图。一个完整准确的地区交通图对于该地区的交通系统至关重要，交通 管理机构可以及时准确的定位各公路状况、流量等信息确定是否需要修理，是否 需要拓宽路面，是否需要增修路段，以及合理规划路口红绿灯时间，公路单黄线、 双黄线的位置等等。同样，一个完整准确的网络拓扑结构图对于网络系统的正常 运转也必不可少。网络管理、规划人员，甚至网络的运营商都需要详细的网络拓 扑结构图，以确定网络哪一段链路故障、哪一段为瓶颈，是否需要新增路由选择， 合理规划网络结构，配置默认路由，选择一种协议或称机制使网络智能化等等诸 如此类的问题。 当然两者也有不可类比的方面，例如，交通网络拓扑图由手工绘制即可得到非 常准确而且详细的结果，而计算机网络变化非常快，结构也更复杂，采用手工绘 制具有不可想象的困难，即使使用强大的拓扑工具也不能得到详细的拓扑结构信 息；再如，交通网络的管理和疏通可借助于另一种截然不同的系统一广播系统来报 告路况，帮助管理使其正常运转，而在计算机网络中完全依赖网络设备的控制、 检测、动态路由算法等机制，使其得以正常运行。而且这些机制的存在使得计算 机网络自身的选路比交通选路要智能得多。 总而言之，由以上讨论我们看到了网络拓扑发现技术在互联网飞速发展的今天 独有的不可或缺性。下面便具体给出了网络拓扑发现所得到的拓扑结构在多方面 的应用： ( 1 ) 模拟网络为了模拟实际网络，分析网络性能、合理扩容和优化网络， 必须先得到该网络的拓扑结构： ( 2 ) 网络管理 网络拓扑信息可帮助网络管理者确定是否需要增加新的路 由器，当前硬件是否正确配置，并发现网络中的瓶颈所在和失败的链路， 进行网络优化； ( 3 ) 用户接入方式的选择网络拓扑信息可帮助用户确定自身处于网络中 的位置，从而决定服务器的位置以及选择哪一个网络服务提供商可以将 时延最小化、可用带宽最大化： ( 4 ) 研究拓扑敏感算法 一些新的协议和算法可以在得到网络拓扑信息的 基础上改善网络性能，例如：基于拓扑敏感策略和q o s 的路由选择算法 与基于拓扑敏感进程组选项的组通信算法： ( 5 ) 确定镜像服务器位置根据拓扑信息合理配置镜像服务器的位置以最 大可能减少时延，解决瓶颈问题； ( 6 ) 实行网络服务管理例如：m a i l f t p ，w e b ，s n m p ，d n s ： ( 7 ) 复杂拓扑的可视化： ( 8 ) 统计数据的采集及关联分析。 网络拓扑发现技术研究及实现 1 3 网络拓扑发现技术的发展现状 有许多研究机构和公司着力于发现网络拓扑结构的研究，如c a i d a t ” n l a n r l 2 i ，j a s p v i i ”，g e o b o y ，o t t e r i “，s k i u e r i ”，m i n c i 3 1 ，h p 的i n t e r n e tm a p p i n g l 4 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 o d i s c o v e rp 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 m 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 大学6 1 以及我国的研究人员1 都在研究物理拓 扑发现方法。同时i e t f ( 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 ) 也制定了物理拓扑的管 理信息库( b r i d g e m i b ) f 7 1 1 8 1 。 1 4 论文承担任务及贡献 该论文题目属于国家自然科学基金重点项目“基于网络探测的i p 网络拓扑发 现和性能分析的研究”，为三所高校联合申请的项目，预期四年完成。该项目主要 内容为：研究i p 网络探测及性能分析技术，包括网络性能、拓扑、无线i p 的探测 和分析原理及技术、网络性能评价及分析预测技术，探讨基于网络探测的新技术 和新应用，研究从大规模数据中解析网络和业务特性、网络和信息安全的理论及 方法，架构及探测测量监控为一体的综合网管体系，保证l p 网络安全有效运行， 为发展有自主知识产权的网络探测体系及网络新方法奠定基础。我校负责i p 网络 探测的体系结构、i p 网络探测的原理和方法、i p 网络流及安全性分析、i p 网络拓 扑发现、无线l p 探测方法和技术的研究五部分。 i p 网络拓扑发现是该项目最基础、最重要的部分，得到一个完整准确的网络 拓扑结构图可以使网络探测、性能分析、网络流及安全性分析等工作更加容易、 高效地进行。该部分计划完成内容如下：通过p i n g 发送i c m p 分组，并用t r a c e r o u t e r 跟踪路由，获得1 p 地址集，判断相应设备，并由路由器的接口地址和网络掩码， 可得网络地址及其范围，同时可由d n s 判断多目主机地址，进而形成拓扑；也可 第一章引言 通过访问m i b 中路由表信息实现网络拓扑自动搜索；选择构造依据时还可选用网 络性能参数如链路时延、丢包率等，采用某种算法推算网络拓扑；此外进一步探 讨网络的物理拓扑。 作为项目计划的第一年，该论文已取得了突破性的进展。完成的主要内容及 为项目所作贡献主要有： 1 系统地总结、分析并比较了各种网络拓扑发现算法； 2 深入研究了基于p i n g 和t r a c e r o u t e r 的网络拓扑发现算法，在原算法1 4 3 l 的 基础上作了改进，大大提高了算法的效率。 3 通过实践总结了大量实际网络特性，对从事网络管理、安全分析、性能分 析等工作的人员都有很大的实用价值； 4 开发了一种全新的算法，即基于i c m p & u d p 的网络拓扑发现算法，并实 现了该算法，利用它得到了实际网络的拓扑结构； 5 提出了一种新的基于丢包率的组播拓扑推算算法( h b l t ) ，并在o p n e t 中建立了组播树模型，利用该算法得到了该组播树的拓扑结构。 本文的内容是这样安排的：第二章介绍了网络拓扑发现技术可采用的协议、 工具等，系统的总结了基于不同协议或工具的拓扑发现算法、物理层拓扑发现方 法、无线网络的拓扑发现方法：第三章详细论述了一种改进型的算法，继之提出 了一种全新的拓扑发现算法，并利用它构造了实际网络的拓扑结构：第四章研究 基于网络性能参数丢包率的拓扑推算算法，提出了新的基于丢包率的组播拓扑推 算算法( h b l t ) ，并且在o p n e t 中建立了组播树模型，搜集了大量数据，然后应 用b l t 和新提出的h b l t 算法重新构造了组播网络拓扑结构：第五章总结全文。 网络拓扑发现技术研究及实现 第二章网络拓扑发现技术 本章首先全面、详细地讨论了网络拓扑发现可采用的协议和工具，其次研究 了基于不同协议或工具的各种网络拓扑发现算法，对其进行了分析和比较，最后 论述了无线网络拓扑发现的方法及面l 临问题。 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 r a c e r o u t e r t r a c e r o u t e r 的功能是发现一条主机到目的主机的路径，它利用i p 头中的t t l 子段。开始时信源设置i p 头的值t t l 为l ，发送报文给信宿，第一个路由器收到 此报文后，将t t l 值减l ，丢弃此报文，并发送一个类型为超时的i c m p 报文给 信源，信源接收到此报文后对它进行解析，这样就得到了该路径中的第一个路由 器的地址。然后信源发送t t l 为2 的报文给信宿，第一个路由器把它的t t l 值减 1 后转发给第二个路由器，第二个路由器收到后再减l 。报文t t l 值变为0 该路 由器丢弃此报文并发送一个类型为超时的i c m p 报文给信源。这样就得到了路由 中的第二个路由器地址。如此循环下去，直到报文正确到达，信源就得到了通往 信宿的路由。 这种发送不同的t t l 值在源与宿之间发现路由的方法，除了网络管理者刻意 要隐藏网络内部拓扑信息外，t r a c e r o u t e 均可正确发现路径，其中使用的是i c m p t t l e x p i r e d p a c k e t 响应。 第三章基于网络协议和工具的拓扑发现算法的研究与实现 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 et 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 网络拓扑发现算法的系统研究 该节集中研究不同网络、不同类型的网络拓扑发现问题，从以下几个方面来 探讨：基于网络管理协议的拓扑发现，包括第三层和第二层拓扑发现；基于网络 主动探测和测量的拓扑发现，包括基于网络常用工具的方法( 如p i n g t r a c e r o u t e 等) 、基于端到端组播测量的推算方法：无线网络的拓扑发现方法。同时比较了各 类拓扑发现算法，分析了网络拓扑发现面临的问题。 2 2 1 基于网络管理协议的拓扑发现 目前大多数商业化的网管软件都是基于s n m p ，借助网络设备中的代理，通 过访问或配置m i b ( 管理信息库) 中的变量来实现网络管理功能( 包括性能、故 网络拓扑发现技术研究及实现 辕、诗赞、配置、安全管理五令功能域) 。这蹙m i b 禽毒对踞盘表和转发表及接翻 懿攒透，嚣茈镬褥提蛰撬造成巍可载，不缀菇以稳造窭瓣终基设备( 路交嚣、阚 关) 魏连接关系，焉显毽霹擒造出链路瑟竣务( 瓣轿、交换辊) 酶连接关系，下 藤分掰描述。 一、熬于s n m p 的网络层拓扑发现 旗子网络管理协议进行i p 层的拓扑发现愁网络管理工具的一个重要功能，需 臻用到m i b 库中的变量有1 9 1 ： 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 ( - f 一跳路由器的i p 地址) 、i p r o u t e t y p e ( 路幽类型) 、i p r o m e p r o t o ( 路由协议) 、 i p r o u t e m a s k ( 掩码) 、i p r o u t e l f l n d e x ( 路融懿接目索引) 可用来搜索拓扑； i f t a b l e 接口表，其中i f l n d e x ( 接翻絮葶 ) 、i f d e s c ( 接口摇述) 、i f t 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 层提供了服务，则乙。 对_ 陂相应的层数，则s y s s e r v i c e s 的值为：m = 2 ( 7 “) ，i = l ，2 ，3 ，4 ，7 分别对应物 理鼷，链路层，网络层，传输层，应用凰。例如若s y s s e r v i c e s 的值为6 ，则它是路 由器； i 廿n e t t o m e d i a t a b l e - - - - - 可以访问相连的终端设备的i p 地址。 旗子这些变量并辅之以p i n g ，采用广魔优先遍历算法即可构造出网络拓扑图， 种算法实现鲡下 1 0 1 ： 秘始纯瓣关敬瓢，子弼麸列，连接队列； 戆簸省阚关驶入弼关获囊孛； w h i l e ( 瓣关驮裂菲空) ；从网关队歹i 中取出一个网关，为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 m 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 的连接不重复地放到连接队列中； j f ( i p r o u t e n e x t h o p 属于i p r o u t c 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 g a t e w a y 与i p r o u t e d e s t 懿连接藏鹫连接获残孛； 予嘲内部的搜索可结合p i n g 工具、m i b 燹爨s y s s e r v i e 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 等) 来确定。 子网和路由器的连接检测算法通过s n m p g e t n e x t 操作获取路由表表中有两项 极为重要的m i b 变量i p r o u t e t y p e 和i p r o u t e d e s t 它们分别表示路由类型和所要到 达的目的网络地址，如果i p r o u t e t y p e 的值为3 ，则表示目的网络与路由器直接相连 因而只需找出对应的i p r o u t e r y p e 的值为3 的目的网络地址即可。同时可利用 i p a d e n t l f l n d e x 作为索引，与i n t e r f a c e 组的l f l n d e x 和i t t y p e 相结合来确定子网的网 络拓扑类型。 对于已经检测出的网络设备，确定其类型可通过访问m i b 库的i p f o r w a r d i n g 和 s y s s e r v i c e s 变量决定。这两个变量在m i b 库中定义如下： o b j e c t ：s y s s e r v i c e s s y s t e m7 s y n t a x ：i n t e g e r ( o 1 2 7 ) s y s s e r v i c e s 值表示网络设备可以提供的服务集合，为一整形变量，设为s 。若 设备为o s i 七层中m 层和n 层服务，则该值为s = ”+ ，”。例如，一个节点 只提供路由功能，则该值为s = ( ，1 ) = 4 。如果一个节点为一个主机，具有路由功 能和应用层功能，则该值为s = ( ，4 + 7 。) = 7 2 。因而根据该值可以判断出一个网 络设备的服务层次。各层的功能如表2 1 。 表2 it c p i p 各层及其功能 层号 功能与设备 l 物理层功能，如中继器( r e p e a t e r ) 2 数据链路层或子网，如桥接器( b r i d g e ) 3 i n t e m e t 层功能，如l p 功能( r o u t e r ) 4端到端功能，如支持t c p 功能 7应用层功能，如s n m p , s m t p 等 访问主机的m i b 库变量，如不能访问，可确定为一般主机，否则再根据 s y s s e r v i c e s 得知判定该设备是工作在o s i 的第几层。例如s y s s e r v i c e s = 2 说明工作 在数据链路层，为桥接器。如i p f o r w a r d i n g = 1 ，则可确定为路由器。如果s y s s e r v i c e s = 6 可得m = 2 ，n = 3 ，说明该设备工作在数据链路层和网络层，即可判定该设备为路由器。 这样就可以判断出网络设备的类型。 二、基于交换表信息的链路层拓扑发现 大多数网络管理工具仅提供i p 层的拓扑发现( 路由器之间及与主机之间的连 接关系) ，第二层的设备( 如网桥、交换机) 需要网管人员手工录入。c i s c o ( c i s c o 网络拓扑发现技术研究及实现 d i s c o v e rp 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 ) 等公司设计了针对特定设备的第二层拓扑发现协议，但在复杂的 i n t e r n e t 环境中，使用范围受到限制。i e t f 定义了描述局域网拓扑的m i b | 8j ，但没 有给出如何发现物理拓扑( 第二层拓扑) 。局域网规模的逐渐庞大使得如何发现物 理拓扑越来越引起了研究人员的注意5 1 1 6 儿i ，这些方法都基于网桥( 多端口网桥即 交换机，以下对网桥和交换机不加区分) 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 基于完全交换表信息的拓扑发现【5 j 【6 1 ： 这时，令s ，i 为交换机s 的第j 个端口，a ，为s 。收到的数据帧的源m a c 地 址集( s i 转发表的子集) 。又令a ( b ) 为交换机a 中节点b 的转发端口。相互连接 的交换机网络中，各交换机可能属于同一子网，也可能属于不同子网。 前一种情况，构造拓扑容易些，算法如下： ( 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 p f o r w a r d i n g 及有无b r i d g em i b 判断交换机。 ( 2 ) 发现边： 若4 ，u 4 ，= “( u 是所有节点集合) 且4 ，n a i ，= 中( 空集) ，则s u 与sk i 相连。 若s 。是叶子端口( 不与任何交换相连) 且a 。包含路由器r 的m a c 地址，则s i i 与路由器r 相连。 若存在交换机集s b ，节点集s e ，令 s = & u s , ， 有：v a s 。，v b ，c s ，有a ( b ) = a ( c ) ，则s 中在s b 当中包含一个共 享网段( 集线器) ，使s 中各节点互联。 后一种情况，含有多个子网的交换机网络。拓扑构造算法如下： ( 1 ) 产生有效并集( u n i o n ，女，= 4 ，u 4 ，) 的集合u 。其中各并集应满足： a ，n a k ，= 中： 对每个子网t ，月。ua u 要么包含t 中所有节点，要么一个都不包含： 若s 。s k 属于同一子网，则不存在另外一个予网中的交换机s 。，使 得 _ ，且4 ，n 厶= 。 ( 2 ) 重复以下步骤直到没有更多的有效并集从u 中删除： 如果s k i 出仅出现在一个有效并集中，则： 除了u i i k t 外删掉所有包含s j 的有效并集 删掉所有有效的u 触，x c j , y ， 第三章基于网络拂议和工具的拓扑发现算法的研究与实现 ( 3 ) 对任一有效的u m 得出结论：s i i 与s k i 相连。 注意上述方法需要每个交换机的交换表中与其他节点相连的信息要完整，实 际上生成树自学习的机制使得交换表要定期更新，交换机难免出现故障或其他原 因使得该条件难以满足，因此产生下述方法。 2 基于不完全交换表信息的拓扑发现| 6 l 该方法不需要每个交换机获得全部其他交换机的所有转发表信息，通过考查 每两个交换机的端口的转发表来判断其是否相连。令b 是交换机集合，乱b 是其 中任意两个交换机，a 、是交换机a 的x 端口，b 。是交换机b 的第y 端口，a 。为交 换机a 在端口x 收到的数据帧的源m a c 地址集，a b ，同样。t 。是a 的转发表中除 a a x 外其余m a c 地址集，即除x 端口外其他端口收到的数据帧的源m a c 集之和， 同理t b ，是b 的转发表中除a b ，外其余m a c 地址集。此时如果乙n 五。= 则a 、 和b ，是连通的，反之亦然。依据这个定理可以有三种依据判断交换机a 的x 端口 与交换机b 的y 端口相连( 至少一个满足，并且此时的连通不一定是直接相连， 中间可能包含其它节点) 6 1 ： ( 1 ) 每一交换机在其地址表中都有一项表明另一个的地址( 不包含带外端口， 如控制端口) ；， ( 2 ) 交换机a 在其a 。中含有b ，并且3 k x ，使得a 。n 4 。o ： 【j 归f ，j ，i ，有( a 。n a h ，巾) n 4 ，l 且j k x a b 。n 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 操作的作用。 2 2 2 基于主动探测或测量的拓扑发现 基于主动测量或探测构造网络拓扑，一方面可以利用网络上用来对i n t e m e t 控 制和管理的协议( 如i c m p , i n t e r n e t 控制消息协议) 以及其它服务( 如d n s 域名 服务) 提供的信息，另一方面可以通过测试网络端到端的性能( 其中包含了内部 网络结构，即拓扑的信息) 所蕴涵的信息来构造。 一、基于网络工具( 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 【2 。，该工具采用类似于t r 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 1 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 l ln e t w o r kr e s e a r c hg r o u p ) 也开发了网络拓 扑的探测方法i l 驯 【”j ，和m e r c a t o r 类似，也利用了类似于t r a c e r o u t e 的方法。国内 也做了大量工作1 1 6 1 【2 3 1 。 利用网络工具和服务进行网络拓扑发现的步骤如下： ( 1 ) 确定探测点，在每个探测点确定临时地址组，选择时可根据已有的积累 及网络地址分配的预先知识： ( 2 ) 在每一探测点用p i n g 逐个探测临时组中地址的存活性( 如存活加入永久 组) ，并用t r a c e r o u t e 跟踪中间路由器，利用d n s 的z o n et r a n s f e r 、i s 及向无效端口 发送u d p 分组发现多端口路由器，由网络地址划分子网，相应信息存入对应链表 中，同时根据子网地址扩充临时地址组。重复执行直至遍历完毕； ( 3 ) 将各探测点的获得的链表进行综合，构造主干拓扑； ( 4 ) 在子网内搜索可能存活的主机，构造子网拓扑。 这种方法能粗略的发现第三层拓扑，但是一方面受网管人员干预，获得的信 息很有限，另一方面搜索的时间太长，可是这种具有一定的普遍性，能在一定的 程度上发现网络拓扑。 二、基于端到端性能测试的拓扑推算 通过测量掌握网络性能，考查服务协议( s l a ，s e r v i c el e v e la g r e e m e n l ) 越 来越引起人们的重视，建立了许多测量的基础结构，如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