杨 慧 ， 李春林 ， 孙 治 ， 张志勇

（1.网络空间安全四川省重点实验室，四川 成都 610041；2.中国电科网络空间安全技术重点实验室，四川 成都 610041；3.中国电子科技网络信息安全有限公司，四川 成都 610041）

0 引 言

互联网由大约50 000个自治域系统（Autonomous Systems，AS）或网络组成，其中大多数网络都由不同的组织拥有和管理，涵盖不同的地理区域，用于不同的目的，并且由不同的物理基础设施构建而成。例如，这些自治系统网络可以是网络服务提供商、内容提供商、内容分发网络、教育网络等。这些构建方式和目的的多样性、大规模、分布式、异构性等特征，使得测量互联网的全球拓扑结构本质上是困难且极具挑战性的。目前没有任何实体或组织具有整个互联网或其单个组成或自治域的完整拓扑画像（即“基本事实”）。此外，不存在其唯一目的是发现网络拓扑的协议或服务[1-2]。两种最常用的拓扑发现技术，即traceroute和BGP（Border Gateway Protocol，边界网关协议），它们最初设计用于完全不同的目的：由V. Jacobson引入的traceroute是一个网络调试工具[3-4]；而BGP是当今全球互联网中事实上的标准域间路由协议[5]。尽管存在这些困难和挑战，但对互联网拓扑结构的研究在过去15至20年间一直吸引着网络和非网络研究人员。非网络研究人员将互联网或其拓扑结构视为复杂和大规模技术网络的主要案例，主要关注其结构特征的研究和预测其行为；网络研究社区的研究人员更加关注因特网的各种拓扑属性如何影响网络协议、网络应用和服务的性能。因此，更好地了解互联网拓扑及其主要特征将使网络研究人员能够设计出更好的网络协议或服务，并在更现实的条件下对其进行评估。此外，准确的互联网地图对于不断尝试改进或优化代理，副本服务器和数据中心等网络资源分配的网络工程师和运营商非常有帮助。同样，拥有详细而完整的互联网拓扑图可以为安全相关问题研究提供支撑。

互联网拓扑通常以图的方式呈现，其中节点表示有意义的网络实体，节点之间的连接表示实体之间的关系。在此基础上，互联网拓扑主要有四种不同的尺度或分辨率，从最精细到最粗略依次为IP（Internet Protocol，互联网协议）接口级、路由器级、PoP（Point of Presence，接入点）级和AS级。鉴于此，本文将按划分尺度的不同对网络拓扑数据的获取和推断方法进行概述和展望。

1 IP接口级拓扑

IP接口级拓扑中节点表示具有特定IP地址的网络接口，接口属于主机或路由器，节点和IP之间存在一对一的映射[6-7]。两个节点之间的连接表示节点之间的直接网络层连接，这种特性表明IP接口级拓扑忽略了二层交换机等网络层之下的设备。因此，IP接口级拓扑中的链路并不总是点到点链路。

traceroute是目前应用最广泛的IP接口级拓扑测量工具，它最早由V. Jacobson于1987年研制出来。发起traceroute探测的源结点通过操控IP报文头部的TTL值来触发报文转发路径上的各个设备对自己进行反馈，从而解析出到达目的结点的完整路由路径。V. Jacobson开发的traceroute基础版本基于ICMP（Internet Control Message Protocol，因特网控制报文协议）协议，后来也陆续出现了基于UDP（User Datagram Protocol，用户数据报协议）和TCP（Transmission Control Protocol，传输控制协议）协议的traceroute工具[8]，以便使探测报文能够以更大概率穿越防火墙等报文过滤设施。M. Luckie等人通过实验对比了基于以上三种协议的traceroute工具解析路由路径的能力，发现基于ICMP的traceroute探测报文到达探测目的的成功率最高，而基于UDP的traceroute工具虽然能够发现更多IP链路，但探测报文到达探测目的的成功率最低[9]。随着路由技术的发展，越来越多的路由器通过负载均衡技术提升网络的路由中继能力，导致网络中的两个IP接口之间同时使用多条路由路径进行通信。多径路由场景下，传统traceroute工具可能产生实际并不存在的虚假链路。针对基于流的多径路由策略，B.Augustin等人设计了Paris traceroute[4]，为同一次探测的探测报文分配相同的流标识，能够有效解决这一问题。但对于基于报文的多径路由场景，该问题依然没有较好解决方案。

