Thèse : Jean Romain Luttringer : Path Computation Algorithms in IP Networks: Reliable Hot-Potato Routing & Deployable Multi-Constrained Tunnels

Jean-Romain Luttringer, doctorant de l’équipe Réseaux, soutiendra sa thèse le 28 novembre prochain à 9h dans l’Amphithéatre A301 au pôle API à Illkirch. La soutenance aura lieu en anglais, suivie d’un pot. 

Titre : Calcul de chemins pour réseaux IP : routage de la patate chaude et froide lors de pannes & chemins multi-contraints pour Segment Routing

Jury : 

• Pr. Fernando A. KUIPERS (TU Delft) : Rapporteur 
• Pr. Guy LEDUC (Université de Liège) : Rapporteur 
• Pr Géraldine TEXIER (IMT Atlantique) : Examinatrice
• Pr. Philippe CLAUSS (ICube, Université de Strasbourg) : Examinateur
• Pr Cristel PELSSER (ICube, Université de Strasbourg) : Directrice de thèse
• Dr. Pascal MERINDOL (ICube, Université de Strasbourg ): Co-encadrant
• Dr. Quentin BRAMAS (ICube, Université de Strasbourg) : Co-encadrant

Résumé

Les besoins stricts des applications modernes communiquant par l’Internet nécessitent de calculer des chemins multi-critères, considérant par exemple le coût opérationnel ainsi que la latence. Ce problème, NP-Hard de nature, semble devenir considérablement plus complexe lorsque l’on considère les contraintes opérationnelles rajoutées par les technologies de déploiement, nécessaires pour implémenter ces chemins dans les routeurs.   En particulier, Segment Routing (la technologie la plus utilisée à l’heure actuelle) demande de considérer une nouvelle métrique contrainte, dont le comportement singulier induit la perte d’optimalité des sous-chemins et empêche de ce fait l’utilisation naïve d’algorithmes existants. Dans cette thèse, nous nous intéressons aux calculs de chemins multi-critères pour Segment Routing. À l’aide d’une structure de données originale, nous concevons méthodes et algorithmes permettant de prendre en compte efficacement ces nouvelles contraintes. Bien qu’une solution complète soit proposée, nous montrons que les méthodes utilisées sont génériques, et peuvent être employées par d’autres algorithmes afin de considérer correctement Segment Routing. Nous implémentons ces algorithmes, et montrons que nos méthodes permettent un calcul très efficace des chemins multi-critères même sur des réseaux large-échelle (moins d’une seconde pour 100 000 noeuds).

— English — 

Jean-Romain Luttringer, Ph.D. student with the Network team, will defend his Ph.D. thesis on November, 28th at 9am, in the amphitheater A301 at Illkirch. The defence will be held in english, followed by a reception. 

Title : Path Computation Algorithms in IP Networks: Reliable Hot-Potato Routing & Deployable Multi-Constrained Tunnels

Jury

• Pr. Fernando A. KUIPERS (TU Delft) : Referee 
• Pr. Guy LEDUC (University of Liège) : Referee 
• Pr Géraldine TEXIER (IMT Atlantique) : Examiner
• Pr. Philippe CLAUSS (ICube, University of Strasbourg) : Examiner
• Pr Cristel PELSSER (ICube, University of Strasbourg) : Director
• Dr. Pascal MERINDOL (ICube, University of Strasbourg ): Supervisor
• Dr. Quentin BRAMAS (ICube, University of Strasbourg) : Supervisor

Summary

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).