Scaling and Evolution:
M. Yannuzzi, X. Masip-Bruin, and O. Bonaventure,
Open Issues in Interdomain Routing: A Survey,
IEEE Network, November/December 2005.
"Interdomain routing is still a challenging research
area... While some of the issues exposed in this
article are rooted in the intrinsic limitations
of BGP and the current interdomain routing architecture,
others derive from the intricate interactions and
dependencies between domains."
Commentary on Inter-Domain Routing in the Internet,
RFC 3221, Informational, December 2001.
"This document examines the various longer term trends visible
within the characteristics of the Internet's BGP table and identifies
a number of operational practices and protocol factors that contribute
to these trends. The potential impacts of these practices and
protocol properties on the scaling properties of the inter-domain
routing space are examined."
"These impacts include the potential for exhaustion of the existing
Autonomous System number space, increasing convergence times for
selection of stable alternate paths following withdrawal of route
announcements, the stability of table entries, and the average
prefix length of entries in the BGP table. The larger long term
issue is that of an increasingly denser inter-connectivity mesh
between AS's, causing a finer degree of granularity of inter-domain
policy and finer levels of control to undertake inter-domain traffic
"Various approaches to a refinement of the inter-domain routing
protocol and associated operating practices that may provide
superior scaling properties are identified as an area for further
- Bill St. Arnaud,
Faster 'Net growth rate raises fears about routers,
April 2, 2001.
"I am often asked by graduate students to suggest possible areas of
To which I always respond that BGP scaling is one of the biggest issues
confronting the Internet."
"It's not the size of the table, but the number of updates per second
that kills a router."
Prefix Taxonomy Ongoing Measurement & Inter Network Working Group
"The purpose of the ptomaine WG is to consider and measure the
problem of routing table growth and possible interim methods for
reducing the impact of routing table resource consumption
within a network and the global Internet. The first step of the WG is to
define the impacts on routing resource consumption
and to identify the problems facing routing scalability."
- Timothy Griffin et al.,
An Analysis of BGP Convergence Properties,
SIGCOMM 99, August 1999.
"The statis analysis approach to solving the BGP
convergence problem faces two practical challenges.
... even if there were complete knowledge of routing policies, the
compexity results presented in this paper show that
checking for various global convergence conditions
is either NP-complete or NP-hard... For these reasons, we
believe that a practical solution to the BGP convergence problem
must be a dynamic one... Several theoretical problems remain open."
- Craig Labovitz et al.,
An Experimental Study of Delayed Internet Routing Convergence,
SIGCOMM 2000, August 2000.
"This paper has argued that the lack of interdomain failover due
to delayed BGP routing convergence will potentially become one of the
key factors contributing to the `gap' between the needs and expectations
of today's data networks."
Atoms - Atomised Routing, CAIDA.
"CAIDA is researching and implementing modifications to BGP routing
that aggregate prefixes into equivalence classes (policy atoms)
based on common AS path from a given topological location. The
motivation behind development of BGP atomization mechanisms is to
achieve potential savings in computation and communication costs,
as well as reduction in BGP table size."
Routing Protocol Overloading -- Issues, Concerns, and Considerations,
draft-meyer-rpo-00.txt, October 2003.
"The Routing Protocol Overloading (RPO) design team was formed to
document the concerns and considerations surrounding the use of
Internet routing protocols for functions not directly related
to routing of IP packets within the Internet and IP networks."
Routing Research Group.
Last modified: May 2002