每一次完整的traceroute探测可以解析出探测源到目的结点的一条路由路径，为了获得整个网络的完整拓扑，需要从多个探测源向一系列目的结点发起traceroute探测，然后将获得的多条路径进行融合。显然，探测源集合和目的结点集合的选择会直接影响最终网络拓扑的完整性。面对规模极其庞大的因特网，这项工作非常具有挑战性，人们为此研究部署了多个大规模探测系统。这些探测系统在全球各地拥有数量不等的探测源结点，有的依赖于专属的测量设备[10-11]，有的则是借助诸如PlanetLab的通用测量平台资源[7，12-13]。早期研究表明，通过增加探测源的方式并不能持续有效地增强探测系统提高所得网络拓扑完整性的能力[14]，因此CAIDA的拓扑探测系统重点关注合理选择探测目标结点，仅使用较少数量的探测源[10-11]。然而近期研究却指出，通过合理增加探测源能够保证获得更完整的网络拓扑，新发现了大量IXP（Internet eXchange Point，互联网交换中心）对等链路[15]。R. Beverly等人提出通过加大测量周期及探测次数，在较长时间里进行多次测量获得更完整的网络拓扑，同时获得其动态变化特征[16]。但是该方法面临着数据一致性的问题：如果曾经发现的链路在后续测量阶段再也不曾出现，那么该链路是否依然存在。

traceroute采用基于不同协议的探测包克服防火墙过滤等问题，但依然存在其他不足，如：中间路由器可能采用多种策略决定应答探测报文的具体IP接口，甚至使用错误的IP地址或者不作任何应答（匿名路由器）。为了克服这些问题，研究人员从其他角度设计了一些新的探测方法，作为traceroute的补充。E. Katz-Bassett等人综合利用IP报头的“路由记录”选项字段，源路由和源地址伪装技术，研制出反向traceroute工具，在探测源与探测目标间的正反向路径不对称的情况下获得反向路径[17]。M. E. Tozal等人基于同一个子网中的IP地址结构特征，提出一系列子网推断准则，发现探测源到探测目标的路径经过的子网，相较于traceroute只能发现部分IP接口，显著提升了拓扑发现能力[18-19]。

2 路由器级拓扑

路由器级别的拓扑通常是对属于同一路由器的接口进行分组的结果，实现这个目标的技术则被称作别名解析[12]。路由器级拓扑中的各个结点或对应具有单个网络接口的端主机，或对应具有多个网络接口的路由器，连接则反映了两个结点之间存在的网络层链接。

Pansiot等人提出了一种针对目标IP的不可到达端口进行探测的别名解析方法：为了识别某个IP地址A的别名，探测源向A的某个未使用端口发送一个TCP或者UDP探测包，A所在的路由器可能会选择一个不同于A的IP接口B向探测源反馈端口不可达报文，探测源收到响应报文后即可发现A、B属于同一个路由器[20]。该方法虽然不会引入假阳性错误，但是目标路由器并不总是采用另一个IP地址作为响应报文的源IP，甚至会直接忽略端口不可达的探测报文，因此它通常只能发现一小部分IP别名。

IP报文头部的ID字段被用于帮助网络通信的接收方进行报文重组。对于某些路由器，不管它发出的IP报文具体经由该路由器的哪个接口发出，所有报文共享同一个ID计数器。因此，这类路由器连续发出的IP报文具有逐一递增的ID。基于这一现象，N. Spring等人在Rocketfuel项目中提出了Ally算法进行别名解析[12]。Ally分别向两个可能的别名IP地址的未使用端口发送UDP探测包，探测包对应的ICMP端口不可到达响应被分别封装在两个IP数据包中，记其ID分别为x、y。探测源收到所有响应报文后向先到达的响应报文对应的IP发送第三个探测包，记这个探测包的响应报文ID为z，如果x＜y＜z成立而且z-x小于某个门限，那么被测量的两个IP被判定为别名。以下情况都可能导致Ally会产生假阴性错误（False Negative）：路由器配置了较大的ID递增步长，或者各个接口使用独立的计数器[21]；甚至探测包或者响应报文在传输过程中遭受时延抖动。此外，Ally每次仅对两个IP地址进行探测和解析，工作效率较低，难以推广到大规模网络中：对于n个目标IP地址，它的探测复杂度为O(n2)。A. Bender等人提出的RadarGun对目标IP地址进行多次探测，通过对比各个IP地址的ID增长速率来识别别名地址，能够有效解决该问题，其探测复杂度为仅O(n)[22]。K. Keys等人综合Ally和RadarGun的优势，采用滑动时窗的思想解决探测复杂度高的问题，所提出的方法能够实际应用于当前互联网，同时兼顾了解析结果的准确性[23]。

