Internet Topology: connectivity of IP graphs

Broido, Andre
Claffy, kc

Abstract

In this paper we introduce a framework for analyzing local properties of Internet connectivity. We compare BGP and probed topology data, finding that currently probed topology data yields much denser coverage of AS-level connectivity. We describe data acquisition and construction of several IP-level graphs derived from a collection of 220M skitter traceroutes. We find that a graph consisting of IP nodes and links contains 90.5% of its 629K nodes in the acyclic subgraph. In particular, 55% of the IP nodes are in trees. Full bidirectional connectivity is observed for a giant component containing 8.3%of IP nodes. We analyze the same structures (trees, acyclic part, core, giant component) for other combinatorial models of Internet (IP-level) topology, including arc graphs and place-holder graphs. We also show that Weibull distrbution N{X >x} = a exp(-(x/b)c approximates outdegree distribution with 10-15% relative accuracy in the region of generic object sizes, spanning two to three orders of magnitude up to the point where sizes become unique. The extended version of this paper includes dynamic and functorial properties of Internet topology, including properties of and diffusion on aggregated graphs, invariance of a reachability function's shape regardless of node choice or aggregation level, analysis of topological resilience under wide range of scenarios. We also demonstrate that the Weibull distribution provides a good fit to a variety of local object sizes.

Keywords

topology
tree
AS

Notes

Shows that 55% of IP nodes are in trees

Related Papers

Bibtex

 @inproceedings{broido.claffy_topo01,
 author      ="A. Broido and K. Claffy",
 title       ="Internet Topology: Connectivity of {IP} graphs",
 booktitle   ="Proceedings of SPIE International Symposium on Convergence of IT and Communication",
 year        ="2001",
 month       ="Aug.",
 documentURL ="http://www.caida.org/outreach/papers/2001/OSD/topologylocal.ps.gz"
}

Back to Intro By Author By Importance By Keyword By Title By Reference