Z. Morley Mao
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.
- G. Battista, M. Patrignani, and M. Pizzonia. Computing the Types of the Relationships Between Autonomous Systems. In Proc. IEEE INFOCOM, March 2003.Google Scholar
Cross Ref
- 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.Google ScholarCross Ref
- M. Coates, R. Castro, R. Nowak, M. Gadhiok, R. King, and Y. Tsang. Maximum Likelihood Network Topology Identification from Edge-based Unicast Measurements. In Proc. ACM SIGMETRICS, June 2002. Google ScholarDigital Library
- L. Gao. On Inferring Automonous System Relationships in the Internet. In IEEE/ACM Trans. Networking, December 2001. Google ScholarDigital Library
- R. Govindan and H. Tangmunarunkit. Heuristics for Internet Map Discovery. In Proc. ACM SIGCOMM, March 2000.Google ScholarCross Ref
- G. Huston. BGP table statistics. http://bgp.potaroo.net.Google Scholar
- V. Jacobson. Traceroute. ftp://ftp.ee.lbl.gov/traceroute.tar.gz.Google Scholar
- R. Mahajan, N. Spring, D. Wetherall, and T. Anderson. Inferring Link Weights using End-to-End Measurements. In Proc. Internet Measurement Workshop, November 2002. Google ScholarDigital Library
- 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.Google Scholar
- Z. M. Mao, J. Rexford, J. Wang, and R. Katz. Towards an Accurate AS-Level Traceroute Tool. In Proc. ACM SIGCOMM, August 2003. Google ScholarDigital Library
- 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.Google Scholar
- 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.Google Scholar
- V. Paxson. End-to-End Routing Behavior in the Internet. IEEE/ACM Trans. Networking, pages 601--615, October 1997. Google ScholarDigital Library
- V. Paxson. Measurements and Analysis of End-to-End Internet Dynamics. PhD thesis, U.C. Berkeley, 1997. Google ScholarDigital Library
- PlanetLab. http://www.planet-lab.org.Google Scholar
- J. Rexford, J. Wang, Z. Xiao, and Y. Zhang. BGP Routing Stability of Popular Destinations. In Proc. Internet Measurement Workshop, November 2002. Google ScholarDigital Library
- B. Selman, H. Kautz, and B. Cohen. Local Search Strategies for Satisfiability Testing. In Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge, 1993.Google Scholar
- N. Spring, R. Majajan, and D. Wetherall. Measuring ISP Topologies with Rocketfuel. In Proc. ACM SIGCOMM, August 2002. Google ScholarDigital Library
- L. Subramanian, S. Agarwal, J. Rexford, and R. Katz. Characterizing the Internet hierarchy from multiple vantage points. In Proc. IEEE INFOCOM, June 2002.Google ScholarCross Ref
- Traceroute.org. http://www.traceroute.org/.Google Scholar
- B. Zhang, R. Liu, D. Massey, and L. Zhang. Collecting the Internet AS-level Topology. In ACM SIGCOMM Computer Communication Review (CCR), special issue on Internet Vital Statistics, January 2005. Google ScholarDigital Library
Index Terms
- On AS-level path inference
Recommendations
Towards an accurate AS-level traceroute tool
SIGCOMM '03: Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communicationsTraceroute 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 ...
On AS-level path inference
Performance evaluation reviewThe 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 ...
Observing BGP route poisoning in the wild
SIGCOMM '20: Proceedings of the SIGCOMM '20 Poster and Demo SessionsOn the Internet, Border Gateway Protocol (BGP) is the standard to construct inter-domain routes among autonomous systems (ASes). Data traffic follows the inverse direction of BGP route propagation. For the outbound traffic, an AS can make its own ...
Comments