（计算机应用技术专业论文）因特网ip接口级拓扑测量方法研究.pdf

中文摘要 中文摘要 因特网显著改变了人们的工作和生活方式，因此人们对因特网的研究和应用 投入了很大的热情。为了解因特网的现状并预测它的发展趋势，研究人员越来越 重视对因特网的拓扑结构和拓扑性质的分析和研究。 本文侧重对因特网p 接口级拓扑测量的相关方法和评价指标的研究。首先对 国内外相关研究现状进行了综述，接着介绍了网络拓扑测量的基本机制和方法， 然后在分析已有的拓扑测量方法评价指标的基础上，提出了最远跳数、中间跳响 应率、相同i p 路径数量等3 个新的、用于比较分析测量效果的拓扑测量方法评价 指标。 本文进一步提出了基于混合t c p 报文和o s p f 路由协议报文的新拓扑测量方 法，并且通过大规模网络测量实验，采用相应的评价指标，对所提出的测量方法 进行了验证和分析，证明了新方法的可行性和有效性。 关键词：拓扑测量；因特网拓扑；i p 接口；传输控制协议；开放最短路径优先 黑龙江大学硕十学何论文 a b s t r a c t i n t e m e th a sc h a n g e dt h ew a y so fo u rw o r ka n dl i f er e m a r k a b l y p e o p l eh a v eb e e n i ne n t h u s i a s mo fs t u d y i n gi tf o rt h i sr e a s o n i no r d e rt o b e t t e ru n d e r s t a n dt h e d e v e l o p m e n to fi n t e r a c t ，r e s e a r c h e r sa r ep a y i n gm o r ea n dm o r ea t t e n t i o nt os t u d ya n d a n a l y z ei n t e r a c t st o p o l o g i e sa n da t t r i b u t e s t h i st h e s i ss p e c i a l i z e sp a r t i c u l a r l yi nm e t h o d sa n de v a l u a t i o nm e t r i c so fi n t e r n e ti p l e v e lt o p o l o g ym e a s u r e m e n t f i r s to f a l lt h e s t a t e o f - a r to ft h er e l e v a n tr e s e a r c h e sf r o m b o t hh o m e a n df o r e i g n - - l a n dw e r er e v i e w e d ；a f t e rt h a tw ei n t r o d u c et h et h e o r ya n d m e t h o d sa b o u tt h en e t w o r kt o p o l o g ym e a s u r e m e n t ；a n dt h e nw ep r e s e n t e do u rt h r e e n e we v a l u a t i o nm e t r i c s ，i n c l u d i n gf u r t h e s th o p ，r e s p o n s er a t eo fi n t e r m e d i a t eh o p sa n d i d e n t i c a li pp a t e f u r t h e r m o r e ，t h i st h e s i sp r o v i d e st w on e wp r o b em e t h o d sb a s e do nm i x e da n d h y b r i dt c pp a c k e t sa n do s p fr o u t i n gp r o t o c o lp a c k e t s w i t hl a r g e s c a l en e t w o r k t o p o l o g ym e a s u r e m e n te x p e r i m e n t s ，w ea n a l y z ea n dv a l i d a t et h et w ok i n d so fm e t h o d s b yav a r i e t yo fm e t r i c s f i n a l l y , o u re x p e r i m e n tr e s u l t sd e m o n s t r a t et h e i rf e a s i b i l i t ya n d e f f e c t i v e n e s so ft h e s en e wm e t h o d s k e y w o r d s ：t o p o l o g ym e a s u r e m e n t ，i n t e r a c tt o p o l o g y , i pi n t e r f a c e ，t c p , o s p f 独创性声明 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研 究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得墨蕉堑盔堂或其他教育机构的 学位或证书而使用过的材料。 学位论文作者签名：丧乙函虹 签字日期：厶f o 年月了日 学位论文版权使用授权书 本人完全了解墨蕉辽太堂有关保留、使用学位论文的规定，同意学校保留并 向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本 人授权墨垄堑太堂可以将学位论文的全部或部分内容编入有关数据库进行检索， 可以采用影印、缩印或其他复制手段保存、汇编本学位论文。 学位论文作者签名：起函虹 导师签名 签字日期：工吖驴年月je t 签字日期：彻汐年月多日 学位论文作者毕业后去向： 工作单位：华中科技大学攻读博士学位电话： 通讯地址：华中科技大学计算机学院 邮编： 第1 章绪论 第1 章绪论 因特网作为一种广泛分布的信息基础设施，是人与人、计算机与计算机之问 协作交互的一种媒介【l 】，像电视、报纸一样已经成为人们获取信息的重要渠道之一。 随着因特网的不断发展，因特网拓扑测量技术应运而生。本章首先介绍论文研究 的目的和意义，然后对因特网拓扑测量领域的研究现状进行综述，最后介绍本文 的主要研究内容和结构安排。 1 1 本文研究的目的和意义 自2 0 世纪6 0 年代开始，计算机网络从无到有，从小到大，经历了飞速的发 展，并为社会进步做出了巨大贡献。随着因特网的不断壮大，越来越有必要对网 络的整体结构和网络行为进行深入的了解和分析，这有助于发现网络瓶颈，优化 网络配置，并进一步提高网络的可靠性。其中，因特网拓扑测量技术是研究网络 结构和网络行为的重要手段之一，它能够帮助人们深入了解因特网的增长过程和 拓扑结构；并为网络模拟2 。5 1 和网络拓扑建模6 9 1 提供了有力的数据支持。因此，网 络拓扑测量这一领域逐渐引起研究人员的关注u o - t 2 】。 近年来，越来越多的科研组织【1 3 - 17 】加入到了i p 路径探测和网络拓扑测量的相 关研究中，c a i d a 的s k i t t e r 15 1 、a r c h i p e l a g o ( a r k ) t 1 8 1 和d i m e s 1 9 3 都是典型的大规 模多源点测量设施。目前，随着研究的深入，人们对网络拓扑测量的各个方面进 行了改进，以期达到更好的测量效果。针对探测报文的改进是其中的一个重要方 面。改进后的探测报文探测能力大大增强，用它们推断出的i p 路径也更为接近实 际网络状况。例如：已经被广泛使用的t c p t r a c e r o u t e t 2 0 1 报文拥有良好的目的主机可 达性，而使用p a r i s t r a c e r o u t e 2 1 1 报文推断出的i p 路径则更加准确可靠，因此研究 与改造探测报文具有重要意义。 如今，因特网拓扑测量技术已经在许多领域中得到应用，人们可以从以下几 黑龙汀大学硕十学付论文 个方面窥其一斑： ( 1 ) 因特网拓扑测量为宏观网络管理和网络布局提供参考材料，例如帮助指导 网络扩容、新增路由器选址 2 2 之3 1 、路由策略配置 2 4 - 2 6 1 等； ( 2 ) 因特网拓扑测量可以辅助网络环境模拟【2 2 1 、协议设计与评价等其他网络研 究课题 2 7 - 2 8 】； ( 3 ) 因特网拓扑测量为研究路由的收敛性质 2 9 - 3 1 】、改进与拓扑结构相关的协议 和算法吲提供依据； ( 4 ) n - j 络拓扑信息可以辅助多镜像服务器的选址；帮助i s p 确定与哪个a s 相连 能够具有更好的i n t e m e t 连通性 2 8 , 3 3 - 3 4 】等； ( 5 ) 因特网拓扑测量技术可用来观察灾难发牛前后网络联通性的变化情况【3 5 】， 例如，c h e s w i c k 等人 3 6 】所进行的i n t e r n e tm a p p i n g 项目采用单点非协作式测量，成 功描述了科索沃战争期问由于网络设施或电力供应设施被破坏而造成有关地区网 络拓扑结构发生显著变化的情况。这从另一个侧面反映了战争对基础设施的破坏 结果，也是网络拓扑测量在军事领域中应用的典范。 1 2 国内外相关研究现状 目前，针对网络拓扑测量技术的研究主要包括三个方面：( 1 ) 钡l j 量因特网拓扑 结构的技术；( 2 ) 分析拓扑图的拓扑性质和网络的标度行为；( 3 ) 分析给定范围内的 选路路径的变化特点等。本文主要针对测量因特网拓扑结构的技术展开研究。 测量因特网拓扑结构时可以按测量层次分类，也可以按测量源点数量分类。 ( 1 ) 按测量层次分类。由于因特网庞大的规模，为了提高路由协议的工作效率， 现在的因特网采用分层次的路由结构，整个因特网被划分成许多较小的自治系统 ( a s ，a u t o n o m o u ss y s t e m ) 。一个自治系内部包含几十至数百台路由器不等。每 台路由器拥有若干个网络接口，每个网络接口一般拥有一个( 也可以是多个) i p 地址。 因此，对于这种层次结构来说，因特网拓扑结构从低到高分为三级结构，各 第1 章绪论 层次关系如图1 一l 所示，分别为：i p 接口级、路由器级和自治系统级。根据对应 的层次，因特网拓扑测量则可以分为i p 接口级拓扑测量、路由器级拓扑测量和自 治系统级拓扑测量 3 7 - 3 羽。其中，i p 接口级( 简称i p 级) 拓扑测量是其它层次拓扑 测量的基础，它的主要任务包括：探测路由器的i p 接口，并推断、分析这些接口 间的联系。通过对i p 接口级拓扑图进行别名解析【】【3 9 1 ，就可以获得路由器级拓扑 图；另外，在路由器级( 或i p 接口级) 网络拓扑图的基础上，把结点按一定的地 理范围进行聚合，即可绘制成另一种被称之为p o p ( p o i n t so f p r e s e n c e ) 级拓扑的 网络拓扑图。 ； 秘维系绒 图1 1 冈特网层次结构示意图 f i g u r e1 - 1d i a g r a mo f i n t e r a c th i e r a r c h i c a ls 仃u c t i l r e 本文针对因特网i p 接口级( 简称i p 级) 拓扑测量的相关方法展开研究。 ( 2 ) 按测量源点数量分类。根据测量源点数量的多少，拓扑测量又可分为单点 测量和多点测量。与单点测量相比，多源点测量绘制的拓扑图更完全，但同时也 增加了网络负载和测量系统的复杂性。本文中的实验目的是证实、刻画某种测量 方法( 报文) 的特性，而非绘制一张准确、全面的拓扑图。所以，文中实验均采 用单点测量模式。 在拓扑测量方法研究方面，v j a c o b s o n 4 0 1 设计了第一版t r a c e r o u t e 程序，该程 序默认使用u d p 高端口报文进行网络探测，同时也允许改用i c m p 回显请求( e c h o 黑龙汀大学硕十学何论文 r e q u e s t ) 报文( 简称为i c m pe - r e q ) 。在i e t f 协议规范 4 1 】中规定的有效i c m p 查 询报文有三种：回显请求、时问戳请求和地址掩码请求。但出于安全角度的考虑， 目前包括i c m p 回显请求在内的i c m p 查询报文容易受到边界路由器或防火墙等安 全设施的过滤。此外，u d p 高端口报文也经常被过滤。在这种情况下传统的 t r a c e r o u t e 程序的探测效果受到严重影响。出于以上原因，m c t o r e n 于2 0 0 1 年发 布了采用t c ps y n 报文的t c p t r a c e r o u t e l 0 ，并于2 0 0 5 年发布改进版 t c p t r a c e r o u t e l 5 b e a t 6 。t c p t r a c e r o u t e 展示了t c ps y n 报文的网络测量能力【4 2 1 。这种 方法发出的t c p 报文一般把目的端口设置为熟知端口8 0 。 由于负载均衡机制给网络拓扑测量带来的不利影响，b a u g u s t i n 等人设计了 p a r i st r a c e r o u t e 【2 ，对上述三类报文( u d p 高端口、i c m p 回显请求、t c ps y n ) 的构造方式做了进一步的改进，改进后的报文能够成功避免因流级负载平衡而造 成的探测异常【4 3 1 ，因此该程序发布之后就受到网络测量人员的广泛重视。 随着探测报文种类的日益增多，m l u c k i e 等人】尝试对这些报文的测量能力 给出分析总结，提出了4 种探测报文的评价指标，同时也提出使用带标准d n s 负 载的u d p p a r i s 报文进行网络测量，这种报文在u d p p a r i s 的基础上，将报文的源 端口设定为5 3 ，并且增加了1 3 0 个字节的标准d n s 响应数据报负载。构造这种报 文的目的就是为了提高探测报文穿透防火墙的能力，因为猜测防火墙可能更高概 率的允许某些协议( 如d n s ) 的报文被转发。他们在研究中还发现，基于i c m p 报文的测量方法到达测量目标地址的路径较多；基于u d p 报文的测量方法到达测 量目标地址的路径最少，但得到的i p 连接数量最多，更适合于测量域内拓扑。 综上所述，目前因特网拓扑测量中各种拓扑测量方法所采用的探测报文分别 是i c m p 回响请求报文、u d p 高端口报文和t c ps y n 报文，它们各有适用的场合。 然而这些方法测量时一方面不同程度地受到过滤机制的影响，从而使测量的拓扑 不完全；另一方面，会受到路由器报文级负载均衡机制的影响，从而使测量的拓 扑部分区域不准确。因此，需要研究新的有效方法。 第1 辛绪论 1 3 本文的主要研究内容 本文的研究工作得到黑龙江省自然科学基金项目( 项目批准号f 2 0 0 8 2 3 ) 资助。 如前所述，本文主要针对因特网i p 接口级拓扑测量的相关方法展开研究。通 过一些实验和分析工作，本文一方面对有效评价拓扑测量方法的评价指标进行研 究，另一方面对新的测量方法进行研究，以期得出一些有价值的结论和创新，包 括采用新的探测报文( 混合t c p 报文、o s p fh e l l o 报文) 进行网络拓扑测量， 并讨论它们的可行性和测量能力。本文希望这些结论有助于进一步改善因特网拓 扑测量的测量效果，使其日臻完善。 尽管日前已经存在一些评价指标用于刻画探测方法的效果，但是这些指标仍 然不够全面也不够准确，为此本文提出了最远跳数、中问跳响应率、相同i p 路径 数量这三种新的评价指标。在本文的相关实验中，将使用这些评价指标对不同的 测量方法进行比较分析。 随着t c ps y n 洪泛攻击的泛滥 4 5 - 4 8 】，各种网络安全设备开始有针对性的过滤 t c ps y n 报文m 9 5 1 】，这无疑将大大削弱t c p t r a c e r o u t e 的测量效果，因此本文考虑 使用设置了其它控制比特( 或比特组合) 的t c p 报文来替代t c ps y n 报文，并用 实验来说明这种方法的可行性和有效性。 从本文1 2 节的介绍中可以看到，现存的各种测量方法都是基于i c m p 、u d p 或t c p 报文进行拓扑测量的。在分析了相关协议的工作机制后，本文提出了一种 新的基于o s p f 路由协议报文的测量方法，并称之为o s p f t r a c e r o u t e ；本文以o s p f h e l l o 报文为代表进行了大量实验，验证了新方法的可行性和有效性。 1 4 本文的结构安排 本文结构安排如下： 第一章丰要介绍本文研究的目的和意义、国内外有关的研究现状，以及本文 的主要研究内容和结构安排。 第二章介绍网络拓扑测量的基本机制和方法，包括：t r a c e r o u t e 原理、探测报 黑龙江大学硕十学何论文 文的构造方法和负载均衡机制等内容。 第三章首先介绍了已有的几种测量方法评价指标，在此基础上，提出3 种新 的评价指标。 第四章提出了采用非t c ps y n 控制比特及其组合报文作为探测报文的测量方 法，并通过实验验证该方法的可行性和有效性。 第五章提出了采用o s p fh e l l o 路由协议报文作为探测报文的测量方法，并通 过实验验证该测量方法的可行性和有效性。 最后是本文的结论，这一部分对当前所做的工作进行总结，并提出进一一步研 究的思路和建议。 第2 幸基本测每机制和方法 第2 章基本测量机制和方法 本章主要介绍因特网拓扑测量的基本测量机制和方法，包括：t r a c e r o u t e 机制、 探测报文的构造方法以及负载均衡机制和p a r i st r a c e r o u t e 原理。 2 1t 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 路径汇集起来，然后分析这些路径间的关系， 最终绘制出各个级别的网络拓扑图。 下面对t r a c e r o u t e 机制进行简要介绍。 众所周知，当某个路由器收到t t l ( t i m e t o l i v e ) 值小于等于1 的i p 报文时， 会丢弃此报文，并向源主机发送一个i c m p 超时报文，通知报文被丢弃的原因； 否则，路由器在转发报文的同时，把该报文的i p 首部的t t l 值减1 。t r a c e r o u t e 程 序正是利用了上述原理，让源和目的主机问的路由器按顺序返回i c m p 超时报文， 并从这些反馈报文中提取相关的拓扑信息。 图2 1 说明了t r a c e r o u t e 的工作过程。s o u r c e 是发起t r a c e r o u t e 的源主机， d e s t i n a t i o n 是要探测的一个目的地址，探测报文途经的路由器依次记为r 1 至r 4 。 首先，s o u r c e 向d e s t i n a t i o n 发送一个t t l 值为1 的u d p 高端口报文( 图2 1 中用蓝色箭头描述) ，路由器r l 收到这个报文后，发现其t t l 值为1 ，于是丢弃 这个报文，并向s o u r c e 发送i c m p 超时报文( 图2 1 中用红色箭头描述) ；通过观 察此i c m p 超时报文，s o u r c e 获知以下两点：( 1 ) 路由器r 1 的一个接口的i p 地 址，( 2 ) s o u r c e 与r 1 之间存在一条链路；于是s o u r c e 记录相关信息，并发送一 个t t l 值为2 的u d p 高端口报文。路由器r 1 转发该报文时，将其t t l 值减1 ， 黑龙江大学硕十学位论文 并转发至路由器r 2 ，r 2 王弃该报文( 因为它的t t l 值已经被减为1 ) 并向s o u r c e 发送i c m p 超时报文；s o u r c e 收到r 2 反馈的报文后，记录相关信息，并继续发送 其它t t l 值更大的探测报文。最终，一个t t l 值足够大的报文到达目的主机 d e s t i n a t i o n ，因为通常情况下探测报文坐发往的目的高端口j 牛= 日的卞机中是被关闭 的，所以d e s t i n a t i o n 会向s o u r c e 回廊i c m p 端口不可达报文( 图2 - l 中用绿色箭 头描述) s o u r c e 由此知道已经探测到达目的主机，于是终止对d e s t i n a t i o n 探测。 这样就获得了一条完整的l p 路释：i p l 一口2 _ i p 3 _ i h d e s t i n a t i o n 。 | 嚣1 磊 图2 - lt t a c e r o u t e 测吊转发路径的机制。划 f i g u i i e2 - 11 h c e r o m e m e c h a n i s m o f m e a s u r i n ga f o r w a r d i n g p a t h 当然，埘l p 地址做探测的时候，人们并非能总是获得完糖的i p 路径，上面描 述的过程只是比较理想的情况。事实上，出现不完整的路径的概率更高”】。以下 是几种不完整路径的例子： ( 1 ) i p i i p 2 一i n i p 4 “+ 一+ ( 2 ) i p l i p 3 一i n 一4 一d e s t i n a t i o n ( 3 ) i p i l p 2 “l p 3 一d e s t i n a t i n n 在i p 接口级拓扑测量中，i p 路径中的路由器位置也被称为跳( h o p ) ，其中， 代表无反馈的跳。当连续出现的无反馈跳的数日超过阈值( 在本文的实验中该值 为3 ) 时，t r a c e r o u t e 程序将终止此次探测，即会产牛如上面例子( 1 ) 中的i p 路径。 第2 辛基本测帚机制和方法 2 2 探测报文的构造方法 由上一节的介绍可以看出，在t r a c e r o u t e 机制中，无论发送什么类型的t t l 渐 增报文，除了探测到达目的主机时收到的响应报文可能有所区别外，中问路由器 的反馈报文都是i c m p 超时报文。基于这一点，研究人员开始改用其它种类的报 文进行网络探测，如t c p t r a c e r o u t e 2 0 1 程序中使用的t c ps y n 报文，w i n d o w s 系统 中t r a c e r t 程序和c a i d a 的a r k t l 8 l 使用的i c m p 回显请求报文( 简称为i c m pe r e q ) ， 这些程序的实现原理与t r a c e r o u t e 相同，只是所用的探测报文有所差异。包括上一 小节介绍的u d p 高端口报文，这三种报文( u d p 高端口报文、t c ps y n 报文、i c m p 回显请求报文) 是目前网络拓扑测量中最广泛使用的报文类型。表2 1 对这三种报 文的实现细节做了概括性的介绍。 表2 1 主要的探测报文构造方法 t a b l e2 1m a i nm e t h o d so fc o n t i g u r i n gp r o b ep a c k e t s 在探测过程中，反馈报文的匹配问题，是拓扑测量实现者所应该考虑的基本 问题。如果报文的匹配环节出现混乱，将导致测量数据不可用或拓扑测量错误的 后果。 一般来说，报文匹配工作分两个方面：( 1 ) 反馈报文与探测进程的匹配；( 2 ) 反馈报文与探测报文的匹配。 为了提高探测效率，进行网络拓扑测量时一般同时肩动多个并发探测进程， 每个进程都能够收到所有发往本丰机的反馈报文，所以首先要解决如何使探测进 程能够准确识别属于自己的反馈报文的问题。对于这个问题，t r a c e r o u t e 的解决办 黑龙江大学砀! 十学何论文 法是在u d p 报文的源端口字段中记录进程的i d 号( 实际上对进程i d 号做了简单 的处理) ，该d 号被复制到i c m p 报文的差错负载中随反馈报文一同返回，进程 在接收反馈报文时，从差错负载中提取这个d 号并检查是否与自己的进程d 号 相同，如果相同则接收此反馈报文，否则不做接收处理。而在使用i c m p 回显请 求报文时，进程i d 号被记录在i c m p i d 字段中。 一个探测进程在同一时问段内会发送多个探测报文，由于网络延迟的不确定 性，进程有可能在较晚的时候才收到先被发送的报文的反馈，所以测量程序需要 对该探测报文和反馈报文进行匹配。t r a c e r o u t e 的解决办法是在u d p 报文的目的端 口字段中记录进程的数据包编号，该包编号被复制到i c m p 报文的差错负载中随 反馈报文一同返回，探测进程提取这个包号并因此知道该反馈属于哪个探测报文， 避免了的错误推测。使用i c m p 回显请求报文做探测报文时，包编号被记录在i c m p 的序列号字段中，而对于t c ps y n 报文包编号被记录在i p i d 字段中。 2 3 负载均衡机制和p a r i s t r a c e r o u t e 目前，许多网络管理员使用负载均衡机制来提高网络的可靠性和资源利用率， 该机制允许路由器在所有可用的链路上发送报文，使网络带宽的利用率得到提高。 但该机制对基于t r a c e r o u t e 机制的拓扑测量方法的测量效果可能产生影响。 2 3 1 负载均衡分类 负载均衡按链路代价分为等价负载均衡和非等价负绒均衡，代价( c o s t ) 在不同 的路由协议中有不同的计算方法和计量单位，在本文以后的叙述中，只把它看作 与路由相关的度量。等价负载平衡将流量均匀分布到多条代价相同的网络链 路上。非等价负载平衡将流量分布到多条代价不相同的网络链路上，各跳链 路上分布的流量大小与路由代价成反比，即代价越低的路径上分配的流量越大， 代价越发高的路径上分配的流量越少。 目前许多主流的动态路由协议都支持等价的负载均衡机制，如o s p f 5 4 1 、 i s i s e 5 5 】等。 第2 章基本测帚机制和方法 在等价负载均衡机制中，按照不同的负载粒度，负载均衡又分为： ( 1 ) 基于目的地址的负载均衡； ( 2 ) 基于流的负载均衡； ( 3 ) 基于数据包的负载均衡。 基于目的地址的负载均衡意味着所有去往指定目的i p 地址的数据包都从相同 的端口转发；根据路由原理，基于目的地址的负载均衡对目标i p 地址网络前缀不 同的数据包在不同的端口转发这些数据包。对目标i p 地址网络前缀相同的数据包 在同一端口转发。因此，这种机制对拓扑测量没有影响。 在基于流的负载均衡中，路由器按照报文首部中的信息，把各个数据包归到 不同的流中，并且在相同的端口转发属于同一个流的所有报文；如果存在到达相 同目标网络的不同端口，那么路由器将不同的流均匀分配到这些端口上进行转发。 通常来说，路由器将( 源地址，目的地址，协议，源端口，目的端口) 这个五元 组当作报文流的标识符，而有些路由器的负载均衡机制中也可能进一步考虑服务 类型( t o s ，t y p eo fs e r v i c e ) 、i c m p 代码以及i c m p 校验和字段。 相比之下，基于数据包的负载均衡机制，并不对额外的信息加以识别，它只 是简单的把去往相同目标网络的数据包均匀分配到不同的可选路径上。 2 3 2 负载均衡对网络拓扑测量的影响 负载均衡的出现意味着源和目的主机之问不再只有一条i p 路径，而可能具有 多条。这给网络拓扑测量技术带来了两个新的问题：( 1 ) 未能发现真正的结点和连 接，( 2 ) 报告错误的连接。下面举例说明这两类问题。 在图2 2 中，l 代表一个负载均衡器，位于一条i p 路径中的第6 跳，假设它 实施了基于数据包或基于流的负载均衡策略。在图的左侧，绘制的是真正的路由 器拓扑图，其中圆圈代表路由器，且人为给每一个路由器的接口分配一个编号。 黑色的小方块代表具有不同t t l 值( 范围6 9 ) 的探测报文，其中假设上面的两 个小方块所代表的探测报文将由路由器l 的接口l 转发，下面的两个小方块所代 黑龙江大学硕士学位论文 表的探测报文将由路由器l 的接口2 转发。在吲的右侧，绘制的是根据t r a c e r o u t e 程序推测出的拓扑斟。对比左右两张拓扑幽，可以发现阿种类型的推断错误： 错误类型( 1 ) 未能发现真正的结点和连接：因为路由器b 和c 没有反馈任何信 息，所以b o 和c 0 没有被发现，相应的( l 0 ，b 0 ) 、( b 0 d o ) 也没有被推测出来。 错误类型( 2 ) 报告错误的连接：在寿侧的实际拓扑图中，可以看到并不存在一 条连接路由器a 和d 的连接，但是在7 、8 两跳，因为探测包在两条不同的路径 中被转发，所以导致t r a c e r o u t e 错误的推断出路由嚣a 和路由器d 之间存在一条 连接( a 0 ，d o ) 。 si _ 。o 蝇j i 也 图2 - 2 带负载均衡机制的转发路径i f i g m _ e2 - 2 f o r w a r d p a t h s w i t h l o a db a l a n c i n g m e c h a n i s m 如上所述，可以看到基于数据包的或基于流的负载均衡策略降低了网络拓扑 测量的准确性；而在构造条i p 路径时，因为所有探测报文的日的地址是相同的， 并不会出现几个探测报文从相同路由器的不同接口被转发的现象，所以基于目的 地址的负找均衡策略对叫络拓扑测量的准确性不造成影响。 2 3 3p a r i st r a c e r o u t e 机制 由于基于流的负载均衡机制给网络拓扑测量的准确性带来的不利影响，b a u g u s t i n 等) k 1 2 1 在其程序p a r i s t r a c e r o u t c 中对原有的三种报文的构造打式做了改进 以避免探测异常。具体的报文构造方法如表2 2 所示。 【 萝m 第2 章基本测帚机制和方法 表2 - 2p a r i s 嗽o u t e 机制中的报文构造方法 t a b l e2 - 2m e t h o do f c o n f i g u r i n gp a c k e ti np a r i st r a c c r o u t e 在p a r i st r a c e r o u t e 机制中，最核心的思想就是保持发往同一个目的地址的所有 探测报文的流标识符不变，即保持五元组( 源地址，目的地址，协议，源端口， 目的端口) 以及t o s 、i c m p 代码字段、校验和字段中的值恒定，这样，使得网络 中实施了流级负载均衡策略的路由器认为这些探测报文属于同一个数据流，于是 路由器在相同的接口中转发报文，这样就避免了上面两种错误类型的出现。 2 4 本章小结 本章中首先介绍了t r a c e r o u t e 机制的基本原理，其次介绍了3 种原始的探测报 文的构造方法，然后说明了负载均衡策略及其对网络拓扑测量的准确性产生的影 响。当这种影响被人们熟知以后，研究人员进一步对原有的报文构造方法进行改 进，以适应这种网络环境的变化，其中b a u g u s t i n 等人设计的p a r i st r a c c r o u t e 程 序效果最为突出。在本文的实验中也将按照p a r i st r a c e r o u t e 的有关原理来构造探测 报文。 黑龙江大学硕+ 学何论文 第3 章测量方法评价指标 不同的拓扑测量方法各有其适用场合，需要对有关方法的测量效果、探测能 力等方面进行量化分析和比较，这就需要用到一些有关的评价指标。已有的评价 指标存在一些不足之处，本章首先介绍这些指标，然后提出新的评价指标。 3 1 已有的测量方法评价指标 2 0 0 8 年，m l u c m e 等人1 首次开展了对已有测量方法的测量效果进行评价比 较的研究工作，他们给出了如下4 种衡量指标：( 1 ) 到达目的地址的路径数量；( 2 ) 完整i p 路径数量；( 3 ) 惟一i p 连接数量；( 4 ) 惟一a s 连接数量。 由于把i p 地址映射到a s 编号这个过程非常容易出现误差【5 7 】，所以本文没有 采用这个指标。本文在分析数据的过程中有选择的使用了上述前3 种评价指标， 以描述探测方法的测量效果。下面将详细说明每一种指标的定义和用途。 3 1 1 到达目的地址数量 按照文献【4 4 的描述，如果出现下列情况之一，就认为到达了目的主机： ( 1 ) 对于基于u d p 或t c p 协议的探测方法，探测原点接收到了一个i c m p 端 口不可达报文； ( 2 ) 对于基于t c p 协议的探测方法，探测原点接收到的一个t c p 报文； ( 3 ) 当使用i c m p 回显请求报文进行网络探测时，探测源点接收到i c m p 回显 应答报文； ( 4 ) 探测源点收到其它i c m p 不可达报文，且这个报文的源地址和探测报文的 目的地址相同。 m l u c r e 等人认为，因探测到达目的主机而终止对一个i p 的探测会比因为连 续无反馈而终止探测获取更丰富的信息，例如：相比之下，可以进一步获得到达 目的主机的往返时延( r 1 广r ) 及到达目的主机的i p 路径长度；因此，在分析实验 第3 章测帚方法评价指标 结果时，m l u e k i e 等人用到达目的地址数量做“标尺”来比较某几种报文探测能 力的强弱对同一组i p 地址做探测的时候，某种报文探测到达目的地址数量越 多，则认为它的探测能力越强。 3 1 2 完整i p 路径数量 完整i p 路径的定义如下：探测到达目的地址，并且在i p 路径中各跳都有反馈， 则称这条i p 路径是完整的。在拓扑测量过程中，该指标的提出者希望更多的获得 完整路径，因为他们认为完整路径降低了拓扑分析中的不确定性：同时，获得一 条完整路径比获得同样长度的不完整路径用时更少。 3 1 3 惟一i p 连接数量 m l u e k i e 等人对i p 连接做了如下定义：在一条i p 路径中，相邻的两个i p 跳 组成一个i p 连接。但是他们没有考虑i p 路径中间存在无反馈跳的情形，例如在路 径i p l - i p 2 一i p 3 一事一i p 5 - - * d e s t i n a t i o n 中，i p 3 与i p s 不相邻。 如果不把类似于( i p 3 ，d 5 ) 这样的i p 连接看做一个i p 连接，则在绘制因特网拓 扑图时，有可能获得一张如文献 5 8 中所描述的非连通图。为了生成连通图，需要 使用文献 1 6 】中所提到的方法：i p 连接中的两个i p 地址均为全局i p 地址，把直接 相连的两个全局i p 记为边权为l 的i p 连接( 以下称为直连i p 连接) ，例如( i p l ，i p 2 ) ； 把中间出现无响应跳或私有i p 地址的两个全局i p 之间记为边权大于1 的i p 连接， 如连接( i p 3 ，i p 5 ) 的边权值为2 。本文把所有不同的i p 连接数目称作惟一i p 连接数。 在本文后面的实验数据分析中，将使用这种新定义的惟一i p 连接数。 在网络拓扑测量中，人们知道这样一个事实：假设在所有条件都相同的情况 下，方法a 探测到的i p 连接的集合为r a ，方法b 探测到的i p 连接的集合为r b ， 如果r a 中的元素个数即惟一i p 连接数量大于r b 中的元素个数，那么 一般认为方法a 所获得的网络拓扑信息更加全面，在此信息基础上绘制出来的路 由器级和a s 级拓扑图也将更加准确。 因此获得惟一i p 连接数量的多少，直接说明了某种方法测量效果的优劣，所 黑龙江大学硕十学位论文 以它被作为评价测量方法的重要量化指标。可以看出完整口路径数量和惟一i p 连 接数量是相互关联的两个指标，但是它们从不同的角度刻画测量效果。另外，完 整路径数量对于一些后续的分析来说并不是必要的。 3 2 新的评价指标 如本文3 1 节所述，为了评估不同测量方法的有效性，文献【4 4 】将完整i p 路径 定义为到达目标地址且所有经过的中间结点均有返回的路径，而惟一i p 连接则定 义为路径中一对相邻的两结点问的i p 连接。 但是，在各个级别( i p 级，路由级，p o p 级或a s 级) 的因特网拓扑图中， 目的丰机的i p 地址并不构成图中的结点；即使一台目的主机可达，它也不会被绘 制到拓扑图中。因此，在网络拓扑测量中，人们一般不需要关心目的主机的可达 性以及是否存在通向目的主机的连接；或者说，如果一条探测路径最后到达了目 的主机，但是中间结点都没有返回，那么这条路径对生成拓扑图也没有多少实际 意义。据此可以认为，把到达目标地址数量作为衡量探测方法的一项指标是不合 理的。所以，在本节，将另外提出3 种新的评价指标。 3 2 1 最远跳数 定义3 1 ( 最远跳) 最远跳是指在路径探测过程中有响应报文返回的最后一跳。 当日的主机有响应时，可以对包括还是不包括目的主机跳这两种情况加以区 别。如果包括目的主机跳，则最远跳就是目的丰机的所在跳；如果不包括目的丰 机跳，则最远跳是指距离目的主机最近的有响应的跳。本文中如无特别说明，在 计算最远跳时均不包括目的主机跳。特别地，如果目的主机无响应，则最远跳就 是有响应报文返回的最后一跳。 图3 1 给出了不包括目的主机跳时，几种情况下的最远跳示例。其中，h 1 - h 6 表示跳数，d 1 d 3 表示到达的目标地址，幸表示无响应跳，f h l f h 5 表示每条路径 中的最远跳。其他a 、b 表示中间有响应的跳。 第3 章测帚方法评价指标 l彳彳 h ： b8b h ；确 聿 f h h df h k dd 口 霉 f h 毫 曰 f h 掌 h“d 擎 髓办f ，p 图3 - 1 不包括目的主机跳时最远跳示例 f i g u r e3 - ie x a m p l e o ff u r t h e s th o pe x c l u d i n gd e s t i n a t i o nh o p s 这一指标意在描述某种方法探测到的路径的有效长度。很明显，当在其它条件 相同时，最远跳数大的测量方法，其测量效果更加优越( 尤其是在不包括目的主 机跳的情况下) 。需要注意的是，最远跳数有别于路径长度，路径长度是指从第一 跳到最后有响应跳问的所有跳数，通常包含目的地址到达的那一一跳和日的地址之 前没有响应的跳。如图3 一l 中( c ) 和( 印这两种情况，若以路径长度作为衡量标准则 会夸大拓扑测量中的有效路径长度。 3 2 2 中间跳响应率 定义3 2 ( 中间跳响应率) 设s u m i - i 表示某一种方法所探测到的全部有响应跳 数之和( 不包括目的地址跳) ；m a x f h i 表示用多种方法所对同一目的地址i p i 做 r t 。 探测所得到的路径f 的最远跳的最大值，则中间跳响应率为s u m h ( m a x f h i ) ， i = 1 卵为路径总数。 h la aaaaa彳a h ，bb b b 转 b 8 8 h ，c| i ，诲厂话sf h n 摩串 钰f h t 韶 f h 4 专稚 f h l l 是5d lf h ： 枣 奉dt 奉 书f ，8 办缸i 童 零 9 4 事 攀d 4 毒 l 融t 醚 冉 图3 - 2 中问跳响应率计算示例 f i g u r e3 - 2e x a m p l eo f c a l c u l a t i n gr e s p o m er a t e 黑龙汀大学硕十学何论文 示例如图3 2 所示，对4 个不同目的i p 地址，分别用m a 、m b 两种方法来探 测。m a 方法中有响应的跳数和s u m h a = 1 5 ( = 4 + 4 + 3 + 4 ) ，m b 方法中有响应的跳数 和s u m h b = 1 3 ( = 3 + 3 + 3 4 ) 。对m a 和m b 两种方法来说，每条路径的最远跳数的 4 最大值之和y m a x f h i = 1 8 ( = 4 + 5 + 4 + 5 ) ，因此m a 的中间跳响应率为8 3 3 百 ( 1 5 1 8 ) ，m b 的中问跳响率为7 2 2 ( = 1 3 1 8 ) 。 本文中将使用这项指标从宏观上描述中问路由器对某种报文的响应程度。当不 同探测方法的其他条件都相同时，中间跳响应率高的方法探测效果更好。需要说 明的是，最初的想法是分别计算每种方法的最远跳数之和，而不是取最远跳数的 最大值之和。但是如果按照这种早期的想法，m a 的最远跳数和为1 6 ( = 4 + 5 + 3 + 4 ) ， m b 最远跳数和为1 5 ( = 3 + 3 “+ 5 ) ，这样就夸大了相应的中间跳响应率，即m a 的 中问跳响应率为9 3 8 ( 1 5 1 6 ) ，m b 的为8 6 7 ( = 1 3 1 5 ) 。 3 2 3 相同i p 路径数量 定义3 3 ( 相同i p 路径) 不同方法在对同一目标地址做探测时，如果它们推