The Lord of the Links

(This page maintained by Yihua He)

 
[Introduction]

The lack of an accurate representation of the Internet topology at the Autonomous System (AS) level is a limiting factor in the design, simulation, and modeling efforts in inter-domain routing protocols. Here, we try to identify AS (Autonomous System) links that are missing from the commonly-used Internet topology snapshots. To provide a large-scale comprehensive synthesis, we cross-validate BGP routing tables, IRR (Internet Routing Registry) and traceroute data, while extract significant new information from IXPs (Internet Exchange Points). In fact most of the missing peer-to-peer AS links are found to be IXP links. We also construct a directed map of AS topology and quantify the effects from the new-found AS edges.

[Publications and Presentations]

  • Y. He, G. Siganos, M. Faloutsos, S. V. Krishnamurthy. "A systematic framework for unearthing the missing links: Measurements and Impact", USENIX/SIGCOMM NSDI 2007, Cambridge, MA, USA, Apr 2007. [PDF] [PPT]

  • Y. He, "Putting Links Together: Measurement and Impacts", CAIDA WIT Workshop, La Jolla, CA May 2006. [PPT]

  • Y. He. "The Lord of the Links: Identifying missing AS links and their implications", CAIDA WIDE workshop, Marina del Rey, CA, Mar 2006 [PPT]

  • Y. He, G. Siganos. "The Missing AS Links and Their Impact On the Internet Topology Model", Extended Abstract, IEEE ICNP, Boston, MA, USA, Nov 2005. [Abstract] [Poster]

[Data]

AS topology with AS relationships as of May 2005.
AS topology without AS relationships as of May 2005.

[Q&A of the Moment]

Quite a few people sent us their questions, and here is a complete list of the most frequent ones and our answers. We continue to update it when we receive questions. If you have a question and can not find the answer there, feel free to drop an email (yhe AT cs.ucr.edu).

[Personal & Lab]

 

[Comments]

Please send your comments to yhe AT cs.ucr.edu. We will try to incorporate your question and our answer into the FAQ.