Routing Questions:

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."

• G. Huston, 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 engineering."
  "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 investigation."

• Bill St. Arnaud, Faster 'Net growth rate raises fears about routers, CAnet-3-NEWS, April 2, 2001.
  "I am often asked by graduate students to suggest possible areas of research. 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 (ptomaine).
  "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."

Convergence:

• 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."

Other:

• 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."

• D. Meyer, 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.