The influence on network topology on the efficiency of multicast heuristic algorithms

• Autorzy: Piechowiak M. , Żmudziński P.
• Języki publikacji: EN

Abstrakty

EN

The article investigates representative heuristic algorithms finding the cheapest spanning trees between a source node and the group of destination nodes (multicast connections). Reliable comparison and analysis of the efficiency of algorithms require the usage of network structures reflecting real Internet topology. This article also presents method for generation that topologies. The key part of the article includes the efficiency analysis and the influence of the parameters of a given structure (network model generated by BRITE tool) upon the efficiency of the algorithms under scrutiny.

Słowa kluczowe

EN

multicast routing; heuristic algorithms; network topology; graphs

PL

trasowanie grupowe; topologia sieci; graf

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

Twórcy

autor

Piechowiak M.

autor

Żmudziński P.

• Institute of Environmental Mechanics and Applied Computer Science, Kazimierz Wielki University, Chodkiewicza 30, 85-072 Bydgoszcz, Poland,

Bibliografia

• [1] Z. Wang, J. Crowcroft, “Quality-of-service routing for supporting multimedia applications”, IEEE Journal on Selected Area in Communications, vol. 14, no. 7, pp. 1228-1234, 1996.
• [2] S. Chen, K. Nahrstedt, “An Overview of Quality of Service Routing for Next-Generation High Speed Networks: Problems and Solutions”, IEEE Network, pp. 64-79,1998.
• [3] J. Moy, “Multicast Extension to OSPF”, Internet Draft, 1992.
• [4] R. Karp, “Reducibility among combinatorial problems”, Complexity of Computer Computations, pp. 85-104, 1972.
• [5] L. Kou, G. Markowsky, L. Berman, “A fast algorithm for Steiner trees”, Acta Informatica, no. 15, pp. 141-145, 1981.
• [6] J. S. Crawford, A. G. Waters, “Heuristics for ATM Multicast Routing”, Computer Science, University of Kent at Canterbury, 1998.
• [7] Q. Sun, H. Langendoerfer, “Efficient Multicast Routing for Delay-Sensitive Applications”, in Proceedings of the 2-nd Workshop on Protocols for Multimedia Systems (PROMS'95), October 1995, pp. 452-458.
• [8] E. Dijkstra, “A note on two problems in connexion with graphs", Numerische Mathematik, vol. 1. pp. 269-271, 1959.
• [9] R. Bellman, “On a routing problem”, Quarterly of Applied Mathematics, vol. 16, no. 1, pp. 87-90, 1958.
• [10] V. P. Kompella, J. Pasquale, G. C. Polyzos, “Multicasting for Multimedia Applications”, in INFOCOM, 1992, pp. 2078-2085.
• [11] M. Doar, I. Leslie, “How bad is naive multicast routing?”, IEEE INFOCOM' 1993, pp. 82-89, 1993.
• [12] B. Waxmann, “Routing of multipoint connections”, IEEE Journal on Selected Area in Communications, vol. 6, pp. 1617-1622, 1988.
• [13] A. L. Barabasi, R. Albert, “Emergence of scaling in random networks”, Science, pp. 509-512, 1999.
• [14] A. Medina, A. Lakhina, I. Matta, J.Byers, “BRITE: An Approach to Universal Topology Generation”, IEEE/A CM MASCOTS, pp. 346-356, 2001.
• [15] C. A. Toronha, F. A. Tobagi, “Evaluation of multicast routing for multimedia streams”, in Proceedings of IEEE International Telecommunications Symposium, 1994.
• [16] D. J. Watts, S. H. Strogatz, “Collective dynamics of 'small-world' networks”, Nature, vol. 12, no. 393, pp. 440-442, 1998.
• [17] M. Faloutsos, P. Faloutsos, C. Faloutsos, “On Power-Law Relationships of the Internet Topology”, ACM Computer Communication Review, Cambridge, MA, pp. 111-122, 1999.
• [18] T. Bu, D. Towsley, “On distinguishing between Internet power law topology generators”, in In Proceedings of INFOCOM, 2002.
• [19] M. Piechowiak, P. Zwierzykowski, “Performance Analysis of Multicast Heuristic Algorithms”, Third International Working Conference on Performance Modelling and Evaluation of Heterogeneous Networks, pp. 41/1-41/8, July 2005.
• [20] -, “Quantitative Comparison of Multicast Heuristic Algorithms”, Polish Teletraffic Symposium (PSRT'2005), pp. 101-110, September 2005.