CAIDA : 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. For example, longitudinal measurements reveal incongruities between the Internet's routing system and the underlying topology, which is evolving away from what the routing system needs to route efficiently. This discovery has radical implications for the future of, Internet routing, another important area of CAIDA's research.

| Ongoing Research Datasets Publications Resources Previous Research |

Ongoing Research
Datasets
Publications
Resources
Previous Research

Ongoing Research

Hidden Metric Spaces

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.

AS Ranking Tables

Building on all of the analysis modules developed above, we have developed a procedure to rank Autonomous Systems (AS Rank) by their location in the Internet hierarchy inferred using either traceroute or 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. AS links annotated with AS relationships are available for download at http://as-rank.caida.org/data/.

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 implements 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 refine 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 study 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.

Internet Mapping and Annotation

Our most recently funded project in topology mapping is Cybersecurity: Leveraging the Science and Technology of Internet Mapping for Homeland Security funded by DHS S&T. In this project, we are applying a decade of experience in Internet topology measurement, analysis, modeling, and visualization capabilities to DHS' immediate cybersecurity needs to understand and protect essential U.S. information infrastructure.

The ultimate deliverables are 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, geographic, latency, etc., attributes. To achieve this main task, the project will also deliver a new Internet topology data acquisition infrastructure and Internet topology data processing, analysis, annotation, and generations software.

Datasets

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

The IPv4 Routed /24 Topology Dataset
Raw Skitter Topology Traces
Internet AS-level topology graphs obtained from skitter measurements, BGP tables, BGP updates, and the RIPE WHOIS database
AS Relationships
AS Taxonomy
AS Links (AS Adjacencies)
Router Adjacencies
Internet Topology Data Kit (ITDK)
Internet Topology Data Kit (ITDK)

Publications

Resources

Previous Research

Analysis of the the Internet Service Provider (ISP) hierarchy at an Autonomous System granularity is critical to a deeper understanding of technical, economic and policy needs of the Internet inter-domain routing system. For the last ten years CAIDA has undertaken several efforts in macroscopic topology semantic analysis and visualization, including making strategic data sets available on a periodic (weekly) basis.

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 (2009) visualizations illustrate and compare topological richness in the IPv4 address space and the IPv6 address space as observed by our 33 IPv4 and 6 IPv6 vantage points (as of January 2009).

AS Classification and Taxonomy

In 2005-2007, in collaboration with Xenofontas Dimitropolous, we devloped 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.

AS Adjacencies

As a part of the Macroscopic Topology Project CAIDA developed the infrastructure for continual traceroute-based Internet topology measurements. We have upgraded and expanded our measurement infrastructure as part of our Internet mapping project for DHS S&T. We automatically abstract the resulting traceroute measurements into AS adjacency matrices representing the Internet graph at the AS level. CAIDA makes available (how often) for public download the adjacency matrix of the Internet AS-level graph computed daily from observed measurements.

Because skitter and scamper (the latter we use on Ark) are traceroute-based tool, the resulting topology data reflects 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.Additionally, we use BGP data to map IP addresses to ASes, so BGP data is fundamental in both cases. Note that the traceroute measurements sometimes have non-responding IP hops, which may lead to unobservable AS hops in AS paths.

AS Relationships

Analysis of the the Internet Service Provider (ISP) hierarchy 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. Our ranking relies upon AS relationship information that we discover using our new inference algorithms. Our approach is rooted in economic AS relationships, 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.