Understanding and detecting BGP instabilities

2010-03-29T22:00:00Z

Understanding and detecting BGP instabilities Cittadini, Luca 2010-03-30 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, ﬁnding 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 conﬁguration languages allow network administrators to deﬁne ﬁne-grained policies to inﬂuence the selection and the dissemination of routes over the network, and is therefore classiﬁed as a policy-based interdomain routing protocol. BGP policies allow each AS to autonomously conﬁgure its network in order, e.g., to minimize the cost of routing traﬃc, or to optimize delay. Ideally, BGP was designed to let each administrative domain choose the best route (where “best” obviously has local signiﬁcance) 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 satisﬁed at the same time, and trap the protocol in inﬁnite oscillations in which a stable routing choice is never reached. This fact spurred lots of research eﬀorts 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 ﬁnding 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 ﬁt 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 diﬀerent models for BGP. This thesis makes three main contributions. First, we show a suﬃcient and necessary condition for BGP safety under ﬁltering, that is, the property of a BGP network to have guaranteed convergence under arbitrary ﬁltering of BGP routes. To the best of our knowledge, this is the ﬁrst complete characterization of safety under ﬁltering. We exploit this ﬁnding to show a debugging technique that is able to spot the potential trouble points of a network by just analyzing two diﬀerent 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 beneﬁts in terms, e.g., of traﬃc 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 eﬃciently 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.

ArcAdiA

Understanding and detecting BGP instabilities