Preprocessing for segment routing optimization
Document type :
Compte-rendu et recension critique d'ouvrage
DOI :
Title :
Preprocessing for segment routing optimization
Author(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]
de Boeck, Jérôme [Auteur]
Fortz, Bernard [Auteur]
Département d'Informatique [Bruxelles] [ULB]
Integrated Optimization with Complex Structure [INOCS]
Journal title :
Networks
Pages :
459-478
Publisher :
Wiley
Publication date :
2023-07-25
ISSN :
0028-3045
HAL domain(s) :
Computer Science [cs]/Operations Research [math.OC]
English abstract : [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 ...
Show more >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.Show less >
Show more >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.Show less >
Language :
Anglais
Popular science :
Non
Collections :
Source :
Files
- document
- Open access
- Access the document
- main.pdf
- Open access
- Access the document