Internet Topology: connectivity of IP graphs

Andre Broido and kc claffy
Cooperative Association for Internet Data Analysis (CAIDA)
San Diego Supercomputer Center
University of California, San Diego

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.