A High Completeness PoP Partition Algorithm for IP Geolocation

Abstract

Point of Presence (PoP) composed of routing nodes with specific connections can reflect structural properties of a local target network, which can be used for capturing the network dynamics and geolocating target IPs. However, PoP with low completeness may cause the failure of existing PoP-based IP geolocation methods. In this paper, a high completeness PoP partition algorithm for IP geolocation is proposed. Unlike some traditional PoP partition methods that directly use non-backbone routing nodes to obtain PoPs, this paper applies iterated subnet analysis to PoP partition of a specific area. Other IPs that are hosted on the same subnet which accommodates each node are acquired; a novel strategy is designed based on the similarity of routing hops and single-hop delays to filter non-regional IPs, and more new non-backbone nodes are acquired using probed results of the remaining IPs; the steps above continue to be applied iteratively to these new nodes and the iteration is aborted until almost no new nodes can be acquired. Alias resolution is introduced into this algorithm and tightly connected network structures (Bi-fan) are extracted to obtain final PoPs. The location attribute of PoPs are determined according to the locations of corresponding landmarks whose probed paths pass through the PoPs, thus these PoPs can be used to geolocate target IPs. Principles analysis and experimental results of some areas in China and the USA show that, compared with existing typical algorithms like PoP-Geo, PoP-NTA, and CRLB, PoPs obtained by the proposed algorithm are more complete and can significantly improve the success rate of geolocating target IPs.

Keywords

• PoP partition
• IP geolocation
• Bi-fan structure
• subnet analysis
• alias resolution