The International Computer Science Institute
is pleased to present a talk:

"Internet Topology"

kc claffy and Andre Broido CAIDA; UC, San Diego Supercomputer Center

kc		ipn.caida.org

Wednesday, March 14, 2001 ICSI, Rm 607 2-3 pm

We describe fundamentals of analyzing Internet graphs at various layers, and problems in gathering and analyzing Internet routing and topology data in graph form. Using skitter topology data and Oregon Route Views BGP table data, we present IP graphs, their connected components, and the combinatorial core of Internet topology. We discuss techniques for assessing which portions of the global Internet are characterized by the highest degree of `connectivity', both in central/backbone and access/delivery components of the topology. We describe several combinatorial approaches, including:

1. extracting the core component of the Internet whose bidirectional connectivity most readily captured by measurement, even in observation conditions which are far from ideal

2. ordering `node centrality' by the lengths of shortest paths originating from them;

3. comparing access points by the size of the "access cone" - the number of nodes/prefixes/ASes and/or the size of address space that depend wholly or in part on this access point for their global connectivity.

Our analysis introduces several new concepts for graph-theoretic routing and topology analysis:

1. the "dual AS graph", that captures more policy constraints in the infrastructure than conventional (dimension 1) graph. In particular, a graph of AS adjacencies is a poor descriptor for peerings further than one hop due to the influence of policy.

2. the BGP atom, a unit of connectivity analysis that correspond to an equivalence class of IPv4 network prefixes that share the same set of AS paths.

3. connected subspaces of a prefix, a unit of IP level connectivity that allows us to avoid certain biases arising in straightforward compression of IP graph to prefix representation.

We will describe how we determine the top 50 `most connected' nodes, at various levels of Internet node granularity. We cover distributions of AS path and prefix lengths, use of prepending, and outdegree vs indegree of ASes. Time permitting, some newer results regarding diffusion on Internet graphs and nodes' geodesic load will be discussed.

web		icsi.berkeley.edu