Skip to Content
[CAIDA - Center for Applied Internet Data Analysis logo]
Center for Applied Internet Data Analysis
www.caida.org > research : topology
Topology Research

CAIDA has been measuring, analyzing, modeling, and visualizing Internet topology since 1998. We seek to characterize macroscopic Internet connectivity using both topological and geographical representations at multiple levels of aggregation granularity. This research goal is particularly challenging due to inconsistencies in different measurement tools and counterincentives for ISPs to support responding to tools that make inferences about connectivity. These constraints make it difficult and often impossible to validate scientific inferences about Internet topology against reality. And yet, an empirically grounded understanding of the Internet's shape, structure, and evolution has already had profound implications for network science theory and practice.

|   Ongoing Research    Datasets    Publications    Resources    Previous Research   |

Ongoing Research

Internet Mapping and Annotation

CAIDA is a worldwide renown leader in Internet topology mapping research. Nearly two decades of experience in Internet topology measurement, analysis, modeling, and visualization support our current state-of-the-art results in this area.

Using the secure and versatile Ark measurement infrastructure and scamper probing tool, CAIDA researchers conduct continuous traceroute-based Internet topology measurements in both IPv4 and IPv6 address space. We automatically abstract the collected traceroute measurement paths into AS adjacency matrices representing the Internet graph at the AS level. Computed daily, these matrices are available for public download.

We also produce periodic updates for router-level and AS-level Internet topologies integrated into the dual-layer router+AS-level topologies and richly annotated with AS business relationships, DNS names, and geographic attributes.

AS Ranking

Analysis of the the Internet Service Provider (ISP) hierarchy at an Autonomous System and organization granularity is critical to a deeper understanding of technical, economic and regulatory aspects of the Internet inter-domain routing system. As part of our research agenda to measure and analyze macroscopic Internet structure, we have developed a procedure to rank Autonomous Systems (AS Rank) by their location in the Internet hierarchy inferred using BGP data. The ranking function is rooted in inferred economics of AS relationships observable in the routing table, ranking each AS as a function of the number of IP prefixes advertised by this AS, its customer ASes, their customers ASes, and so on.

Comparative Analysis of Internet Topologies

Our Internet connectivity graphs are derived from active probing measurements and we use BGP data to map IP addresses to ASes. The resulting AS paths reflect packets that have actually traversed a forward path segment to a destination, rather than paths calculated and propagated across the loosely coupled BGP system. Thus, the traceroute data provides a view of Internet topology that differs from that derived from BGP tables. Note that the traceroute measurements sometimes have non-responding IP hops, which may lead to unobservable AS hops in AS paths.

To shed more light on the differences between Internet topologies derived at different granularities (IP, router, AS) from data sources of different kind (active probing, BGP, IRR), we conducted a systematic comparative analysis. We believe that it is the most comprehensive study thus far comparing and interpreting structural characteristics of topologies inferred from the best available data sources. We hope these results would facilitate more informed selection of topology datasets to support specific research or analysis needs.

AS Core Network Visualizations

Since 2000, CAIDA has produced (resources permitting) a yearly AS core map, a visualization of the Internet's AS topology at a macroscopic scale, using our continuous active topology measurements as input. Our most recent (2011) visualizations illustrate and compare topological richness in the IPv4 address space and the IPv6 address space as observed from our 54 IPv4 and 16 IPv6 vantage points (as of April 2011).

Datasets

Datasets sources used for topology modeling and topology graphs are available for download.

Publications

Resources

Hidden Metric Spaces

Theoretical Modeling of Complex Network Topologies

We are exploring the concept of Hidden Metric Spaces or "geometry-under-topology" model that helps to discover some geometric underpinnings of purely topological objects (graphs). Geometry makes the analysis of these objects tractable and intuitively transparent. Moreover, our research results indicate that the HMS model yields a most general explanation of intrinsic connection between complex network structure and functions.

The dK-series and dK Annotations

The ability to capture the fundamental characteristics that define the Internet topology stands as a key component toward generating realistic Internet models and understanding the driving forces of Internet evolution. CAIDA researchers developed a systematic method of analyzing and synthesizing topologies called the dK-series, which offers a dramatic improvement to the set of tools available to network topology and protocol researchers. We further refined the dK-series method by augmenting the network graphs with abstract annotations, called dK annotations, and by treating these annotations as an extended correlation profile of a network. The resulting topology modeling framework provides a generic mechanism to rescale annotated graphs for realistic simulations of networks of varying sizes.

Internet Evolution Models

To capture fundamental laws of network evolution, we studied the growth models of the Internet at the AS graph granularity level. In particular, we developed a new and analyzed an existing model simulating the Internet AS graph evolution. Our results are elegantly generic in nature; they potentially will shed light on evolution of not only the Internet but also of other types of self-evolving large-scale networks.

AS Classification and Taxonomy

In 2005-2007, in collaboration with Xenofontas Dimitropolous, we developed a scheme for taxonomizing ASes by type resulting in the most veracious Internet AS taxonomy to date. We analyze data from IRRs and RouteViews to annotate every AS with the following six attributes: 1) the organization description record, 2) the number of inferred customers, 3) the number of inferred providers, 4) the number of inferred peers, 5) the number of advertised IP prefixes, and 6) the equivalent number of /24 prefixes covering all the advertised IP space. Using this method, we successfully classify 95.3% of ASes with an expected accuracy of 78.1%. We release to the community the Autonomous System Taxonomy Repository as well as: 1) the AS taxonomy information and 2) the set of AS attributes we used to classify ASes.

  Last Modified: Tue Oct-13-2020 22:21:54 UTC
  Page URL: https://www.caida.org/research/topology/index.xml