(Thesis) Path Computation in IP Networks : Reliable Hot-Potato Routing and Multi-Constrained Tunnels

Abstract

The first path of this thesis is dedicated to path computation. The strict requirements of modern applications communicating over the Internet require computing multi-criteria paths, considering for example operational cost as well as latency. This problem, NP-Hard in nature, seems to become considerably more complex when considering the operational constraints added by the deployment technologies, necessary to implement these paths within the routers. In particular, Segment Routing (the most widely used technology at the moment) requires to consider a new constrained metric, whose singular behaviour induces the loss of the subpaths optimality property and thus prevents the naive use of existing algorithms. In this thesis, we focus on multi-criteria path computations for Segment Routing. Using an original data structure, we design methods and algorithms to efficiently take into account these new constraints. Although a complete solution is proposed, we show that the methods used are generic, and can be used by other algorithms to properly consider Segment Routing. We implement these algorithms, and show that our methods allow a very efficient computation of these multi-criteria paths even on large-scale networks (less than one second for 100 000 nodes). In the second part of this thesis, we focus on inter and intra-domain routing. We show that intra-domain event may lead to the reconvergence of the inter-domain routing protocol, which is slow. We devise a new way to combine the two protocols to mitigate these effects for a limited overhead. We" show that our approach can lead to promising results through an extensive theoretical evaluation.

Jean-Romain Luttringer

Assistant Professor at the University of Strasbourg

My research interests include Path computation, routing, measurements and programmable networks.