iBGP Deceptions: More Sessions, Fewer Routes
Wed, 12/14/2011 - 19:12 by Laurent Vanbever
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 paper, 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.
- Stefano Vissicchio, Luca Cittadini, Laurent Vanbever and Olivier Bonaventure
In 31th IEEE International Conference on Computer Communications (IEEE INFOCOM 2012), 2012.
- Full text
- (153.74 KB)
- (374.08 KB)
- Cite it
- See here
IEEE Copyright Notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.
ACM Copyright Notice: Copyright 1999 by the Association for Computing Machinery, Inc. Permission to make digital or hard copies of part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page or intial screen of the document. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, to republish, to post on servers, or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from Publications Dept., ACM Inc., fax +1 (212) 869-0481, or firstname.lastname@example.org.
Springer-Verlag LNCS Copyright Notice: The copyright of these contributions has been transferred to Springer-Verlag Berlin Heidelberg New York. The copyright transfer covers the exclusive right to reproduce and distribute the contribution, including reprints, translations, photographic reproductions, microform, electronic form (offline, online), or any other reproductions of similar nature. Online available from Springer-Verlag LNCS series.