(CiscoURB 2002) Connectivity Ranking of Autonomous Systems

1  Proposal Title


2  Primary Investigators

k claffy, Ph.D., PI with CAIDA researcher Brad Huffaker, M.S.

3  Description of Research and Goals

After the phenomenal Internet growth during the 1990s, tracking macroscopic Internet connectivity is a daunting task. CAIDA's Autonomous System (AS) core graph [4] and table [1] provide a ranking of AS outdegree based on massive topology data as measured by CAIDA's macroscopic IP topology monitoring project and observed by RouteViews BGP table snapshots [2,3]. The coverage of these topology probes is unprecedented, dramatically higher than any previous work in this area, and the data yield significant insight into the relative richness of IP connectivity of different ASes.

To extend and improve our methodology for deriving and depicting this connectivity ranking, we would like to extend the project in two ways:

  1. Automate the rankings of AS connectivity as inferred from large scale active topology probes
  2. Identify and depict exchange points and their influence on AS inter-connectivity and these rankings

3.1  Automate AS connectivity rankings

We will provide weekly updates to this table as specifically requested by Cisco (Barry Greene) for support in their critical incident notification process.

We are also experimenting with techniques for animating the AS core graph; a preliminary prototype [4] shows promise to meet this challenge. This first animation displays eighteen months of AS core data from July 2000 to January 2002. This particular data set indicates that the ranking of major ISPs remained essentially unchanged over this period, but infrastructural shifts over the next decade are likely to be exposed using this technique.

3.2  Extend methodology to incorporate knowledge of exchange points

We propose to identify and depict exchange and quantify their influence on AS connectivity rankings. Several colleagues in the operational community have expressed interest in having a version of the AS core graph that depicts exchange points in addition to ASes. Finding an appropriate visualization will require experimenting with several different presentation metaphors.

We will rely on CAIDA macroscopic topology data [5], BGP tables from RouteViews [2], and PCH's database of exchange point prefixes [6] to derive a map of ASes and exchange points that integrates topological and geographic information. A knowledge base of this kind will allow pursuit of answers to several infrastructurally relevant questions, e.g.:

  1. How much connectivity can be observed at exchange points?

  2. What fraction of the overall connectivity of the core occurs at exchange points rather than at bi-lateral private peering points?
  3. How can we effectively visualize the connectivity at as well as between exchange points?

3.3  Impact

Both tasks are aimed at improving our understanding of macroscopic view of Internet connectivity among ASes, and the role that different exchange points play in sustaining this core connectivity. The results will allow for improved incident notification process in the case of learned vulnerabilities (e.g., viruses, protocol weaknesses), as well as increased awareness of potential vulnerabilties deriving from excessive concentration of connectivity provided by a single or few exchange points.

4  Timeframes for Funding and Research Completion

Funding ($100,000) to begin 1 July 2002. (or whenever possible)

Research Milestones

4.1  Any Required/expected Research Cooperation with Cisco

Researchers are available to meet with Cisco staff to discuss methodologies and the implications of analysis results, in particular with respect to Cisco's incident notification process or router instrumentation that might improve the quality of data gathered.


CAIDA, ``Connectivity ranking of Autonomous Systems (using large topology sample) as viewed by CAIDA's macroscopic topology mapping project,'' Apr 2002. https://www.caida.org/research/topology/rank_as/.

D. Meyer, ``RouteViews,'' 2002. http://www.routeviews.org.

A. Broido and k claffy, ``Analysis of RouteViews BGP data: policy atoms,'' in Network Resource Data Management Workshop, Santa Barbara, CA, May 2001. https://www.caida.org/publications/papers/2001/NdrmBgp/.

CAIDA, ``Visualizing Internet Topology at a Macroscopic Scale,'' Apr 2002. https://www.caida.org/research/topology/as_core_network/index.xml\#animation.

B. Huffaker, D. J. Plummer, D. Moore, and k claffy, ``Topology discovery by active probing,'' in Symposium on Applications and the Internet (SAINT), Jan 2002. https://www.caida.org/publications/papers/2002/SkitterOverview/.

B. Woodcock, ``Exchange point database,'' 2002. http://www.pch.net/documents/data/exchange-points/ep-in-addrs.txt.

File translated from TEX by TTH, version 2.92.
On 13 Sep 2002, 12:02.