互联网拓扑测量技术与工程实践

余卓勋，张 宇，贾召鹏，郑 儿

(1.哈尔滨工业大学 计算机科学与技术学院，黑龙江 哈尔滨 150000；2.华北计算机系统工程研究所，北京 100083)

0 引言

网络空间测绘对网络空间中虚实组件、结构关系和交互规律进行测量与绘制，是站在更高层次上了解、控制、管理和建设网络空间的基础。对网络空间中互联网拓扑进行测量是构建网络空间基础设施“地图”的主要方式之一，对一个地区的互联网进行拓扑测量可以为发现地区网络基础设施中脆弱环节和消除断网风险提供重要依据。

互联网拓扑是指互联网中节点及其链接根据不同粒度分成接口级、路由器级、PoP(机房)级和自治域级等网络拓扑层级[1]，各级拓扑概念如表1所示。尽管已经存在的拓扑测量技术日趋成熟，然而基于基础的Traceroute测量获取地区级别互联网拓扑仍存在工程上的挑战。首先，由于IP地址本身不带有地理位置属性，因此难以直接获得地区内互联网完整IP地址范围；其次，可用的测量点以及测量能力难以完整地发现给定地址范围内的互联网拓扑。针对上述问题，本文介绍一个互联网拓扑测量工程实践，概述当前拓扑测量技术；介绍一个基于虚拟虚拟服务器的测量平台——VTopo；分析了VTopo对区域互联网拓扑测量的效率与完整性，并与CAIDA Ark测量项目进行了比较。

表1 各层级网络拓扑含义

1 拓扑测量技术与平台概述

经过20多年的发展，互联网拓扑测量研究和测量技术已逐渐成熟。按表1中各层次拓扑列举了主要的测量技术，如表2所示。它们为大规模互联网拓扑测量提供了基础性技术支撑。互联网拓扑测量技术的本质是对路由协议进行测量，最主要的技术是Traceroute[2]。Traceroute是一种通过向目标IP地址顺序发送TTL递增的探测包，利用中间路由器返回的TTL超时回复或目标的回复来获取测量点到目标之间IP路径的方法；路由器级、PoP级、自治域级等更高层次级别拓扑测量主要建立在接口级拓扑基础上，对接口级拓扑节点进行聚合。

表2 网络拓扑测量工具/技术列举

表3枚举了测量平台的四种类型，并总结了其在目标选择自由度、地理位置分布、数量和可用性等方面的特点。其中，CAIDA Ark[16]平台作为三方公开数据平台的代表，具有数量较多分布较广的节点，周期性对整个Internet进行大规模网络拓扑探测；本文采集该平台的测量数据作为分析比较的基线，用来评估测量的完整性。这些平台虽然各有优势，但都存在可用性差(第三方测量平台)或测量点数量不足(部署可控监测点)、部署不灵活等问题。

虚拟专用服务器(Virtual Private Sever，VPS)服务的兴起为搭建更健壮、更灵活的大规模拓扑测量平台提供了新的契机。VPS不光具有可伸缩、易部署、易迁移、可用性强等IAAS(Infrastructure As A Service)的天然优势，还具有节点众多，地理位置分布广泛的特点。这些节点所在的数据中心因为业务的需要，通常部署在接入网络的位置，在网络拓扑上与终端用户比较邻近；这些VPS测量节点与CAIDA位于教育研究网络的测量节点和Looking Glass位于核心骨干网络的测量节点形成互补，可以为网络拓扑测量贡献更多的完整性。

表3 网络拓扑测量平台及其特点

2 一个基于虚拟专用服务器的拓扑测量系统

测量平台的系统架构如图1所示，包括目标生成、测绘逻辑和VPS平台三个部分；目标生成部分以目标地区的地区代码作为输入，从合并后的地理定位数据库中提取出目标地区的IP地址范围；测量逻辑部分是拓扑测量的核心组件，负责测量任务的调度与控制，调度模块将地区内的测量目标分配给最佳的测量节点，并通过分布式任务队列将任务分发给VPS平台的对应监测点；监测点异步地执行测量任务并实时回传测量结果。此外，在进行适应性测量时，测绘逻辑模块还会根据当前测量点回传的测量结果来进一步指导测量任务的调度，原始任务调度-测量-测量结果指导调度修改-按照新的调度继续测量，依此类推，形成闭环。还有，大规模拓扑测量中的路径和时延信息也可以作为修正IP地理定位结果的信息来源，为下一轮的地区网络拓扑测量提供更精确的IP地址范围。

图1 VTopo测量平台的系统架构

3 互联网拓扑测量结果与分析

首先在选择测量目标时，从同时期(2019年3月4日)的BGP路由表和5个地理定位数据库中，提取出该地区内96万个可路由的IP前缀，并将其拆分成401万个粒度为“/24”的子网作为目标前缀列表；然后，使用测量平台的150个节点，每个节点独立测量目标列表中401万个“/24”前缀，各节点使用互不相同的偏移选择前缀中的IP地址；同时，为了不给目标网络带来过高的网络负载，限制最高发包速率pps(packet per second)为150。

