Path Diversity Protection in Two-Layer Networks
DOI:
https://doi.org/10.26636/jtit.2009.3.934Keywords:
link dimensioning, path diversity, resilient routing, two-layer network optimizationAbstract
The paper addresses an optimization problem related to dimensioning links in a resilient two-layer network. A particular version of the problem which assumes that links of the upper layer are supported by unique paths in the lower layer is considered. Two mixed-integer programming formulations of this problem are presented and discussed. Direct resolving of these formulations requires pre-selection of "good" candidate paths in the upper layer of the network. Thus, the paper presents an alternative approach which is based on decomposing the resolution process into two phases, resolved iteratively. The first phase subproblem is related to designing lower layer path flows that provide the capacities for the logical links of the upper layer. The second phase is related to designing the flow patterns in the upper layer with protection assured through diversity of paths. In this phase we take into account the failures of the logical links that result from the failures of the lower layer links (so called shared risk link groups).
Downloads
References
[1] S. Borne, E. Gourdin, B. Liau, and A. R. Mahjoub, „Design of survivable IP-over-optical networks”, in Proc. INOC’2003 Conf., Paris, France, 2003, pp. 114-118.
View in Google Scholar
[2] M. Pióro and D. Medhi, Routing, Flow, and Capacity Design in Communication and Computer Networks. San Francisco: Morgan Kaufmann, 2004.
View in Google Scholar
[3] D. Coudert, P. Datta, S. Perennes, H. Rivano, and M.-E. Voge, „Shared risk resource group: complexity and approximability issues”, Paral. Proces. Lett., vol. 17, no. 2, pp. 169-184, 2007.
View in Google Scholar
[4] M. Dzida, T. Śliwiński, M. Zagożdżon, W. Ogryczak, and M. Pióro, „Path generation for a class of survivable network design problems”, in NGI 2008 Conf. Next Gener. Internet Netw., Cracow, Poland, 2008.
View in Google Scholar
[5] G. B. Dantzig and P. Wolfe, „The decomposition algorithm for linear programming”, Oper. Res., vol. 8, no. 1, pp. 101-111, 1960.
View in Google Scholar
[6] T. Stidsen et al., „Optimal routing with single backup path protection”, in Proc. INOC 2007 Conf., Spa, Belgium, 2007.
View in Google Scholar
[7] S. Irnich and G. Desaulniers, „Shortest path problems with resource constraints”, in Column Generation, G. Desaulniers, J. Desrosier, and M. M. Solomon, Eds. New York: Springer, 2005, pp. 33-65.
View in Google Scholar
Downloads
Submitted
Published
Issue
Section
License
Copyright (c) 2023 Journal of Telecommunications and Information Technology
This work is licensed under a Creative Commons Attribution 4.0 International License.
