（计算机科学与技术专业论文）非授权目标网络拓扑发现技术研究.pdf

国防科学技术大学研究生院硕上学位论文 摘要 随着计算机技术和网络技术的快速发展，计算机网络拓扑结构无论是结点还 是它们之间的连接关系都越来越复杂。网络结点，例如自治系统、服务提供商、 路由器、交换机、主机，和结点间关系的多样化和复杂化都极大增加了网络拓扑 发现的难度。而网络拓扑发现又是网络构建、维护和研究等的基础，只有了解整 个计算机网络拓扑结构才能更好地设计和维护网络，研究者只有拥有足够可信的 网络拓扑才能获得可信的研究结果。 大多数研究者并不具有网络的管理权限，所以很难直接得到研究网络特性的 拓扑数据。所以对于非授权目标网络的拓扑发现是研究者必须解决的问题，但目 前的非授权目标网络拓扑发现系统和技术中存在着各种亟待解决的问题，例如路 由器多址综合问题、匿名路由器问题等。 本文针对非授权目标网络中的自治系统级和路由器级拓扑发现过程和现有发 现技术中存在的问题，提出了几种解决这些问题的关键技术，并开发了一套自动 进行非授权目标网络拓扑发现系统- t o p d i s c 。本文的主要工作包括： ( 1 ) 系统地分析了现有网络拓扑发现中自治系统级拓扑发现技术和路由器级 拓扑发现技术及这些技术的特点和不足。 ( 2 ) 进一步区分了授权目标网络和非授权目标网络拓扑发现，并针对非授权目 标网络提出了一套系统的拓扑发现过程和技术。 ( 3 ) 针对现有路由器多址综合技术的不足，提出了邻居子网综合法，较好地解 决了路由器级拓扑发现中路由器多址综合问题。 ( 4 ) 提出了一种新的匿名路由器处理技术带条件的最大匿名综合法。较好 地解决了路由器级拓扑发现中的匿名路由器问题。 ( 5 ) 改进了现有的弹簧磁力模型，使其更加适合绘制结点数较多、连接关系较 复杂的计算机网络拓扑图。 ( 6 ) 开发了一套非授权目标网络自动拓扑发现工具- t o p d i s c 。该工具实现 了全自动对非授权目标网络中自治系统级和路由器级拓扑发现，并将发现结果分 别以数据库和图形化的形式展示给用户。 本文提出的网络拓扑发现过程和技术主要针对非授权目标网络，在t o p d i s c 中应用后不但增加了拓扑发现范围、缩短了发现时间，而且完善了目标网络的拓 扑图展示，使其更加完整和准确。 关键词：计算机网络，i n t e m e t ，拓扑发现，自治系统，路由器拓扑 第i 页 国防科学技术大学研究生院硕卜学位论文 a b s t r a c t w i t ht h ed e v e l o p m e n to fc o m p u t e rs c i e n c ea n dn e t w o r kt e c h n o l o g i e s ，t h es t r u c t u r e o fc o m p u t e rn e t w o r ki sm o r ea n dm o r ec o m p l i c a t e dd u et ot h ei n c r e a s i n gn o d e sa n d l i n k s d i f f e r e n tk i n d so fn o d e si nc o m p u t e rn e t w o r k ，s u c ha sa u t o n o m o u ss y s t e m s ， i n t e r n e ts e r v i c ep r o v i d e r s ，r o u t e r s ，s w i t c h e s ，h o s t s ，a n ds oo n ，a n dv a r i o u sl i n k sm a k e t h ed i s c o v e r yo fc o m p u t e rn e t w o r kt o p o l o g ym u c hm o r ed i f f i c u l tt h a nb e f o r e a tt h e s a m et i m e ，a st h eb a s e so fn e t w o r kb u i l d i n g ，m a i n t e n a n c ea n dr e s e a r c h ，n e t w o r k t o p o l o g yd i s c o v e r yi ss t u d i e db ym a n yr e s e a r c h e r s m o s to fr e s e a r c h e r sa len o tt h en e t w o r ka d m i n i s t r a t o r s ，s oi ti sn o ta ne a s yt h i n gf o r t h e mt og e tt h et o p o l o g yi n f o r m a t i o no ft a r g e tn e t w o r k d i r e c t l y w h a tt h e s er e s e a r c h e r s c a nd oi sm a k i n gi tp o s s i b l ei nu n a u t h o r i z e dt a r g e tc o m p u t e rn e t w o r k h o w e v e r ，t h e r e a r es o m ep r o b l e m si nt h er e c e n tt e c h n i q u e sa n ds y s t e m s ，f o re x a m p l et h er o u t e ra l i a s r e s o l u t i o na n da n o n y m o u sr o u t e rp r o c e s s i n g t h i sd i s s e r t a t i o n ，a i m i n ga tt h ep r o b l e m si na st o p o l o g ya n dr o u t e rt o p o l o g y d i s c o v e r yt e c h n i q u e sa n dp r o c e d u r e s ，p r o p o s e ss e v e r a lc r i t i c a lt e c h n i q u e st os o l v et h e s e p r o b l e m s ，a n dd e v e l o p sat o o ln a m e da st o p d i s ct od i s c o v e r yt h et o p o l o g yo f u n a u t h o r i z e dt a r g e tn e t w o r k t h em a i nw o r ko ft h i sp a p e ri sg i v e na sf o l l o w s ( 1 ) i n t r o d u c ea n da n a l y z et h er e c e n tt e c h n i q u e so fd i s c o v e r ya st o p o l o g ya n d r o u t e rt o p o l o g ya n dt h e i rd i s a d v a n t a g e s ( 2 ) d i s t i n g u i s h b e t w e e nt h e t o p o l o g yd i s c o v e r y i na u t h o r i z e da n d u n a u t h o r i z e dt a r g e tn e t w o r k ，a n dp r o p o s ea p r o c e d u r ea n das e to ft e c h n i q u e si n u n a u t h o r i z e dt a r g e tn e t w o r kt o p o l o g yd i s c o v e r y ( 3 ) p r o p o s e an e wr o u t e ra l i a sr e s o l u t i o n t e c h n i q u e ， n a m e da s n e i g h b o r s - s u b n e tr e s o l u t i o n ，w h i c hi sm u c hb e t t e rt h a nt h ee x i s t i n gm e t h o d s ( 4 ) p r o p o s ea n e wa n o n y m o u sr o u t e rp r o c e s s i n gm e t h o d ，n a m e da sm a x i m a l a n o n y m o u sr o u t e rp r o c e s s i n g ( 5 ) e n h a n c et h ee x i s t i n gs p r i n gm a g n e t i cm o d e l ，a n dm a k ei tm o r es u i t a b l e f o rd r a w i n gt h et o p o l o g i e so f c o m p u t e rn e t w o r k ( 6 ) d e v e l o pas y s t e m ，n a m e da st o p d i s c ，w h i c hi sa na u t o n o m o u st o p o l o g y d i s c o v e r ys y s t e mf o ru n a u t h o r i z e dn e t w o r k t o p d i s ca l s oc a np r o v i d ev i s u a l i z a t i o n o ft h et o p o l o g i e s b yu s i n gt h et e c h n i q u e so ft o p o l o g yd i s c o v e r yp r o p o s e di nt h i sp a p e r ，t o p d i s c g e t sl a r g e rt o p o l o g yr a n g ea n dl e s st i m ec o n s u m p t i o n ，a n dt h et o p o l o g i e sa r em o r e a c c u r a t ea n dc o m p l e t e k e y w o r d s ：c o m p u t e rn e t w o r k ，i n t e r n e t ，t o p o l o g yd i s c o v e r y ，a u t o n o m o u s s y s t e m ，r o u t e rt o p o l o g y 第i i 页 国防科学技术大学研究生院硕一f 二学位论文 图2 1 图2 2 图3 1 图3 2 图4 1 图4 2 图4 4 图4 5 图4 3 图4 6 图4 7 图4 8 图4 9 图5 1 图5 2 图5 3 图5 4 图5 5 图5 6 图6 1 图6 2 图 图 图 图 图7 2 图 图 图 图 图7 7 图7 8 图目录 i r r 数据库中某a s 的配置信息1 0 t r a c e r o u t e 工作过程1 1 b g p 路由表基本格式16 m i s s i n g 1 i n k 问题示意图18 同一地址段的t r a c e r o u t e 示意图2 3 “叶柄”问题示意图2 3 u d p 高端口探测原理示意图2 5 u d p 高端口探测的失效2 5 i p 报文i d 值判定原理2 6 双向t r a c e r o u t e 子网综合原理2 7 邻居子网综合法原理示意图2 7 带条件的最大匿名综合法举例一3 0 带条件的最大匿名综合法算法描述一3 1 弹簧模型初始状态3 3 弹簧模型平衡状态3 3 各种磁场模型3 5 磁力模型示意图3 5 弹簧磁力模型举例3 6 结点收缩举例3 8 t o p d i s c 系统结构图4 0 目标探测子系统结构4 1 t r a c e r o u t e 原始数据格式4 3 数据库子系统结构4 6 信息展示子系统结构一4 7 未经优化的目标网络a s 拓扑图4 9 使用改进的弹簧磁力模型的a s 拓扑图5 0 目标网络a s 度数分布图5 0 路由器度数分布5 1 各种方法的回包率、别名率和综合率5 2 匿名元分布图一5 3 未经优化和匿名处理的路由器拓扑图5 3 经过优化但未匿名处理的路由器拓扑图5 4 第v 页 国防科学技术大学研究生院硕l 二学位论文 图7 9 未经改进但匿名处理后的路由器拓扑图5 4 图7 1 0 改进后且匿名处理后的路由器拓扑图。5 5 第v i 页 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已 经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它教育机构的学 位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文 中作了明确的说明并表示谢意。 学位论文作者签名： 叟翊仝趟日期：小气器年阻月易日 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留使用学位论文的规定。本人授权国 防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子文档，允 许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据库进行检索， 可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密学位论文在解密后适用本授权书。) 学位论文作者签名：垫k 遂l 作者指导教师签名：逝 日期：忒、分年i 。月，占日 日期：g ? 年1 1 月i 日 国防科学技术大学研究生院硕士学位论文 第一章绪论 1 1 非授权目标网络拓扑发现 网络拓扑作为一种基本的描述网络结构的信息，在计算机网络安全【l ，2 1 、网络 建模【3 - 7 1 、网络协议设计0 1 、网络评估等研究工作中有着基础地位【1 1 1 。但随着计 算机网络特别是i n t e m e t 的普及，计算机、路由器等网络设备和网络协议的多样化， 使得计算机网络从结构、功能、拓扑上越来越复杂。这给构建、研究和维护计算 机网络都带来了很多新的挑战。网络拓扑作为网络构建、研究和维护的必要信息， 其发现也变得越来越困难。 非授权目标网络拓扑发现是目标网络拓扑发现的一种。目标网络拓扑发现是 指针对研究者关心的处于一个物理地域或逻辑区间( 同一或相邻地址空间) 中的 网络设备以及它们之间连接关系的发现，有较强的针对性。非授权目标网络拓扑 发现是指研究者不具备要进行拓扑发现的目标网络的管理权限，只能作为一般网 络用户来对目标网络进行探测发现。与其相对的为授权目标网路拓扑发现，研究 者拥有整个目标网络的访问权限、甚至是管理权限，研究者只要对目标网络中的 每个网络设备的配置信息、连接信息等进行获取和综合分析就可以获取该目标网 络拓扑图。相对非授权目标网络拓扑发现来说授权目标网络拓扑发现要容易得多。 目前的网络拓扑发现一般分为三个拓扑发现级别，分别是自治系统 ( a u t o n o m o u ss y s t e m ，简称a s ) 级、路由器级和局域网级拓扑发现。各个层次的 拓扑发现都有不同的特点和技术手段。目前a s 级拓扑发现主要通过对i i 汛( i n t e m e t r o u t i n gr e g i s t r y ，i n t e r n e t 路由注册) 数据库( 例如a p n i c 、r i p e 等数据库) 中信 息的分析和使用t r a c e r o u t e 工具【l 卜b 】来完成；路由器级拓扑发现技术主要通过使用 一些网络协议如s n m p ( s i m p l e n e t w o r km a n a g e m e n tp r o t o c o l ，简单网络管理协 议) 、o s p f ( o p e ns h o r t e s tp a t hf i r s t ，开放优先最短路径协议) 等【l l h 6 1 ，和 t r a c e r o u t e 工具l l 卜1 9 j 来实现；局域网拓扑发现主要是通过使用i c m p 协议( i n t e m e t c o n t r o lm e s s a g ep r o t o c o l ，因特网控制报文协议) 、p i n g 工具等来实现【l l 1 3 - 1 6 ，1 8 。2 1 1 。 在非授权目标网络拓扑发现中，研究者无法使用基于管理员权限的拓扑发现 方法，例如s n m p 、o s p f 等基于网络设备配置信息或路由器路由表的技术手段。 此时研究者需要通过一些辅助的探测工具( 例如t r a c e r o u t e ，p i n g 等) 来发现目标 网络拓扑，同时在探测和发现过程中要尽量不引起目标网络结构、流量等的变化。 由于网络的复杂性、多样性、不稳定性等因素，现有的计算机网络拓扑发现 过程和技术手段存在很多问题，例如发现周期长、使用探测结点多、探测结点部 署困难、结点和连接遗漏等。匿名路由器问题、路由器多址综合问题等成为计算 第1 页 国防科学技术大学研究生院硕士学位论文 机网络拓扑发现的难点。同时考虑非授权目标网络固有特点，使得原有的拓扑发 现模型、方法、技术和手段并不能直接用于非授权目标网络拓扑发现。因此需要 提出新的技术手段和模型才能较好地解决这些问题，实现非授权目标网路拓扑发 现。 非授权目标网络拓扑发现，让研究者可作为一般网络用户对目标网络进行拓 扑发现和研究。使网络拓扑研究更加普及，而不只是一些研究机构或研究者的特 权。而且准确、完全的网路拓扑也是网络协议发展、网络安全研究、网络构建、 网络演化等研究工作的基础【1 1 ，1 4 l5 1 ，对网络技术的发展可以产生重大作用。 1 2 网络拓扑发现的国内外研究现状 网络拓扑是各种网络研究的基础，具有非常重要的作用。因此网络拓扑发现 技术在国内外都得到了广泛的重视和充分的研究。以下是目前国内外一些再网络 拓扑发现方面取得一定成就的一些研究者和研究机构及他们的研究成果。 ( 1 ) r o c k e t f u e l ，是以n e i ls p r i n g 、r a t u lm a h a j a n 和t h o m a sa n d e r s o n 为主要成 员的计算机网络拓扑探测、研究小组，对整个i n t e m e t 进行探测。他们主要使用路 由信息，选择最有价值的i p 地址进行t r a c e r o u t e 探测，同时进行路径缩减、路由 器多址综合等工作。r o c k e t f u e l 的目的在于使用尽可能少的探测量来建立精确的网 络拓扑刚2 2 - 2 4 】。 ( 2 ) 德州大学( u n i v e r s i t yo f t e x a s ) 的m e h m e tg u n e s 和k a m i ls a r a c 在路由器 多址综合( i pa l i a sr e s o l u t i o n ) 方面使用u d p 高端口探测和i p 报文i d e n t i f y 属性获 取技术，取得了非常好的效果1 2 m 引。 ( 3 ) 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 原始数据著称，并开发了s k i t t e r 等系统1 2 9 j 。 ( 4 ) 康奈尔( c o m e l l ) 大学开发的o c t o p u s 系统，综合s n m p 、t r a c e r o u t e 、启 发式猜想等拓扑发现方法，进行域内和骨干网的拓扑发现。 ( 5 ) 南加州大学工程学院信息科学研究所( t h eu n i v e r s i t yo fs o u t h e r nc a l i f o m i a s c h o o lo fe n g i n e e r i n g si n f o r m a t i o ns c i e n c e si n s t i t u t e ) 设计了一个拓扑发现模型 m e r c a t o r ，利用t r a c e r o u t e 等工具提供的逐跳回馈( h o p b y h o pf e e d b a c k ) ，发现 网络拓扑中的i p 地址，构造网络拓扑图。尽管有一些路由器不响应t r a c e r o u t e 报 文，但该方法仍在当前的i n t e m e t 上取得了可喜的结果。 ( 6 ) 还有一些其它学术组织和研究者也有非常好的研究成果【1 ，1 8 。2 1 ，2 8 ，3 0 。3 6 1 。 目前，市场上也有一些产品实现简单的网络拓扑发现功能，但主要是针对网 络故障管理和网络性能管理的。网络故障管理主要侧重于实时的监控，而网络性 第2 页 国防科学技术大学研究生院硕上学位论文 能管理更看中历史分析。网络管理的软件很多，商用的企业级网络和系统管理平 台主要有：h p 的o p e n v i e w ，i b m 的t i v o l i ，c i s c o 的c i s c o w o r k 2 0 0 0 ，c a 的u n i c e n t e r t n g ，s u ns o l s t i c ee n t e r p r i s em a n a g e r ，a d v e n t n e t 公司的a d v e n t n e tw e bn m s ， 3 c o m 的t r a n s c e n d ，还有国内网络博视的i pv i e w 系列网络管理系统，清华紫光的 b i t v i e w 网络管理系统，巨澜中文版网络管理系统，方正集团的n e t i n w a y 系统等 垄奎【1 1 ，1 3 ，1 5 ，1 6 ，2 0 ，2 l ，3 7 】 弋丁。 这些产品和工具都是针对网络管理来实现的，这就要求拓扑探测者具有网络 管理员身份。它们具有以下特性： ( 1 ) 主要是对于局域网进行管理和拓扑发现，能够发现一部分路由器级网络， 但不涉及更高级别的网络拓扑发现； ( 2 ) 只能对处于系统管理中的网络进行发现，对于非授权的目标网络则无能为 力； ( 3 ) 主要是针对企业用户而并不是一般的研究者，更侧重于网络管理； ( 4 ) 拓扑发现一般作为网络管理的手段，并不做独立的研究，这使得这些工具 拓扑发现能力较弱。 从以上内容可以看出现有系统和工具虽然实现了一部分网络拓扑发现功能， 但它们并不适合非授权目标网络的拓扑发现。 1 3 课题研究背景和意义 在信息技术、计算机技术和网络技术高速发展的大背景下，i n t e m e t 开始在人 类社会中扮演越来越重要的角色。越来越依靠网络的人们，开始对网络拓扑结构 及其演化开始进行深入研究。这不是偶然的，是有其内在必然因素的。 计算机网络以极快的速度渗透到我们生活的方方面面，但其安全问题却日益 严峻，网络安全时间屡见不鲜。有报道【3 别称在2 0 0 3 年年初网络攻击事件已经造成 的全球经济损失高达1 6 0 亿美元，将近2 0 0 2 年同期的两倍。这是由于在2 0 0 3 年1 月2 5 日，一只针对s q ls e r v e r2 0 0 0 系统漏洞的蠕虫病毒在全球蔓延开来，美国 银行系统受到侵害，韩国互联网开始出现全国范围内的瘫痪，其它国家也受到不 同程度的影响。在网络安全日益严峻的情况下，对网络拓扑特征、病毒传播特性 等的研究迫在眉睫。而这些研究都必须以获知计算机网络拓扑为前提，可见拓扑 发现的重要性。具体体现在以下几方面。 ( 1 ) 计算机网络拓扑信息是网络攻击防御中的必要信息【1 ，2 1 。只有对自身或对 方网络有足够的认识才有可能在强度网络攻击中保护自身网络核心设施、维护网 络正常运行。 ( 2 ) 计算机网络拓扑信息还是网络构建和安全评估的重要根据【3 - 1 7 1 。拓扑结构健 第3 页 围防科学技术大学研究生院硕十学位论文 壮的网络比拓扑结构脆弱的网络更加安全，例如全互联网络在安全性能上明显优 于星形网络或树形网络。 ( 3 ) 计算机网络拓扑信息还是网络建模的重要依据p 刁j 。一个好的模型能够模拟 出更多真实对象的行为特征，对该对象的研究有着重要的作用。而一个好的计算 机网络模型则需要尽量准确完整的拓扑信息的支持。 ( 4 ) 计算机网络拓扑信息还可以影响网络协议的设计f 8 - l o 】。 ( 5 ) 计算机网络拓扑信息是研究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 拓扑信息的不断获取。 以上内容说明了拓扑发现在网络研究中的基础地位，而非授权目标网络拓扑 发现是指在不具有管理权限的情况下针对计算机网络中一个子集的拓扑发现。因 此，非授权目标网络拓扑发现除了具有网络拓扑发现的一般意义外，还有如下的 特殊性。 ( 1 ) 对目标网络的拓扑发现其实就是对i n t e m e t 一个子集的拓扑发现。这是发 现整个网络拓扑的基础，同时也是研究整个网络的起点。 ( 2 ) “非授权”这个特性是指研究者不必要具有网络管理员权限就可以对网络进 行发现和研究。使得更多的研究者能够以丰富的拓扑数据为基础对网络拓扑进行 研究，在很大程度上推进了网络研究工作的发展。 总的说来，在网络安全形势不断升级的背景下，拓扑发现、尤其是非授权目 标网络拓扑发现在计算机网络相关研究中起着重要的基础作用，是研究者们必须 关注的问题。 1 4 课题任务及研究目标 拓扑发现是发现目标网络中结点和边的信息。在实际应用中拓扑发现并不要 求得到与实际网络拓扑完全相同、没有任何错误和遗漏的拓扑图，这是没有必要 也是不可能的。拓扑发现的目的是获取目标网络中骨干部分、稳定部分的拓扑， 这部分拓扑最能体现目标网络特性。尤其在目标网络的局域网中，设备开关频繁 使得网络拓扑不断变化，作为网络拓扑研究者根本没有必要去了解这些细节。同 时拓扑发现的时间耗费较大，由于网络结构变化可能产生前后不一致的探测数据。 所以提取目标网络中关键、稳定部分才是拓扑发现的主要目的，拓扑发现的目标 应该是实际拓扑的一个尽量准确和完整的子集。 针对非授权目标网络拓扑发现的特点，课题完成的主要任务为： ( 1 ) 完成对非授权目标网络中a s i p 表( a s 与i p 地址的映射关系表) 等基本 第4 页 国防科学技术大学研究生院硕上学位论文 信息的采集和构建； ( 2 ) 完成对非授权目标网络中a s 级拓扑信息的探测； ( 3 ) 完成对非授权目标网络中路由器级拓扑信息探测： ( 4 ) 统计和评估拓扑发现数据及结果，并比较各种发现技术； ( 5 ) 图形化展示拓扑探测结果。 拓扑发现技术的优劣主要由两个方面决定，一个方面是在拓扑发现过程中的 探测性能，如探测时间消耗、设备使用量等；另一个方面是通过该拓扑发现技术 获得的拓扑信息与实际拓扑信息相比的完整性和准确性。对于非授权目标网络探 测，评价拓扑发现技术优劣还必须加上另一个方面，即在发现过程中对目标网络 造成的影响和是否可能被目标网络的管理员感知。这对非授权目标网络拓扑发现 提出了更高的研究目标，具体描述如下： ( 1 ) 获得尽量完整、准确的非授权目标网络基本探测信息； ( 2 ) 探测得到的a s 级拓扑不仅包括各个a s 之间的准确的互连关系，还应该 包括这些a s 的基本信息； ( 3 ) 探测得到的路由器级拓扑要经过匿名路由器处理和路由器多址综合，最终 的路由器拓扑要与实际网络中路由器级拓扑基本一致； ( 4 ) 整个探测过程尽量减少时间消耗，保证较快的探测速度； ( 5 ) 在探测过程中不被目标网络管理员感知，因此应尽量减少因拓扑探测带来 的对目标网络的影响； ( 6 ) 在分析拓扑发现结果时能够得到目标网络特性； ( 7 ) 能够在图形化展示中体现目标网络特性。 课题的总体目标就是能够得到一个对非授权目标网络进行拓扑发现的工具 _ t o p d i s c 。t o p d i s c 应能够对非授权目标网络中各级拓扑进行自动探测、记录 探测结果、分析拓扑并以图形化的方式展示给用户。 1 5 论文组织 本文是对硕士期间研究工作的总结和升华，包括八个部分。 第一部分，绪论。介绍了非授权目标网络拓扑发现的基本概念与意义，该领 域国内外研究现状，以及课题研究背景、任务和研究目标等。 第二部分，目标网络拓扑发现。介绍了目标网路拓扑发现的现状，典型的a s 级和路由器级拓扑发现方法。 第三部分，给出了非授权目标网络中a s 级拓扑发现方法。针对非授权目标网 络的特点，提出了基于b g p 路由表的a s 级拓扑信息获取方法，并综合了其它各 种典型方法。 第5 页 i 习i 坊科学技术大学研究午院硕i ：学位论文 第四部分，提出了非授权目标网络路由器级拓扑发现方法。针对非授权目标 网络的特点和路由器级拓扑探测过程，给出了t r a c e r o u t e 优化方法，现有路由器多 址综合和匿名路由器处理技术，并提出了解决这两个问题的新方法。 第五部分，对现有的基于弹簧磁力模型的拓扑图绘制技术进行改进，使其更 加适合绘制计算机网络拓扑图： 第六部分，给出了一个非授权目标网络拓扑发现系统t o p d i s c 的整体结构， 以及其各个子系统的详细描述。 第七部分，托普发现效果分析和结果对比。对t o p d i s e 的拓扑发现效果和结 果从不同的角度进行了分析，并与已有技术和方法进行了比较。 第八部分，结论。对课题工作和文章内容作了简单总结，并提出下一步工作 目标。 第6 页 国防科学技术人学研究生院硕士学位论文 第二章目标网络拓扑发现 这一章主要从总体上介绍并区分了网络拓扑发现和目标网络拓扑发现，并给 出了现有目标网络拓扑发现中a s 级拓扑发现和路由器级拓扑发现的技术及其不 足。 2 2 1 网络拓扑发现 2 1 目标网络拓扑发现概述 计算机网络中的结点主要指主机、路由器交换机、自治系统、服务提供商等 网络实体i l l 1 4 ，1 5 j 。结点属性主要指这些网络实体所固有的属性，例如i p 地址、主 机名、主机所属网段、路由器名、路由器接口地址、路由器配置信息、路由表、 自治系统号、自治系统所属服务商、自治系统包含的地址段、自治系统所属地域、 自治系统包含的活动主机数、服务提供商名、服务提供商拥有的地址段、服务提 供商拥有的域名、服务提供商所能提供的服务等。 计算机网络中的边信息主要指计算机网络中结点之间的连接关烈1 1 ，1 4 ，1 5 】，包 括邻居关系、从属关系、同辈关系等。边属性主要包括主机或路由器之间数据传 输链路、数据传输的方向、数据传输性能、自治系统间的配置关系、服务提供商 之间服务关系等。 网络拓扑发现具有非常重要的意义，在计算机网络构建、网络安全、网络特 性研究、网络进化研究等领域起着至关重要的作用。没有对网络拓扑的发现和研 究就不可能从宏观上对网络进行研究。 网络拓扑发现可以是对整个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 进行拓扑发现非常困难。而且作为一般的研究者也没有必 要知道整个网络的拓扑状况，而只要关注某个区域的网络即目标网络的拓扑即可。 2 2 2 目标网络拓扑发现 目标网络拓扑发现是对目标地理区域或逻辑区域中计算机网络拓扑的发现。 与网络拓扑发现相同，包含了对目标网络中结点和边以及它们属性的探测、分析 和展示【l l ，1 4 , 15 1 。 由于特定区域的计算机网络在一定的时间内比较稳定，所以研究者可以探测 到在很大程度上与目标网络实际拓扑相同的拓扑结构。而且由于其区域性，目标 第7 页 国防科学技术大学研究生院硕- l ：学位论文 网络的结构、设备、协议、配置信息等基本由某个服务提供商，甚至有u j 能由同 一个网络管理员规划、实现和配置的。只要有针对性地使用各种网络拓扑方法就 可以得到目标网络较完整、准确的拓扑图。 因此目标网络的拓扑发现比对整个i n t e r a c t 的拓扑发现来说更加容易实现，而 且得到的拓扑更加完全和准确。而且目标网络作为i n t e m e t 的子集，也是对整个网 络进行发现的基础。 2 2 3 目标网络拓扑发现分级 目标网络拓扑发现可以分为三个层次：自治系统级、路由器级和局域网级【i 4 。 目标网络可能拥有若干个自治系统，对这些自治系统之间的连接关系和自治 系统本身信息的发现有助于研究者从整体上把握目标网络的特性【l 玉1 4 3 4 。 路由器级网络拓扑发现是最重要的一个方面，因为路由器在目标网络中起着 中转数据、连接网路的重要作用。得知路由器网络的拓扑是研究目标网络中的数 据流动特性、网络性能瓶颈、关键路由器部署等网络特性的基础【1 4 ，1 5 ，1 8 ，2 7 ，2 8 ，3 1 ，3 6 1 。 局域网级网络拓扑发现主要指对连接在同一个或几个处于同一区域并相互连 接的路由器上的设备的属性及它们之间连接关系的发现【1 1 1 4 ，1 5 】。这是目标网络拓 扑发现中最深入、最细节的一层，主要通过一些基本探测协议来完成发现。由于 局域网级拓扑非常不稳定，而且一般研究者也没有必要了解如此细节的拓扑变化。 所以本文中对局域网级拓扑发现不作深入探讨。 2 2 现有目标网络a s 级拓扑发现技术 自治系统和域( d o m a i n ) 的概念可以替换使用。其基本定义是：在统一技术 管理下的一组路由器，在内部使用一种域内网关协议( i n t e r i o rg a t e w a yp r o t o c o l ， 简称i g p ) 和共同的距离度量，转发数据包，在域间使用外部网关协议( e x t e r i o r g a t e w a yp r o t o c o l ，简称e g p ) 。随着技术发展，一个a s 内可以使用多种i g p ，多 种距离度量，但是不同的a s 之间仍表现为单一、一致的内部路由规划和通过该 a s 可达网络的一致映象。自治系统是由一个i s p ( i n t e r a c ts e r v i c ep r o v i d e r ，因特 网服务提供商) 运营的网络，可以独立的设置本地网关结构，但通常的情况是一 组网络作为一个完整的系统进行管理【1 2 。1 4 3 引。 每个自治系统都有一个唯一的自治系统编号，这个编号是由i n t e r a c t 授权的管 理机构分配的。它的基本思想就是希望通过不同的编号来区分不同的自治系统。 这样，当网络管理员不期望自己的通信数据通过某个自治系统时，这种编号方式 就十分有用了。或许，该网络管理员的网络完全可以访问这个自治系统，但由于 它可能是由竞争对手在管理，或是缺乏足够的安全机制，因此，可能要回避它。 第8 页 国防科学技术大学研究生院硕上学位论文 通过采用路由协议和自治系统编号，路由器就可以确定彼此间的路径和路由信息 的交换方法。自治系统的编号范围是1 到6 5 5 3 5 ，其中1 到6 5 4 1l 是注册的i n t e m e t 编号，6 5 4 1 2 到6 5 5 3 5 是专用网络编号。 a s 拓扑发现主要有两种方法，一个是通过查询i r r 数据库获取a s 配置信息 来得到a s 的邻居关系。另一个方法是通过t r a c e r o u t e 工具和a s 包含地址段信息 来确定a s 间连接关系【1 2 - 1 4 , 3 4 。 2 2 1i i 冰数据库查询 因特网是由大大小小的i s p ( i n t e m e ts e r v i c ep r o v i d e r ，i n t e m e t 服务提供商) 网络构成，可以看成是一个网络的互联结构，其中很多网络单独构成一个自治系 统，所谓自治系统是由一个网络管理者按照统一的网络管理策略管理的一组互联 网络。不同自治系统间需要交换它们的路由信息，通常不同自治系统的路由管理 和交换是采用边乔网关协议第4 版( b g p 4 ) t ”训】实现的，这是一个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 ，i n t e r n e t 工程任务组) 的标准网问路由交换协议。 但是由于所有的路由控制均是一个a s 独立制定的，其他自治域的管理者不知 道其路由策略是如何实现。由于网络管理者的水平或使用的设备问题，错误的路 由配置会给邻接自治系统带来路由震荡、路由黑洞等问题，同时邻接自治域无法 知道其策略配置是否符合双方的互联协议，互联网本身就是所有网络的连接，需 要建立一套透明和互信系统解决这一问题，i e t f 组成了一个工作组，定义描述路 由策略的语言规范。在1 9 9 5 年开始建立因特网路由注册服务，目前已经有很多国 际大型网络运行商开始使用i r r ( i n t e m e tr o u t i n gr e g i s t r y ，i n t e m e t 路由注册) 技 术。其中比较著名的i r r 服务有亚洲的a p n i c 、美国的r a d b 和欧洲的r i p e ， 它们为需要注册的网络提供公共服务，所有i s p 均可向其中的任何一个i r r 服务 提供者提出注册申请。另外一些大型的网络运营商也相继建立自己的i r r 服务， 包括美国u u n e t 、c a b l e & w i r e l e s s 和加拿大贝尔，这些i r r 服务主要是运营商向其 用户网络提供路由注册服务1 3 。 某i r r 数据库中一个a s 的配置信息如图2 1 所示。其中a u t - n u m 是指该a s 的自治系统号，a s n a m e 指这个a s 的名字，d e s c r 是对这个a s 的一些描述信息， c o u n t r y 是指出其拥有国家，i m p o r t 和e x p o r t 属性指与它相连的a s 号及其配置信 息，其它剩余信息主要是该a s 管理机构及管理员信息。从图2 1 中可以得到很多 关于a s 的信息。研究者可以通过对每个目标网络中a s 的i m p o r t 和e x p o r t 属性查 询就可以得知所有a s 与其它a s 之间的有向连接关系，进而获取a s 拓扑【l 4 。 但是由于i r r 数据库中的信息是由网络管理员提交，其中可能有一些错误信 息，且i r r 数据库中提供信息并不完全。最致命的缺点是i r r 数据库中的数据一 第9 页 国防科学技术大学研究生院硕士学位论文 旦被提交就很少被修改，而整个网络是不稳定的，那么就会包含很多过时信息。 同时，多个i r r 数据库中对同一个a s 的描述可能不一致。这些都严重影响了a s 拓扑的准确性和完全性。 a u t - n u m ： a s - n a m e ： d e s c r ： d e s c r ： d e s c r ： d e s c r ： c o u n t r y ： i m p o r t ： i m p o r t ： i m p o r t ： a s 9 4 3 l a k u n i n z t h eu n i v e r s i t yo fa u c k l a n d i t s sc e n t r e p r i v a t eb a g9 2 0 1 9 2 4s y m o n