Improving internal BGP routing

Wed, 12/08/2010 - 13:03 by Virginie Van den Schrieck


While initially designed as a research network, the Internet has become a large interconnection of networks all over the world. Its infrastructure and the applications that it supports are in constant evolution. The Border Gateway Protocol (BGP) plays a key role in today's Internet, as the interdomain routing protocol used to build end-to-end paths. BGP is affected by the growth of the Internet, and this is problematic as the dataplane performances depend on the robustness and stability of this protocol. It is however difficult to modify BGP itself, as such a change requires cooperation between concurrent Internet Service Providers (ISPs).
In this thesis, we study the behavior of BGP inside an ISP, and show that its internal organization is often responsible for a lack of alternate paths, preventing fast and local failure recovery. Slow BGP convergence inside an ISP affects the global reachability of impacted destinations and the number of BGP messages exchanged between ISPs. First, we propose several modifications to the classical iBGP organization to improve iBGP stability and reactivity upon failure. In the second part, we study a new variant of iBGP that allows several paths to be advertised for the same prefix on a session. This solution is promising, as it is able to solve several iBGP issues at once, but ISPs must be aware that additional paths increase the memory consumption inside routers and the number of BGP messages to process. We analyse the trade-offs of several deployment scenarios and provide a tool to simulate and compare them quantitatively.
With the solutions presented in this thesis, ISPs are able to recover quickly from link failures and to reduce the number of BGP messages they propagate to their neighbors. They are thus able to contribute individually to a global improvement of Internet performances.

Virginie Van den Schrieck
PhD thesis
Université catholique de Louvain, December 2010.
Full text
pdf   (3.49 MB)
pdf   (5.4 MB)
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

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.