The main objective of this paper is to develop an effective evolutionary algorithm (EA) for the path-assignment problem in survivable connection-oriented networks. We assume a single-link failure scenario, which is the most common and frequently reported failure event. Since the network flow is modeled as a non-bifurcated multicommodity flow, the discussed optimization problem is NP-complete. Thus, we develop an effective heuristic algorithm based on an evolutionary algorithm. The main novelty of this work is that the proposed evolutionary algorithm consists of two levels. The "high" level applies typical EA operators. The "low" level is based on the idea of a hierarchical algorithm. However, the presented approach is not a classical hierarchical algorithm. Therefore, we call the algorithm quasi-hierarchical. We present its description and the results of simulation runs over various networks.
@article{bwmeta1.element.bwnjournal-article-amcv16i4p487bwm,
author = {Przewozniczek, Michal and Walkowiak, Krzysztof},
title = {Quasi-hierarchical evolution algorithm for flow assignment in survivable connection-oriented networks},
journal = {International Journal of Applied Mathematics and Computer Science},
volume = {16},
year = {2006},
pages = {487-502},
zbl = {1122.68151},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-amcv16i4p487bwm}
}
Przewozniczek, Michal; Walkowiak, Krzysztof. Quasi-hierarchical evolution algorithm for flow assignment in survivable connection-oriented networks. International Journal of Applied Mathematics and Computer Science, Tome 16 (2006) pp. 487-502. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-amcv16i4p487bwm/
[000] Corne D., Oates M. and Smith D. (Eds.) (2000): Telecommunications Optimization: Heuristic and Adaptive Techniques. - New York: Wiley.
[001] Davis L. (1996): Handbook of Genetic Algorithm. - New York: Van Nostrand Reinhold.
[002] Elbaum R. and Sidi M. (1996): Topological design of local area networks using genetic algorithms. - IEEEATM Trans. Networking, Vol. 4, No. 5, pp. 766-778.
[003] Grover W. (2004): Mesh-Based Survivable Networks: Options and Strategies for Optical, MPLS, SONET and ATM Networking. - Upper Saddle River, NJ: Prentice Hall.
[004] Fratta L., Gerla M. and Kleinrock L. (1973): The flow deviation method: An approach to store-and-forward communication network design. - Networks, Vol. 3, No. 2, pp. 97-133. | Zbl 1131.90321
[005] Jae ger B. and Tipper D. (2003): Prioritized traffic restoration in connection oriented QoS based networks. - Comput. Commun., Vol. 26, No. 18, pp. 2025-2036.
[006] Karp R. (1975): On the computational complexity of combinatorical problems. - Networks, Vol. 5, No. 1, pp. 45-68. | Zbl 0324.05003
[007] Kasprzak A. (2003): Exact and approximate algorithms for topological design of wide area networks with non-simultaneous single commodity flows. - Lect. Notes Comput. Sci., Vol. 2660, pp. 799-808. | Zbl 1188.68028
[008] Kwaśnicka H. (1998): Genetic and Evolutionary Algorithms-an Overview. - Wrocław: University of Technology Press.
[009] Michalewicz Z. (1996): Genetic Algorithms + Data Structures = Evolution Programs, 3-rd Ed. - Berlin: Springer. | Zbl 0841.68047
[010] Murakami K. and Kim H. (1996): Virtual path routing for survivable ATM networks. - IEEEATM Trans. Networking, Vol. 4, No. 2, pp. 22-39.
[011] Nilsson P., Pioro M. and Dziong Z. (2003): Link protection within an existing backbone network. - Proc. Int. Network Optimization Conf., INOC, Evry, Paris, pp. 435-440.
[012] Pioro M. and Medhi D. (2004): Routing, Flow, and Capacity Design in Communication and Computer Networks. - San Francisco: Morgan Kaufman. | Zbl 1069.68021
[013] Przewoźniczek M. (2003): Genetic algorithms in use of routes finding in computer connection oriented networks. - M.Sc. thesis, Wrocław University of Technology, Wrocław, Poland.
[014] Przewoźniczek M. and Walkowiak K. (2005): Evolutionary algorithm for congestion problem in connection-oriented networks. - Lect. Notes Comput. Sci., Vol. 3483, pp. 802-811.
[015] Radcliffe N. and Surry P. (1994): Co-operation through hierarchical competition in genetic data mining. - Tech. Rep., No. EPCC-TR94-09, Edinburgh Parallel Computing Center.
[016] Riedl A. (1998): A versatile genetic algorithm for network planning. - Proc. 4-th s Open European Summer School, EUNICE'98, Munich, Germany, pp. 97-103.
[017] Riedl A. (2002): A hybrid genetic algorithm for routing optimization in IP networks utilizing bandwidth and delay metrics. - Proc. IEEE Workshop s IP Operations and Management, IPOM, Dallas, pp. 166-170.
[018] Walkowiak K. (2001): Genetic approach to virtual paths assignment in survivable ATM networks. - Proc. 7-th Int. Conf. s Soft Computing MENDEL, Brno, Czech Republic, pp. 13-18.
[019] Walkowiak K. (2003): A new approach to survivability of connection oriented networks. - Lect. Notes Comput. Sci., Vol. 2657, pp. 501-510. | Zbl 1033.68528
[020] Walkowiak K. (2004a): A branch and bound algorithm for primary routes assignment in survivable connection oriented networks. - Comput. Optim. Applic., Vol. 27, No. 2, pp. 149-171. | Zbl 1044.90093
[021] Walkowiak K. (2004b): A new method of primary routes selection for local restoration. - Lect. Notes Comput. Sci., Vol. 3042, pp. 1024-1035.
[022] Walkowiak K. (2004c): Survivable online routing for MPLS traffic engineering. - Lect. Notes Comput. Sci., Vol. 3266, pp. 288-297.
[023] Walkowiak K. (2006): Lagrangean heuristic for primary routes assignment in survivable connection-oriented networks. - Tech. Rep., Wrocław University of Technology, Wrocław. | Zbl 1155.68316
[024] White A.R.P., Mann J.W. and Smith G.D. (1999): Genetic algorithms and network ring design. - Annals Oper. Res., Vol. 86, No. 1, pp. 347-371. | Zbl 0921.90074