We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Robust FIPP p-cycles against dual link failures.
- Authors
Jaumard, Brigitte; Hoang, Hai; Kien, Do
- Abstract
We propose a new generic flow formulation for Failure-Independent Path-Protecting (FIPP) p-cycles subject to multiple failures. While our new model resembles the decomposition model formulation proposed by Orlowski and Pioro (Networks, ) in the case of classical shared path protection, its originality lies in its adaptation to FIPP p-cycles. When adapted to that last pre-configured pre-cross connected protection scheme, the bandwidth sharing constraints must be handled in a different way in order to take care of the sharing along the FIPP p-cycles. It follows that, instead of a polynomial-time solvable pricing problem as in the model of Orlowski and Pioro (Networks, ), we end up with a much more complex pricing problem, which has an exponential number of constraints due to some subtour elimination constraints. Consequently, in order to efficiently solve the pricing problem, we consider: (i) a hierarchical decomposition of the original pricing problem; (ii) heuristics in order to go around the large number of constraints in the pricing problem. Performance evaluation is made in the case of FIPP p-cycles subject to dual failures. For small to medium size networks, the proposed model remains fairly scalable for increasing percentages of dual failures, and requires much less bandwidth than p-cycle protection schemes (ratio varies from 2 to 4). For larger networks, heuristics are required in order to keep computing times reasonable. In the particular case of single link failures, it compares very favorably (5 to 10 % of bandwidth saving) to the previously proposed column generation ILP model of Rocha, Jaumard and Stidsen (Telecommun. Syst., ).
- Subjects
NETWORK failures (Telecommunication); POLYNOMIALS; HEURISTIC algorithms; MATHEMATICAL models of pricing; BANDWIDTH allocation
- Publication
Telecommunication Systems, 2014, Vol 56, Issue 1, p157
- ISSN
1018-4864
- Publication type
Article
- DOI
10.1007/s11235-013-9825-8