Paper Info
Title
Optimization methods for improving IP-level fast protection for local shared risk groups with Loop-Free Alternates
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.
Year
DOI
Venue
2014
10.1007/s11235-013-9822-y
Telecommunications Systems
Keywords
Field
DocType
IP Fast ReRoute,Loop-Free Alternates,Link and node protection,Heuristics
Fast reroute,Graph,Software deployment,General topology,Suite,Computer science,Bipartite graph,Computer network,Real-time computing,Heuristics,Optimization problem,Distributed computing
Journal
Volume
Issue
ISSN
56
1
1018-4864
Citations 
PageRank 
References 
2
0.37
31
Authors
3
Name
Order
Citations
PageRank
Máté Nagy141.07
János Tapolcai236441.42
Gábor Rétvári319424.87