（计算机应用技术专业论文）ip级拓扑测量技术的研究.pdf

摘要 摘要 测量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 拓扑的演化规律等方面都具有重要意义，现实的需要推动了i n t e m e t 拓扑测量研究领域的形成和发展。i n t e m e t 拓扑分为a s 级拓扑和i p 级拓扑。 i n t e m e ti p 级拓扑测量通过测量多条报文转发路径来生成拓扑图，其中测量转发 路径主要采用t r a c e r o u t e 机制，这是目前惟一的、不需要从每个管理域获取专有 路由信息的、可有效地观察报文如何在i n t e m e t 中流动的方法。 随着i n t e r n e t 规模的急剧扩大，网络安全问题越来越受到人们的重视，各种 各样的防火墙被广泛地部署在i n t e m e t 的各个角落。这些防火墙给口级拓扑测量 工作带来了很大的困难。以往的拓扑测量工作通常是使用p i n g 和t r a c e r o u t e 这两 个工具来完成。但是p i n g 发出的i c m pe c h or e q u e s t 数据包以及t r a c e r o u t e 发出 的目标端口为3 3 4 3 4 的u d p 数据包现在已经成为了防火墙的重点过滤对象。因 此，针对i n t e m e t 上广泛部署的防火墙，我们有必要对已有的拓扑检测方法进行 拓展和补充，以使我们的拓扑测量工作能够在现有的网络环境中正常的工作。 我们知道防火墙的作用是过滤那些恶意的数据包而不是过滤所有的数据包。 我们之所以无法获取防火墙后面的网络拓扑结构是因为防火墙将我们的正常探 测数据包当作恶意数据包而进行了过滤。因此如果我们能够在进行拓扑检测之前 通过一定的方法和手段能够对探测路径上的防火墙规则进行探测，然后根据具体 的防火墙的规则构造相应的探测数据包，那么就可以使得我们的探测数据包绕过 防火墙的干扰。 针对上述提出的问题，本文对传统的网络拓扑测量方法进行了扩展，使得扩 展后的拓扑测量方法能够在防火墙的干扰下顺利进行。同时，本文还提出了两种 算法来消除网络拓扑中的无效结点，从而进一步提高网络拓扑测量的完整性。为 了验证本文提出的方法和算法的有效性，我们选择了教育网中的一个子网来进行 拓扑测量实验。在试验中我们分别采用传统的拓扑测量方法和本文提出的方法来 进行网络拓扑检测试验。通过试验数据的对比，我们发现通过使用本文提出的拓 扑测量方法，探测得到的活动节点和路由器的数量都有很大程度的提高。并且， 通过使用本文提出的无效结点消除算法对得到的拓扑数据进行进一步的处理，最 终可以消除绝大部分的无效结点。因此，我们可以得出结论：虽然广泛部署的防 火墙为我们的拓扑测量带来了一定的困难，但是通过认真分析防火墙的安全规 则，我们依然能够找到方法来消除防火墙的干扰，从而得到我们需要的拓扑数据。 关键词防火墙；拓扑测量；安全规则；无效结点消除 a b s t r a c t 皇皇曼曼曼曼! 曼! ! ! ! ! ! ! ! 曼曼! 曼! ! 蔓曼曼! 曼曼! 曼曼曼曼曼曼! ! 曼! 曼! 曼曼! ! 曼! ! ! ! 曼皇! 曼曼曼曼曼曼! 曼! ! ! 蔓! ! 曼! ! 曼曼! ! 曼曼曼i i i t i s v e r yi m p o r t a n t u n d e r s t a n d i n gt h es t l l j c t l l r e a b s t r a c t t om e a s u r et h es t r u c t u r e o fi n t e m e t ，s i m u l a t i n gt h e o fi n t e r n e t t o p o l o g y , f o r e n v i r o n m e n to fi n t e m e t ， a n a l y z i n gt h ee v o l v i n gr u l e so fi n t e r a c tt o p o l o g y , t h en e e do fr e a l i t yi m p e l st h e f o r m a t i o na n dd e v e l o p i n go fm e a s u r i n go fi n t e m e tt o p o l o g y i n t e m e tt o p o l o g yi s c l a s s e dt ot w o ：a sl e v e la n di pl e v e l i n t e m e ti pc r e a t e sg r a p ho ft o p o l o g yb y m e a s u r i n gm a n yf o r w a r dp a c k e t s t h em e a s u r i n g o ff o r w a r dp a c k e t sa d o p t s t r a c e r o u t em e c h a n i s mm a l f l y w i t ht h ee x p l o s i o ni nt h ew o r l d w i d ei n t e m e t ，w ep a y m o r ea t t e n t i o nt ot h ei n t e r a c ts e c u r i t y , m o r ea n dm o r ef i r e w a l l sa r ed i s p o s e do nt h e i n t e r a c t t h e s ef i r e w a l l sb r i n gm a n yd i f f i c u l t i e sf o rm e a s u r i n gt o p o l o g y w eu s u a l l y u s ep i n ga n dt r a c e r o u t et om e a s u r et h et o p o l o g yi nt h ep a s t b u tt h ei c m pe c h o r e q u e s tp a c k e t ss e n tb yp i n ga n dt h eu d pp a c k e t sw h i c h t h ed e s t i n a t i o np o r ti s3 3 4 3 4 h a v eb e c o m et h ei m p o r t a n to b j e c to ff i l t e r i n g s o ，i ti sn e c e s s a r yt oe x t e n dt h e t r a d i t i o n a lm e t h o d so ft o p o l o g yd i s c o v e r y a sw ek n o w n ，t h ef u n c t i o no ft h ef i r e w a l li st of i l t e rv i c i o u sp a c k e t s ，t h er e a s o n w h yw ec a n tg e tt h es 觚c t u r eo fi n t e r a c tt o p o l o g yb e h i n dt h ef n e w a l li st h a tt h e f i r e w a l lf i l t e r st h en o r m a lp a c k e t s s o w ec a nm a k et h ep a c k e tb y p a s st h ef i r e w a l l i f w ec a l ld i s c o v e r 也er u l e so ft h ef i r e w a l l ，a n dc o n s t r u c tt h ec o r r e s p o n d i n gp a c k e t s a c c o r d i n gt ot h er u e so ft h ef i r e w a l lb e f o r em e a s u r i n g t h et o p o l o g y i nt h i sp a p e r , w ep u tf o r w a r dn e wm e t h o d so fm e a s u r i n gt o p o l o g yb a s e do nt h e f i r e w a l lr u l e s ，w ec a ng e tt o p o l o g yd a t ab yt h en e wm e t h o d sw i t ht h ef i r e w a l le x i s t i n g a tt h es a m et i m e ，w ep u tf o r w a r dt w oa l g o r i t h m st oa v o i di n v a l i dn o d e ，c o n s e q u e n t l y t h ei n t e g r a l i t yo fm e a s u r i n gt o p o l o g yi sf u r t h e ri m p r o v e d t ov e r i f yt h ev a l i d i t yo ft h e n e wm e t h o d sa n dt h ea l g o r i t h m s ，w ec h o o s eas u b n e tf r o mc e r n e tt om e a s u r e t o p o l o g y w eu s et h et r a d i t i o n a lm e t h o do fm e a s u r i n gt o p o l o g ya n dt h en e w m e t h o d w ep u tf o r w a r dt om e a s u r et h et o p o l o g y , w ef o u n dt h a t ，w i t ht h en e wm e t h o d so f m e a s u r i n gt o p o l o g y , t h en u m b e ro fl i v eh o s ta n dr o u t e ri si n c r e a s e dal o t ，a n dw e c a l l e l i m i n a t et h em o s ti n v a l i dn o d e sb yu s i n gt h ei n v a l i dn o d ee l i m i n a t i o na l g o r i t h m st o t r e a tt h et o p o l o g yd a t a s o ，w ec a nc o n c l u d e ：t h ef i r e w a l lb r i n g sm a n yd i f f i c u l t i e sf o r t h em e a s u r i n go ft o p o l o g y , b u tw ec a ns t i l lf i n dam e t h o dt oa v o i dt h ed i s t u r b a n c eo f f i r e w a l l ，a n dg e tt h et o p o l o g yd a t aw en e e d ，i fw ec a r e f u l l ya n a l y z et h es e c u r i t yr u l e s o ff i r e w a l l k e y w o r d sf i r e w a l l ；t o p o l o g yd i s c o v e r y ；s e c u r i t yr u l e s ；e l i m i n a t ei n v a l i d n o d e s i i i 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我 所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研 究成果，也不包含为获得北京工业大学或其它教育机构的学位或证书而使用过的材料。与我 一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。 签名： 关于论文使用授权的说明 日期： 堕岁。 本人完全了解北京工业大学有关保留、使用学位论文的规定，即：学校有权保留送交论 文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部分内容，可以采用影印、 缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 签名：导师签名： 蛭监互 日期： 2 的占s ；d 镌l 章绪论 1 1 研究背景及意义 第1 章绪论 2 0 世纪9 0 年代以来，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 r n e t 拓扑结 构进行动态描述具有以下几方面应用： ( 1 ) 宏观网络发展布局以及辅助网络管理：如增加新路由器、网络扩容、从宏 观层次管理规划大范围内的网络发展布局以缩小地区间差距等； ( 2 ) 为仿真模拟i n t e m e t 环境【2 】、协议设计与评价提供研究基础； ( 3 ) 为与拓扑结构相关的算法的性能改进提供依据【3 j ； ( 4 ) 拓扑图可以帮助选择多镜像服务器的位置【4 】、确定连接哪个i s p 可能获得 最小延迟与最大有效带宽等； ( 5 ) 通过在大范围内进行网络监测，包括对网络拓扑和网络性能( 如丢包率、 i 玎t 、网络伸缩性) 的监测等，有可能发现网络异常，分析大规模网络自 动攻击( 如d d o s ) 的发起范围、控制病毒传播范围，以及故障隔离 ( f a u l t i s o l a t i o n ) 【5 】，为防范大规模网络攻击提供研究平台和预警手段，使 国家对全网络更具宏观控制力； ( 6 ) 为i n t e m e t 流量工程( t r a f f i ce n g i n e e r i n g ) 【6 】和网络行为学的研究提供基础 辅助依据。 目前已经由许多高校和科研项目开始进行网络拓扑检测方面的试验和研究： i m p 开始于1 9 9 8 年夏天，其长期目标是获得并保存i n t e m e t 拓扑数据，以 反映其随时间变动的增长情况，这些数据也可用于路由变化问题、d d o s 攻击以 及图论等方面的研究。他们取得了一些拓扑发现成果，发布了一些i n t e m e t 地图， 地图以树状结构采用着色方式显示，美观、漂亮。但正如作者所说，目前只是从 一定程度反映其拓扑结构，实用性尚不是很强【l o 】。 s k i t t e r 1 】结合t r a c e r o u t e 和p i n g ，主动探测转发( f o r w a r d ) 路径，记录r 盯， 跟踪低频持久的路由变化，可视化网络连接。1 9 9 8 年7 月4 个s k i t t e r 结点开始 运行，现在已经有1 8 个s k i t t e r 结点对4 种不同的目标集、超过6 6 万个目的地 址( 覆盖全球可路由网络前缀的5 2 以上) 【l l 】进行探测。需要说明的是s k i t t e r 计 划的目标是研究i n t e m e t 基础设施中的关键组成部分，其工作主要集中于发现 北京工业大学丁学硕士学位论文 a s 级拓扑、拓扑图可视化( v i s u a l i z i n g ) 和i n t e m e t 测量( i n t e m e tm e a s u r e m e n t ) 等方面。 南加州大学的m e r c a t o r 1 2 】采用u d p 报文进行有限跳( 1 i m i t e d h o p ) 的主动 测量，对目的i p 地址采用启发式猜测方法。在有限跳的情况下，该启发式方法 有助于性能的提高【13 1 。m e r c a t o r 也使用松散源路由来辅助发现交叉链接和进行路 由器端口合并1 12 1 。但是，一方面源站选路速度较慢，自动确定采用那些i p 进行 源路由也比较困难，另一方面源站选路有可能使网关崩溃，支持源路由的路由器 不到1 0 ，无法在大规模拓扑发现中使用源路由反映交叉链接和进行端口合并。 c o m e l l 大学的o c t o p u s 2 】项目试验了s n m p 、b r o a d c a s tp i n g 以及z o n e t r a n s f e r 机制。 国内关于i p 网络拓扑发现算法”1 5 】主要是基于s n m p 协议，通过访问 m i b ，结合i c m p 等协议，在局域网或一个管理域等小范围内构造网络拓扑，有 些还考虑发现链路层拓扑。文献 1 6 1 、 1 7 1 简要讨论了基于p 协议拓扑搜索原理， 未涉及在多管理域中进行拓扑发现所可能遇到的问题。可以看出，目前进行 i n t e m e t 路由器级拓扑发现主要是利用所有路由器都支持的i c m p 、u d p 协议， 进行主动探测。 图1 1 省级网络拓扑图 f i g u r e l 一1n e t w o r kt o p o l o g yb e t w e e nt h ep r o v i n c e s 第l 章绪论 图1 - 2 路由疋局部逻辑连接图 f i g u r e l - 2l o g i c a ln e t w o r kt o p o l o g yb e t w e e n r o u t e ri p s 国内的国防科学技术大学、西南交通大学等单位在基于i c m p 协议的i p 拓 扑探测方面的技术比较成熟，但未见有其他面向i n t e r n e t 的大规模网络测量 与分析、可视化技术的相关报道。目前，哈尔滨工业大学计算机科学与工程系实 现了一个大规模网络拓扑测量的原型系统，能够针对大规模网络进行路由口拓 扑结构的自动发现，并进行可视化显示。该课题组对全国范围内的近1 7 万个i p 进行了探测，获得了1 6 1 2 个路由p 结点间的29 4 0 个连接关系，并结合各i p 的 地理信息，生成了分层次的地理拓扑图。与实际结构相比，准确度达到9 0 以上。 其中的省级拓扑图和局部逻辑连接图如图1 1 、图1 2 所示【5 。 1 2 研究内容和研究目标 人们通常会使用p i n g 和t r a c e r o u t e 来获取网络拓扑数据。在传统的网络环境 中，它们工作得很好。但是随着i n t e m e t 的爆炸性增长，网络安全问题变得越来 越严重。为了保护各自的内部网络，网络管理员会在边界路由器上部署各种各样 的防火墙。不幸的是，这些防火墙通常会将我们用于拓扑测量的i c m pe c h o r e q u e s t 数据包和u d p 数据包过滤掉，因此，我们往往不能得到所需要的网络拓 扑数据。为了获得更加完整精确的网络拓扑数据，我们需要寻找其他的网络拓扑 北京工业大学工学硕士学位论文 测量方法来达到这个目的。 本文研究的重点是如何在复杂的网络环境中探测到更多的拓扑数据。本文在 传统的i p 拓扑测量技术的基础上进行了扩展并提出了两种无效节点消除算法来 达到获取更多的拓扑数据的目的。 本文的试验环节中，我们对一个真实的网络分别采用传统的拓扑测量方法和 本文提出的拓扑测量方法进行检测，根据比较最终得到的数据，从而来说明本文 提出的方法和算法的有效性。 1 3 论文的结构 论文的第一章是绪论部分。对研究背景，研究意义以及研究内容进行了概括 的介绍。 论文的第二章将对各种网络拓扑测量方法进行介绍，分析各种方法的适用范 围以及优缺点。 论文的第三章将将对各种防火墙技术进行简要的介绍并分析防火墙的存在 对我们的拓扑测量技术的影响。 论文的第四章提出了通过对传统拓扑测量技术进行扩展，提出了能够提高拓 扑测量完整性的技术。 论文的第五章提出了两种无效结点消除算法，能够进一步提高网络拓扑测量 的完整性。 论文的第六章介绍了网络拓扑测量的实验方案，通过实验数据的对比来验证 本文提出的拓扑测量方法和算法的有效性。 论文的第七章是结论和展望部分。 第2 章各种网络拓扑涮量技术介绍与比较 第2 章网络拓扑测量技术介绍与比较 2 1 拓扑测量技术的分类 2 1 1 按照测量方式分类 网络拓扑测量按照探测方式来分，网络测量技术分为主动探测与被动探测两 种。 主动测量方式 主动测量方式是指通过网络管理主机主动向所有管理网络发送探测包，并收 集返回的信息，进行分析最终形成网络拓扑。 优点：能够比较快的形成整个网络的拓扑 缺点：需要产生的流量比较大。而且一些子网内拓扑发现技术只能适用在本 局域网段，如a r p 协议。 被动测量方式 被动测量方式是指通过在所有观测的网络都加入一个探测器，由它来采集信 息，并发送到网络管理主机来形成网络的拓扑结构。 优点：除了向管理主机递交各个网络的拓扑信息，不产生额外的流量。网络 流量小，网络负担小。 缺点：由于各个探测器被动的通过收集各自网络中的信息，所以要花费长时 间才能收集到足够的信息来形成最后的网络拓扑，并且由于要将探测器安装在所 有涉及的网络中，这对于一个大的网络来说是不大现实的。 2 1 2 按照测量范围分类 网络拓扑测量按照探测范围可分为i p 级拓扑测量和a s 级拓扑测量。 i p 级拓扑测量技术 i p 拓扑测量的主要测量方法分为两类：基于s n m p 协议、基于t r a c e r o u t e 方法。前者主要通过访问m i b 库进行拓扑关系的获取，由于权限的关系，适合 北京工业大学工学硕士学位论文 于在具有管辖权的网络范围内进行测量，所以难以推广应用。后者通过t r a c e r o u t e 实现，可用于i n t e m e t 上的大规模网络测量，一般来讲，当网络上安装有防火墙 软件时，则无法进行测量。这是t r a c e r o u t e 方法面临的问题，也是本文研究的重 点。 基于t r a c e r o u t e 方法的探测过程如下：首先得到网络i p 地址分段，然后利 用路由追踪技术得到一个数据包从源i p 地址到目的i p 地址所经历的所有路由器 的i p 地址，对某一网络的所有口地址进行路由追踪，就会得到该网络所有的路 由器的i p 地址及互联关系。路由追踪技术是基于下面的原理来实现的：首先以 t t l = i 向目的i p 地址的一个不可达端口( 通常是1 0 0 0 0 以上的端口) 发一个u d p 包，这个包在经过第1 个路由器以后，将被路由器丢弃，同时路由器将向源主机 发送一个i c m p 包通知该包丢失，通过解开这个i c m p 包，就可以得到该路由器 的i p 地址。然后，我们再以t t l = 2 向目的i p 地址发u d p 包，重复上面的操作， 直到返回的i c m p 包的类型为目的端口不可达，表明已经到达了目的主机，这样 就得到从本机到目的主机所经过的路由器i p 地址。目前，所有的路由器都支持 这种实现方式。根据由数据搜集模块得到的路径总表，可以直接生成反映逻辑连 接关系的路由口拓扑图，结合各p 所在的地理位置，可以生成城市覆盖拓扑图。 a s 级拓扑测量技术 对于a s 级拓扑检测，人们可以使用b g p 数据【”圳】来构造拓扑图。总的来 说，生成a s 级拓扑图的方法可归结为基于b g p 路由信息的a s 图、基于 t r a c e r o u t e 的a s 图以及基于某些特性采用拓扑生成器合成( s y n t h e s i z i n g ) 的a s 级拓扑图三类。其中，第1 种方法较为普遍。该方法有被动测量和主动测量两种 测量方式可供选择。前者在关键路由结点获取b g p 数据包，再采用有限状态自 动机技术，对捕获的b g p u p d a t e 报文进行处理；后者自备一台路由器，运行b g p 协议，通过与i s p 协商，与相应的路由器建立b g p 对等连接，只接收路由更新 报文，不转发用户数据，这需要对等双方对相应路由器的正确配置。在大量测量 数据的基础上，生成a s 拓扑连接图。通过a s 拓扑连接图，可以直观地了解各 a s 连接关系，分析出哪些a s 起重要作用，不仅可以为新a s 的接入提供指导， 而且还可以为将来信息战中的计算机攻防提供指导依据。 第2 章各种网络拓扑洲量技术介绍与比较 2 2 基于各种协议的拓扑信息获取 2 2 1 基于i c m 协议 在网络拓扑发现中可以把i c m p 的功能分为四类： ( 1 ) i c m p 的请求、回应报文可以实现“p i n g ”功能，得到网络设备的活动性信 息； ( 2 ) 可以利用i c m p 实现广播“p i n g ”。这样可以根据回应主机的i p 地址来探 测目标网络的子网掩码等信息。 ( 3 ) 利用i c m p 的子网地址掩码请求与应答报文获得目标网络的子网掩码。 ( 4 ) 利用设置i c m p 报文中的t t l 值来获取从探测源到目标p 地址的路径信 息，即通常我们所讲的t r a c e r o u t e 命令或技术。 2 2 2 基于s n m p 协议 简单网络管理协议( s n m p ) 是现代网络管理的标准协议，它提供了一种从 网络上的设备中收集网络拓扑信息的方法【2 9 。0 1 。该协议由其代理端( a g e n t ) 收 集相关信息放进m i b 库中，可以通过s n m p 定义的g e t r e q u e s t 和g e t n e x t r e q u e s t 操作来获取设备信息，这种信息是分析各个网络结点之间相互连接关系的判断依 据。在m i b 库中主要有三组信息和拓扑发现相关：系统组( s y s t e m ) 、接口组 ( i n t e r f a c e ) 和i p 组。 ( 1 ) 系统组包括7 个简单变量，其中变量s y s s e r v i c e 可用于判断设备类型：是 否是交换机或网桥，是否是路由器设备等； ( 2 ) 接口组( i n t e r f a c e ) 定义了一个表示设备接口数量的简单变量i t n u m b e r 和 一个接口表i f t a b l e ，表格每行对应一个接口的系列特征参数。由它们我们 可以得到某个设备的接口数量、接口名称、接口类型等接口信息； ( 3 ) i p 组定义了很多简单变量和3 个表格变量，其中变量i p f o r w a r d i n g 为4 表 示该结点具有转发功能，可作为路由器的判定依据。 表格变量包括地址表i p a d d r t a b l e 、i p 路由表i p r o u t e t a b l e 和a r p 地址转换 表i p n e t t o m e d i a t a b l e ，它们都网络层拓扑发现的重要信息来源。访问路由器的 地址表，可得到其各个接口的地址信息。a r p 地址转换表提供了结点所在子网 内设备地址到物理地址的对应转换。从i p 路由表中每一行都能够获取5 个非常 重要的信息，如表2 1 ： 北京工业大学1 二学硕士学位论文 表2 1 i p 路由表部分信息 t a b l e 2 - 1i pr o u t et a b l ei n f o r m a t i o n 属性名称属性含义 i p r o u t e d e s t l p a d d r e s s本路由的目的i p 地址 i p r o u t e i f l n d e x接口索引值 i p r o u t e n e x t h o p l p a d d r e s s本路由的下一跳i p 地址 i p r o u t e t y p e 路由类型 i p r o u t e m a s k本路由的子网掩码 在拓扑发现中主要就是要获取这些设备的基础信息和连接信息，因此，这是 用来得到各个网络结点之间相互连接关系的一种主要的判断依据，目前国内以网 络管理为目的的网络拓扑研究中中大多也使用了这种方法【3 1 弓3 1 。 2 2 3 基于b g p 、o s p f 等路由协议 o s p f t 7 j ( o p e ns h o r t e s tp a t hf i r s t ) 路由协议是i n t e m e t 网络t c p i p 协议族 中一种内部网关路由协议，它是一种典型的链路状态( l i n k - s t a t e ) 的路由协议， 一般用于自治系统a s ( a u t o n o m o u ss y s t e m ) 内。在这个a s 中，所有的o s p f 路由器都维护一个相同的描述这个a s 结构的数据库，该数据库中存放的是各路 由域内部链路的状态信息，通过访问这个数据库可以得到拓扑信息。 b g p 8 j ( 边界网关协议) 是一种外部网关协议( e g p ) ，运行于各个b g p 路 由器之上，它是用来在自治系统之间传递选路信息的路径向量协议。b g p 选路 信息带有一个a s 号码的序列，它指出一个路由已通过的路径。通过它在多个自 治系统间执行路由，与其它b g p 系统交换网络可达性信息。每个b g p 路由器维 护到特定网络的所有可用路径构成的路由表。 对a s 层网络拓扑的研究数据大多来自于r o u t ev i e w 项目所收集的b g p 路 由表，即俄勒冈州r o u t e v i e w s t 2 3 】。现在这些数据可以从一些站点中下载，比如 p c h ( p a c k e t c l e a r i n gh o u s e ) 和w w w r o u t e v i e w s o r g 。还可以从一些公共路由服 务器中获取其完整的b g p 路由表：许多的i n t e m e tl o o k i n gg l a s s ( 窥镜) 服务器 站点上可以运行p i n g 、t r a c e r o u t e 或b g p 等命令，由此也会获取大量的b g p 路 由表信息，如站点t r a c e r o u t e o r g 上就提供了成百上千可用的窥镜服务器。此外， 借助i r r ( i n t e r n e tr o u t i n gr e g i s t r y ) 也可以获取大量的a s 连接信息。可以通过 对这些数据进行分析来得到不同a s 间的拓扑连接情况。 第2 章各种网络 石扑测量技术介绍与比较 2 2 4 基于m o i s 协议瓜m o i s 协议 r f c 812 定义了i n t e r n e t 信息查询协议w h o i s 协议。各级i n t e m e t 管理机 构设立了可以查知i p 地址、域名等所有者登记资料的w h o i s 服务器。用户通 过w h o i s 协议【2 5 j 提供的信息服务，能够获取以下信息： ( 1 ) 有关i p 地址和负责某个口地址范围的系统管理员数据； ( 2 ) 域和相关的注册信息、系统管理员信息； ( 3 ) 自治系统和其相关信息； ( 4 ) 己注册单位的e m a i l 地址、通讯地址、联系电话等信息； ( 5 ) 与主、次域名服务器对应的i p 地址 w h o i s 协议遵循服务器客户端模型。查询w h o i s 服务最常用的u n i x 客户程 序是w h o i s 程序，有些机构也提供了可以使用t e l n e t 手工键入命令的方式使用 m o i s 服务，目前而言，最方便的就是通过浏览器客户端程序来查询使用啪o i s 服务。当然，也可以通过编程的方式来使用。 全球最顶级的w h o i s 服务器是i n t e r n i c 2 6 】( i n t e r a c t 网络信息中心) 的r s 。 i n t e r n i c 。n e t ，还有维护全球教育网的w h o i s 。e d u c a u s e 。n e t 、美国政府网的w h o i s 。 n i c 。g o v 、美国军事网的r i l e 。d d n 。m i l 。各个国家通常有该国家相应的w h o i s 服务器，比如中国的是w h o i s 。c n n i e 。n e t ；而各个i s p 也都提供了相应的w h o i s 服务器，比如v e r i s i g n 公司的w h o i s 。n e t w o r k s o l u t i o n s 。t o m 。 r w h o i s 2 7 】( r e f e r r a lw h o i s ) 与w h o i s 的功能类似，不同的是r w h o i s 在 分等级和可缩放形式等方面作了扩展，然而对用户而言，它的使用方式与w h o i s 查询是一样的。 2 2 5 基于d n s 协议 域名系统( d n s ) 是一种用于t c p i p 应用程序的分布式数据库，它提供主 机名字和p 地址之间的转换及有关电子邮件的选路信息。每个站点保留它自己 的信息数据库，并运行一个服务器程序供i n t e r n e t 上的其他系统( 客户程序) 查 询。对域信息的查询主要有以下几种： ( 1 ) a 查询地址查询，由主机域名得到主机的口地址信息。 ( 2 ) n s 查询查询区域的授权名字服务器。 ( 3 ) p t r 查询域名查询，根据i p 地址( 或m 地址段) 得到对应的主机域 名( 或主机名) 信息。 ( 4 ) h i n f o 查询主机信息查询，包括主机的c p u 和操作系统名称等。 北京工业大学工学硕士学位论文 ( 5 ) a f x - r 查询完全区域传送查询，根据区域名( z o n e n a m e ) 得到该域名 服务器的数据库中有关该区域及其子域的所有资源记录信息。 我们从中获取的i p 地址信息、域名信息以及区域信息对网络拓扑分析都是 非常有帮助的。 2 3 各种方法的特点 2 3 1i c 田协议 p i n g 方法 p i n g 命令用来监测网络结点是否存活，或用于监测到网络结点间的往返时延 ( r 1 r t ) 。通常p i n g 只涉及网络上的源和目的两结点，而忽略网络细节。另外我 们可以使用广播p i n g ，其p i n g 的地址不是一个单一的地址，而是子网的广播地 址，所有位于该子网的主机均对此p i n g 包进行响应，从而一次就可得到子网内 的全部活动主机。 使用p i n g 的最大问题是，当p i n g 一个不存在的或非活动的主机时，一般的 超时值加上为了减少丢包对测量结果的影响而采取的发2 - - 3 个p i n g 包使用的时 间，这样对这类主机的监测代价就非常大。这个问题最直接的解决方案是减少超 时值，但是必须注意不要小于网络实际的往返时延。通过精心设计超时和重发策 略，可以有效减少等待时间同时又减少误判。 使用广播p i n g 的问题是，现在实际网络中广播p i n g 很少得到完全支持，部 分网络由路由器代替子网内的主机响应。在另外一些网络中主机根本就不对广播 p i n g 进行响应，甚至路由器根本不转发能引起广播的包。对该问题的一个解决方 案是设计一个专门的b r o a d c a s tp i n g 程序，其内部实现是直接将子网的广播地址 转变为多个主机地址，然后启动多个线程或进程来分别向主机发送p i n g 包，从 而获取子网内的全部主机地址。 t r a c e r o u t e 方法 t r a c e r o u t e 9 】可用来发现测试点和目标主机之间的路由器。路由器在转发包之 前总是将其t t l 值减1 ，如果t t l 降为0 ，则路由器向源地址发送t t l e x p i r e d i c m p 消息。t r a c e r o u t e 应用了路由器的这个特性，通过发送”几逐渐增大的探 测包，由测试点到目标间的路由器会依次向测试点发送t t l e x p i r e di c m p 包， 从而发现所有路由器。 因为几乎所有的路由器设计时都实现了发送t t l e x p i r e di c m p 消息的功 1 0 第2 章各种网络打i 扑洲军技术介绍与比较 能，所以大多数情况下t r a c e r o u t e 的结果是准确可信的。由于采用逐渐增大t t l 值的方法，每探测一个目标就需要依次发送不同t t l 值的多个包，因此用 t r a c e r o u t e 获取结果比p i n g 要慢的多。可以设计一种并发式的t r a c e r o u t e 命令， 一次发送不同t t l 值的多个包，从而加速路由器的发现速度。 基于i c m p 协议方法的优点 实现简单，针对性强，可以根据不同的目的构造不同的i c m p 报文，如探测 结点可用p i n g 报文，探测连接关系可用t r a c e r o u t e 报文； 由于几乎所有基于t c p i p 协议体系结构的网络设备都支持i c m p 协议，因 此它可以发现网络中活动的所有网络设备，通用性较好； 不仅拓扑发现，也可用于监测网络设备的活动状况。 基于i c m p 协议方法的不足 主要用于判定网络设备的活动性，无法直接得出各网络设备间的直接拓扑连 接关系，因此在构建拓扑关系时还必须依赖其他信息或技术； 用户在使用相关方法获取拓扑信息时，需要有效解决目标网络的边界问题， 合理控制发现范围。 另外有些网络的管理机构考虑到安全的原因，已经将该协议的部分甚至全部 功能禁用，因此，该方法的实际效果受到实际网络配置的约束。 2 3 2d n s 使用d n s 服务器提供的区域传输功能可以一次获取域内许多主机和路由器 的信息，快捷方便，这是它的优点。 但是，如果主机的地址通过d h c p 获得，则d n s 对此就无能为力。此外， d n s 服务器提供的信息可能与实际情况不一致，甚至有些d n s 服务器没有提供 区域传输功能。尽管如此，d n s 在拓扑发现中还是很重要的，我们可以把d n s 返回的信息作为其他算法的起点；我们还可以在不知道网络具体结构的情况下， 使用不同时间返回来的信息直接用来估算网络的增长速度等。 2 3 3 、o i s 由前述可以看出，通过w h o i s 查询，可以得到相关i p 、a s 、域名甚至注册 单位的非常详细的信息，这在进行网络拓扑研究期间是非常完备的，但是相应的 也增加了处理的复杂性，即有些信息可能并不是必需的，这就需要研发者通过一 北京t 业人学丁学硕 ：学何论文 定的策略或方法来过滤和分析出自己所需要的信息，抛弃冗余信息。 另外，随着网络化速度的加快，w h o i s 查询数据库中的信息也可能与实际的 信息有所偏差甚至出现错误，这就需要在实际的应用过程中，通过其它的技术或 方法对其有效性和正确性进行验证，加以补充。 2 3 4s n s n m p 方法的优点 信息自动随网络的状况更新，这样通过s n m p 获取的拓扑信息总是反映网 络最新的状况； 实现的过程和算法相对比较简单； 目标明确，发现效率高，系统和网络开销小； 由于从路由器m i b 表可以获得下一站地址信息，因此对于受到访问限制的 网络，仍然可以发现其第一级路由器，得到比较完整的整体网络拓扑关系。 正由于此，该实现方法除了用于局域网的网络管理之外，还用于大型主干网 络的拓扑发现，发现网络中的路由设备，反映网络的整体拓扑情况。 s n m p 方法的缺点 对于只使用静态路由配置的路由器，其发现效果将受到很大约束。这是由于 仅仅使用静态路由配置的路由器，其路由表中的下一站地址项对应的很可能是该 路由器本身相应端口的i p 地址，而不是实际的下一结点； 路由器m i b 表中包含了大量对拓扑发现来说是冗余的信息； 并不是所有设备都支持s n m p 协议，而且除了标准的m i b 信息外，各厂家 都为自己的设备开发了专门的m i b ，如果在拓扑自动发现程序中使用了这些 m i b ，其处理上可能不得不随厂家的不同而作特殊的处理。 2 3 5 基于b g p 路由协议的方法和t r a c e r o u t e 方法的比较 t r a c e r o u t e 和b g p 路由协议方法通常都被作为网络的拓扑和性能分析的有效 手段，相比较起来，前者很好的提供了路由器级的网络连接图；后者则可以得到 更多的有关于网络上自治系统间( a s ) 的连接关系，构造的是a s 级的网络连接 图。t r a c e r o u t e 是主动的获取路径信息，需要使用探测包，而且获取的路由信息 是探测数据包所走的真正路径；而b g p 则不需要探测数据包，它反应的路由信 息不是数据包实时的路径，而是到达某网络的最佳路径。 第2 章再种网络拓扑测量技术介绍与比较 通过t r a c e r o u t e 和b g p 路由协议所获得的数据很可能会有所不同。实际的 网络拓扑研究指明，s k i t t e r ( 利用t r a c e r o u t e ) 构造的a s 路径图比用r o u t e v i e w s ( 收集的是全球b g p 路由表) 中所构造的a s 路径图在数量和规模上都要大， 也就是说在使用这两种方法得到的a s 路径之间存在有不一致的数据。 分析其原因，主要包括：为网络交换点( i x ) 所分配的a s 通常很少出现在 b g p 表中，却大量的出现