Robust optimization for the Segment Routing Traffic Engineering Problem

Segment Routing (SR) introduces a flexible approach to IP network routing, addressing limitations present in conventional protocols. SR is to be used on top of an existing routing protocol and allows traffic to take detours through nodes and links called node segments and adjacency segments. The segment routing traffic engineering problem (SRTEP) uses shortest path based underlying pro- tocols such as OSPF and assumes that the link weights are set. Only the SR-paths can be changed, and there can only be one unique SR-path between two (ordered) pairs of nodes. The goal of the SRTEP is to minimise the maximum link utilisation with respect to one traffic matrix (TM) [4]. This paper focuses on robust optimization within the SRTEP. Unlike traditional approaches that rely on a single traffic matrix for optimization, we deal with an infinite set of matrices defined by linear constraints. The objective is to identify routing strategies robust to the worst-case scenario within this set.
We build upon prior work by introducing new linear formulations inspired by Bertsimas and Sim, exploring their efficiency in comparison to exhaustive enumeration methods and constraint generation methods. Our findings reveal promising results, showcasing the practicality and speed advantages of our approach.