Recently, there have been significant concerns within the research and operational community regarding the scalability of BGP interdomain routing. A workshop organized by the Internet Architecture Board concluded that ``routing scalability is the most important problem facing the Internet today.'' A recent measurement study showed that BGP churn increases at a much faster pace than the routing table size. During 2005, the daily rate of update messages almost doubled, while the size of the routing table grew by 18%. Projections of this growth trend indicate that the processing load on core routers demands expensive router upgrades in the near-term, and it raises concerns about the feasibility of BGP routing in the global Internet in the longer-term. Some people are already asking: ``Is the Internet getting too big for a distributed interdomain routing protocol such as BGP?''

The Internet community does not know the exact growth rate of BGP churn, and more importantly, does not understand the factors that drive the churn growth. Consequently, a possible outcome for the next few years is that even the fastest and most expensive core routers might not be able to cope with the observed routing dynamics. Needless to say, should this occur it will be much too late to understand and correct its root causes. Corrective action might be as simple as the introduction of novel BGP implementation features that will protect the protocol's scalability, or as drastic as a complete overhaul of the interdomain routing architecture and protocols.

The high-level goal of this research is to investigate the scalability of interdomain routing using the BGP protocol, understand the factors that affect the magnitude of BGP churn, and provide practical recommendations to router vendors and the network operations community. Instead of focusing only on the current Internet, or on its historical trends, we will also examine several plausible ``what-if'' questions about the future of the Internet, in terms of its topology and policy structure, frequency of certain routing operations (such as policy changes and traffic engineering), and deployed BGP features and extensions.

Specifically, we have identified three dimensions along which we will examine the scalability of BGP churn. The first dimension is about the topology structure and growth pattern of the Internet. The topological structure in this context includes inter-AS routing policies. The second dimension is about the various types of routing events that create instability in the Internet. Such events include link and network failures, policy changes, or IGP/EGP traffic engineering methods. The third dimension is about the various BGP configurations, optional or recommended mechanisms, and proposed extensions. For instance, the MRAI timer, whether Explicit Withdrawals are rate-limited or not (WRATE), Route-Flap Dampening (RFD), iBGP configurations and the recently proposed BGP multipath extension.