Preprocessing for segment routing optimization

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.

Automated summary

In this article, a preprocessing technique is introduced to efficiently solve the Segment Routing Traffic Engineering Problem by utilizing fewer computational resources. The article focuses on the scalability issue of the exponential increase in segment paths when calculating optimal solutions. The notion of dominated segment paths is introduced to eliminate unnecessary paths, and a dynamic programming algorithm is proposed to handle any number of segments. Numerical results indicate the high dominance percentage of paths for different segment numbers in benchmark network topologies.