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

Michal Przewozniczek; Krzysztof Walkowiak

International Journal of Applied Mathematics and Computer Science (2006)

  • Volume: 16, Issue: 4, page 487-502
  • ISSN: 1641-876X

Abstract

top
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.

How to cite

top

Przewozniczek, Michal, and Walkowiak, Krzysztof. "Quasi-hierarchical evolution algorithm for flow assignment in survivable connection-oriented networks." International Journal of Applied Mathematics and Computer Science 16.4 (2006): 487-502. <http://eudml.org/doc/207808>.

@article{Przewozniczek2006,
abstract = {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.},
author = {Przewozniczek, Michal, Walkowiak, Krzysztof},
journal = {International Journal of Applied Mathematics and Computer Science},
keywords = {optimization; evolution algorithm; connection-oriented networks; path-assignment problem},
language = {eng},
number = {4},
pages = {487-502},
title = {Quasi-hierarchical evolution algorithm for flow assignment in survivable connection-oriented networks},
url = {http://eudml.org/doc/207808},
volume = {16},
year = {2006},
}

TY - JOUR
AU - Przewozniczek, Michal
AU - Walkowiak, Krzysztof
TI - Quasi-hierarchical evolution algorithm for flow assignment in survivable connection-oriented networks
JO - International Journal of Applied Mathematics and Computer Science
PY - 2006
VL - 16
IS - 4
SP - 487
EP - 502
AB - 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.
LA - eng
KW - optimization; evolution algorithm; connection-oriented networks; path-assignment problem
UR - http://eudml.org/doc/207808
ER -

References

top
  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. - IEEEATM 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. Zbl1131.90321
  6. 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. 
  7. Karp R. (1975): On the computational complexity of combinatorical problems. - Networks, Vol. 5, No. 1, pp. 45-68. Zbl0324.05003
  8. 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. Zbl1188.68028
  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. Zbl0841.68047
  11. Murakami K. and Kim H. (1996): Virtual path routing for survivable ATM networks. - IEEEATM Trans. Networking, Vol. 4, No. 2, pp. 22-39. 
  12. 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. 
  13. Pioro M. and Medhi D. (2004): Routing, Flow, and Capacity Design in Communication and Computer Networks. - San Francisco: Morgan Kaufman. Zbl1069.68021
  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-oriented networks. - 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 s 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 s 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. s 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. Zbl1033.68528
  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. Zbl1044.90093
  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. Zbl1155.68316
  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. Zbl0921.90074

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.