The apparent BGP4 square law relationships

Original publication

Observed Relationships between Size Measures of the Internet, ACM SIGCOMM CCR, 39(2) (April 2009) 6-12

Abstract:

This paper reports some observations on the relationships between three measures of the size of the Internet over more than ten years. The size of the BGP4 routing table, the number of active BGP4 Autonomous Systems, and a lower bound on the total size of the Internet, appear to have fairly simple relationships despite the Internet's growth by two orders of magnitude. In particular, it is observed that the size of the BGP4 system appears to have grown approximately in proportion to the square root of the lower-bound size of the globally addressable Internet. A simple model that partially explains this square law is described. It is not suggested that this observation and model have predictive value, since they cannot predict qualitative changes in the Internet topology. However, they do offer a new way to understand and monitor the scaling of the BGP4 system.

Note that the observations concern IPv4 only. ISC domain count data are used as lower bounds on the total size of the IPv4-addressable Internet. The choice and validity of this metric are discussed in the paper.

Errata:

The authors of references [15] and [16] have been swapped.
The parenthesis next to Fig. 3 "(or more accurately, about 8 entries above a baseline of about 18000)" should end "...about 15000)".

Cited in:

Boguna, M. et al., Sustaining the Internet with hyperbolic mapping, Nature Communications 1:62 (2010).
L. Cittadini, W. Muhlbauer, S. Uhlig, R. Bush, P. Francois and O. Maennel, Evolution of Internet Address Space Deaggregation: Myths and Reality, IEEE Journal on Selected Areas in Communication (JSAC), August 2010.

Updated graphs based on data through July 2011

The approximate square law relationships originally observed in data through 2008 still appear to exist. However, there is a hint in the data of an upward inflection of the relative growth of the BGP4 system, starting in 2007.

BGP4 routes vs active AS count (1997-2011):

BGP4 routes vs square root of domain count (1994-2011):

Active AS count vs square root of domain count (1997-2011):

As always, thanks to isc.org and potaroo.net for the data.

External talks on this topic

BGP scaling revisited, (IEPG Meeting, Taipei, China, November 2011)

BGP growth over 15 years, or Is the Internet really just a star network after all? (Keynote at APRICOT 2010, March 2010)

Observed Relationships between Size Measures of the Internet, or Is the Internet really just a star network after all? (Seminar, University of Cambridge, June 2009)

Some multi-year graphs (IEPG Meeting, Dublin, Ireland, July 2008)

Page updated 2011-11-21. Disclaimer