Abstract
The complete topology design problem of survivable mesh-based transport networks is to address simultaneously design of network topology, working path routing, and spare capacity allocation based on span-restoration. Each constituent problem in the complete design problem could be formulated as an Integer Programming (IP) and is proved to be \(\mathcal{NP}\) -hard. Due to a large amount of decision variables and constraints involved in the IP formulation, to solve the problem directly by exact algorithms (e.g. branch-and-bound) would be impractical if not impossible. In this paper, we present a two-level evolutionary approach to address the complete topology design problem. In the low-level, two parameterized greedy heuristics are developed to jointly construct feasible solutions (i.e., closed graph topologies satisfying all the mesh-based network survivable constraints) of the complete problem. Unlike existing “zoom-in”-based heuristics in which subsets of the constraints are considered, the proposed heuristics take all constraints into account. An estimation of distribution algorithm works on the top of the heuristics to tune the control parameters. As a result, optimal solution to the considered problem is more likely to be constructed from the heuristics with the optimal control parameters. The proposed algorithm is evaluated experimentally in comparison with the latest heuristics based on the IP software CPLEX, and the “zoom-in”-based approach on 28 test networks problems. The experimental results demonstrate that the proposed algorithm is more effective in finding high-quality topologies than the IP-based heuristic algorithm in 21 out of 28 test instances with much less computational costs, and performs significantly better than the “zoom-in”-based approach in 19 instances with the same computational costs.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Al-Rumaih, A., Tipper, D., Liu, Y., Norman, B.A.: Spare capacity planning for survivable mesh networks. In: Proceedings of the IFIP-TC6 / European Commission International Conference on Broadband Communications, High Performance Networking, and Performance of Communication Networks. Lecture Notes in Computer Science, pp. 957–968. Springer, Berlin (2000)
Álvarez, A.M., Gonzälez, J.L., De-Alba, K.: Scatter search for a network design problem. Technical Report PISIS-2003-02, Universidad Autónoma de Nuevo León, Facultad de Ingeniería Mecánica y Eléctrica, División de Posgrado en Ingeniería de Sistemas, Mexico (2003)
Anticona, M.T., Villegas, C.E.: Design of ant colony-based ant route for solve the OSPF problem. CERMA, pp. 386–394 (2007)
Baluja, S.: Population-based incremental learning: a method for integrating genetic search based function optimization and competitive learning. Technical Report, Carnegie Mellon University (1994)
Buriol, L.S., Resende, M.C.G., Thorup, M.: Survivable IP network design with OSPF routing. Networks 49(1), 51–64 (2007)
Boorstyn, R., Frank, H.: Large-scale network topological optimization. IEEE Trans. Commun. COM-25 1, 29–47 (1977)
Cancela, H., Robledo, F., Rubino, G.: A GRASP algorithm with tree based local search for designing a survivable Wide area network backbone. J. Comput. Sci. Technol. 4(1), 52–58 (2004)
Chou, W., Gerla, M., Frank, H., Eckl, J.: A cut saturation algorithm for topological design of packet switched networks. In: Proc. IEEE National Telcom. Conf., pp. 1074–1085 (1974)
Cinkler, T., Henk, T., Gordos, G.: Stochastic algorithms for thrifty single-failure-protected networks. In: Proceedings of Design of Reliable Communication Networks, Munich, Germany, pp. 299–303 (2000)
Cook, W.J., Cunningham, W.H., Pulleyblank, W.R., Schrijver, A.: Combinatorial Optimization. Wiley, New York (1998)
Corne, D., Dorigo, M., Glover, F. (eds.): New Ideas in Optimization. McGraw–Hill, New York (1999)
Dorigo, M., Maniezzo, V., Colorni, A.: The ant system: optimization by a colony of cooperating agents. IEEE Trans. Syst. Man Cybern., Part B 26(1), 29–41 (1996)
Faria, Jr.H., Binato, S., Resende, M.G.C., Falcao, D.M.: Power transmission network design by greedy randomized adaptive path relinking. IEEE Trans. Power Syst. (2004)
Ferentinos, K.P., Tsiligindis, T.A.: A memetic algorithm for dynamic design of wireless sensor network. CEC 2007, pp. 2774–2781
Gavish, B.: Topological design of computer communication networks—the overall design problem. Eur. J. Oper. Res. 58, 149–172 (1992)
Gil, C., Banos, R., Montoya, M.G., Gomez, J.: Performance of simulated annealing, tabu search and evolutionary algorithms for multi-objective network partitioning. 1, 55–64 (2006)
Glover, F., Laguna, M.: Tabu Search. Kluwer Academic, Dordrecht (1998)
Glover, F., Laguna, M., Marti, R.: Fundamentals of scatter search and path relinking. Control Cybern. 39(3), 653–684 (2000)
Grover, W.D., Doucette, J.: Topological design of survivable mesh-based transport networks. Ann. Oper. Res. 106, 79–125 (2001)
Hsu, C.-Y., Wu, J., Wang, S., Hong, C.: Survivable and delay-guaranteed backbone wireless mesh network design. J. Parallel Distrib. Comput. 68, 306–320 (2008)
Jan, R.H.: Design of reliable networks. Comput. Oper. Res. 20(1), 25–34 (1993)
Kershenbaum, A.: Telecommunications Network Design Algorithms. McGraw–Hill, New York (1993)
Kershenbaum, A., Kermani, P., Grover, G.A.: MENTOR: An algorithm for mesh network topological optimization and routing. IEEE Trans. Commun. 39(3), 503–513 (1991)
Larrañaga, P., Lozano, J.A.: Estimation of Distribution Algorithms: a New Tool for Evolutionary Computation. Kluwer Academic, Dordrecht (2002)
Mukherjee, B.: WDM optical communication networks: progress and challenges. IEEE J. Sel. Areas Commun. 18(10), 1810–1824 (2000)
Ooubutra, M., Avemprayoon, P., Wnrdkein, P.: Topological communication network design using ant colony optimization. In: Proceedings of the 7th Conference on Advanced Communication Technology, vol. 2, pp. 1147–1151 (2005)
Pickavet, M., Demeester, P.: A zoom-in approach to design SDH mesh-restorable networks. J. Heur. 6(1), 103–126 (2000)
Pierre, S., Elgibaoui, A.: A tabu-search approach for designing computer-network topologies with unreliable components. IEEE Trans. Reliab. 46(3), 350–359 (1997)
Randall, M., McMahon, G., Sugden, S.: A simulated annealing approach to communication network design. J. Comb. Optim. 6, 55–65 (2002)
Runggeratigul, S.: A memetic algorithm for communication network design taking into consideration an existing network. Appl. Optim. 615–626 (2004)
Sakauchi, H., Nishimura, Y., Hasegawa, S.: A self-healing network with an economical spare-channel assignment. In: Proc. IEEE Globecom, pp. 438–444 (1990)
Shen, J., Xu, F., Zheng, P.: A tabu search algorithm for the routing and capacity assignment problem in computer network. 32(11), 2785–2800 (2005)
Taheri, J., Zomaya, A.Y.: A simulated annealing approach for mobile location management. 30(4), 714–730 (2007)
Wille, E.C.G., Mellia, M., Leonardi, E., Marsan, M.A.: Topological design of survivable IP networks using meta-heuristic approaches. In: The 3rd International Workshop on QoS in Multiservice IP Networks (2005)
Zhang, Q., Sun, J., Xiao, G., Tsang, E.: Evolutionary algorithm refining a heuristic: a hybrid method for shared path protection in WDM networks under SRLG constraints. IEEE Trans. Syst. Man Cybern., Part B 37(1), 51–61 (2007)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Sun, J., Zhang, Q. & Li, J. Two-level evolutionary approach to the survivable mesh-based transport network topological design. J Heuristics 16, 723–744 (2010). https://doi.org/10.1007/s10732-009-9115-5
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10732-009-9115-5