基于主动网络探测的低成本高精度IP地理定位

目前基于主动网络测量的IP地理定位方法存在两个重要的缺陷：

1. 高成本问题。测量方法需要一定数量的地理位置已知的机器来对目标地址进行主动探测，这些机器叫做探测点（vantage point， VP）。方法所需VP较多，使用服务器作为VP总体成本过高，虽然目前有诸如RIPE Atlas这样的探测平台，但使用仍然需要消耗平台中的积分，总体的成本仍然偏高。

2. 低精度问题。测量方法都会使用网络时延来进行位置推测，但是网络错综复杂，数据包传输的时延受到许多因素的影响，如中间路由器的处理性能、物理链路的传输速度、路由路径是否存在绕行路径等，因此探测所得时延和地理距离虽然有关联但并非完全的正比例关系。然而目前方法仍较为简单暴力，准确率无法达到应用的要求。

本文提出将网络中公开的 Looking Glass 作为地理定位的 VP。Looking Glass是一种由网络管理员部署在路由器上的一种网络检测工具，通过该工具可以让一些路由器进行网络时延探测、网络拓扑探测等操作，用于调试网络问题（如图1所示）。一些 Looking Glass 可以通过网页访问，如果找到这些 Looking Glass 的地理位置和调用的API，那么就能够使用它们作为地理定位的 VP。本文基于此思想对网络中开源的 Looking Glass 进行了分析，完成两个部分的工作：提取地理位置、提取时延调用API。

图1：某Looking Glass网页实例

首先是提取Looking Glass的地理位置，本文发现网络管理员部署时通常使用固定常用的模板，因此根据模板进行分析能够有效提取相关信息并且产生错误的概率较小。

之后是提取Looking Glass的时延调用API，这里本文同样是使用循环筛选的半自动化方式来获取：对各个Looking Glass进行不同的API调用，查看是否返回结果。如此得到了可以自动化利用、地理位置可知的探测点，这样只需要一台机器和这些探测点进行通信即可完成探测。

本文第二个工作是尝试提高定位的精度，由于网络探测所得结果受到多种因素的干扰，而这些因素很难去进行详细的获取，因此使用机器学习算法直接处理探测结果是直观但又很有效的方式。在利用探测点探测各个IP地址得到时延之后，本文提出了包含三个步骤的多阶段定位方法。

第一步本文对时延缺失值进行补充，其基本思想类似于矩阵补全的思想，其认为其他探测点所得时延可以有效帮助某个特定探测点进行缺失值补充，本文使用XGBoost决策树模型来完成该工作。每一轮针对其中某一个探测点V进行处理，直到所有的缺失值补充完毕。

第二步本文使用随机森林算法对目标IP地址的地理区域进行预测。一个探测点对于不同的地理区域传输速度有所不同，因此引入地理区域信息能够帮助定位。将各个探测点和IP地址的时延作为输入，使用机器学习模型预测地理区域，比较了常用的分类算法后，发现其中随机森林算法效果最好，因此选用随机森林作为该步骤的模型。

第三步本文使用随机森林算法对目标IP地址的地理坐标进行预测。算法的输入是各个探测点和IP地址的时延以及第二步所预测的区域类别，输出为经纬度坐标。为了适配定位场景，根据大圆距离对损失函数进行了修改，由于涉及到三角函数运算次数较多，使用下图公式进行了转换。此时输出不再为经纬度坐标，而是一个三维向量，误差函数中三角函数运算次数会减小到一次。

图2：将经纬度进行转换以及转换后的地理距离计算公式

由于涉及到对IP地址的定位，因此首先需要一大批地理位置可知的IP作为测试数据集。我们采用了三种手段来收集这些地址：探测平台的探针、摄像头托管网页分析、DNS域名分析。

1. 探测平台的探针中，直接通过调用RIPE Atlas这个平台下的API，得到了一部分用户部署时主动填写地理位置的探针。

2. 借鉴参考文章[1]实现了一种基于摄像头托管网页的收集方法，摄像头托管网页中地理位置是网页中一定会提供的（如网页会显示某某城市的摄像头），而一些网页在展示摄像头内容时暴露了其IP地址（展示的时候调用了摄像头对应的API，其中就可得知其IP地址）。如图3所示，该网页同时暴露了IP地址和地理位置。

图3：某同时暴露IP地址和地理位置的网页

3. 一些IP地址对应的域名包含了地理信息（如表1所示），因此可以基于此得出一部分IP地址的地理位置。本文在参考文章[2]的工作基础上进行了处理，使用CAIDA给出的ITDK数据集作为源数据，对其中的路由器地址进行了分析，得到了一部分地理位置可知的路由器地址。

表1：基于域名获取对应地理位置的实例

收集完IP地址后，使用后续所收集的探测点对收集而来的IP地址进行探测，最终得到了17276个终端地址（方法1和方法2）和26625个路由器地址（方法3），表2是其在5个RIR的分布。

表2：收集而来的IP地址在RIR的分布情况

最终本文从1367个网站中提取了407个地理位置可知、可以自动化利用的Looking Glass，图4是其中的地理分布情况。

图4：获取的Looking Glass的地理分布

使用其中的175个Looking Glass对前期准备的IP地址集进行了时延探测，探测结果显示有 8.61% 的探测尝试无法获取时延数据，如果探测失败则继续探测五次，发现其中仍然有 29.8% 的探测仍然无法获取时延数据。这一数据即证明了Looking Glass作为探测点的可行性，也说明了多阶段定位方法中的阶段一的必要性。对阶段一和二进行了分析，比较了阶段一和二的处理和常见处理手段的定位情况，结果如下图所示，其验证了这两个阶段的必要性。

图5：阶段一和常用补充缺失值算法对比

表3：使用不同地理区域划分时定位精度对比

最后对比本文工作和其他相关工作，结果如图6所示。本文方法取得了最好结果，平均误差为69千米，而相关工作中最好方法的平均误差为160千米。

图6：本文方法和相关工作的对比

本文针对目前基于主动网络探测的IP地理定位方法的两个痛点进行了改进。首先通过对Looking Glass进行分析，将其运用为定位的探测点，解决了高成本问题。之后提出一个多阶段定位方法，进一步降低了该类IP地理定位方法的误差。

但本文还存在一些问题，其对一些训练数据较少的地区定位较差，需要考虑如何收集更多这些地区的训练数据以及如何对这些地区采用特殊的定位方法。此外，对于Anycast类型的IP地址，该类方法会产生严重的错误，需要考虑如何定位前识别Anycast类型的IP地址。

参考文献