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.

Skitter data from all available monitors in Spring 2001

Iffinder probing to identify interfaces on the routers. Out of 638 K IP addresses probed, an identification with at least one other IP was found for 76 K nodes, which make up about 30 K connected components. Most of these components consist of only two nodes. While many of the components can be interpreted as groups of addresses on the same router, some of them contain long chains of redirections and even loops, which makes unlikely their interpretation as routers.

A.Broder e.a., Graph structure in the Web. Computer Networks 33, 2000.