Copyright and Licensing
Articles accepted for publication will be licensed under the Creative Commons BY-NC-SA. Authors must sign a non-exclusive distribution agreement after article acceptance.
A GRASP algorithm with tree based local search for designing a survivable wide area network backbone
Keywords:
survivability, node connectivity, meta-heuristics, GRASP, topological designAbstract
System survivability is the ability to give service in spite of failures of some of the components. To assure survivability is an important goal when designing a communications network backbone, to ensure that it can resist to failures in the switch sites as well as in the connection lines. Previous work has employed a Greedy Randomized Adaptive Search Procedure (GRASP), based on path algorithms, to build low cost network topologies which comply with heterogeneous node-connectivity requirements, which can model the survivability goals. In this work, we present another variant of the GRASP procedure, based on a tree search, which obtains good results in topologies with a large number of switch nodes.
Downloads
Download data is not yet available.
References
[1] M.Baıou and A.R. Mahjoub, “Steiner 2-edge-connected subgraph polytopes on series-parallel graphs”, SIAM Journal on Discrete Mathematics 10 (3), pages 505-514 (1997).
[2] B. Bollobas, Modern Graph Theory, Springer (1998).
[3] H. Cancela, F. Robledo and G. Rubino, “Network design with node connectivity constraints”, LANC’03 (IFIP/ACM Latin America Networking Conference 2003), October 3-5, La Paz, Bolivia (2003).
[4] H. Cancela, F. Robledo and G. Rubino, “A GRASP algorithm for the Generalized Steiner Problem with Node Connectivity Constraints”, Internal Report IRISA 1586 (2003).
[5] T.A. Feo and M.G.C Resende, “A probabilistic heuristic for a computationally difficult set covering problem”, Operations Research Letters, 8:67-71 (1989).
[6] T.A. Feo and M.G.C Resende, “Greedy randomized adaptive search procedures”, Journal of Global Optimization, 6:109-133 (1995).
[7] M. Grotschel, C.L. Monma, and M. Stoer, “Polyhedral and computational investigations for designing communication networks with high survivability requirements”, Operations Research 43 (1995), pages 1012-1024.
[8] A.R. Mahjoub, “Two-edge-connected spanning subgraphs and polyhedra”, Mathematical Programming 64 (1994), pages 199-208.
[9] M. Priem and F. Priem, “Ingenierie des WAN”, ISBN 2-10-004510-5, Dunod InterEditions (1999).
[10] F. Robledo, “Dise ̃ no topológico de redes : casos de estudio The generalized Steiner problem y The Steiner 2-Edge-Connected subgraph problem”. Master Thesis (2000). F. de Ingeniería, UDELAR, Montevideo, Uruguay.
[11] F. Robledo and O. Viera, “A parallel algorithm for the Steiner 2-edge-survivable network problem”, Internal Report 1504, IRISA (2002).
[12] K. Stiglitz, P. Weiner, D. J. Kleitman, “The design of minimum-cost survivable networks”, IEEE Trans. on Circuit Theory, CT-16, 4 (1969) pages 455-460.
[13] M. Stoer, “Design of Survivable Networks”, Lecture Notes in Mathematics, ISBN 3-540-56271-0, ISBN 0-387-56271-0, Springer-Verlag (1996).
[14] M.G.A. Verhoeven, M.E.M. Severens, and E.H.L. Aarts, “Local search for Steiner trees in graphs”, In Modern Heuristics Search Methods, V.J. Rayward-Smith et al. (Eds.), John Wiley, 117-129 (1996).
[15] P. Winter, “Generalized Steiner problem in series-parallel networks”, Journal of Algorithms 7 (1986), pages 549-566.
[16] P. Winter, “Steiner problem in networks: A survey”, Networks 17 (1987), pages 129-167.
[17] J. Y. Yen, “Finding the K shortest loopless paths in a network”, Management Science 17 (1971), pages 712-716.
[2] B. Bollobas, Modern Graph Theory, Springer (1998).
[3] H. Cancela, F. Robledo and G. Rubino, “Network design with node connectivity constraints”, LANC’03 (IFIP/ACM Latin America Networking Conference 2003), October 3-5, La Paz, Bolivia (2003).
[4] H. Cancela, F. Robledo and G. Rubino, “A GRASP algorithm for the Generalized Steiner Problem with Node Connectivity Constraints”, Internal Report IRISA 1586 (2003).
[5] T.A. Feo and M.G.C Resende, “A probabilistic heuristic for a computationally difficult set covering problem”, Operations Research Letters, 8:67-71 (1989).
[6] T.A. Feo and M.G.C Resende, “Greedy randomized adaptive search procedures”, Journal of Global Optimization, 6:109-133 (1995).
[7] M. Grotschel, C.L. Monma, and M. Stoer, “Polyhedral and computational investigations for designing communication networks with high survivability requirements”, Operations Research 43 (1995), pages 1012-1024.
[8] A.R. Mahjoub, “Two-edge-connected spanning subgraphs and polyhedra”, Mathematical Programming 64 (1994), pages 199-208.
[9] M. Priem and F. Priem, “Ingenierie des WAN”, ISBN 2-10-004510-5, Dunod InterEditions (1999).
[10] F. Robledo, “Dise ̃ no topológico de redes : casos de estudio The generalized Steiner problem y The Steiner 2-Edge-Connected subgraph problem”. Master Thesis (2000). F. de Ingeniería, UDELAR, Montevideo, Uruguay.
[11] F. Robledo and O. Viera, “A parallel algorithm for the Steiner 2-edge-survivable network problem”, Internal Report 1504, IRISA (2002).
[12] K. Stiglitz, P. Weiner, D. J. Kleitman, “The design of minimum-cost survivable networks”, IEEE Trans. on Circuit Theory, CT-16, 4 (1969) pages 455-460.
[13] M. Stoer, “Design of Survivable Networks”, Lecture Notes in Mathematics, ISBN 3-540-56271-0, ISBN 0-387-56271-0, Springer-Verlag (1996).
[14] M.G.A. Verhoeven, M.E.M. Severens, and E.H.L. Aarts, “Local search for Steiner trees in graphs”, In Modern Heuristics Search Methods, V.J. Rayward-Smith et al. (Eds.), John Wiley, 117-129 (1996).
[15] P. Winter, “Generalized Steiner problem in series-parallel networks”, Journal of Algorithms 7 (1986), pages 549-566.
[16] P. Winter, “Steiner problem in networks: A survey”, Networks 17 (1987), pages 129-167.
[17] J. Y. Yen, “Finding the K shortest loopless paths in a network”, Management Science 17 (1971), pages 712-716.
Downloads
Published
2004-04-01
Issue
Section
Original Articles
License
How to Cite
[1]
“A GRASP algorithm with tree based local search for designing a survivable wide area network backbone”, JCS&T, vol. 4, no. 01, pp. p. 52–58, Apr. 2004, Accessed: Apr. 17, 2026. [Online]. Available: https://journal.info.unlp.edu.ar/JCST/article/view/914
