Observing the evolution of internet as topology

Ricardo V. Oliveira, Beichuan Zhang, Lixia Zhang

Research output: Chapter in Book/Report/Conference proceedingConference contribution

101 Scopus citations


Characterizing the evolution of Internet topology is important to our understanding of the Internet architecture and its interplay with technical, economic and social forces. A major challenge in obtaining empirical data on topology evolution is to identify real topology changes from the observed topology changes, since the latter can be due to either topology changes or transient routing dynamics. In this paper, we formulate the topology liveness problem and propose a solution based on the analysis of BGP data. We find that the impact of transient routing dynamics on topology observation decreases exponentially over time, and that the real topology dynamics consist of a constant-rate birth process and a constant-rate death process. Our model enables us to infer real topology changes from observation data with a given confidence level. We demonstrate the usefulness of the model by applying it to three applications: providing more accurate views of the topology, evaluating theoretical evolution models, and empirically characterizing the trends of topology evolution. We find that customer networks and provider networks have distinct evolution trends, which can provide an important input to the design of future Internet routing architecture.

Original languageEnglish (US)
Title of host publicationACM SIGCOMM 2007
Subtitle of host publicationConference on Computer Communications
Number of pages12
StatePublished - 2007
EventACM SIGCOMM 2007: Conference on Computer Communications - Kyoto, Japan
Duration: Aug 27 2007Aug 30 2007

Publication series

NameACM SIGCOMM 2007: Conference on Computer Communications


OtherACM SIGCOMM 2007: Conference on Computer Communications


  • Internet topology
  • Topology evolution

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Hardware and Architecture
  • Software


Dive into the research topics of 'Observing the evolution of internet as topology'. Together they form a unique fingerprint.

Cite this