Abstract
This paper analyses one key issue of designing reliable networks: assignment of spare capacities in transmission networks. The spare capacities are optimized to facilitate the restoration of single failures. This problem can be formulated as an integer linear program and approximated by its continuous relaxation. This model is based on arc-path formulation especially efficient for dealing with end-to-end rerouting and providing appreciable economies in comparison with local rerouting. The main idea of our method resides in a linear programming decomposition, which permits us to solve problems for medium and large networks. Our approach could be applicable to both STM and ATM-based networks. This method was tested successfully on medium and large DCS-meshed networks and some numerical examples are given to illustrate its performances in terms of CPU time and ratio of optimality.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
B.A. Coan, W.E. Lelet, M.P. Vecchi, A. Weinrib and L.T. Wu, Using distributed topology update and preplanned configurations to achieve trunk network survivability, IEEE Transactions on Realibility 40(4) (1991).
R. Doverspike, A Multi-layered model for survivability in intra-lata transport networks, in: Proc. of GLOBECOM'91 (1991) pp. 2025–2031.
W.D. Grover, T.D. Bllodeau and B.D. Venables, Near optimal spare capacity planning in a mesh restorable network, in: Proc. of GLOBECOM'91 (1991) pp. 2007–2012.
M. Herzberg, A decomposition approach to assign spare channels in self-healing networks, in: Proc. of GLOBECOM'93 (1993) pp. 1601–1605.
M. Herzberg and S.J. Bye, Spare-capacity assignment in survivable networks for multi-link and node failures with hop limits, in: NETWORKS'94, Budapest (1994) pp. 381–386.
G.L. Nemhauser and L.A. Wolsey, Integer and Combinatorial Optimization (Wiley Interscience, New York, 1988).
Y. Sakauchi, Y. Nishimura and S. Hasegawa, A self-healing network with an economical sparechannel assignment, in: Proc. of GLOBECOM'90 (1990) pp. 438–443.
T.H. Wu, H. Kobrinski, D. Ghosal and T.V. Lakshman, The impact of SONET digital cross-connect system architecture on distributed restoration, IEEE Journal on Selected Areas in Communications 12(1) (1994) 79–88.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Lutton, JL., Nace, D. & Carlier, J. Assigning spare capacities in mesh survivable networks. Telecommunication Systems 13, 441–451 (2000). https://doi.org/10.1023/A:1019164611304
Issue Date:
DOI: https://doi.org/10.1023/A:1019164611304