On AS-level path inference

ABSTRACT

The ability to discover the AS-level path between two end-points is valuable for network diagnosis, performance optimization, and reliability enhancement. Virtually all existing techniques and tools for path discovery require direct access to the source. However, the uncooperative nature of the Internet makes it difficult to get direct access to any remote end-point. Path inference becomes challenging when we have no access to the source or the destination. Moveover even when we have access to the source and know the forward path, it is nontrivial to infer the reverse path, since the Internet routing is often asymmetric.In this paper, we explore the feasibility of AS-level path inference without direct access to either end-points. We describe RouteScope-a tool for inferring AS-level paths by finding the shortest policy paths in an AS graph obtained from BGP tables collected from multiple vantage points. We identify two main factors that affect the path inference accuracy: the accuracy of AS relationship inference and the ability to determine the first AS hop. To address the issues, we propose two novel techniques: a new AS relation-ship inference algorithm, and a novel scheme to infer the first AS hop by exploiting the TTL information in IP packets. We evaluate the effectiveness of RouteScope using both BGP tables and the AS paths collected from public BGP gateways. Our results show that it achieves 70% - 88% accuracy in path inference.

REFERENCES

• 1: G. Battista, M. Patrignani, and M. Pizzonia. Computing the Types of the Relationships Between Autonomous Systems. In Proc. IEEE INFOCOM, March 2003.
• 2: O. Bonaventure, P. Trimintzios, G. Pavlou, B. Quoitin, A. Azcorra, M. Bagnulo, P. Flegkas, A. Garcia-Martinez, P. Georgatsos, L. Georgiadis, C. Jacquenet, L. Swinnen, S. Tandel, and S. Uhlig. Internet Traffic Engineering. In Quality of Future Internet Services, 2003.
• 3: Mark Coates , Rui Castro , Robert Nowak , Manik Gadhiok , Ryan King , Yolanda Tsang, Maximum likelihood network topology identification from edge-based unicast measurements, Proceedings of the 2002 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 15-19, 2002, Marina Del Rey, California
• 4: 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]
• 5: R. Govindan and H. Tangmunarunkit. Heuristics for Internet Map Discovery. In Proc. ACM SIGCOMM, March 2000.
• 6: G. Huston. BGP table statistics. http://bgp.potaroo.net.
• 7: V. Jacobson. Traceroute. ftp://ftp.ee.lbl.gov/traceroute.tar.gz.
• 8: Ratul Mahajan , Neil Spring , David Wetherall , Tom Anderson, Inferring link weights using end-to-end measurements, Proceedings of the 2nd ACM SIGCOMM Workshop on Internet measurment, November 06-08, 2002, Marseille, France [doi>10.1145/637201.637237]
• 9: Z. M. Mao, D. Johnson, J. Rexford, J. Wang, and R. Katz. Scalable and Accurate Identification of AS-Level Forwarding Paths. In Proc. IEEE INFOCOM, March 2004.
• 10: Zhuoqing Morley Mao , Jennifer Rexford , Jia Wang , Randy H. Katz, Towards an accurate AS-level traceroute tool, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany [doi>10.1145/863955.863996]
• 11: P. R. McManus. A Passive System for Server Selection within Mirrored Resource Environments Using AS Path Length Heuristics. Apr. 1999. http://www.ducksong.com:81/patrick/proximate.pdf.
• 12: T. Ogino, M. Kosaka, Y. Hariyama, K. Matsuda, and K. Sudo. Study of an Efficient Server Selection Method for Widely Distributed Web Server Networks. In The 10th Annual Internet Society Conference (INET), July 2000. http://www.isoc.org/inet2000/cdproceedings/1g/1g_1.htm.
• 13: 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]
• 14: Vern Edward Paxson, Measurements and analysis of end-to-end Internet dynamics, University of California at Berkeley, Berkeley, CA, 1998
• 15: PlanetLab. http://www.planet-lab.org.
• 16: Jennifer Rexford , Jia Wang , Zhen Xiao , Yin Zhang, BGP routing stability of popular destinations, Proceedings of the 2nd ACM SIGCOMM Workshop on Internet measurment, November 06-08, 2002, Marseille, France [doi>10.1145/637201.637232]
• 17: B. Selman, H. Kautz, and B. Cohen. Local Search Strategies for Satisfiability Testing. In Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge, 1993.
• 18: 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
• 19: L. Subramanian, S. Agarwal, J. Rexford, and R. Katz. Characterizing the Internet hierarchy from multiple vantage points. In Proc. IEEE INFOCOM, June 2002.
• 20: Traceroute.org. http://www.traceroute.org/.
• 21: Beichuan Zhang , Raymond Liu , Daniel Massey , Lixia Zhang, Collecting the internet AS-level topology, ACM SIGCOMM Computer Communication Review, v.35 n.1, January 2005 [doi>10.1145/1052812.1052825]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols
          Subjects: Routing protocols

General Terms:
Algorithms, Experimentation, Measurement

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