Scalable and accurate identification of AS-level forwarding paths
Authors:
- Z. Morley MaoZMZ. Morley Mao
- D. JohnsonDJD. Johnson
- J. RexfordJRJ. Rexford
- Jia WangJWJia Wang
- R. KatzRKR. Katz
- 23 December 2004
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 3, 1605-1615
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 toolKeywords
This publication has 7 references indexed in Scilit:
- Measuring ISP Topologies With RocketfuelIEEE/ACM Transactions on Networking, 2004
- Characterizing the Internet hierarchy from multiple vantage points2003
- Heuristics for Internet map discovery2002
- Issues with inferring Internet topological attributes2002
- Inferring AS-level Internet topology from router-level path traces2001
- On the marginal utility of network topology measurements2001
- An analysis of BGP multiple origin AS (MOAS) conflicts2001