Understanding and detecting BGP instabilities

Abstract

Communication networks have reached amazing size and complexity nowadays. The Internet, which was born as an experimental network connecting a handful of volunteer research institutes, has grown to become a huge distributed system interconnecting almost 700 millions of hosts at present. As soon as it was clear that computer networks would have driven the information revolution, the Internet drew a lot of interest both from academia and from industry. Moreover, the demand for features that were not envisaged when the Internet was designed grew alongside with the size and complexity of the Internet itself. Routing, that is, finding a path in a network that interconnects a given source to a given destination, also needed to evolve accordingly: as soon as the Internet got into its commercial era, there was a strong demand for routing protocols that supported policies. Among the wide variety of routing protocols that can be found today in the Internet, the Border Gateway Protocol (BGP) is responsible for connecting large administrative domains (called Autonomous Systems, or ASes), each administering its own network. BGP configuration languages allow network administrators to define fine-grained policies to influence the selection and the dissemination of routes over the network, and is therefore classified as a policy-based interdomain routing protocol. BGP policies allow each AS to autonomously configure its network in order, e.g., to minimize the cost of routing traffic, or to optimize delay. Ideally, BGP was designed to let each administrative domain choose the best route (where “best” obviously has local significance) given the alternatives proposed by neighboring ASes. Unfortunately, as it is often the case in other branches of computer science, many agents that independently pursue a local optimum do not always converge into a global optimum. In particular, it has been shown that there exist sets of BGP policies that cannot be satisfied at the same time, and trap the protocol in infinite oscillations in which a stable routing choice is never reached. This fact spurred lots of research efforts towards techniques to characterize, discover, mitigate and eliminate BGP instabilities. This thesis presents novel research contributions as well as related work regarding the characterization and the detection of BGP instabilities under a common framework. We cover both the necessary theoretical background, as well as practical techniques and methodologies to analyze real BGP networks. First, we tackle the problem of finding a suitable model for studying BGP oscillations. This is indeed a nontrivial task, as many of the simplifying assumptions that have often been made to ease the analysis provably make the model unable to capture certain kinds of routing instabilities. Besides allowing us to pick the model that is best fit to study oscillations, the insight provided by our study also makes us able to review related work with a deeper understanding of the interplay among many different models for BGP. This thesis makes three main contributions. First, we show a sufficient and necessary condition for BGP safety under filtering, that is, the property of a BGP network to have guaranteed convergence under arbitrary filtering of BGP routes. To the best of our knowledge, this is the first complete characterization of safety under filtering. We exploit this finding to show a debugging technique that is able to spot the potential trouble points of a network by just analyzing two different routing states. Second, we study the possibility of manipulating internal BGP (iBGP) attributes. While in general such a practice exacerbates the BGP stability problem, adherence to simple guidelines ensures BGP stability while still providing some benefits in terms, e.g., of traffic engineering capabilities. Third, we devise and implement an algorithm which is able to tell whether a given BGP network is stable. This algorithm is provably free from false positives, and it is able to pinpoint the trouble points of a potentially unstable network. We show that this algorithm, together with techniques to perform some preprocessing on BGP networks, can be implemented efficiently enough to deal with Internet scale BGP topologies as well as very large iBGP networks. Finally, we propose a BGP monitoring system that is able to collect BGP data in such a way to enable the analysis of what-if scenarios.