Scalable and accurate identification of AS-level forwarding paths
- 23 December 2004
- proceedings article
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 3, 1605-1615
- https://doi.org/10.1109/infcom.2004.1354573
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 pointsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Heuristics for Internet map discoveryPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Issues with inferring Internet topological attributesPublished by SPIE-Intl Soc Optical Eng ,2002
- Inferring AS-level Internet topology from router-level path tracesPublished by SPIE-Intl Soc Optical Eng ,2001
- On the marginal utility of network topology measurementsPublished by Association for Computing Machinery (ACM) ,2001
- An analysis of BGP multiple origin AS (MOAS) conflictsPublished by Association for Computing Machinery (ACM) ,2001