iBGP and Constrained Connectivity

Michael Dinitz, Gordon Wilfong

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 d…