An Investigation of Geographic Mapping Techniques for Internet Hosts（2001年）第二部分

被引次数：766

Padmanabhan V N, Subramanian L. An investigation of geographic map** techniques for Internet hosts[C]//Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications. 2001: 173-185.

之前的部分见：An Investigation of Geographic Mapping Techniques for Internet Hosts（2001年）第一部分-CSDN博客

6. The GeoCluster Technique

GeoCluster不同于GeoTrack和GeoPing，因为它不依赖于主动网络测量。相反，它使用网络路由信息和位置信息的知识，为IP地址空间的一个大子集构建位置映射。

GeoCluster操作如下。

首先，将IP地址空间分解成集群，使集群中所有具有IP地址的主机可能都位于（该位置的粒度取决于应用程序的上下文。），即地址形成一个地理集群。

然后，了解集群中几个主机对应的位置（并假设位置在很大程度上一致），地理集群推断出整个集群的位置。

地理集群运行的关键是从第3.5节中提到的来源获得的IP-to-location的映射信息。（我们将在第6.5节中讨论获取此类数据的一般问题。）然而，这种映射信息在覆盖范围内往往是部分的（因为它只包含IP地址空间中相对较小的一个子集的位置信息），而且可能不准确。这些问题限制了IP-to-location映射数据的效用。

GeoCluster通过根据其（可能的）位置集群IP地址来解决这两个问题。集群有助于扩展部分IP到位置映射信息的覆盖范围。位置信息的聚合也使我们能够识别和消除由于单个位置数据点的不准确而造成的异常值。

举个例子，假设我们知道128.127.126.0/243形成了一个地理集群。进一步假设部分映射信息告诉我们，该集群中10个第二IP地址对应的位置是西雅图，而另一个IP地址对应的位置是Boston。这样我们就可以合理地推断出波士顿数据点是错误的，并且这个集群中的所有(256)个IP地址(如果确实在使用的话)都可能对应于西雅图(或附近)的主机。

6.1 Identifying Geographic Clusters

我们将在第4、5和6节中详细介绍这三种IP2Geo技术的细节，并对它们的性能进行了分析。

确定地理集群是一个具有挑战性的问题。地理集群所使用的基本方法是将部分IP-to-location映射信息与网络路由信息结合起来。我们建立在在[12]中提出的关于识别拓扑簇的工作的基础上。互联网中的地址分配和路由是分层的。路由信息可跨单个管理域（也称为自治系统（AS）)下的主机进行聚合。例如，大学校园里主机的路由通常会作为一个聚合广告给互联网的其他部分，比如prex 128.127.0.0/16的地址，而不是65536个单独的IP地址。因此，对路由协议所使用的地址前六（APs）的知识使我们能够识别拓扑簇，如在[12]中所观察到的那样。我们推测APs也可能构成地理集群。我们将在下面详细说明这一点。

[12] B. Krishnamurthy and J. Wang. On Network Aware Clustering of Web Clients. ACM SIGCOMM, August 2000.

我们从用于互联网上的域间（即AS）路由的边界网关协议（BGP）中获取关于APs的信息。在一个路由器上的BGP表中的每个条目都是一个目标AP和通向它的AS级路径。出于我们的目的，我们只对AP信息感兴趣，因此我们构建了一个唯一的APs列表（超过100000个APs，如第3.4节所述）。APs的数量比ASs的数量大一个数量级。这是因为，由于策略和/或性能考虑（例如，对于负载平衡），可能会发布更多的特定路由（例如针对某些客户）。

AS（及其相关的AP (s)）通常对应于一个地理集群，如大学校园或公司。即使AS是一个具有大地理覆盖的ISP，通过BGP广告的相关AP可能是更特定（比如对应于个人客户），如上所述。在这两种情况下，GeoCluster都能够从美联社信息中识别地理集群。然而，大型ISP（例如，AT&T，Sprint，UUNet等）。出于可伸缩性的原因，通常只发布聚合AP。在这种情况下，一个AP可能跨越一个很大的地理区域。如果我们能够更详细地了解大型聚合如何通过ISP中使用的域内路由协议进行细分，那么这个问题将会得到缓解。但是，获取这些信息对我们来说是不可行的，所以我们只使用来自BGP的域间路由信息。

总之，我们的基线Geo集群算法，我们称之为BGPonly，它基于BGP数据发现AP，并推测这些AP是地理集群。然而，如上所述，这个猜想可能并不总是正确的，例如，当ISP只宣传大的聚合时。我们现在提出了一种子聚类算法来解决这个问题。我们将包含该算法的地理聚类的变体称为BGP+子聚类。