On the Correctness of IBGP Configuration

We investigate the correctness of IBGP configuration. In particular, we look at two types of misconfigurations -- those that can cause the protocol to diverge, and those that can cause a router's chosen forwarding path to an egress point to be deflected by another router on that path. This second problem arises in IBGP because, unlike EBGP, the forwarding paths and signaling paths are not always the same. Deflections can greatly complicate the debugging of routing problems, and in the worse case multiple deflections can lead to persistent forwarding loops. We show that static detection of protocol divergence is NP-hard. Then, even if the IBGP configuration is such that the protocol is guaranteed to converge, we show that static detection of possible deflections is an NP-hard problem. However, we give simple sufficient conditions on network configurations that guarantee both IGBP convergence and the absence of forwarding deflections.