Translating Traffic Engineering outcome into Segment Routing paths: The Encoding problem

Traffic Engineering (TE) algorithms aims at determining the packet routing paths in order to satisfy specific QoS requirements. These paths are normally established through control procedures e.g., exchange of RSVP messages in MPLS networks or links weights modification in pure IP networks. An increase of control traffic or long convergence time intervals, respectively, are the drawbacks of these solutions. Segment Routing (SR) is a new network paradigm able to implement TE routing strategies over legacy IP/MPLS networks with no need of dedicated signaling procedures. This result is obtained by inserting in each packet header an ordered list of instructions, called Segments List, that indicates the path to be crossed. This paper provides the formulation of the Segment List Encoding problem i.e., the detection of the proper Segment Lists to obtain TE network paths minimizing the Segment Lists sizes. The SL encoding procedure is composed of two steps: i) the creation of an auxiliary graph representing the forwarding paths between the couple of source and destination nodes; ii) the solution of a Multi-commodity Flow (MCF) problem over the auxiliary graph. The performance evaluation shows that properly performing SL encoding allows to implement TE outcome with a reduced reconfiguration cost with respect to E2E tunneling and Hop-by-Hop solutions; moreover a significant advantage in terms of packets overhead is obtained.