On the Size Distribution of Autonomous Systems

Marwan Fayed, P. L. Krapivsky, John W. Byers, Mark Crovella, David Finkel, S. Redner2003 · DOI

TL;DR

This paper models the evolution of Autonomous System (AS) sizes on the internet, proposing that a combination of AS birth, growth, and mergers explains the observed high variability. They develop analytical models and validate them against real-world data, finding that while growth alone provides a good approximation, incorporating mergers improves accuracy, especially for smaller ASes.

What Problem Does This Paper Address?

The internet's structure is often represented as a graph where nodes are routers and end systems, and edges are network links. A crucial layer of abstraction is the Autonomous System (AS), a collection of IP networks and routers under a single administrative domain. Accurately modeling the size distribution of these ASes (i.e., how many hosts or IP addresses they control) is vital for understanding network topology, simulating traffic flow, and analyzing interdomain routing policies. While previous work has looked at AS degree (number of connections), the evolution of AS sizes and the underlying processes driving their variability have remained less understood. This paper aims to fill that gap by proposing and testing models for AS size evolution.

Methods

The authors propose two main models:

  1. Growth-Only Model: This is the simplest model, focusing on AS births and growth. It's described by a system of linear differential equations for the total number of ASes ($N$) and the total number of hosts ($M$). They derive analytical solutions for the AS size distribution, showing it can exhibit a power-law tail.
  2. Growth and Merger Model: This model extends the first by incorporating AS mergers. Mergers are treated as a coalescence process, where two ASes combine. They introduce a "merger kernel" ($K_{ij}$) to describe the rate at which ASes of size $i$ and $j$ merge. They analyze a simplified case with a "constant kernel" ($K_{ij}=1$) and derive the resulting size distribution, which also exhibits a power-law tail, with the exponent being independent of the specific merger details.

They use techniques from statistical mechanics and analyze differential equations to derive the asymptotic behaviors of these models.

Datasets

  • Internet Registries (ARIN, RIPE, APNIC): Used to track AS number allocations over time, providing data for estimating the AS birth rate ($q$).
  • Internet Domain Survey (IDS): Used to estimate the number of Internet hosts over time, providing data for estimating the host growth rate ($p$).
  • Mercator and Skitter Datasets: Large router inventories used to map routers to their associated ASes, providing empirical AS size distributions for model validation.
  • BGP Table Archives (RouteViews): Used to infer AS merger events by analyzing IP prefix advertisements and disappearances over time. This data was collected from U. Oregon, NLANR, and PCH, spanning from 1997 onwards.

Key Insights and Ideas

  • AS size distribution is not scale-free: Unlike some network models (e.g., Barabási-Albert for node degree), the average AS size grows over time, indicating a deviation from strict scale-free properties.
  • Growth alone is a good first approximation: The simple model incorporating only AS births and host growth captures the general shape of the empirical AS size distribution reasonably well, especially in the "body" of the distribution.
  • Mergers are crucial for accuracy: The model's predictions show discrepancies with empirical data, particularly in the tail of the distribution. The authors hypothesize that AS mergers are a significant missing factor.
  • Power-law tails are robust: Even with mergers, the resulting AS size distribution is analytically shown to exhibit a power-law tail, with the exponent being surprisingly independent of the specific details of the merging process (for the constant kernel case).
  • Distinguishing mergers from churn is hard: Identifying actual AS mergers from BGP data is challenging due to normal network "churn" (temporary disappearances and reappearances of prefixes). The authors develop a heuristic to differentiate these events.

Key Results

  • The growth-only model provides a reasonable first-order approximation to empirical AS size distributions.
  • The growth and merger model, particularly with a constant merger kernel, shows improved agreement with empirical data for small to medium-sized ASes compared to the growth-only model.
  • The exponent of the power-law tail in the merger model is analytically derived and found to be $\tau = 1 + q/p - r/p$ (for the constant kernel), where $q$ is the birth rate, $p$ is the host growth rate, and $r$ is the merger rate.
  • Estimates for growth rates were derived: $q \approx 3.8 \times 10^{-4}$ and $p \approx 4.8 \times 10^{-4}$.
  • An estimated merger rate $r \approx 1.8 \times 10^{-4}$ was derived from BGP data analysis.
  • Despite improvements, neither model perfectly predicts the tail of the AS size distribution, suggesting that more complex merger processes might be at play.

Limitations and Future Work

  • Complex Merger Kernels: The analysis of mergers was primarily done using a simplified "constant kernel." The authors acknowledge that more realistic merger kernels, which depend on the sizes of the merging ASes, are needed for greater accuracy. They are actively analyzing empirical data to determine the best-fitting kernel.
  • Tail Discrepancies: While the models show general agreement, they don't perfectly capture the shape of the tail of the empirical AS size distribution. This suggests that other factors or more nuanced modeling of mergers might be necessary.
  • Distinguishing Coalescence from Evaporation: The methods used to detect mergers can also pick up "evaporation" events (where prefixes simply disappear). Distinguishing between these two is noted as a difficulty.
  • Future Work: The authors explicitly state that their ongoing work focuses on identifying the kernel that best reflects actual coalescence behavior and on analyzing more general classes of kernels. They also aim to improve the simple model's predictive power and accuracy.

Summary updated

Abstract

This paper explores reasons for the high degree of variability in the sizes of ASes that have recently been observed, and the processes by which this variable distribution develops. AS size distribution is important for a number of reasons. First, when modeling network topologies, an AS size distribution assists in labeling routers with an associated AS. Second, AS size has been found to be positively correlated with the degree of the AS (number of peering links), so understanding the distribution of AS sizes has implications for AS connectivity properties. Our model accounts for AS births, growth, and mergers. We analyze two models: one incorporates only the growth of hosts and ASes, and a second extends that model to include mergers of ASes. We show analytically that, given reasonable assumptions about the nature of mergers, the resulting size distribution exhibits a power law tail with the exponent independent of the details of the merging process. We estimate parameters of the models from measurements obtained from Internet registries and from BGP tables. We then compare the models solutions to empirical AS size distribution taken from Mercator and Skitter datasets, and find that the simple growth-based model yields general agreement with empirical data. Our analysis of the model in which mergers occur in a manner independent of the size of the merging ASes suggests that more detailed analysis of merger processes is needed.
BibTeX
@misc{fayed2003size,
  author = {Marwan Fayed and P. L. Krapivsky and John W. Byers and Mark Crovella and David Finkel and S. Redner},
  title = {{On the Size Distribution of Autonomous Systems}},
  year = {2003},
  doi = {10.21236/ada450795},
}

Loading related content...

Figure