CAIDA : research : topology

| Ongoing Research Previous Completed Research Datasets Publications Resources |

Ongoing Research
Previous Completed Research
Datasets
Publications
Resources

Routing information through networks is a universal phenomenon in both natural and man-made complex systems. When each node has a full view of the global network topology, finding efficient communication routes is a well-understood process although it can be computationally intensive. A persistent mystery is how so many complex networks observed in nature exhibit communication efficiency without nodes having a full view of the network. In search of an explanation, we explore the concept of hidden metric spaces - an underlying geometric frame containing all nodes of an observable network. Distances between nodes in this space guide routing decisions, affecting the network topology, and define its routing conductivity, or navigability.

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.

Self-Similarity of Complex Networks

We demonstrate that the self-similarity of some scale-free networks with respect to a simple degree-thresholding renormalization scheme finds a natural interpretation in the assumption that network nodes exist in hidden metric spaces. Clustering, i.e., cycles of length three, plays a crucial role in this framework as a topological reflection of the triangle inequality in the hidden geometry. We prove that a class of hidden variable models with underlying metric spaces are able to accurately reproduce the self-similarity properties that we measured in the real networks. Our findings indicate that hidden geometries underlying these real networks are a plausible explanation for their observed topologies and, in particular, for their self-similarity with respect to the degree-based renormalization.

Evolution

We developed an analytically tractable model of Internet evolution at the level of Autonomous Systems (ASes). We call our model the Multiclass Attraction (MA) model. All of its parameters are measurable based on available Internet topology data. Given the estimated values of these parameters, our analytic results accurately predict a definitive set of statistics characterizing the AS topology structure. Since these statistics are not parts of model formulation, the MA model thus closes the measure-model-validate-predict loop. We describe the evolution of AS graphs, including the emergence of ASes, peering links formation, bankruptcies and multihoming. Our model also explains how certain circumstances naturally lead to consolidation of providers over time, unless some exogenous force interferes. We validate our model using recent results in Internet topology data analysis.

AS Core Network

When the Internet was in its infancy, monitoring traffic was relatively simple. However, after experiencing phenomenal growth in the 1990's, tracking connectivity has become a daunting task. Recently, CAIDA researchers work on Visualizing Internet Topology at a Macroscopic Scale, stripping away lesser connected autonomous systems (or `ASes') in order to find out how Internet connectivity is distributed among ISPs.

Workshops

Internet topology analysis has recently experienced a surge of activity in computer science, physics, mathematics, and statistics communities. Notably, researchers often approach essentially the same problems from different angles, but their findings are not always complementary and sometimes even conflict, leading to inconsistent conclusions. CAIDA believes interdisciplinary workshops will help to move this area of research forward.

To help bring the most active researchers from the involved communities together, CAIDA hosted the ISMA - Workshop on the Internet Topology (WIT). The main objectives of the workshop were to promote synergy, enable interdisciplinary cross-fertilization, and reveal common ground in different approaches. At a high-level, the workshop focused on recent advances, sought to resolve arguments, and identify open problems that require further research. Workshops in routing and topology, as well as in other topics, are available on the CAIDA Workshops web page.

Previous Completed Research

AS Classification and Taxonomy

CAIDA has developed an AS classification scheme 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 has developed the infrastructure for continual traceroute-based Internet topology measurements. We automatically map these measurements into AS adjacency matrices representing the Internet graph at the AS level. CAIDA makes available for public download the adjacency matrix of the Internet AS-level graph computed daily from observed measurements.

Because skitter is a traceroute-based tool, skitter data reflects packets that have actually traversed a forward path to a destination, rather than paths calculated and propagated across the loosely coupled BGP system. Thus, skitter provides a view of Internet topology that differs from those derived from BGP tables, e.g. RouteViews.

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 ASs, and so on.

AS links annotated with AS relationships are available for download at http://as-rank.caida.org/data/.

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)