An online column generation framework for segment routing optimization

Segment Routing (SR) is an Interior Gateway Protocol that has been developed in the recent years which offers a much larger flexibility than common routing protocols such as the OSPF protocol. This protocol consists in routing requests through the shortest path in a network
from the entering to the exiting router. It is technically difficult to modify these paths, which can lead to congestion if a link is on the shortest path between several pairs of routers with high traffic. The SR protocol offers the possibility to add deviations, called segments, that requests must reach before reaching the exiting router. These deviations can
be dynamically added when a request enters a network. It has been shown some standard traffic measures can be improved by 40% in a deterministic context.
The main difficulty in handling SR appropriately compared to OSPF lies in the number of routing possibilities that are exponential in the number of segments. Path-based mathematical programs tend to quickly become untractable. We present a column generation algorithm that tackles the issues on large-scale instances. Recent prepro-
cessing techniques for SR are used to work on a reduced-size formulation, speeding up the computation times of the state-of-the-art algorithms. The fast computation times of the column generation algorithm allow to embed it in an online procedure that can take into consideration the real-time demand observed on the network.