Topology discovery and mapping

Discovering and analyzing Internet structure has been the subject of many studies. Much of the work has focused on studying topology purely at the network level, without any regard to geography. Recently several tools have been developed to map network nodes to their corresponding geographic locations. A few Internet mapping projects have used such tools to incorporate some notion of geographic location in their maps. The Mercator project [6] focuses on heuristics for Internet Map Discovery. The basic approach is to use traceroute-like TTL limited probe packets coupled with source routing to discover routers¹. A key component of Mercator is the set of heuristics used to resolve aliases, i.e., multiple IP addresses corresponding to (possibly different interfaces on) a single router. The basic idea is to send a UDP packet to a non-existent port on a router and wait for the ICMP port unreachable response that it elicits. In general, the destination IP address of the UDP packet and the source IP address of the ICMP response may not match, indicating that the two addresses correspond to different interfaces on the same router. In our work we use geographic information to identify points of sharing in the network. We view this as complementary to network-level heuristics such as the ones employed in Mercator. The Internet Mapping Project [2] at Bell Labs also uses a traceroute-based approach to map the Internet from a single source. The map is colored according to the octets of the IP address, so portions corresponding to the same ISP tend to be colored similarly. The map, however, is not laid out according to geography. Other efforts have produced topological maps that reflect the geography of the Internet. Examples include the MapNet [24] and Skitter [28] projects at CAIDA and the commercial Matrix.Net service [25]. A number of tools have been developed for determining the geographic location corresponding to an IP address. These tools use a variety of approaches to map an IP address to location: inferring location from Whois records [7] (e.g., NetGeo [11]), extracting location information from traceroute data (e.g., GeoTrack [13], VisualRoute [30]), determining the location coordinates using delay measurements (e.g., GeoPing [13]), etc. Our previous work on IP2Geo [13] focused on developing several tools, including GeoTrack, to do IP-to-location mapping. In this work, we use the GeoTrack tool to analyze geographic properties of Internet routing.