Genetic routing algorithm for multicast connections in packet networks

• Autorzy: Chojnacki A. , Piechowiak M. , Zwierzykowski P.
• Języki publikacji: EN

Abstrakty

EN

The article analyzes and explores the influence of different genetical solutions on the efficiency and effectiveness of the performance of genetic algorithms for multicast routing. The results of the simulation studies were compared with the results obtained with the application of classic heuristics, i.e. (KPP [12], CSPT [5] and LD). The tests were carried out for a wide range of parameters defining properties and characteristics of test networks topologies. The simulation study takes into consideration topology generation methods in line with the Waxman model and the Barabasi-Albert model.

Słowa kluczowe

EN

multicast; routing algorithms; genetic algorithms

PL

rozsyłanie zbiorowe; algorytm trasowania; algorytm genetyczny

• Wydawca: Instytut Telekomunikacji i Informatyki Uniwersytetu Technologiczno-Przyrodniczego w Bydgoszczy
• Czasopismo: Image Processing & Communications
• Rocznik: 2008
• Tom: Vol. 13, no 1-2
• Strony: 13--20
• Opis fizyczny: Bibliogr. 23 poz., wykr.

Twórcy

autor

Chojnacki A.

autor

Piechowiak M.

autor

Zwierzykowski P.

• Chair of Communication and Computer Networks, Poznan University of Technology, Polanka 3, 60-965 Poznan, POLAND

Bibliografia

• [1] A. L. Barabasi and R. Albert. Emergence of scaling in random networks. Science, pages 509-512, 1999.
• [2] R. Bellman. On a routing problem. Quarterly of Applied Mathematics, 16(1):87-90, 1958.
• [3] R. Bhattacharya, P. Venkateswaran, S. Sanyal, and R. Nandi. Genetic algorithm based efficient routing scheme for multicast networks. In IEEE International Conference on Personal Wireless Communications, pages 500-504, 2005.
• [4] Adam Chojnacki. The applictaion of the genetic algorithms in the multicast routing. Master’s thesis, Poznan University of Technology, Poznań, Poland, June 2008.
• [5] J. S. Crawford and A. G. Waters. Heuristics for ATM Multicast Routing. In Proceedings of 6th IFIP Workshop on Performance Modeling and Evaluation of ATM Networks, pages 5/1-5/18, July 1998.
• [6] E. Dijkstra. A note on two problems in connexion with graphs. Numerische Mathematik, 1:269-271, 1959.
• [7] S. Dreyfus. An appraisal of some shortest-paths algorithms. Operations Research, 17:395-412, 1969.
• [8] T.D. Gwiazda. Algorytmy genetyczne. Wydawnictwo Naukowe PWN, 2007.
• [9] M. Hamdan and M.E El-Hawary. Multicast routing with delay variation constraints using genetic algorithm. In CCECE, Niagara Falls, May 2004.
• [10] N. Schmamoto and A. Hiramatu and K. Yamasaki. A dynamic routing control based on a genetic algorithm. IEEE International Conference on Neural Networks, pages 1123-1128, 1993.
• [11] R. Karp. Reducibility among combinatorial problems. Complexity of Computer Computations, pages 85-104, 1972.
• [12] Vachaspathi P. Kompella, Joseph Pasquale, and George C. Polyzos. Multicasting for Multimedia Applications. In INFOCOM, pages 2078-2085, 1992.
• [13] L. Kou, G. Markowsky, and L. Berman. A fast algorithm for Steiner trees. Acta Informatica, (15):141-145, 1981.
• [14] E. Martins, M. Pascoal, and J. Santos. The k shortest paths problem, 1998.
• [15] A. Medina, A. Lakhina, I. Matta, and J.Byers. BRITE: An Approach to Universal Topology Generation. IEEE/ACM MASCOTS, pages 346-356, 2001.
• [16] M. Piechowiak and P. Zwierzykowski. Heuristic Algorithm for Multicast Connections in Packet Networks. In Proceedings of EUROCON 2007 The International Conference on: Computer as a tool, pages 948-955, Warsaw, Poland, September 2007.
• [17] Q. Sun and H. Langendoerfer. Efficient Multicast Routing for Delay-Sensitive Applications. In Proceedings of the 2-nd Workshop on Protocols for Multimedia Systems (PROMS`95), pages 452-458, October 1995.
• [18] B. Waxmann. Routing of multipoint connections. IEEE Journal on Selected Area in Communications, 6:1617-1622, 1988.
• [19] Qing Zhu, M. Parsa, and J. J. Garcia-Luna-Aceves. A source-based algorithm for delay-constrained minimum-cost multicasting. In INFOCOM `95: Proceedings of the Fourteenth Annual Joint Conference of the IEEE Computer and Communication Societies (Vol. 1)-Volume, page 377. 1995.
• [20] P. Zwierzykowski and M. Piechowiak. Efficiency Analysis of Multicast Routing Algorithms in Large Networks. In Proceedings of The Third International Conference on Networking and Services ICNS 2007, pages 101-106.
• [21] P. Zwierzykowski and M. Piechowiak. Performance of Fast Multicast Algorithms in Real Networks. In Proceedings of EUROCON 2007 The International Conference on: Computer as a tool, pages 956-961, Warsaw, Poland, September 2007.
• [22] P. Zwierzykowski, T. Szewczyk, M. Piechowiak, and T. Bartczak. Jaki kształt ma Internet? Networld, (11):70-74, Listopad 2007.
• [23] P. Zwierzykowski, T. Szewczyk, M. Piechowiak, and T. Bartczak. Multicast IP technologia przyszłości. Networld, (6):65-68, Czerwiec 2007.