FOLC-SR: Fast and Optimal Loop-free Convergence using Segment Routing for link-state protocols.

In large networks, operators usually rely on a link-state IGP protocol (such as IS-IS or OSPF) to route packets inside their network. In case of network topology changes, routers can efficiently recompute their shortest paths toward each destination by using the Dijkstra's algorithm. Even if routers update their forwarding table (FIB) very quickly, some transient forwarding contradictions may arise during this short period. Such inconsistencies may form transient forwarding loops, called micro-loops, known to provoke traffic losses, bandwidth waste, delay and jitter. In this paper, we present a new mechanism, built on top of Segment Routing, enforcing during the IGP convergence forwarding along shortest paths for any IGP topology change, and hence preventing micro-loops. The main difficulty resides in the ability to compute protections very quickly while minimizing the number of segments to remain backward-compatible with legacy equipments. The contributions of this paper are threefold. First, we introduce FOLC-SR, the first protection mechanism able to guarantee optimal forwarding for any IGP topology change. Second, we provide an open-source proof of concept of our mechanism. Third, we prove the tractability of FOLC-SR and evaluate our proposal through simulations performed on real network topologies.