iBGP and Constrained Connectivity

Sep 30, 2009

Abstract:

In this work we first show that the problem of minimizing the size of

an iBGP overlay subject to maintaining a natural notion of correctness

can be reduced to a new connectivity problem that we call "constrained

connectivity". In constrained connectivity we are given a graph and

are asked to find the smallest subgraph in which every pair of nodes

is connected by a path that is contained in a special subset defined

by the pair. The iBGP problem is equivalent to a special case of

constrained connectivity with G = K_n. For this case we give an

Omega(log n) hardness of approximation result and an O(n^{2/3})

approximation algorithm, and for the general case we show that it is

as hard to approximate as Label Cover. We will also discuss the

integrality gap of the natural LP and some special cases for which

constrained connectivity is easier.

In this work we first show that the problem of minimizing the size of

an iBGP overlay subject to maintaining a natural notion of correctness

can be reduced to a new connectivity problem that we call "constrained

connectivity". In constrained connectivity we are given a graph and

are asked to find the smallest subgraph in which every pair of nodes

is connected by a path that is contained in a special subset defined

by the pair. The iBGP problem is equivalent to a special case of

constrained connectivity with G = K_n. For this case we give an

Omega(log n) hardness of approximation result and an O(n^{2/3})

approximation algorithm, and for the general case we show that it is

as hard to approximate as Label Cover. We will also discuss the

integrality gap of the natural LP and some special cases for which

constrained connectivity is easier.