Ahmed Elmokashfi (Simula Research Laboratory, NO); Amund Kvalbein (Simula Research Laboratory, NO); Constantine Dovrolis (Georgia Institute of Technology, US)
The scalability of BGP routing is a major concern for the Internet community. Scalability is an issue in two different aspects: increasing routing table size, and increasing rate of BGP updates. In this paper, we focus on the latter. Our objective is to characterize the development of churn experienced by ASes in different levels of the Internet hierarchy as the network grows. We look at several ``what-if'' growth scenarios that are either plausible directions in the evolution of the Internet or educational corner cases, and investigate their scalability implications. In addition, we examine the effect of the BGP update rate-limiting timer (MRAI), considering both major variations with which it has been deployed. Our findings explain the dramatically different impact of multihoming and peering on BGP scalability, identify which topological growth scenarios will lead to very fast increase in BGP churn, and emphasize the importance of not rate-limiting explicit withdrawals (despite what RFC-4271 recently required).