T. Griffin and G. Wilfong, "On the Correctness of IBGP Configuration", in ACM SIGCOMM, 2002.
|On the Correctness of IBGP Configuration|
|Published:||ACM SIGCOMM, 2002|
|Abstract:||The Border Gateway Protocol (BGP) has two distinct modes of operation. External BGP (EBGP) exchanges reachability information between autonomous systems, while Internal BGP (IBGP) exchanges external reachability information within an autonomous system. We study several routing anomalies that are unique to IBGP because, unlike EBGP, forwarding paths and signaling paths are not always symmetric. In particular, we focus on anomalies 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. Deflections can greatly complicate the debugging of routing problems, and in the worst case multiple deflections can combine to form persistent forwarding loops. We define a correct IBGP configuration to be one that is anomaly free for every possible set of routes sent by neighboring autonomous systems. We show that determination of IBGP configuration correctness is NP-hard. However, we give simple sufficient conditions on network configurations that guarantee correctness.|
Defines correctness of an AS's network configuration as follows:
for every possible set of inputs (external routing messages) the
configuration produces a stable routing free of deflections.
Roughly speaking, a forwarding path (supplied by IGP) from a BGP speaker
to an egress point from the AS is said to be deflected if along
the forwarding path another BGP speaker chooses a different egress point.
Deflection can lead to forwarding loops.
The authors show that determining if a configuration has the following anomalies is NP-hard:
However, for both types of routing anomalies the authors define sufficient conditions that guarantee configuration correctness. Roughly:
In general, the authors conclude that potential anomalies can arise if the relationship between forwarding and signalling paths is unconstrained. They note that deflection problem vanishes if traffic is tunneled (e.g. using MPLS), rather than routed, to egress points.