Calcul de chemins pour réseaux IP : routage de la patate chaude et froide lors de pannes & chemins multi-contraints pour segment routing
Path computation algorithms in IP networks : reliable hot-potato routing & deployable multi-constrained tunnels
Routage
Calcul de chemins
DCLC
Segment Routing
BGP
IGP
Qualité de Service
Ingénierie de Trafic
Routing
Path Computation
DCLC
Segment Routing
BGP
IGP
Quality of Service
Traffic Engineering
004.6
Routage (informatique)
Réseaux d'ordinateurs
Qualité de Service (télécommunications)
Les travaux présentés dans cette thèse se décomposent en deux parties centrées autour du routage. Nous nous intéressons d'abord aux calculs de chemins multicritères, notamment utiles pour router du trafic exigeant une latence faible. Le problème NP-Difficile étudié, appelé DCLC, devient radicalement plus complexe lorsque l'on considère les contraintes opérationnelles rajoutées par la technologie utilisée pour déployer ces chemins, Segment Routing. Nous proposons différents méthodes et algorithmes afin de résoudre DCLC dans un tel contexte opérationnel, et montrons l'efficacité de nos solutions via une évaluation sur des réseaux large-échelle. Nous nous concentrons ensuite sur les effets néfastes induits par les interactions inter-protocolaires. Les interactions entre BGP (le protocole de routage utilisé dans l'Internet) et l'IGP (utilisé au sein d'un réseau) provoquent un temps de convergence long lors de changements topologiques. Nous retravaillons ces interactions et proposons OPTIC, ramenant ce temps de convergence à une durée marginale. Nous montrons la faisabilité d'OPTIC via évaluation théorique basée sur des données réelles.
The work presented in this thesis is divided into two parts centered around routing. First, we focus on multi-criteria path computations, which are particularly useful for routing traffic requiring low latency. The NP-hard problem studied, called DCLC, becomes radically more complex when we consider the operational constraints added by the technology used to deploy these paths, Segment Routing. We propose different methods and algorithms to solve DCLC in such an operational context, and show the efficiency of our solutions via an evaluation on large-scale networks. We then focus on the adverse effects induced by inter-protocol interactions. Interactions between BGP (the routing protocol used in the Internet) and the IGP (used within a network) cause long convergence times during topological changes. We rework these interactions and propose OPTIC, reducing this convergence time to a marginal duration. We show the feasibility of OPTIC via theoretical evaluation based on real data.
Electronic Thesis or Dissertation
Text
en
PDF
9366609
Université de Strasbourg
Strasbourg
2023-12-31
https://theses.hal.science/tel-04089268
application/pdf
9418177
https://publication-theses.unistra.fr/public/theses_doctorat/2022/LUTTRINGER_Jean-Romain_2022_ED269.pdf
http://www.theses.fr/2022STRAD038/abes
https://theses.hal.science/tel-04089268
https://theses.hal.science/tel-04089268
https://theses.hal.science/tel-04089268
Luttringer
Jean-Romain
1995-11-24
FR
269730516
1506021235D
21305441
4200018
https://theses.fr/2022STRAD038
2022STRAD038
https://doi.org/10.70675/db29b7b5z96b2z4600za45ez99fd534f02fd
2022-11-28
Informatique
Strasbourg
131056549
Doctorat
Docteur es
non
oui
Pelsser
Cristel
MADS_DIRECTEUR_DE_THESE_1
242358004
Texier
Géraldine
MADS_PRESIDENT_DU_JURY
127231692
Clauss
Philippe
MADS_MEMBRE_DU_JURY_1
098478389
Kuipers
Fernando A.
MADS_RAPPORTEUR_1
269730850
Leduc
Guy
MADS_RAPPORTEUR_2
035261684
École doctorale Mathématiques, sciences de l'information et de l'ingénieur (Strasbourg ; 1997-....)
MADS_ECOLE_DOCTORALE_1
269
156504863
Laboratoire des sciences de l'ingénieur, de l'informatique et de l'imagerie (Strasbourg ; 2013-....)
MADS_PARTENAIRE_DE_RECHERCHE_1
260728
176969721
ddc:004
Pelsser
Cristel
Texier
Géraldine
Clauss
Philippe
Kuipers
Fernando A.
Leduc
Guy
École doctorale Mathématiques, sciences de l'information et de l'ingénieur (Strasbourg ; 1997-....)
Laboratoire des sciences de l'ingénieur, de l'informatique et de l'imagerie (Strasbourg)
PDF
9366609