Towards an accurate AS-level traceroute tool

ABSTRACT

Traceroute is widely used to detect routing problems, characterize end-to-end paths, and discover the Internet topology. Providing an accurate list of the Autonomous Systems (ASes) along the forwarding path would make traceroute even more valuable to researchers and network operators. However, conventional approaches to mapping traceroute hops to AS numbers are not accurate enough. Address registries are often incomplete and out-of-date. BGP routing tables provide a better IP-to-AS mapping, though this approach has significant limitations as well. Based on our extensive measurements, about 10% of the traceroute paths have one or more hops that do not map to a unique AS number, and around 15% of the traceroute AS paths have an AS loop. In addition, some traceroute AS paths have extra or missing AS hops due to Internet eXchange Points, sibling ASes managed by the same institution, and ASes that do not advertise routes to their infrastructure. Using the BGP tables as a starting point, we propose techniques for improving the IP-to-AS mapping as an important step toward an AS-level traceroute tool. Our algorithms draw on analysis of traceroute probes, reverse DNS lookups, BGP routing tables, and BGP update messages collected from multiple locations. We also discuss how the improved IP-to-AS mapping allows us to home in on cases where the BGP and traceroute AS paths differ for legitimate reasons.

REFERENCES

• 1: Van Jacobson, "Traceroute," ftp://ftp.ee.lbl.gov/traceroute.tar.gz.
• 2: Vern Paxson, End-to-end routing behavior in the Internet, IEEE/ACM Transactions on Networking (TON), v.5 n.5, p.601-615, Oct. 1997 [doi>10.1109/90.649563]
• 3: Stefan Savage , Andy Collins , Eric Hoffman , John Snell , Thomas Anderson, The end-to-end effects of Internet path selection, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.289-299, August 30-September 03, 1999, Cambridge, Massachusetts, United States
• 4: Ramesh Govindan and Hongsuda Tangmunaraunkit, "Heuristics for Internet map discovery," in Proc. IEEE INFOCOM, 2000.
• 5: "Skitter," http://www.caida.org/tools/measurement/skitter.
• 6: Neil Spring , Ratul Mahajan , David Wetherall, Measuring ISP topologies with rocketfuel, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 7: Paul Barford , Azer Bestavros , John Byers , Mark Crovella, On the marginal utility of network topology measurements, Proceedings of the 1st ACM SIGCOMM Workshop on Internet Measurement, November 01-02, 2001, San Francisco, California, USA [doi>10.1145/505202.505204]
• 8: Ratul Mahajan , David Wetherall , Tom Anderson, Understanding BGP misconfiguration, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 9: "Visualizing Internet topology at a macroscopic scale," http://www.caida.org/analysis/topology/as_core_network/.
• 10: Hongsuda Tangmunarunkit, Ramesh Govindan, Scott Shenker, and Deborah Estrin, "The impact of policy on Internet paths," in Proc. IEEE INFOCOM, 2001.
• 11: Lisa Amini, Anees Shaikh, and Henning Schulzrinne, "Issues with inferring Internet topological attributes," in Proceedings of SPIE, July 2002, vol. 4865.
• 12: Timothy G. Griffin , Gordon Wilfong, On the correctness of IBGP configuration, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 13: "Nanog traceroute," ftp://ftp.login.com/pub/software/traceroute/.
• 14: "Prtraceroute," http://www.isi.edu/ra/RAToolSet/prtraceroute.html.
• 15: Paul Barford and Winfred Byrd, "Interdomain routing dynamics," Unpublished report, June 2001.
• 16: Xiaoliang Zhao , Dan Pei , Lan Wang , Dan Massey , Allison Mankin , S. Felix Wu , Lixia Zhang, An analysis of BGP multiple origin AS (MOAS) conflicts, Proceedings of the 1st ACM SIGCOMM Workshop on Internet Measurement, November 01-02, 2001, San Francisco, California, USA [doi>10.1145/505202.505207]
• 17: Young Hyum, Andre Broido, and k claffy, "Traceroute and BGP AS Path incongruities," 2003. http://www.caida.org/outreach/papers/2003/ASP/.
• 18: Hyunseok Chang, Sugih Jamin, and Walter Willinger, "Inferring AS-level internet topology from router-level path traces," in Proc. Workshop on Scalability and Traffic Control in IP Networks, SPIE ITCOM Conference, August 2001.
• 19: Lixin Gao, On inferring autonomous system relationships in the internet, IEEE/ACM Transactions on Networking (TON), v.9 n.6, p.733-745, December 2001 [doi>10.1109/90.974527]
• 20: Lakshminarayanan Subramanian, Sharad Agarwal, Jennifer Rexford, and Randy H. Katz, "Characterizing the Internet hierarchy from multiple vantage points," in Proc. IEEE INFOCOM, June 2002.
• 21: Craig Labovitz , Abha Ahuja , Abhijit Bose , Farnam Jahanian, Delayed Internet routing convergence, IEEE/ACM Transactions on Networking (TON), v.9 n.3, p.293-306, June 2001 [doi>10.1109/90.929852]
• 22: "University of Oregon Route Views Project," http://www.routeviews.org/.
• 23: "Ripe NCC," http://www.ripe.net/ripencc/pub-services/np/ris/.
• 24: "Singaren," http://noc.singaren.net.sg/netstats/routes/.
• 25: "Packet Clearing House," http://www.pch.net/resources/data/exchange-points/.
• 26: Paul Barford , Azer Bestavros , John Byers , Mark Crovella, On the marginal utility of network topology measurements, Proceedings of the 1st ACM SIGCOMM Workshop on Internet Measurement, November 01-02, 2001, San Francisco, California, USA [doi>10.1145/505202.505204]
• 27: E. Chen and J. Stewart, "A Framework for Inter-Domain Route Aggregation," Request for Comments 2519, February 1999.
• 28: J. Postel, "Internet Control Message Protocol," RFC 792, September 1981.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.3 Network Operations
          Subjects: Network monitoring

General Terms:
Management, Measurement

Keywords:
AS-level path, border gateway protocol, internet topology, network measurements