Geodesic
Quasi-hierarchical evolution algorithm for flow assignment in survivable connection-oriented networks
International Journal of Applied Mathematics and Computer Science, Tome 16 (2006) no. 4, pp. 487-502.

Voir la notice de l'article provenant de la source Library of Science

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.
Keywords: evolution algorithm, optimization, connection-oriented networks
Mots-clés : algorytm ewolucyjny, optymalizacja, sieć komputerowa 
@article{IJAMCS_2006_16_4_a5,
     author = {Przewo\'zniczek, M. and Walkowiak, K.},
     title = {Quasi-hierarchical evolution algorithm for flow assignment in survivable connection-oriented networks},
     journal = {International Journal of Applied Mathematics and Computer Science},
     pages = {487--502},
     publisher = {mathdoc},
     volume = {16},
     number = {4},
     year = {2006},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/IJAMCS_2006_16_4_a5/}
}
TY  - JOUR
AU  - Przewoźniczek, M.
AU  - Walkowiak, K.
TI  - Quasi-hierarchical evolution algorithm for flow assignment in survivable connection-oriented networks
JO  - International Journal of Applied Mathematics and Computer Science
PY  - 2006
SP  - 487
EP  - 502
VL  - 16
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/IJAMCS_2006_16_4_a5/
LA  - en
ID  - IJAMCS_2006_16_4_a5
ER  - 
%0 Journal Article
%A Przewoźniczek, M.
%A Walkowiak, K.
%T Quasi-hierarchical evolution algorithm for flow assignment in survivable connection-oriented networks
%J International Journal of Applied Mathematics and Computer Science
%D 2006
%P 487-502
%V 16
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/IJAMCS_2006_16_4_a5/
%G en
%F IJAMCS_2006_16_4_a5
Przewoźniczek, M.; Walkowiak, K. Quasi-hierarchical evolution algorithm for flow assignment in survivable connection-oriented networks. International Journal of Applied Mathematics and Computer Science, Tome 16 (2006) no. 4, pp. 487-502. http://geodesic.mathdoc.fr/item/IJAMCS_2006_16_4_a5/

[1] Corne D., Oates M. and Smith D. (Eds.) (2000): Telecommunications Optimization: Heuristic and Adaptive Techniques. - New York: Wiley.

[2] Davis L. (1996): Handbook of Genetic Algorithm.-New York: Van Nostrand Reinhold.

[3] Elbaum R. and Sidi M. (1996): Topological design of local area networks using genetic algorithms. - IEEE/ATM Trans. Networking, Vol. 4, No. 5, pp. 766-778.

[4] Grover W. (2004): Mesh-Based Survivable Networks: Options and Strategies for Optical, MPLS, SONET and ATM Networking. Upper Saddle River, NJ: Prentice Hall.

[5] 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.

[6] Jæger B. and Tipper D. (2003): Prioritized traffic restoration in connection oriented QoS based networks. - Comput. Commun., Vol. 26, No. 18, pp. 2025-2036.

[7] Karp R. (1975): On the computational complexity of combinatorical problems. -Networks, Vol. 5, No. 1, pp. 45-68.

[8] Kasprzak A. (2003): Exact and approximate algorithms for topological design of wide area networks with nonsimultaneous single commodity flows.-Lect. Notes Comput. Sci., Vol. 2660, pp. 799-808.

[9] Kwaśnicka H. (1998): Genetic and Evolutionary Algorithms-an Overview. - Wrocław: University of Technology Press.

[10] Michalewicz Z. (1996): Genetic Algorithms + Data Structures = Evolution Programs, 3-rd Ed.- Berlin: Springer.

[11] Murakami K. and Kim H. (1996): Virtual path routing for survivable ATM networks. - IEEE/ATM Trans. Networking, Vol. 4, No. 2, pp. 22-39.

[12] Nilsson P., Pióro M. and Dziong Z. (2003): Link protection within an existing backbone network.-Proc. Int. Network Optimization Conf., INOC, Evry, Paris, pp. 435-440.

[13] Pióro M. and Medhi D. (2004): Routing, Flow, and Capacity Design in Communication and Computer Networks.-San Francisco: Morgan Kaufman.

[14] 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.

[15] Przewoźniczek M. and Walkowiak K. (2005): Evolutionary algorithm for congestion problem in connection-orientednetworks.-Lect. Notes Comput. Sci., Vol. 3483, pp. 802-811.

[16] 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.

[17] Riedl A. (1998): A versatile genetic algorithm for network planning. - Proc. 4-th Open European Summer School, EUNICE' 98, Munich, Germany, pp. 97-103.

[18] Riedl A. (2002): A hybrid genetic algorithm for routing optimization in IP networks utilizing bandwidth and delay metrics. - Proc. IEEE Workshop IP Operations and Management, IPOM, Dallas, pp. 166-170.

[19] Walkowiak K. (2001): Genetic approach to virtual paths assignment in survivable ATM networks. - Proc. 7-th Int. Conf. Soft Computing MENDEL, Brno, Czech Republic, pp. 13-18.

[20] Walkowiak K. (2003): A new approach to survivability of connection oriented networks. - Lect. Notes Comput. Sci., Vol. 2657, pp. 501-510.

[21] 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.

[22] Walkowiak K. (2004b): A new method of primary routes selection for local restoration. - Lect. Notes Comput. Sci., Vol. 3042, pp. 1024-1035.

[23] Walkowiak K. (2004c): Survivable online routing for MPLS traffic engineering. - Lect. Notes Comput. Sci., Vol. 3266, pp. 288-297.

[24] Walkowiak K. (2006): Lagrangean heuristic for primary routes assignment in survivable connection-oriented networks. - Tech. Rep., Wrocław University of Technology, Wrocław.

[25] 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.