FOLC-SR: Fast and Optimal Loop-free IGP Convergence using Segment Routing

Large networks usually rely a link-state IGP protocol (such as IS-IS or OSPF) to route packets inside their network. In case of topology change, routers recompute their shortest paths toward each destination using Dijkstra's algorithm. Even id routers update their forwarding table (FIB) quickly, transient forwarding contradictions between routers may arise during IGP convergence, forming transient forwarding loops, called micro-loops. These provoke traffic losses, bandwidth waste, delay and jitter. In this paper, we present a new mechanism, built on top of Segment Routing, called FOLC-SR. Our mechanism prevents micro-loops, by enforcing for any arbitrary topology change(s), correct forwarding along the new shortest paths during IGP convergence. The main challenge resides in the ability to compute protections quickly, while minimizing the number of segments to ensure backward-compatibility with legacy equipments. The contributions of this paper are threefold. First, we formalized the notion of P-space, the set of destinations that can be reached by a router without being impacted by a microloop. Second, we introduce FOLC-SR, the first decentralized protection mechanism that guarantees optimal forwarding for any burst of IGP topology changes. We also provide an opensource implementation. Third, we evaluate our proposal through simulations performed on real network topologies.