URL: http://www.sigcomm.org/sigcomm2002/papers/rocketfuel.pdf Entry Date: 2002-5-30 Abstract: To date, realistic ISP topologies have not been accessible to the research community, leaving work that depends on topology on an uncertain footing. In this paper, we present new Internet mapping techniques that have enabled us to directly measure router-level ISP topologies. Our techniques reduce the number of required traces compared to a brute-force, all-to-all approach by three orders of magnitude without a significant loss in accuracy. They include the use of BGP routing tables to focus the measurements, exploiting properties of IP routing to eliminate redundant measurements, better alias resolution, and the use of DNS to divide each map into POPs and backbone. We collect maps from ten diverse ISPs using our techniques, and find that our maps are substantially more complete than those of earlier Internet mapping efforts. We also report on properties of these maps, including the size of POPs, distribution of router outdegree, and the inter-domain peering structure. As part of this work, we release our maps to the community. Results:

• Presents new techniques to measure router-level ISP topologies. These and other techniques are used by Rocketfuel to discover ISP maps that consist of backbone, access and directly connected neighouring domain routers along with the IP-level interconnections between them. The new techniques reduce the number of required traces compared to a brute-force, all-to-all approach by three orders of magnitude without significant loss in accuracy. The techniques used are:
  • Use of BGP routing tables (obtained from Routeviews) to focus measurements. Only traceroutes are performed that will likely transit the ISP.
  • Exploiting properties of IP routing to eliminate likely redundant traceroutes.
  • Alias resolution: Uses the existing technique (from Mercator) of eliciting a "UDP port unreachable" message (from Mercator). New techiques used are router identification hints such as IP identifier (IP fragmentation), ICMP rate-limiting by routers of "unreachable" messages, and TTL values in "unreachable" messages.
  • o Use of hints embedded in DNS names to determine which routers belong to the ISP, the role of routers (e.g. backbone vs access), and the geographical location of routers (to determine POPs).
• Collected maps from ten ISPs and claim that they are substantially more complete than earlier Internet mapping efforts. The maps and raw measurement data are released to the community.
• Report refined results for the distribution of POP sizes and router outdegree, and the inter-domain peering structure.
• Found that ISPs have differing backbone designs but similar POP designs.
• To evaluate the ISP maps produced by Rocketfuel the maps are compared with:
  • Public ISP maps. Found that public ISP maps often have missing POPs, optimistic deployment projections, and contain parts of partner networks of other IPSs.
  • An email survey with three ISPs. Results are favorable.
  • The total number of routers found by scanning sampled subnets. 41-79% of such routers were found by Rocketfuel (64-96% of backbone routers and 35-92% of access routers).
  • Peerings from Routeviews BGP tables. In the worst case (Sprint) 70% of peerings visible in RV were found. Rocketfuel finds a small number of additional peerings. BGP tables find more small (low AS degree) neighbours, whereas Rocketfuel finds more large neighbours.
  • Skitter maps. Rocketfuel finds seven times as many nodes and links in the area of focus. Skitter finds a small number of additional nodes and links.
• To evaluate alias resolution, a comparison was made with:
  • Mercator. A superset of Mercator aliases was found which was almost three times as large.
  • DNS-predicted aliases of Ebone (119 out of 139 correct) and Sprint (240 out of 303? correct).

Datasets:

• Analysis of ten ISPs: Abovenet, AT&T, Ebone, Exodus, Level3, Sprint, Telstra, Tiscali (Europe), Verio, VSNL (India), using 294 public traceroute servers representing 784 vantage points.
• Routeviews BGP table snapshots.
• Email survey of three ISPs.
• Public ISP maps.
• For comparison with Skitter:
  • Skitter data of Nov 27 2001 and Nov 28 2001.
  • Rocketfuel data of Jan 2002.

References:

• Complements:
  • k. claffy, T. E. Monk, and D. McRobb. Internet tomography. In Nature, January 1999.
• Refines some of:
  • M. Faloutsos, P. Faloutsos, and C. Faloutsos. On power-law relationships of the Internet topology. In ACM SIGCOMM, 1999.
  • R. Govindan and H. Tangmunarunkit. Heuristics for Internet map discovery. In IEEE INFOCOM, 2000.
• Comparable:
  • H. Burch and B. Cheswick. Mapping the Internet. IEEE Computer, 32(4):97 98, 102, 1999.
  • k. claffy, T. E. Monk, and D. McRobb. Internet tomography. In Nature, January 1999.
  • R. Govindan and H. Tangmunarunkit. Heuristics for Internet map discovery. In IEEE INFOCOM, 2000.
• Builds on:
  • V. N. Padmanabhan and L. Subramanian. An investigation of geographic mapping techniques for Internet hosts. In ACM SIGCOMM, August 2001.