Optimizing IGP link costs for improving IP-level resilience with Loop-Free Alternates

The IP Fast ReRoute-Loop-Free Alternates (LFA) standard is a simple and easily deployable technique to provide fast failure protection right in the IP layer. To our days, most major IP device vendors have products on the market that support LFA out of the box. Unfortunately, LFA usually cannot protect all possible failure scenarios in a general network topology. Therefore, it is crucial to develop LFA-based network optimization tools in order to assist operators in deciding whether deploying LFA in their network will supply sufficient resiliency. In this paper, we give a new graph theoretical framework for analyzing LFA failure case coverage, and then we investigate how to optimize the Interior Gateway Protocol (IGP) link costs in order to maximize the number of protected failure scenarios. We show that this problem is NP-complete even in a very restricted formulation, and we give an exact algorithm as well as a complete family of heuristics to solve it. Our simulation studies indicate that a deliberate tuning of the approximation strategy can significantly improve the quality of the IGP link costs, and we conclude that LFA cost optimization has the potential for boosting LFA-based resilience in most operational networks significantly.