Abstract

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.