Abstract
Although traceroute has the potential to discover AS links that are invisible to existing BGP monitors, it is well known that the common approach for mapping router IP address to AS number (IP2AS) based on the longest prefix matching is highly error-prone. In this paper we conduct a systematic investigation into the potential errors of the IP2AS mapping for AS topology inference. In comparing traceroute-derived AS paths and BGP AS paths, we take a novel approach of identifying mismatch fragments between each path pair. We then identify the origin and cause of each mismatch with a systematic set of tests based on publicly available data sets. Our results show that about 60% of mismatches are due to IP address sharing between peering BGP routers in neighboring ASes, and only about 14% of the mismatches are caused by the presence of IXPs, siblings, or prefixes with multiple origin ASes. This result helps clarify an argument that comes from previous work regarding the major cause of errors in converting traceroute paths to AS paths. Our results also show that between 16% and 47% of AS adjacencies in two public repositories for traceroute-derived topology are false.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Archipelago Measurement Infrastructure, http://www.caida.org/projects/ark/
Internet Routing Registry, http://www.irr.net/
RIPE routing information service project, http://www.ripe.net/
RouteViews routing table archive, http://www.routeviews.org/
UCLA IRL Internet topology collection, http://irl.cs.ucla.edu/topology/
Augustin, B., Cuvellier, X., Orgogozo, B., Viger, F., Friedman, T., Latapy, M., Magnien, C., Teixeira, R.: Avoiding traceroute anomalies with paris traceroute. In: IMC 2006 (2006)
Chang, H., Jamin, S., Willinger, W.: Inferring AS-level Internet topology from router-level path traces. In: SPIE ITCom (2001)
Hunt, J.W., Mcllroy, M.D.: An algorithm for differential file comparison. Tech. rep., Bell Laboratories (1976)
Hyun, Y., Broido, A., Claffy, K.C.: On third-party addresses in traceroute paths. In: Proc. of Passive and Active Measurement Workshop, PAM (2003)
Hyun, Y., Broido, A., Claffy, K.C.: Traceroute and BGP AS path incongruities. Tech. rep., CAIDA (2003)
Madhyastha, H., Isdal, T., Piatek, M., Dixon, C., Anderson, T., Krishnamurthy, A., Venkataramani, A.: iPlane: an information plane for distributed services. In: Proc. of OSDI (2006)
Mao, Z.M., Johnson, D., Rexford, J., Wang, J., Katz, R.H.: Scalable and accurate identification of AS-level forwarding paths. In: INFOCOM 2004 (2004)
Mao, Z.M., Rexford, J., Wang, J., Katz, R.H.: Towards an accurate AS-level traceroute tool. In: Proc. of ACM SIGCOMM (2003)
Oliveira, R., Pei, D., Willinger, W., Zhang, B., Zhang, L.: In search of the elusive ground truth: The Internet’s AS-level connectivity structure. In: Proc. ACM SIGMETRICS (2008)
Oliveira, R., Zhang, B., Zhang, L.: Observing the evolution of Internet AS topology. In: ACM SIGCOMM (2007)
Shavitt, Y., Shir, E.: DIMES: Let the Internet measure itself. ACM SIGCOMM Computer Comm. Review, CCR (2005)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Zhang, Y., Oliveira, R., Zhang, H., Zhang, L. (2010). Quantifying the Pitfalls of Traceroute in AS Connectivity Inference. In: Krishnamurthy, A., Plattner, B. (eds) Passive and Active Measurement. PAM 2010. Lecture Notes in Computer Science, vol 6032. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-12334-4_10
Download citation
DOI: https://doi.org/10.1007/978-3-642-12334-4_10
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-12333-7
Online ISBN: 978-3-642-12334-4
eBook Packages: Computer ScienceComputer Science (R0)