iBGP and Constrained Connectivity

We initiate the theoretical study of the problem of minimizing the size of an iBGP (Interior Border Gateway Protocol) overlay in an Autonomous System (AS) in the Internet subject to a natural notion of correctness derived from the standard "hot-potato" routing rules. For both natural versions of the problem (where we measure the size of an overlay by either the number of edges or the maximum degree) we prove that it is NP-hard to approximate to a factor better ~ than (log n) and provide approximation algorithms with ratio O( n). This algorithm is based on a natural LP relaxation and randomized rounding technique inspired by the recent work on approximating directed spanners by Bhattacharyya et al. [SODA 2009], Dinitz and Krauthgamer [STOC 2011], and Berman et al. [ICALP 2011]. In addition to this theoretical algorithm, we give ~ a slightly worse O(n2/3 )-approximation based on primal-dual techniques that has the virtue of being both fast (in theory and in practice) and good in practice, which we show via simulations on the actual topologies of five large Autonomous Systems. The main technique we use is a reduction to a new connectivity-based network design problem that we call Constrained Connectivity. In this problem we are given a graph G = (V, E), and for every pair of vertices u, v V we are given a set S(u, v) V called the safe set of the pair. The goal is to find the smallest subgraph H = (V, F ) of G in which every pair of vertices u, v is connected by a path contained in S(u, v).