Quasi-hierarchical evolution algorithm for flow assignment in survivable connection-oriented networks

• Autorzy: Michal Przewozniczek , Krzysztof Walkowiak
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

optimization; evolution algorithm; connection-oriented networks

• Wydawca: University of Zielona Gora Press
• Czasopismo: International Journal of Applied Mathematics and Computer Science
• Rocznik: 2006
• Tom: 16
• Numer: 4
• Strony: 487-502

Daty

wydano

2006

otrzymano

2005-12-01

poprawiono

2006-08-10

Twórcy

autor

Michal Przewozniczek

• Faculty of Computer Science and Management, Wrocław University of Technology, ul. Wybrzeże Wyspiańskiego 27, 50-370 Wrocław, Poland

autor

Krzysztof Walkowiak

• Chair of Systems and Computer Networks, Faculty ofElectronics, Wrocław University of Technology, ul. Wybrzeże Wyspiańskiego 27, 50-370 Wrocław, Poland

Bibliografia

• Corne D., Oates M. and Smith D. (Eds.) (2000): Telecommunications Optimization: Heuristic and Adaptive Techniques. - New York: Wiley.
• Davis L. (1996): Handbook of Genetic Algorithm. - New York: Van Nostrand Reinhold.
• 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.
• Grover W. (2004): Mesh-Based Survivable Networks: Options and Strategies for Optical, MPLS, SONET and ATM Networking. - Upper Saddle River, NJ: Prentice Hall.
• 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.
• 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.
• Karp R. (1975): On the computational complexity of combinatorical problems. - Networks, Vol. 5, No. 1, pp. 45-68.
• 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.
• Kwaśnicka H. (1998): Genetic and Evolutionary Algorithms-an Overview. - Wrocław: University of Technology Press.
• Michalewicz Z. (1996): Genetic Algorithms + Data Structures = Evolution Programs, 3-rd Ed. - Berlin: Springer.
• Murakami K. and Kim H. (1996): Virtual path routing for survivable ATM networks. - IEEEATM Trans. Networking, Vol. 4, No. 2, pp. 22-39.
• 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.
• Pioro M. and Medhi D. (2004): Routing, Flow, and Capacity Design in Communication and Computer Networks. - San Francisco: Morgan Kaufman.
• 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.
• 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.
• 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.
• 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.
• 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.
• 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.
• Walkowiak K. (2003): A new approach to survivability of connection oriented networks. - Lect. Notes Comput. Sci., Vol. 2657, pp. 501-510.
• 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.
• Walkowiak K. (2004b): A new method of primary routes selection for local restoration. - Lect. Notes Comput. Sci., Vol. 3042, pp. 1024-1035.
• Walkowiak K. (2004c): Survivable online routing for MPLS traffic engineering. - Lect. Notes Comput. Sci., Vol. 3266, pp. 288-297.
• Walkowiak K. (2006): Lagrangean heuristic for primary routes assignment in survivable connection-oriented networks. - Tech. Rep., Wrocław University of Technology, Wrocław.
• 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.