The contents of this legacy page are no longer maintained nor supported, and are made available only for historical purposes.

Bibliography Details

Z. Mao, D. Johnson, J. Rexford, J. Wang, and R. Katz, "Scalable and Accurate Identification of AS-level Forwarding Paths", in IEEE INFOCOM, March 2004.

Scalable and Accurate Identification of AS-level Forwarding Paths
Authors:	Z. Mao D. Johnson J. Rexford J. Wang R. Katz
Published:	IEEE INFOCOM, 2004
URL:	http://www.eecs.umich.edu/~zmao/Papers/infocom04.pdf http://www.ieee-infocom.org/2004/Papers/34_2.PDF
Entry Date:	2004-06-30
Abstract:	Traceroute is used heavily by network operators and researchers to identify the IP forwarding path from a source to a destination. In practice, knowing the Autonomous System (AS) associated with each hop in the path is also quite valuable. In previous work we showed that the IP-to-AS mapping extracted from BGP routing tables is not sufficient for determining the AS- level forwarding paths [1]. By comparing BGP and traceroute AS paths from multiple vantage points, [1] proposed heuristics that identify the root causes of the mismatches and fix the inaccurate IP-to-AS mappings. These heuristics, though effective, are labor- intensive and mostly ad hoc. This paper proposes a systematic way to construct accurate IP-to-AS mappings using dynamic programming and iterative improvement. Our algorithm reduces the initial mismatch ratio of 15% between BGP and traceroute AS paths to 5% while changing only 2.9% of the assignments in the initial IP-to-AS mappings. This is in contrast to the results of [1], where 10% of the assignments were modified and the mismatch ratio was only reduced to 9%. We show that our algorithm is robust and can yield near-optimal results even when the initial mapping is corrupted or when the number of probing sources or destinations is reduced. Our work is a key step towards building a scalable and accurate AS-level traceroute tool.
Datasets:	whois data was obtained from Internet Routing Registries (IRRs). Traceroute data sets were collected from 8 locations, done to 200,000 prefixes, 2 addresses in each prefix, between May and June, 2003. BGP routing table data was obtained around May 29, 2003 from RouteViews (from 23 ASes), RIPE-NCC (from 75 ASes), SingAREN
Results:	Mismatch ratio improved from 15% to 5% by changing only 2.9% of IP-to-AS mappings Results are almost as good when using only one probe for each unique BGP path at a given vantage point, even if that path corresponds to multiple prefixes (87% reduction in traceroute probes) or when using only four out of the eight vantage points.
References:	Continuation of work: Z. Morley Mao, Jennifer Rexford, Jia Wang, and Randy Katz, "Towards an Accurate AS-level Traceroute Tool," in Proc. ACM SIGCOMM, September, 2003.