EURO 2025 Leeds
Abstract Submission

602. An online column generation framework for segment routing optimization

Invited abstract in session MD-55: Network Optimization 4, stream Network Optimization.

Monday, 14:30-16:00
Room: Liberty 1.09

Authors (first author is the speaker)

1. Jérôme De Boeck
HEC Liège, Université de Liège

Abstract

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 preprocessing 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.

Keywords

Status: accepted

Back to the list of papers