  We initiate the theoretical study of the problem of minimizing the size of an
iBGP 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 $\Omega(\log n)$ and provide
approximation algorithms with ratio $\tilde{O}(\sqrt{n})$. In addition, we give
a slightly worse $\tilde{O}(n^{2/3})$-approximation based on primal-dual
techniques that has the virtue of being both fast 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 \in V$ we are
given a set $S(u,v) \subseteq V$ called the safe set of the pair. The goal is
to find the smallest subgraph $H$ of $G$ in which every pair of vertices $u,v$
is connected by a path contained in $S(u,v)$. We show that the iBGP problem can
be reduced to the special case of Constrained Connectivity where $G = K_n$ and
safe sets are defined geometrically based on the IGP distances in the AS. We
also believe that Constrained Connectivity is an interesting problem in its own
right, so provide stronger hardness results ($2^{\log^{1-\epsilon} n}$-hardness
of approximation) and integrality gaps ($n^{1/3 - \epsilon}$) for the general
case. On the positive side, we show that Constrained Connectivity turns out to
be much simpler for some interesting special cases other than iBGP: when safe
sets are symmetric and hierarchical, we give a polynomial time algorithm that
computes an optimal solution.
