被引次数：492
Abstract
我们提出了基于拓扑的地理定位（Topology-based Geolocation，TBG），一种新的估计任意互联网主机的地理位置的方法。我们激励我们的工作表明1)现有的方法，基于端到端延迟测量从一组地标，未能超越简单的技术，和2)这些方法的误差强烈由距离最近的地标，即使三角测量用于结合估计从不同的地标。我们的方法改进了这些早期的技术，利用网络拓扑，以及网络延迟的测量，来约束主机的位置。我们将拓扑数据和延迟数据转换为一组约束条件，然后同时求解路由器和主机的位置。这种方法提高了位置估计的一致性，在我们对Abilene和Sprint的实验中，大大减少了结构化网络的误差。对于结构约束不足的网络，我们的技术集成了外部提示，在被信任之前使用度量进行验证。总之，这些技术将我们基于大学的数据集的中值估计误差降低到67公里，而之前最好的计算方法为228公里。
Categories and Subject Descriptors
C.2.4 [Computer-Communication Networks]:分布式系统
General Terms
算法（Algorithm）、测量（Measurement）
Keywords
地理定位（Geolocation），网络拓扑（Network topology），延迟测量（Delay measurements），路由测量（Route measurements）
1. INTRODUCTION
确定一个互联网主机的地理位置的能力将使各种应用程序成为可能，从平凡的到必要的。商业数据库目前提供粗略和不完整的位置信息，使一些有针对性的广告提供，以及其他内容本地化。如果可靠，它可以作为E-911系统的一部分或区域紧急情况的广播系统的一部分。作为基础设施的一部分，一个无处不在的定位服务已经被一些人确定为未来互联网[5,13]的一个重要愿景。
[5] D. Clark, C. Partridge, R. Braden, B. Davie, S. Floyd, V. Jacobson, K. Kitabi, G. Minshall, K. Ramakrishnan, T. Roscoe, I. Stoica, J. Wroclawski, and L. Zhang. Making the World (of Communication) a Different Place. ACM SIGCOMM Computer Communication Review, 35(3), 2005.
[13] A. LaMarca, Y. Chawathe, S. Consolvo, J. Hightower, I. Smith, J. Scott, T. Sohn, J. Howard, J. Hughes, F. Potter, J. Tabert, P. Powledge, G. Borriello, and B. Schilit. Place Lab: Device positioning using radio beacons in the wild. In Proc. of Pervasive, Munich,Germany, 2005.
我们将查找互联网主机的地理位置的过程称为IP地理定位。这是一个困难的问题，即使把移动性放在一边，因为互联网的分散管理意味着没有关于主机位置的权威数据库。确实存在的数据库是通过组合各种源代码（包括DNS LOC记录、whois注册和DNS主机名解析规则）而派生出来的。它们都是手动维护的，因此受到不一致和过时的信息。自动化系统是可取的，因为它们可以消除这些问题并产生可靠的结果。然而，它们只存在于特殊的情况和设备，如使用GPS [8]和GSM或802.11 beacons[13]；甚至后者也依赖于一个必须手动输入的大型地标数据库。
[8] P. Enge and P. Misra. Special issue on global positioning system. In Proceedings of the IEEE, volume 87, pages 3–15, jan 1999.
[13] A. LaMarca, Y. Chawathe, S. Consolvo, J. Hightower, I. Smith, J. Scott, T. Sohn, J. Howard, J. Hughes, F. Potter, J. Tabert, P. Powledge, G. Borriello, and B. Schilit. Place Lab: Device positioning using radio beacons in the wild. In Proc. of Pervasive, Munich,Germany, 2005.
我们更大的目标是开发一种针对IP地理定位的自动化服务，它广泛适用，并可扩展到互联网的规模。这样的服务将由IP地址进行查询，并返回一个准确的位置估计值。与现有的系统相比，它将具有关键的优势。与GPS、GSM和802.11方法不同，它不需要专门的硬件，因此可以真正地无处不在，适用于所有的互联网主机。与基于DNS名称[15,18]的方法不同，即使DNS名称不可用或不正确，它也会自动推导出位置估计值，这在高流失率数据库中很常见。
[15] D. Moore, R. Periakaruppan, J. Donohoe, and K. Claffy. Where in the world is netgeo.caida.org? In Proc. of the INET, Yokohama,Japan, 2000.
[18] V. Padmanabhan and L. Subramanian. An investigation of geographic mapping techniques for Internet hosts. In Proc. of the ACM SIGCOMM, San Diego,CA,USA, 2001.
在本文中，我们考虑了实现这种服务必须解决的核心问题：如何估计给定主机IP地址的位置。为了设计一个自动化的解决方案，我们专注于网络测量的使用。由于我们不是第一个这样做的人，所以我们通过研究其他人提出的技术来开始我们的研究。这些技术是基于来自一组已知位置[18,10]的地标的端到端延迟测量。当我们使用在PlanetLab上收集的数据集对变化进行实验和评估时，我们惊讶地发现，更简单的基于延迟的算法能够提供与最先进的算法一样好或更好的性能。
[18] V. Padmanabhan and L. Subramanian. An investigation of geographic mapping techniques for Internet hosts. In Proc. of the ACM SIGCOMM, San Diego,CA,USA, 2001.
[10] B. Gueye, A. Ziviani, M. Crovella, and S. Fdida. Constraint-based geolocation of Internet hosts. To appear in ACM Transactions on Networking.
我们进一步发现，我们研究的所有纯延迟算法的误差在很大程度上取决于与最近地标的距离。这种影响是由于互联网路径的迂回和不规则性造成的，将跨地标的延迟合并在一起的技术几乎没有帮助。结果是，基于延迟的算法必须使用许多经过仔细选择的地标，才能始终如一地达到任何合理的精度水平。由于很难在各处均匀地找到标记点，这些算法通常对一小部分目标效果不佳;在我们的美国实验中，有超过1000公里估计距离。
这种推理路线使我们得出结论，认为还需要其他类型的技术。为此，我们研究了结合延迟和拓扑来考虑互联网电路路径的算法。启发来自算法用于定位传感器网络[7,4]，我们将互联网路线测量转换成一组约束目标的未知位置的路线和中间路由器，然后同时定位目标和所有的路由器的方式最好地满足约束。这种方法，我们称之为基于拓扑的地理定位（TBG），它有许多理想的特性：
TBG将结构化的Abilene和Sprint网络上的目标的平均误差分别降低了约40%和70%，以及第90百分位的误差为4倍。
[7] L. Doherty, K. S. J. Pister, and L. E. Ghaoui. Convex position estimation in wireless sensor networks. In Proceedings of Infocom, pages 1655–1633, 2001.
[4] P. Biswas and Y. Ye. Semidefinite programming for ad hoc wireless sensor network localization. In Proceedings of Information Processing in Sensor Networks, 2004.
然而，我们的研究表明，仅基于网络测量的技术有其固有的局限性。例如，如果到目标的互联网路由没有充分限制目标的位置——比如当所有路由的尾部收敛到一个具有显著延迟的共享段时——那么在没有其他信息来源的情况下就不可能准确地地理定位目标。幸运的是，我们基于拓扑的技术可以验证和合并“被动”参考节点的位置——这些节点不能发布度量，但可以被“主动”地标探测——以帮助约束拓扑。它生成包含目标和被动参考节点的网络拓扑，使用延迟和拓扑测量来验证被动节点的位置，然后基于整个拓扑得到目标的位置估计。与已建立的技术相比，我们将困难目标的中位数误差提高了3倍以上。我们相信，这种方法有望成为未来IP地理定位工作的一个方向。
本文的其余部分组织如下。在第2节中，我们将更详细地介绍这个问题，并回顾相关的工作。第3节介绍并评估了基于延迟的地理定位技术的新的和现有的变化，并确定了它们的一些局限性。第4节然后介绍了一种地理定位技术，该技术还考虑了互联网的结构及其路由，第5节评估了它与基于延迟的技术相比的性能。最后，我们讨论了不同技术的优缺点。
2. PROBLEM AND PRIOR WORK
在第2节中，我们将更详细地介绍这个问题，并回顾相关的工作。
2.1 Problem
我们所考虑的IP地理定位问题的版本是如何自动估计互联网上任意计算机的粗粒度地理位置。我们自动的意思是该技术不应该依赖人工输入，而不是为参考主机建立地理坐标；所有方案都需要一些真实值来引导系统，但一小部分参考主机应该能够实现更大的目标集的位置。此外，如果由外部源提供节点的可能位置，必须由参考主机自动验证，然后才能用于地理定位目标。通过任意的计算机，我们的意思是该技术应该能够定位所有的IP地址，而不是属于一个特定的提供者的子集，已经以某种方式注册，等等。通过粗粒度位置，我们的意思是估计应该准确到一个主要大都市区的水平内。更严格的估计是可取的，但城市层面的估计对于许多应用就足够了。
本文研究了基于网络度量的IP地理定位技术。在这种情况下，我们有一组具有已知位置的参考主机，我们将其称为地标。有些是可以发出探测器的主动地标，而有些可能是被动的地标，不能发出探测器。在本文的其他地方，我们将指定，当区别很重要时，地标是被动的；否则，就可以假定它们是主动的。我们收集地标和其他未知位置的主机之间的测量，以及地标之间的测量。然后，我们根据指定的算法来处理测量值，以估计目标的位置。因为我们希望能够在不首先升级其软件的情况下绘制主机，所以我们只考虑可以使用源自地标的测量来运行的算法，例如，测量路径和到目标的延迟。我们不使用任何源自目标的测量方法。
2.2 Internet Measurement Techniques
两种已发布的地理定位技术适合我们的问题和方法，GeoPing [18]和基于约束的地理定位（CBG）[10]。两者都使用从地标上进行的延迟测量来估计互联网主机的位置。我们将在下面详细介绍它们，因为它们显示了延迟如何以重要的方式与位置相关，而且我们将很快在这些基础上构建（第3节）。
[18] V. Padmanabhan and L. Subramanian. An investigation of geographic mapping techniques for Internet hosts. In Proc. of the ACM SIGCOMM, San Diego,CA,USA, 2001.
[10] B. Gueye, A. Ziviani, M. Crovella, and S. Fdida. Constraint-based geolocation of Internet hosts. To appear in ACM Transactions on Networking.
2.2.1 GeoPing
GeoPing通过将目标映射到最具代表性的地标，并使用该地标的位置作为目标[18]位置的估计值来定位目标。为了做到这一点，GeoPing假设两个相邻的主机将测量与其他地标相似的延迟。从所有地标探测目标，建立一个延迟向量，作为地标“接近”的轮廓。目标被映射到轮廓最相似的地标。相似度计算为延迟向量之间的欧氏距离，即在“延迟空间”中到目标的距离。
有趣的是，GeoPing可以通过一组不能对目标执行探测的被动地标来增强其地标集。在这种设置中，目标可以映射到主动或被动地标。这种设置很有趣，因为添加被动地标“更便宜”，而且它们可能允许技术在不增加探测地标密度的情况下表现得更好。
2.2.2 Constraint-Based Geolocation
基于约束的地理定位（CBG）采用了地标的位置，而是使用类似三角的技术来组合来自多个地标的延迟，并可以返回位于地标之间的位置。为了将延迟与距离联系起来，每个地标测量从自身到所有其他地标的延迟。然后它符合这个数据的最佳线。这本质上是所有（延迟，距离）对的最紧的线。图1显示了普林斯顿大学（Princeton University）地标的例子。因为最佳线位于所有测点之上，所以它将延迟转换为被当作上界的距离估计。然后假设目标在一个圆圈内，以地标为中心，其半径为估计的距离。
图1：散点图和CBG最佳线
然后，CBG通过相交于所有的圆来组合来自所有地标的距离估计值。这个交点产生了一个假定目标所在的可行区域。目标被任意估计为位于区域的质心上，并将区域的大小作为估计中的不确定性（或置信度）的度量。图2显示了一个示例。“+”标志是地标，虚线圆是约束条件，交叉点区域以粗体周长为界。实验表明，在美国和欧洲的数据集[10]上，CBG比GeoPing和基于dns的方法（如[28]）提供更好的地理定位估计。