A Simple and General Operational Framework to Deploy Optimal Routes with Source Routing

Abstract

Source Routing as enabled by Segment Routing (SR) allows controlling forwarding paths by specifying a list of detours (or segments) to deviate the packets along arbitrary routes. Computing the list of segments to encode a path is a challenging task (in particular when the number of segments has to be minimized) that has never been properly addressed.

In this paper, we finally tackle this challenge. We show that, conversely to what is often proposed in the literature, the segment list computation must be tied within the path computation to solve this task correctly and efficiently. Thus, we design a flexible framework, GOFOR-SR, that can wrap SR around usual path computation algorithms to output minimal segment lists encoding the solutions. Our generic formal model supports many use cases with diverse optimization strategies and contains the first incremental algorithm that encodes a path into a minimal list of segments of any type.

GOFOR not only eases the optimal integration of SR into varied path computation algorithms but also offers various path diversity models, all for a linear overhead. We implement GOFOR and demonstrate its benefits when tackling challenging use cases through an experimental evaluation.

Jean-Romain Luttringer

Assistant Professor at the University of Strasbourg

My research interests include Path computation, routing, measurements and programmable networks.