Segment Routing (SR) is a powerful tool to solve traffic engineering in large networks. It enables steering the traffic along any arbitrary network path while limiting scalability issues as routers do not need to maintain a global state.
Mathematical programming approaches proposed so far for SR either do not scale well with the size of topology or impose a strong limit on the number of possible detours (typically at most one). Moreover they do not support Segment Routing fully by ignoring the adjacency segments.
This paper leverages column generation, a widely used technique for solving large scale linear programs, combined with a novel dynamic program for solving the pricing problem.
Our approach reaches near optimal solutions with gap guarantees by also computing a strong lower-bound tighter than the multi-commodity flow relaxation. It scales even on large topologies and exploits the full expressiveness of SR including adjacency segments.
Our experiments compared with existing traffic engineering techniques on various topologies and demand matrices demonstrate the advantages of our approach in terms of scalability, any-time behavior and quality of the solutions.
This paper will be presented at INFOCOM 2019, on 29 April - 2 May 2019 / Paris, France
About the authors :
Mathieu Jadin : 3rd year PhD student under supervision of Pr. Olivier Bonaventure. He is working on Segment Routing in the context of Software Defined Networks to enhance their flexibility.
François Aubry is a teaching assistant at INGI/UCLouvain, finishing his PhD
Pierre Schaus is assistant professor of computer science at UCLouvain in the ICTeam Institute. I'm also part of the Be Cool research group.
Olivier Bonaventure, Professor of Computer Science, UCLouvain, Department of Computing Science and Engineering of the Institute