An Efficient Calculation for TI-LFA Rerouting Path

Recently, segment routing, which is a modern forwarding mechanism, and Topology Independent Loop-free Alternate, which is an IP fast-reroute method using segment routing, have been proposed and have begun to be applied to real networks. When a failure occurs in a network, TI-LFA quickly restores packet forwarding without waiting for other nodes to update their routing tables. It does so by using segment routing to forward sections that may cause loops in the rerouting path. However, determining the segment routing sections has a high computational cost because it requires computation for each destination. This paper therefore proposes an algorithm to determine the egress node that is the exit of the segment routing section for all destination nodes with only three shortest-path tree calculations. The evaluation results of the proposed algorithm showed that the average tunnel lengths are at most 2.0 to 2.2 hops regardless of the size of the network. I also showed that the computational complexity of the proposed algorithm is O(N log N).

Automated summary

This paper introduces the concepts of segment routing and TI-LFA and their application in real networks. To address the high computational cost of determining segment routing sections, an algorithm is proposed that only requires three shortest-path tree calculations to determine the egress node of the segment routing section for all destination nodes.