The (in)completeness of the observed internet as-level structure

Ricardo Oliveira, Dan Pei, Walter Willinger, Beichuan Zhang, Lixia Zhang

Research output: Contribution to journalArticlepeer-review

153 Scopus citations


Despite significant efforts to obtain an accurate picture of the Internet's connectivity structure at the level of individual autonomous systems (ASes), much has remained unknown in terms of the quality of the inferred AS maps that have been widely used by the research community. In this paper, we assess the quality of the inferred Internet maps through case studies of a sample set of ASes. These case studies allow us to establish the ground truth of connectivity between this set of ASes and their directly conncted neighbors. A direct comparison between the ground truth and inferred topology maps yield insights into questions such as which parts of the actual topology are adequately captured by the inferred maps, which parts are missing and why, and what is the percentage of missing links in these parts. This information is critical in assessing, for each class of real-world networking problems, whether the use of currently inferred AS maps or proposed AS topology models is, or is not, appropriate. More importantly, our newly gained insights also point to new directions towards building realistic and economically viable Internet topology maps.

Original languageEnglish (US)
Article number5200324
Pages (from-to)109-122
Number of pages14
JournalIEEE/ACM Transactions on Networking
Issue number1
StatePublished - Feb 2010


  • Border Gateway Protocol (BGP)
  • Interdomain routing
  • Internet topology

ASJC Scopus subject areas

  • Software
  • Computer Science Applications
  • Computer Networks and Communications
  • Electrical and Electronic Engineering


Dive into the research topics of 'The (in)completeness of the observed internet as-level structure'. Together they form a unique fingerprint.

Cite this