An evaluation of approximate network optimization methods for improving ip-level fast protection with loop-free alternates

Demand for fast failure recovery in modern IP-based networks has become compelling recently. Loop-Free Alternates (LFA) is a simple IP Fast ReRoute (IPFRR) specification proposed by the IETF that does not require profound changes to the network infrastructure before deployment. However this simplicity has a disadvantage, in that usually LFA does not provide complete protection for all possible failure cases in a general topology. The LFA graph extension problem asks for adding new links to the network in an attempt to improve the failure case coverage. Unfortunately, this problem is NP-complete. In this paper, we give a detailed graph model for this problem, for the first time formulating it both for the link and node protecting cases, and we propose several fast approximation algorithms to solve it. We compare the performance of the algorithms in extensive numerical studies and we conclude that the optimum can be approximated well in most cases relevant to practice.