Scalable and accurate identification of AS-level forwarding paths

Z. Morley Mao, David Johnson, Jennifer L. Rexford, Jia Wang, Randy Katz

Research output: Contribution to journalConference articlepeer-review

75 Scopus citations


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.

Original languageEnglish (US)
Pages (from-to)1605-1615
Number of pages11
JournalProceedings - IEEE INFOCOM
StatePublished - 2004
EventIEEE INFOCOM 2004 - Conference on Computer Communications - Twenty-Third Annual Joint Conference of the IEEE Computer and Communications Societies - Hongkong, China
Duration: Mar 7 2004Mar 11 2004

All Science Journal Classification (ASJC) codes

  • General Computer Science
  • Electrical and Electronic Engineering


Dive into the research topics of 'Scalable and accurate identification of AS-level forwarding paths'. Together they form a unique fingerprint.

Cite this