Expect the Unexpected : Sub-Second Optimization for Segment Routing

We study how to perform traffic engineering at extremely-small time scale with segment routing, addressing a critical need for modern wide area networks. Prior work has shown that segment routing enables to better engineer traffic thanks to its ability to create detours in forwarding paths, at scale. Two main approaches have been explored so far, respectively based on integer linear programming and constraint programming. However, none of the previous works deeply investigated how much the proposed algorithms allow network controllers to quickly react to unexpected traffic changes and failures. We highlight limitations of previous algorithms in terms of required execution time. We therefore propose a new approach, based on local search that support recomputation of segment-routing paths complying with load requirements. Our experiments show that our solution is able to answer critical network situations in (sub-)seconds on large IP network.

• Algorithms and Theory

• Machine Intelligence