Traffic Engineering in Segment Routing using MILP
Xiaoqian Li, Kwan Lawrence Yeung · 2019
For a given network topology and traffic matrix, we study the problem of finding a set of K-segment paths to carry all the traffic such that the maximum link utilization is minimized. A K-segment path is a path that can be identified by no more than K segment identifiers (SIDs). A SID can be either a node-SID or an adjacency-SID. But existing linear programming based solutions only support node-SIDs. In this paper, we first enhance an existing linear programming formulated for 2-segment paths only to support adjacency-SIDs. We call it e2-LP. Then a mixed integer linear programming, or K-MILP, is formulated for optimal solutions using K-segment paths. To reduce the complexity of K-MILP, a simplified formulation (K-sMILP) is also designed. Numerical results show that our proposed linear programs consistently outperform the existing solutions.