Internal BGP (iBGP) is used to distribute interdomain routes within a single ISP. The interaction between iBGP and the underlying IGP can lead to routing and forwarding anomalies. For this reason, several research contributions aimed at deﬁning sufﬁcient conditions to guarantee anomaly-free conﬁgurations and providing design guidelines for network operators.
In this work, we show several anomalies caused by defective dissemination of routes in iBGP. We deﬁne the dissemination correctness property, which models the ability of routers to learn at least one route to each destination. By distinguishing between dissemination correctness and existing correctness properties, we show counterexamples that invalidate some results in the literature. Further, we prove that deciding whether an iBGP conﬁguration is dissemination correct is computationally intractable. Even worse, determining whether the addition of a single iBGP session can adversely affect dissemination correctness of an iBGP conﬁguration is also computationally intractable. Finally, we provide sufﬁcient conditions that ensure dissemination correctness, and we leverage them to both formulate design guidelines and revisit prior results.
Luca Cittadini’s personal site
This event will be conducted in English