traceroute测量得到的IP接口级拓扑自身也包含了别名解析所需的相关信息。首先，在相同traceroute路径中出现的IP不可能互为别名，这是因为正常情况下数据报文在网络中传输时，不会多次经过同一个路由器，形成路由回路。其次，如果分属两条路径的两个IP地址A和B的下一跳同为一个IP地址C，那么A和B很有可能属于同一个路由器。基于以上现象，N. Spring等人提出启发式方法进行别名解析[24]。该方法的缺点在第二个启发式规则假设IP地址C所在链路为点对点型链路，否则会产生假阳性错误。M. H. Gunes等人提出的AAR[25]一定程度上克服了以上不足，他们首先根据一系列规则推测traceroute数据中所有IP可能所在的子网，然后将各条traceroute路径按照子网对齐，解析IP别名，该方法可被视作N. Spring等人工作的一般化。M. H. Gunes等人在AAR的基础上提出改进方案APAR[26]，通过对AAR的分析结果进行探测验证，能够进一步提高AAR的准确性。

此外，网络中的路由器开启了对某些查询报文的响应功能。基于该条件，简单网络测量协议（Simple Network Measurement Protocol，SNMP） 和 因 特 网组管理协议（Internet Group Management Protocol，IGMP）可分别用于在本地局域网和因特网中发现路由器结点[27]。

3 PoP级拓扑

PoP是属于同一AS的路由器集中区[28]。因为AS通常会以分层方式构建其物理网络，AS中的PoP互连形成AS的“骨干”，并且由PoP对其客户或终端用户提供访问能力。目前学术界和工业界对于PoP的定义尚无严格统一的定义：互联网服务提供商们认为他们用来部署路由器结点的某栋建筑，或者能够享用其服务的用户所在的某个城市地区都可算作是一个PoP结点；学术界则通常将属于某个相同AS并为其用户和其他PoP提供连接的路由器集群定义为一个PoP结点。但没有疑问的是，结点的地理位置属性在PoP级拓扑中尤为重要。PoP级拓扑中的每个结点通常用该AS的AS号和该PoP的地理位置进行标识。若某两个PoP属于相同AS，那么它们之间的链路被称作骨干链路；否则，称这两个PoP之间的链路为对等链路。因此，节点表示属于AS的PoP，连接表示两个PoP的路由器之间存在的物理连接。

同路由器级拓扑类似，现有研究中最普遍的PoP级拓扑测量技术也是通过对更小尺度的IP接口级拓扑、路由器级拓扑进行结点聚合，从而得到PoP级拓扑。其中，N. Spring等人研制的Rocketfuel系统是此类工作的先驱[12]。他们首先采用别名解析算法Ally从traceroute数据中识别出别名IP，然后根据一系列DNS（Domain Name System，域名系统）命名规则推测IP地址的地理位置，最后将位于相同地理位置的IP集合聚合为PoP结点，从而得到PoP级拓扑。H. V. Madhyastha等人对Rocketfuel进行了多方位的改进[7]：综合多个别名解析算法[25，29]提升IP别名识别的精度，并克服了DNS命名规则解析的某些缺陷[30]。Tian等人用IP地理位置数据库替代由DNS信息推测得到的地理信息[13]，并采用启发式方法根据地理位置信息将IP地址聚类为PoP结点。

PoP级拓扑反映了各个AS在部署自己的网络基础设施时为了达到可扩展性和可维护性而形成的层次化结构。网络管理者通常参考设备制造商建议的某些固定模式设计PoP架构，从而保障PoP的服务性能，提供更好的连接服务[31-32]。因此，互联网络中各个AS的大多PoP都具有相似的内部结构。基于此，Feldman和Y. Shavitt等人针对时延信息进行分析，在IP接口级拓扑中发现此类重复模式，识别PoP结点[33-34]。

4 AS级拓扑

AS级拓扑中的每个结点对应一个其中设备采用相同路由策略的自治系统，并用唯一标识AS号进行区分。连接表示两个AS之间的商业业务关系，这些关系反映了AS之间交换流量时谁向谁付费，因此这些连接本质上是虚拟的而不是物理的，它是一个抽象，通常代表两个AS之间的多个物理连接[35]。它们之间的连接类型可能是Customer-Provider，Peer-Peer和 Sibling-Sibling。AS连 接 对应的物理实体通常是两个AS的PoP之间的多条物理链路。

