（计算机应用技术专业论文）高效路由级网络拓扑检测技术的研究.pdf

摘要 摘要 随着网络在社会、经济、生活等各个方面重要性的不断提升，越来越多地 研究机构和科研人员开始从事网络拓扑结构方面的研究。网络拓扑检测是将检 测到的网络设备及其之间的动态连接关系用图形的方式直观地显示出来的技 术，其中可以加入各种有价值的网络属性，如流量、带宽、延迟等等，使网络 管理和研究人员能够从宏观上掌握整个网络的结构。由于网络的规模可能十分 庞大，而且处于快速增长和随时变化之中，通过人工进行网络拓扑的检测工作 是不现实的。拓扑检测的目标是要在尽可能少地影响网络本身运行的情况下自 动发现网络的拓扑结构，具体有两大要求： 高效性：尽可能快地检测网络的拓扑结构； 完整性：尽可能地发现网络中的所有设备及其之间的连接关系。 快速而准确地检测网络的拓扑结构，无论对于各种实际的网络应用，还是 网络相关的理论研究，都有着很广阔的需求和应用前景。尽管目前已经有一些 拓扑检测系统，例如s k i t t e r 项目，正在运行已获取i n t e m e t 的拓扑结构，但这 些系统通常需要数月甚至数年的运行才能完成整个网络的拓扑检测，而且很少 有研究机构和科研人员专门对拓扑检测系统算法的效率进行评估和研究。目前 随着无线网络的不断普及，对网络拓扑检测技术效率上的要求也越来越高，因 此专门针对效率方面的研究是非常重要和有价值的。 本论文专注于网络拓扑检测技术效率方面的研究，为了有效地提高网络检 测的效率，本论文对传统网络拓扑检测算法的效率进行了试验分析和评估，在 分析了传统网络拓扑检测算法的实现之后，认识到该算法效率较低的原因在于 其有很高的拓扑检测冗余度，从而导致大量重复和无效的探测。为了有效地降 低这种拓扑检测冗余度来提高拓扑检测算法的效率，本论文利用基本的网络探 测工具t r a c e r o u t e 和网络拓扑的树状特征设计和实现了b a c k t r a c e t r e e 算法，该 算法对整个网络进行回溯式探测，同时根据探测目的地址是否有响应对其进行 分类探测，从而有效地提高了网络拓扑检测的效率。论文最后的分析结果表明， b a c k t r a c e t r e e 算法的效率是传统网络拓扑检测算法的3 4 倍，同时能够保证算 法的覆盖率在9 5 以上。 关键词网络；拓扑检测；t r a c e r o u t e ；效率 a b s t r a c t a b s t r a c t a st h ei n c r e a s i n gs t a t u so fn e t w o r k i n gi nt h ea l l a s p e c t s ，i n c l u d i n gs o c i e t y , e c o n o m y , l i v e sa n ds oo n ，m o r ea n dm o r er e s e a r c ho r g a n i z a t i o n sa n dr e s e a r c h e r sa r e e n g a g e di nt h er e s e a r c ha b o u tt h en e t w o r kt o p o l o g ya r c h i t e c t u r e m e t h o d so nt h e n e t w o r kt o p o l o g yd i s c o v e r ya r et h et e c h n o l o g i e sw h i c hc a ns h o wt h et o p o l o g y a r c h i t e c t u r eo fn e t w o r ki nt h ew a yo fg r a p h i c s ，a n dt h e s eg r a p h i c sa r em a d eu po f d i s c o v e r e dn e t w o r ke q u i p m e n t sa n dt h el i n k sb e t w e e nt h e m i nt h eg r a p h i c sw ec a n a d dm u c hu s e f u li n f o r m a t i o n ，f o re x a m p l e ，t h r o u g h o u t ，b a n d w i d t h ，d e l a yt i m eo ft h e n e t w o r k n e t w o r ka d m i n i s t r a t o r sa n dr e s e a r c h e r sc a nu s et h i si n f o r m a t i o nt ok n o w t h en e t w o r ka r c h i t e c t u r eb e r e r b e c a u s et h en e t w o r kc a nb ev e r yh u g e ，a n di t s a r c h i t e c t u r ei sc h a n g i n ga l lt h et i m e ，s oi ti su n r e a l i s t i ct od ot h en e t w o r kt o p o l o g y d i s c o v e r yb yh a n d a n dt h et w om a i nr e q u i r e m e n t so fn e t w o r kt o p o l o g yd i s c o v e r y a r e ： e f f i c i e n c y ：d i s c o v e rt h en e t w o r kt o p o l o g ya sf a s ta sp o s s i b l e i n t e g r i t y ：d i s c o v e ra sm a n yt y p e so fe q u i p m e n ti nt h en e t w o r ka n dt h el i n k s b e t w e e nt h e ma sp o s s i b l e i t sv e r yi m p o r t a n tt od i s c o v e rt h en e t w o r kt o p o l o g yf a s ta n de x a c t l yf o rv a r i o u s p r a c t i c a la p p l i c a t i o n sa n da c a d e m i cr e s e a r c h a l t h o u g hm a n ym e a s u r e m e n ts y s t e m s ， f o re x a m p l e ，s k i t t e r , a r ed e p l o y e dt od i s c o v e rt h et o p o l o g yo ft h ei n t e m e t b u tt h e s e s y s t e m su s u a l l yn e e dt or u ni nav e r yl o n gt i m et of i n i s ht h ew h o l et o p o l o g y d i s c o v e r yp r o c e s s ，a n df e wi n d i v i d u a l sa n dr e s e a r c hc o m m u n i t i e sa r ec o n c e m e d a b o u tt h ee f f i c i e n c yo ft h et o p o l o g yd i s c o v e r ym e t h o d s a n da st h ew i r e l e s sn e t w o r k b e c o m e sm o r ea n dm o r ep o p u l a r , t h er e q u i r e m e n t sa b o u tt o p o l o g y d i s c o v e r y m e t h o d sa r es t r i c t e r s ot h er e s e a r c h f o c u s i n g o nt h e e f f i c i e n c yo ft o p o l o g y d i s c o v e r yw i l lb ev e r yi m p o r t a n ta n du s e f u l t h ep a p e rf o c u s e so nt h e r e s e a r c ha b o u tt h ee f f i c i e n c yo fn e t w o r kt o p o l o g y d i s c o v e r y t oi m p r o v et h ee f f i c i e n c yo fn e t w o r kt o p o l o g yd i s c o v e r y , w ee v a l u a t e a n da n a l y z et h ei m p l e m e n to ft h et r a d i t i o n 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 mb y e x p e r i m e n t sa n df i n dt h a ti th a st o oh i g hr e d u n d a n c yr a t es ot h a tt h ee f f i c i e n c yi s v e r yl o w a f t e rr e a l i z i n gt h er e a s o n sw h yt h et r a d i t i o n a lt o p o l o g yd i s c o v e r ym e t h o d i sv e r yi n e f f i c i e n c y , w ei n t r o d u c et h eb a c k t r a c em e t h o da n dd e s i g nb a c k t r a c e t r e e a l g o r i t h mt oi n d u c et h er e d u n d a n c yr a t eo fn e t w o r kt o p o l o g yd i s c o v e r ym e t h o d s i t t a k e sa d v a n t a g eo ft h et r a c e r o u t et o o la n dt r e e - l i k ef e a t u r eo f t o p o l o g ya r c h i t e c t u r e t oi m p r o v et h ee f f i c i e n c yo ft o p o l o g yd i s c o v e r ym e t h o d i nt h ef i n a lp e r f o r m a n c e i i i 北京t 业人学t 学硕i j 学位论文 a n a l y s i s ，w ec a ns e et h a tt h ee f f i c i e n c yo fb a c k t r a c e t r e ea l g o r i t h mi sm o r et h a n t w i c eh i g h e rt h a nt h et r a d i t i o n a lt o p o l o g yd i s c o v e r ym e t h o d ，w h i l et h en e t w o r k t o p o l o g y c o v e r a g ek e e p sa b o v e9 5 k e yw o r d sn e t w o r k ；t o p o l o g yd i s c o v e r y ；t r a c e r o u t e ；e f f i c i e n c y i v 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的 研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含 其他人已经发表或撰写过的研究成果，也不包含为获得北京工业大学或其它教 育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示了谢意。 签名： 关于论文使用授权的说明 本人完全了解北京工业大学有关保留、使用学位论文的规定，即：学校有 权保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部 或部分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 签名：盘次导师签名： 垒至! 圣婪 日期：丝圣：、弓。 第1 章前言 1 1 概述 第1 章前言 随着科技的不断发展和进步，特别是计算机网络技术的发展，越来越多的 企业及个人加入i n t e m e t ，使i n t e m e t 的网络规模持续扩大。为了适应越来越多 和越来越高的应用要求，新节点、新链路不断地被引入到网络中。路出器 ( r o u t e r ) 、服务器( s e r v e r ) 、交换机( s w i t c h ) 、集线器等设备都会影响到网 络运行。管理人员必须手工查看庞大的网络结构，网络的维护工作越来越复杂， 给网络管理带来许多困难瞳1 。于是有许多研究结构和研究人员开始研究自动化 的网络拓扑检测技术口刊，自动化网络拓扑检测能发现工作在网络中的所有或部 分主要设备，自动绘制网络拓扑技术再将它们自动绘制出来，让管理人员能方 便、直观、及时地了解整个网络的运行情况。 网络拓扑检测是将搜索到的网络设备及其之间的动态连接关系用图形的方 式直观地显示出来的技术口吲，包括互连设备( 如路由器、网桥、交换机等) 、 主机和子网等信息，其中也可以加入各种感兴趣的网络属性，如流量、带宽、 延迟抖动等等，使网络管理和研究人员能够从宏观上掌握整个网络的结构，同 时拓扑检测也是网络管理的一个重要组成部分。 拓扑检测同时也是衡量一个商业网络管理系统成败的重要尺度，在整个网 络管理系统的开发中占有相当重要的地位。由于网络的规模可能十分庞大，而 且处于快速增长和随时变化之中，通过人工进行网络拓扑的检测工作是不现实 的。拓扑检测的目标是在对网络本身所做假设尽量少的情况下自动发现网络的 拓扑结构。具体到网络拓扑检测技术有如下的要求： 高效性：尽可能快地检测网络的拓扑结构。 完整性：尽可能地发现网络中的所有设备及其之间的连接关系。 快速而准确地检测网络的拓扑结构，无论对于实际的各种网络应用，还是 网络相关的理论研究，都有着很广阔的需求和应用自i 景。目前对i n t e m e t 拓扑 结构进行动态检测至少在以下方面有着广阔的应用： 1 从宏观上描述网络布局和结构，用以辅助网络所属的管理机构对现有网络 进行分析、调整和优化：如在网络用户相对较多的区域增加新的路由器来 扩容网络、从宏观层次管理规划大范围内的网络布局以缩小地域问差异等； 2 为仿真和模拟大规模网络的总体环境提供大量可靠的原始数据，使仿真后 的网络结构能够更加真实、有效地描述其代表的真实网络。目前，很多网 络研究领域的组织、高校和学者出于实际操作的难易程度、安全性等方面 的考虑，不能直接在i n t e m e t 上进行相关的研究性工作( 例如病毒危害性的 北京t 业人学t 学硕i j 学位论文 研究) ，这就使对i n t e m e t 进行仿真和建模更有着实际研究的价值，而且网 络拓扑建模已经成为网络拓扑研究领域的一个重要分支； 3 为网络协议的设计、分析、优化、实现和评价等相关研究提供研究的基础， 而且网络拓扑检测的研究有利于发现当前网络协议中存在的缺陷，从而对 其进行改进和优化； 4 通过在大范围内进行网络监测，包括对网络拓扑和网络性能( 如网络带宽使 用情况、网络丢包率、r t t 、网络伸缩性等) 的监测，有可能发现网络中的 异常行为，分析大规模分布式网络攻击( 如d d o s ) 的发起范围、控制病毒 传播，以及网络故障隔离，为防范大规模网络攻击提供研究平台和预警手 段； 5 随着无线网络在现实生活中的应用变得越来越普及，对无线网络的拓扑进 行检测也变得越来越来可行。但是无线网络拥有一些不同于传统网络的特 性，例如网络节点由电池供电，而电池的容量一般不是很大，其应用领域 决定了在使用过程中，不能随意给电池充电或更换电池，一旦电池能量用 完，这个节点也就失去了作用。还有动态拓扑特性，无线传感器网络是一 个动态的网络，节点可以随处移动；一个节点可能会因为电池能量耗尽或 其他故障，退出网络运行；一个节点也可能由于工作的需要而被添加到网 络中，这些都会使网络的拓扑结构随时发生变化，因此无线网络应该具有 动态拓扑组织功能。这些特性决定了无线网络的网络拓扑结构不会像传统 的有线网络那样相对稳定，也不能无限地耗费节点的资源。因此，在无线 网络环境中对如何快速、高效地检测出网络拓扑结构的通用技术的研究更 有研究的价值。 网络拓扑图( n e t w o r kt o p o l o g ym a p ) 是网络拓扑结构的可视化表现形式， 拓扑检测生成的网络拓扑图可以帮助网络管理员更好地掌握网络拓扑结构，迅 速定位失效地点，确定失效影响的范围，还可以成为拾取网络元素并调用其它 管理功能模块的共同出发点。随着i n t e m e t 的出现，基于w e b 的网络管理成为 网络管理的一种新的趋势，它使网络管理不再需要地理位置、具体平台和专业 技能等要求，从而给网络管理带来许多方便。 目前，在网络管理标准中，主要有两大网络管理体系：i s o 的c m i s c m i p ( 公共管理信息服务及协议) n 训和i e t f 的s n m p ( 简单网络管理协议) ，它们 从不同的技术观点来看待网络管理问题。其中c m i p 庞大、复杂，是一个大而 全的协议，难以理解、不易实现，且使用时c m i p 的资源占用量是s n m p 的数 十倍，所以并没有得到工业界的广泛支持；而i e t f 的s n m p 设计简单、易于 实现，所以一经提出就得到了( 业界的广泛响应，许多公司相继推出了基于 s n m p 协议标准的网络管理系统和产品，如s u n 公司的s u nn e t m a n a g e r ，h p 第1 章前言 的o p e n v i e w ，i b m 的n e t v i e w 6 0 0 0 等等。 1 2 国内外研究现状 国外的网络拓扑检测研究起步较早，这方面研究的投入也很大。随着 s n m p 旧1 的广泛使用，许多公司采用s n m p 进行网络拓扑检测，开发了一些高 性能的网络管理平台。这些软件包括美国的h p 公司开发的o p e n v i e w n ， a c t u a l i t 公司的o p t i m a ls u r v e y o r ，i b m 的n e t v i e w 2 3 和s u n 公司的s u n n e t m a n a g e 。其中，h po p e n v i e w 在国内较受欢迎。刚丌始，网络拓扑检测集 中于对第三层设备及连接的发现。随着网络的不断扩大、交换机在网络中大量 使用以及网络管理要求的不断提高，许多公司认识到第二层拓扑检测( 物理网 络拓扑检测) 的重要性。h po p e n v i e w 的n n m 6 0 ，c a 的n e t w o r k l t 与f l u k e 公司的新产品m a p s h o t 都加入了这一功能。另外一些设备制造商也加入了这一 行列，例如c i s c o 制定的c i s c od i s c o v e r yp r o t o c o l ( c d p ) 。 贝尔实验室的b r e i t b a r t 与c a r n e g i em e l l o nu n i v e r s i t y 的b r u c el o w e k a m p 等人分别提出了各自基于地址转发表的第二层连接确定算法。b r e i t b a r t 算法主 要通过查询桥地址转发表确定物理拓扑。b r u c e 的算法主要解决在一个广播域 内出现使用集线器连接交换机这类特殊的拓扑问题。包括h p 及c i s c o 在内的 开发网络管理平台的大部分公司，对网络拓扑显示都有研究。此外国外较有名 的软件是o t t e r ，只要能在指定文件中按一定格式提供网络节点和连接信息， o t t e r 便能显示任意一个大型网络。 国内在网络拓扑检测和显示领域起步相对较晚。到现在为止，亦取得了一 些成果。上海金桥网络工程中心开发了在w i n d o w sp c 平台上使用的网络管理 软件g o l dv i e w 。该软件基于简单网络管理协议s n m p 实现对t c p i p 网络的拓 扑检测。该系统能实现对第三层设备及连接关系较正确地发现并以逻辑图的方 式显示。然而，该软件在国内未能推广使用。 华中理工大学对网络拓扑检测也有深入的研究，但也只是完成对第二层设 备及连接关系的发现并以逻辑图的方式显示发现结果。包括西安交通大学在内 的高校和研究所对网络拓扑检测也有较深入的研究。中国科学技术大学研究生 院计算机学部和中国科学院计算技术研究所的几名工作人员，研究了国外的算 法后，提出了一种新的物理网络拓扑检测算法。 目前针对网络拓扑检测技术和算法本身的研究比较多，关注的焦点也是如 何设计和实现能够获得不同级别网络拓扑结构图的系统，但很少有专门针对这 些技术和算法效率方面的研究，其中口3 1 钉的作者在实现拓扑检测系统时做了一 定的效率改进，该研究方向最著名的成果是b d o n n e t 等人的著作n 朝，b d o n n e t 北京t 业人学t 学硕l ：学位论文 在分布式环境下实现了自己的拓扑检测系统，并提出了d o u b l e t r e e 算法来较明 显地提高了算法的效率。 1 3 论文课题的研究意义 高效路由级网络拓扑检测技术的研究意义主要有以下几点： 1 网络拓扑是网络管理的重要组成部分，是网络管理系统保证网络正常、稳 定、高效地运行所不可或缺的功能。 2 高效、快速地检测出网络的拓扑结构让网络管理者能够在较短的时间内了 解网络整体结构，实时得知网络运行中出现的异常情况并进行紧急处理。 3 无线网络的不断普及对传统网络拓扑检测算法的效率提出了挑战，因为无 线网络的拓扑随时都可能变化，网络拓扑检测过程必须在很短时间内完成 才有意义，这就要求拓扑检测系统必须快速完成探测过程。 1 4 论文研究内容及目标 本论文的研究内容如下： 1 介绍了当前各种网络拓扑检测技术及其实现原理。随后在网络拓扑检测的 大环境下分析了各种网络拓扑检测技术及其算法实现的优缺点。在研究了常见 网络拓扑检测技术和相关算法之后，发现在实现大规模网络拓扑检测时传统的 拓扑检测技术和算法的检测冗余度非常高，导致检测的效率很低。 2 分析了传统拓扑检测技术和算法的效率瓶颈和效率较低的原因。 3 设计和实现了基于t r a c e r o u t e t 1 和网络拓扑的树型结构的高效 b a c k t r a c e t r e e 算法【17 1 。 4 对比分析了传统网络拓扑检测算法、b a c k t r a c e t r e e 、d o u b l e t r e e 算法的效率， 总结了b a c k t r a c e t r e e 算法的性能。 本论文的研究目标是在分析传统拓扑检测算法的效率及其性能瓶颈的基础 上，设计和实现高效的路由级网络拓扑检测算法，以适应大规模网络以及具有 动态和实时拓扑结构特征的无线网络等环境下的拓扑检测应用。 1 5 论文结构 本论文的结构安排如下： 第1 章介绍了网络拓扑检测技术的背景和应用，以及国内外关于网络拓扑 检测研究的现状。 第2 章详细地介绍了网络拓扑检测技术的基本概念、功能定义和应用的分 第1 章前言 类，然后介绍了主要的拓扑检测技术、协议及其算法，并分析了各种算法的适 用情况和优缺点。 第3 章分析了传统网络拓扑检测算法的性能，得出了该算法中只有不到 1 0 的探测是有效的，因此其冗余度非常高，算法的拓扑检测效率也很低。本 章随后分析了传统网络拓扑检测算法的性能瓶颈和性能较低的根本原因。在前 面分析的基础上，设计和实现了b a c k t r a c e t r e e 算法来降低探测过程中的冗余 度，提高拓扑检测算法的效率。 第4 章详细分析了b a c k t r a c e t r e e 算法的执行性能，并在模拟试验的基础上 与传统网络拓扑检测算法、d o u b l e t r e e 算法的效率进行了对比。 第2 章网络拓扑检测概述 第2 章网络拓扑检测概述 2 1 常见网络拓扑结构 常见的网络拓扑结构有以下几种： 1 ) 总线型结构： 总线结构是指各网络中的各个工作站和服务器均连接在一条总线上( 如图 2 1 ) ，各个工作站在网络中的地位是平等的，不存在中心控制节点。公用总线 上的信息以串行方式传递，其传递方向总是从发送信息的节点开始向两端扩一 散。 工作站 s口却 心 ) a 图2 1 总线型拓扑 f i g u r e2 - ib u sn e t w o r kt o p o l o g y 总线型结构的网络具有如下优却点：结构简单，可扩充性好；当需要增加 节点时，只需要在总线上增加一个分支接口便可与分支节点相连，当总线负载 不允许时还可以扩充总线；使用的电缆少，且安装容易；使用的设备相对简单， 但可靠性较差；较难维护，分支节点故障查找难。 2 ) 星型结构 星型结构是指网络中的各工作站以星型方式连接组成网络，如图2 2 。星 型网络有一个或多个中央节点，其他节点都与中央节点直接相连，因为这种结 构以中央节点为中心，因此又称为集中式网络。它具有如下特点：控制简单， ：童：些盔兰：耋篓：篓兰三 便于建网；网络延迟时间较小，传输误差较低结构简单：便于管理。但缺点也 是明显的：可靠性较差、成本高、资源共享能力也较差。 图2 - 2 星型拓扑 f i g u r e 2 - 2s t a r t o p o l o g y 3 ) 环型结构 环型结构由网络中若干节点通过点到点的链路首尾相连形成一个闭合的环 ( 如图2 - 3 ) ，这种结构使公共传输电缆组成环型连接，数据在环路中沿着一个 方向在各个节点间传输，信息从一个节点传到另一个节点。 图2 - 3 环型拓扑 f i g u n ：2 - 3r i n g t o p o l o g y 环型结构具有如下特点：环路上各节点都是自举控制，故控制软件简单 由于信息源在_ 环路中是串行穿过各个节点，当环中节点过多时，势必影响信息 传输速率。使网络的响应时间延长；信息流在网中是沿着固定方向流动的，两 个节点仅有一条道路，放简化了路径选择的控制：环路是封闭的。不便于扩充： 可靠性低，个节点故障，将会造成全网瘫痪：维护难，对分支节点故障定位 较难。 4 ) 混合拓扑结构： 星型与总线型相结合的混合型拓扑结构，如图2 - 4 。这种连接比较灵活 适合于较复杂的网络，在实际应用中比较广泛。 图2 4 混合型拓扑 f i g u r e 2 - 4 m i x e d t o p o l o g y 2 2 网络拓扑检测的目标 网络拓扑检测就是探测网络的拓扑结构信息，即发现网络设备并确定网络 设备之间的链接关系，并形象地用拓扑图表示所发现的拓扑结构。网络拓扑检 锢4 涉及到的问题比较多，要实现一个网络拓扑检测方案主要有四方面问题需要 明确： 1 确定某项技术使用的协议属于网络协议层的哪一层以及该协议具体是什么 协议。因为只有确定了网络的层次和协议，才能明确到底什么样的信息要 被采集，才能使这项技术具有比较好的适应性。 2 确定是采用被动监测技术还是主动探测技术来实现网络拓扑信息的采集。 被动监测技术是通过在所有观测的网络都加入一个探测器，由它来采集信 息，并发送到网络管理主机来形成网络的拓扑结构。这种技术的优点是本 身除了向管理主机递交各个网络的拓扑信息，不产生额外的流量。缺点是 由于是各个探测器被动地通过收集各自网络中交换的信息，所以需要花费 北京t 业人学t 学硕f ：学位论文 长的时间才能收集到足够的信息来形成最后的网络拓扑。主动探测技术是 通过网络管理主机主动向所有管理网络发送探测包，并采集返回的信息， 进行分析最终形成网络的拓扑。这种技术的优点是能够比较快的形成整个 网络的拓扑。缺点是需要产生的流量比较大，不适用于带宽较窄的网络。 3 确定网络拓扑检测的目标及检测的深度。这两点均与实际网络业务需求息 息相关，但不管采用哪种协议和工具，网络拓扑检测的最终目标是得到一 个快速、完整、正确和高效的网络拓扑检测算法或拓扑检测工具。对网络 拓扑结构的发现程度可根据具体的需求而定，对一个无特殊要求的网络进 行拓扑检测，发现路由器和主机级即可。 4 采用单点式的拓扑检测还是分布式的拓扑检测。分布式拓扑检测是通过建 立服务器和客户机之间的连接，在服务器端起动拓扑检测过程，将各个探 测点处收集到的拓扑信息发送到客户端，然后在客户端对这些信息进行收 集和整理，最后得到整个网络完整的拓扑结构。 拓扑检测技术有两个重要的指标：一是性能，就是拓扑检测的速度；二是 获得网络拓扑结构的完备性，完备性就是指拓扑搜索得到的网络拓扑结构是否 能真实反映网络结构的实际情况，但由于路由信息本身的不完备性等其它原因， 拓扑检测方法很难得到真实的拓扑结构。这两个问题恰恰是拓扑检测技术中的 难点。 2 3 网络拓扑检测技术的应用 拓扑检测主要应用于以下各个方面： 1 对真实网络进行模拟； 2 网络管理和优化； 3 用户接入方式的选择； 4 研究拓扑敏感算法的性能； 5 确定镜像服务器的位置； 6 执行网络服务管理； 7 统计数据的采集及关联分析； 8 网络战。 2 4 网络拓扑检测技术分类 根据不同的网络拓扑检测粒度，网络拓扑可分为自治系统( a s ) 级拓扑、 i p ( 或路由器) 级拓扑和物理拓扑。在a s 级网络拓扑中每个网络节点表示一 个a s ，是一种粗粒度的拓扑；i p 级网络拓扑中的节点代表一个路由器或一个 第2 章网络拓扑检测概述 子网，是一种中粒度的拓扑；而物理拓扑中的节点还包括交换机、网桥和主机 终端是一种细粒度的拓扑。对应不同的拓扑类型有相应的拓扑检测技术，以下 介绍a s 级拓扑检测技术和路由器级拓扑检测技术。 2 4 1a s 级拓扑检测技术 整个i n t e r n e t 是由许许多多个自治系统a s 组成。自治系统a s 可以定义为： 在单一技术管理下，采用同一种内部网关协议和统一度量值在a s 内转发数据 包、并采用一种外部网关协议将数据包转发到其它a s 的一组路由器和连接的 集合。一般来说，不同的a s 都有不同的域管理者来管理，一个管理域可能拥 有一个或几个a s 。在i n t e r n e t 中目前大约有1 1 0 0 0 个a s 。这些a s 通过外部网 关路由协议b g p ( b o r d e rg a t e w a yp r o t o c 0 1 ) 进行路由数据交换。对于i n t e m e t 中自治系统拓扑，我们是以每一个自治系统为基本单位，分析它们之间的互联 关系，如图2 5 所示。 图2 _ 5 a s 级拓扑图 f i g u r e2 4a s - l e v e lt o p o l o g y 近年来对i n t e m e t 网络拓扑的研究和建模日益增多，特别是自治系统级的 网络拓扑检测。许多研究对于研究因特网自身发展规律有着重要作用，在此基 础上人们已经总结出很多关于i n t e m e t 拓扑的幂率特征嗍。从而为迸一步研究 i n t e m e t 网络，研究和设计下一代网络和协议提供了重要依据。目前，i n t e m e t 中a s 拓扑检测技术n 删主要有b g p 鼯由信息分析法和t r a c e r o u t e 瑚l 测法。 1 b g p 路由信息分析法 边界网关协议( b g p ) 是一个自治系统间的路由协议，从外部网关协议诤 发展而来。b g p 协议己经发布了多个版本，当前较新版本是b g p - 4 。b g p 协议 的一个主要功能是与其他自治系统交换网络可达性信息，包括到达其他自治系 统所要经过的自治系统列表一在进行路由信息交换之前，该协议会将路由信息 进行聚合，并且在存在多路径韵路百肘只交换最优路径的路由。经过这样的处 # 京t 业 学t 学日论z 理可以太大减少自治系统日】需要交换的路由信息，减轻了对网络的负担。 由于b o p 路由器只交换最优的路径所以网络中为了增加可靠性而设置的 备份连接很可能无法通过算法发现。因为实际条件下往往只能从部分a s 路由 器获得b g p 信息，这样经过几次转发后这些连接的相关信息会被隐藏掉。 2 t r a e e r o u t e 探测法 t m e e m u t e 探测法首先需要利州下一节将介绍的基于通用协议的算法获得 网络的i p 级拓扑图。然后再利用其他信息将图中的节点划分到不同的a s 内， 从而得到a s 级的拓扑图。 2 42i p 级拓扑检测技术 在网络拓扑检测领域，i p 级拓扑检测是出现得最早、研究得最多的一个方 面，目前有很多商用软件都实现了这个功能。i p 级拓扑检测主要任务就是发现 i p 网络中第三层( 对应于i s o 七层模型中的网络层) 中各个路由器节点及其互 连关系，另外还要发现路由器各端口所关联的予网，如图2 - 8 所示。 一瑟圈 i n t e r n e t 图2 - 6 i p 级拓扑幽 f i g u r e 2 - 6 i p - l e v e l t o p o l o g y 该技术涉及的问题也是多。首先，由于互联网的迅猛发展，加之t c p 1 p 协议洲只是一个工业标准，有关网络拓扑检测的规范和文档比较少使得拓扑 检测的研究缺少可供参考的标准。因此需要广泛研究各种i p 网络特征，掌握 各类路由设备所能提供的路由信息数据。其次，标准的缺乏最直接的一个影响 就是发现方法种类繁杂。很多发现方法都是基于一定的前提，完成一定范围内 的拓扑检测。再次，网络拓扑结构是一种重要的阻络信息，因而会涉及网络安 全方面的问题。例如，路径信息有时会因为不具备访问权限而无法获取，或者 探测数据包被防火墙过滤等等。所有这些对网络拓扑检测都造成了一定程度的 第2 章网络拓扑柃测概述 影响。 目前主要有三类m 级拓扑检测方法： 1 基于s n m p 协议的拓扑检测方法。该方法通过s n m p 协议查询各网络设备 的m i b 信息来构建整个网络的拓扑结构，所以网络设备是否支持或允许使 用s n m p 协议对直接影响这种方法的发现覆盖率。 2 基于通用协议( 如i c m p ，d n s ) 的发现方法。该方法主要通过收集和分析 t r a c e r o u t e 和p i n g 工具的探测结果重构网络的拓扑。由于t r a c e r o u t e 和p i n g 的探测响应时间较，所以这种方法比较适合于发现中小型网络的拓扑。 3 基于路由协议的发现方法。该方法通过收集r i p ，o s p f 乜2 吨3 3 等协议的路由 信息从而推出网络的拓扑结构。可以通过监听网络中数据或者查询各路由 器的m i b 数据来获得这些路由信息。 2 5 主要的拓扑检测技术和算法分析 确定一个规模较大且经常变化的网络的拓扑结构是相当困难的，但准确的 网络拓扑信息在网络管理等方面至关重要，我们可以通过网络拓扑信息判断当 前设备的配置是否合理，同时它也为网络管理员在网络中排查瓶颈和错误等工 作提供了重要依据。 网络拓扑表征网络中相邻实体的互连情况，具体可以分为物理拓扑和逻辑 拓扑。物理拓扑中的每一个实体直接连接在物理传输链路上。一个物理拓扑可 以对应多个逻辑拓扑，每一个逻辑拓扑是该物理拓扑在某个层次上的抽象，比 如，在i p 层，相邻实体指彼此相隔一跳( h o p ) 的路由器或主机。在本文中， 我们忽略集线器、网桥等工作在链路层的物理设备，只讨论i p 层面上的逻辑拓 扑结构，其中的每个实体对应一个或多个i p 地址。 本节介绍了目前常用的拓扑检测技术和算法，并对它们进行分析比较。下 面首先介绍几种常被用于进行拓扑检测的工具和算法。 2 5 1 相关协议 首先介绍一下与拓扑检测技术相关的各种协议。 2 5 1 1s n m p 协议简介 目前s n m p 是商业、大学和网络研究中最流行的网络管理协议，是事实上 的网络管理工业标准。s n m p 是一个相当简单的协议，但它可以驾驭各种复杂 的异构网络。 1 s n m p v l 的协议层次 北京t 业人学t 学硕f j 学化论文 简单网络管理协议( s n m p ) 是一个应用层的协议，它用于实现网络设备 之间管理信息的交换。使用s n m p 来访问网络设备的m i b 数据库，网络管理 员可以迅速发现影响网络性能的问题并解决问题。 s n m p 工作于u d p 协议之上，因此使用它在主机间通讯时无需先建立连 接。这种方法降低了系统开销，但对报文到达的正确性不作保证。 s n m p 将管理问题分为两个部分，并为每个部分定义了标准。第一部分是 有关信息通信规则的，协议定义了管理机上的客户软件如何与代理通信，同时 定义了管理机与代理交换消息的格式和含义以及名字与地址的形式。第二部分 有关被管理的数据，协议定义网络设备必须保存的数据项和每个数据项的名字 以及用于表示名字的语法。 2 s n m p v l 的体系结构和通信原语 ( 1 ) 体系结构 s n m p 的体系结构包括s n m p 代理和s n m p 管理者两个组成部分。每一个 支持s n m p 的网络设备中都包含一个s n m p 代理，此代理随时记录网络设备的 各种信息；s n m p 管理者通过s n m p 通信协议查询或修改代理所记录的信息。 s n m p 的体系结构模型如图2 7 所示。 臼峨伊臂理系统 蝴麓f 系统 图2 7s n m p 体系结构 f i g u r e2 7s n m p a r c h i t e c t u r e ( 2 ) 通信原语 s n m p 定义了5 种通信原语实现管理进程和代理进程之间的交互信息，它 们分别是： a ) g e t - r e q u e s t 原语：由管理进程发出，请求从代理进程处提取一个或多个 变量的值； b ) g e t n e x t r e q u e s t 原语：由管理进程发出，请求从代理进程处提取一个 第2 章网络拓扑愉测概述 或多个变量的下一个变量的值； c ) s e t r e q u e s t 原语：由管理进程发出，请求设置代理进程中一个或多个变 量的值； d ) g e t r e s p o n s e 原语：由代理进程发出的，向管理进程返回的一个或多个 变量的值，它是前面3 中操作的响应； e ) t r a p 原语：代理进程主动发出的报文，通知管理进程有某事发生。 管理操作原语是被封装在s n m pp d u ( p r o t o c o ld a t au n i t ：协议数据单元) 中。从高层角度来看，p d u 可以看作是包含若干变量的对象，每个变量有它的 变量名和变量值。当一个s n m p 管理者需要查看某个网络设备的配置、性能等 信息时，它就发出一个包含读请求的p d u ，如果相应设备连在网上，并启动了 s n m p 代理，则s n m p 代理将对s n m p 管理者的安全性进行验证，若验证通过， 代理将发出一个p d u 来响应管理者的查询，在这个p d u 中给出待查变量的值。 一个s n m p 报文由三个主要部分组成：一个协议版本( v e r s i o n ) 、一个s n m p 共同体( c o m m u n i t y ) 标识符和一个数据区。图2 8 给出s n m p 报文格式。 l 版本i 共同体数据区 图2 - 8s n m p 报文格式 f i g u r e2 - 8f o r m a to fs n m pm e s s a g e 版本指定s n m p 的版本号( 对于s n m p v l ，它为o ) ； 共同体字段的类型为o c t e ts t r i n g ，它用作一个密码，以验证是否 有权获取或修改管理数据； 数据区可以包括一个或多个s n m pp d u ，每个s n m pp d u 可以是一个 s n m p 请求操作( g e t 、g e t - n e x t 或s e t ) 、对s n m p 操作的响应( r e s p o n s e ) 或一个陷阱消息。s n m p v l 的g e 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 和 g e t n e x t r e q u e s t 操作具有相同的p d u 格式，如图2 - 9 所示。 p d u r e q u e s t e r r o r t y p e i ds t a t u s e r r o r o b j e c t1o b i e e t 2o b j e c t n i n d e xv a l u e1v a l u e2 v a l h en 图2 - 9p d u 的格式 f i g u r e2 - 9f o r m a t o fp d u p d u t