We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Optimization methods for improving IP-level fast protection for local shared risk groups with Loop-Free Alternates.
- Authors
Nagy, Máté; Tapolcai, János; Rétvári, Gábor
- Abstract
Lately, demand for fast failure recovery in IP networks has become compelling. The Loop-Free Alternates (LFA) specification is a simple IP Fast ReRoute (IPFRR) scheme proposed by the IETF that does not require profound changes to the network infrastructure before deployment. However, this simplicity comes at a severe price, because LFA does not provide complete protection for all possible failure cases in a general topology. This is even more so if network components are prone to fail jointly. In this paper, we study an important network optimization problem arising in this context, the so called LFA graph extension problem, which asks for augmenting the topology with new links in an attempt to improve the LFA failure case coverage. Unfortunately, this problem is NP-complete. The main contributions of the paper are a novel extension of the bipartite graph model for the LFA graph extension problem to the multiple-failure case using the model of Shared Risk Groups, and a suite of accompanying heuristics to obtain approximate solutions. We also 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.
- Subjects
IP networks; NETWORK failures (Telecommunication); MATHEMATICAL optimization; BIPARTITE graphs; GRAPH extension; HEURISTIC algorithms
- Publication
Telecommunication Systems, 2014, Vol 56, Issue 1, p103
- ISSN
1018-4864
- Publication type
Article
- DOI
10.1007/s11235-013-9822-y