Preprocessing for segment routing optimization

Callebaut, Hugo; de Boeck, Jérôme; Fortz, Bernard

Type de document :

Compte-rendu et recension critique d'ouvrage

DOI :

10.1002/net.22165

Titre :

Preprocessing for segment routing optimization

Auteur(s) :

Callebaut, Hugo [Auteur]
de Boeck, Jérôme [Auteur]
Fortz, Bernard [Auteur]
Département d'Informatique [Bruxelles] [ULB]
Integrated Optimization with Complex Structure [INOCS]

Titre de la revue :

Networks

Pagination :

459-478

Éditeur :

Wiley

Date de publication :

2023-07-25

ISSN :

0028-3045

Discipline(s) HAL :

Computer Science [cs]/Operations Research [math.OC]

Résumé en anglais : [en]

In this article we introduce a preprocessing technique to solve the Segment Routing Traffic Engineering Problem optimally using significantly fewer computational resources than previously introduced methods. Segment routing ...
Lire la suite >In this article we introduce a preprocessing technique to solve the Segment Routing Traffic Engineering Problem optimally using significantly fewer computational resources than previously introduced methods. Segment routing is a recently developed interior gateway routing protocol to be used on top of existing protocols that introduces more flexibility in traffic engineering. In practice, segment routing allows to deviate traffic from its original path by specifying a list of intermediate nodes or links, called segments, to visit before going to its destination. The issue we tackle in this article is that the number of segment paths scales exponentially with the maximum number of segments allowed leading to scalability issues in mathematical formulations. This article introduces the notion of dominated segment paths, these are paths that can be eliminated from the solution space when searching for an optimal solution. We propose a dynamic programming algorithm eliminating dominated paths for any number of segments. Numerical results show that respectively 50%, 90%, and 97% of paths are dominated when considering up to 2, 3, and 4 segments on benchmark network topologies.Lire moins >

Langue :

Anglais

Vulgarisation :

Non

Collections :

Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189

Source :

Harvested from HAL

Fichiers

document
Accès libre
Accéder au document

main.pdf
Accès libre
Accéder au document

Preprocessing for segment routing optimization BibTeX CSV Excel RIS

Fichiers

Preprocessing for segment routing optimization

BibTeX

CSV

Excel

RIS