Scalability of the Internet backbone routing infrastructure.

Abstract

Over the last several years, the Internet has sustained exponential growth in the number of endsystems, traffic, and network adjacencies. This rate of growth poses significant engineering challenges for both researchers and backbone service providers. In this thesis, we explore one aspect of the network's growth---the performance and scaling properties of Internet routing algorithms and the backbone infrastructure. Specifically, we examine network routing instability which impacts the level of state information and processing power required by each backbone router. High levels of network topological state oscillation can also lead to packet loss, increased network latency and delayed times to reach convergence. This thesis explores the origins and propagation behaviors of Internet topological state information through the experimental instrumentation of key portions of the Internet backbone infrastructure. We analyze more than three years of routing update messages collected from backbone routers at five of the major US Internet exchange points, as well as routers throughout national and regional backbones. Our analysis identifies significant pathologies in Internet routing, including several orders of magnitude more routing updates in the Internet core than anticipated, large numbers of duplicate routing messages, and unexpected frequency components between routing instability events. Through analysis of our data and ongoing discussions with router vendors and network service providers, we identify specific router software and network architectural changes that once deployed reduced the volume of Internet routing update messages by an order of magnitude. Finally, we provide analysis of wide-area and intra-domain network failures and explore the impact of these failures and their resulting topological state changes on the Internet routing infrastructure.