测量按照上述调度方法进行10天探测，共得到了16亿2 641万条Traceroute数据。采集CAIDA Ark 60个测量节点3月同时期共20天的测量数据，共8亿6 300万条Traceroute。对二者进行了预处理，从IP路径中提取出IP接口级别的拓扑图，分别记作VTopo和CAIDA。为了评估拓扑发现的完整性，对发现的拓扑规模进行了计算，并与CAIDA Ark平台同时期规模相近的数据集合进行了重合关系比较；然后，为了评估测量效率，对发现拓扑规模随发起Traceroute测量的次数的变化率进行了分析。

Traceroute数据可以看成IP路径的集合P，由P产生拓扑图G，此外根据是否有转发行为，定义网络拓扑图中的路由器节点集合为R，这些概念的定义如下：

P={pi|pi=(h(i,1),…,hi,ki)}

G=G(V,E)

V={h|∃i,j≤ki,h=hij}

E={(a,b)|∃i,j≤ki,(a,b)=(hi,j,hi,j+1)}

R={h|∃i,j

其中hij代表第i条IP路径的第j跳IP地址(跳过匿名路由器，即在Traceroute中回复为“*”的跳，只在链接属性中保留连续的匿名路由器跳数)；G是以IP地址在网络层的相邻关系(一条IP路径上相邻两跳IP地址)为边，以所有在IP路径中出现的IP地址为节点的拓扑图；路由器节点集合是在IP路径中的中间跳IP地址或者不是本次Traceroute测量目标(ti)的末跳IP地址。

按照上述定义生成测量区域的网络拓扑图VTopo，并与CAIDA进行对比分析，本文给出了如表4所示的拓扑规模对比结果。对比的项目包括拓扑中的节点数、路由器节点数、链接数、路由器链接数4种。其中，节点数是节点集合的大小，路由器节点数是路由器节点集合R的大小，链接数是边集E的大小，路由器链接数是端点都在R中的链接组成的集合的大小。

为了分析VTopo和CAIDA的重合关系，对于每一个比较项，表4列举了VTopo和CAIDA的文氏图中各个部分的元素数目。其中，VTopo和CAIDA共同发现的部分是VTopo∩CAIDA；VTopo和CAIDA单独发现的部分分别是VTopo-VTopo∩CAIDA和CAIDA-VTopo∩CAIDA。此外，为了评价VTopo平台新发现拓扑的能力，表4还给出了VTopo新发现拓扑的比例，即VTopo单独发现数/VTopo发现总数。观察表4，可以得到如下发现：

表4 VTopo与CAIDA测量结果比较(单位：万)

(1)新发现拓扑比例上，VTopo平台新发现拓扑的比例较高，尤其新发现终端的比例较高，说明VTopo平台的测量结果是对CAIDA平台完整性上的较大补充。

(2)发现拓扑规模上，VTopo发现拓扑的规模大于CAIDA同时期测量发现的拓扑规模：发现的节点数、链接数都是CAIDA发现的近3倍。这说明通过对特定地区目标的针对性测量可以显著地增加发现地区内网络拓扑的完整性。

(3)发现路由器拓扑上，VTopo发现的路由器节点总数是CAIDA的2倍，但占总节点数量的比例小于CAIDA。这说明了VTopo能贡献更多处在网络拓扑核心部分的完整性，随着发现拓扑规模的不断增加发现新路由器节点的效率会有所下降。

为了评价VTopo测量发现拓扑的效率，对发现拓扑的规模随Traceroute测量次数的增长情况作了统计，如图2所示。

图2 VTopo测量发现率

在图2(a)，2(b)中分别给出了在进行前5亿7 000 万次Traceroute时，拓扑中新发现节点和新发现链接的增长情况，图中数据点在横坐标以10万次Traceroute测量为间隔进行采样。图中的直线是对数据点线性回归分析后得到的线性模型的预测直线，图2(a)和图2(b)中线性回归的r2分数分别为0.994和0.996，呈现较强的线性性，预测直线的斜率分别为0.30和0.34，这说明平均一次Traceroute测量仅能发现不足一个新的IP级节点和链接，这说明实验中的Traceroute测量存在较高的冗余。

导致高冗余的原因可能是每个测量点都独立测量所有401万个“/24”网段，而且测量顺序不是乱序，使得许多属于同一较大网段的IP地址被连续测量多次，增加了测量失败的几率，即很多测量都只测到同一路由器就遇到gap停止测量了；导致线性的原因是Traceroute每次测量目标IP地址都不同，并且测量完整性尚未达到最高值，所以尽管测量冗余较高，但新发现的拓扑信息总能以较低的速率线性增长。

4 结论

本文介绍了互联网拓扑测量技术，实现了一个基于VPS的拓扑测量平台VTopo，试验结果显示VTopo与CAIDA Ark数据集具有很大的互补性。未来研究方向为：如何实现适应性和多探测点间协作式探测以降低测量冗余；如何根据历史数据调度测量点以更完整高效地发现拓扑。