AS级拓扑的原始数据主要来自三个方面：BGP路由信息、traceroute测量数据、互联网路由注册信息（Information Resource，IRR）。其中，BGP协议的设计初衷就是为了确定数据报文在AS间，因而BGP路由信息中包含大量AS级的拓扑信息。利用BGP信息获取AS级拓扑的工作中，当属B. Zhang[36]和P. Mahadevan[37]等人的工作最具代表性。他们通过在网络中部署一系列BGP收集器，采用被动测量的方式获得网络中路由器间交互的BGP信息。Z. M. Mao[38]和R. Bush[5]等人部署的探测结点则能够主动向其他路由器广播BGP路由，根据对方的响应解析可用信息。

将traceroute测量得到的IP接口级拓扑中各个IP地址映射到它所属的AS，如果某条路径上的两个连续IP分属不同AS，那么对应的两个AS之间存在链路，从而根据traceroute数据得到AS级拓扑。为达成这一目的，Z. M. Mao等人研究了如何利用BGP路由表和IRR信息简历IP地址到AS的映射[39]。这个方法的优势在于能够获得更详细的AS级拓扑：如果两个AS通过多条不同链路连接，这些链路在traceroute数据显然能被区分，因而最后的AS级拓扑仍可保留这些链路的信息。

此外，IRR提供的一系列查询数据库RADb（Routing Assets Database）收录了当前互联网的基础路由信息。全世界已有上千个机构组织将自己名下的网络路由信息发布到这些数据库中[40]。经过IRR获取AS级拓扑信息十分简单快捷，无需再执行探测操作，因而能够有效避免各类探测方法的缺点。然而，RADb收录的数据由多个贡献者自愿提供，因而其可用数据的完整性和一致性可能存在问题[41]。

5 局限及问题

目前针对不同尺度的网络拓扑都存在相应的测量或推断方法，但均存在某些问题或局限。traceroute或BGP都不是专门设计用来测量网络拓扑的方法，由此得出的互联网拓扑数据质量和完整性都很难评估。

traceroute主要用于网络故障排除，它被设计为通用的可达性诊断工具，使用它来发现互联网的接口级拓扑结构是后来想到的，也是一个不完美的探索性步骤[42]。第一，路由器对TTL零探测的响应没有唯一的设置。网络运营商通常选择以下五种策略之一：不响应、使用探测接口的IP地址响应、使用接收探测消息的接口IP地址响应、使用固定接口IP地址响应、和使用随机IP地址响应。除了路由器配置设置，防火墙也可以配置为防止被探测的路由器响应。第二，traceroute在每一跳上记录的IP地址不一定是有效的IP地址，这可能是由于向路由器接口错误分配IP地址的做法导致的。第三，每一跳报告的RTT值不能用于准确测量往返目标的延迟。traceroute是一个前言路由诊断工具，Internet路由中的经验法则是两个IP之间的路由并不总是对称的。因此，traceroute探测所采用的路径可能与其响应所采用的路径不同。事实上，两个连续跳之间的延迟变化可能是由于链路拥塞，路由器队列中的可变延迟或不对称路由造成的。第四，二层云通常对于traceroute是不透明的，这些云的明确目的是对IP层隐藏网络基础设施。

对于AS级拓扑而言，使用BGP推断AS级拓扑有一些优点，如与互联网注册管理机构相比，从BGP收集的数据显示了实际的可达性，数据通常不会陈旧过时或不正确，BGP更新可以用于研究互联网路由动态行为等。但用BGP推断AS拓扑也存在一些缺陷，主要原因是BGP仅仅是一种信息隐藏协议，仅表明可达性，而不是连通性。AS路径通告主要用于环路检测。而且，AS可能会宣布与真实路径不相符的AS路径[43]。此外，BGP不会通告每个可用路径的信息，仅通告最佳路径，所以备份路径可能永远不会出现在BGP转储中。由于路由收集器通常部署在较大的ISP（Internet Service Provider，互联网服务提供商）中，并且大部分位于美国和欧洲，因此观察到的AS级拓扑结构偏向于对这些区域更加完整。即使路由收集器随机放置在不同的AS中，发现AS关系的可能性也与使用该链路的AS的数量成正比[5，44]。

由于现有方法存在以上局限，学者们提倡为特定级别的互联网拓扑发现设计新的测量技术，使研究人员能够测量他们想要测量的东西，而不仅仅是他们可以测量的东西。

6 结 语

互联网拓扑研究对于网络服务性能分析和优化、网络安全等具有重要的意义，而此类研究依赖于互联网拓扑数据获取。因大规模、分布式、异构性等特征，使得互联网拓扑结构的获取本质上是极具挑战性的。本文对当前不同尺度上的互联网拓扑数据的获取方法进行了详细的综述，分析了现存方法中普遍存在的局限性。互联网拓扑数据获取急需新的思想和更优的解决方法，以突破瓶颈，以更好地为网络优化、网络安全服务。