URL: http://www.acm.org/sigcomm/sigcomm2002/papers/ibgp.pdf Entry Date: 2002-5-30 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. Results: 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:

• the configuration will converge for all possible inputs
• the configuration produces deflection-free routing

However, for both types of routing anomalies the authors define sufficient conditions that guarantee configuration correctness. Roughly:

• The graph of route-reflector <-> client edges is a DAG
• All route reflectors favour exit routes learned from clients over those from non-clients.
• Each shortest path (in IGP) corresponds to some signalling path (in IBGP).

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. References:

• Complements:
  • Timothy Griffin and Gordon T. Wilfong. An Analysis of BGP Convergence Properties. In Proceedings of ACM SIGCOMM, pages 277-288, 1999.
  • R. Mahajan, D. Wetherall and T. Anderson. Understanding BGP Misconfigurations. In Proceedings of ACM SIGCOMM, 2002.
• Alternative solution to:
  • Anindya Basu, C.-H. Luke Ong, April Rasala, F. Bruce Shepherd, and Gordon Wilfong. Route Oscillations in I-BGP with route reflection. In Proceedings of ACM SIGCOMM, 2002.