The Application of K–Shortest Path Algorithm in Multicast Routing

• Autorzy: Stasiak M. , Piechowiak M. , Zwierzykowski P.

Warianty tytułu

PL

Nowy heurystyczny algorytm routingu dla połączeń typu „multicast”

• Języki publikacji: EN

Abstrakty

EN

There have been many heuristic algorithms finding multicast trees proposed over the past few years. The necessity for finding a better and more suitable algorithm is still a current and important challenge. The article presents a new multicast routing algorithm for finding a multicast tree in packet networks. The objective of the K-Shortest Path Multicast Algorithm (KSPMA) is to minimize the cost of paths between the source and each destination node using a generalized Dijkstra’s algorithm that would comply with maximum delay bound along each path. A wide range of simulation research carried out by the authors for many network topologies and parameters has confirmed the effectiveness of the proposed algorithm.

PL

W artykule zaproponowano nowy algorytm routingu dla połączeń rozgałęzionych. Prezentowany algorytm stosuje algorytm K–najkrótszych ścieżek do wyznaczenia ścieżek o minimalnych kosztach pomiędzy węzłem źródłowym, a każdym z węzłów docelowych, z uwzględnieniem maksymalnej dopuszczalnej wartości opóźnienia (c) wzdłuż każdej ścieżki. Algorytm KSPMA został przebadany symulacyjnie biorąc pod uwagę parametry określające zarówno struktura, jak i właściwości sieci. Badania przeprowadzono wykorzystując topologie sieci wygenerowane metodami Waxmana [2] oraz Barabasi-Alberta [24]. W symulacjach zbadano również efektywność algorytmu w funkcji podstawowych parametrów sieci tj. liczba węzłów sieci, liczność grupy odbiorców, średni stopień grafu (węzła) oraz maksymalne opóźnienie wzdłuż ścieżki. W badaniach uwzględniono także średnie koszty ścieżek uzyskane po zastosowaniu algorytmów CSPT, KPP oraz LDC. Liczne doświadczenia symulacyjne przeprowadzone przez autorów potwierdziły efektywność proponowanego algorytmu KSPMA.

Słowa kluczowe

EN

multicast; routing algorithms; network topology

• Wydawca: Instytut Informatyki Teoretycznej i Stosowanej Polskiej Akademii Nauk
• Czasopismo: Theoretical and Applied Informatics
• Rocznik: 2009
• Tom: Vol. 21, No. 2
• Strony: 69--82
• Opis fizyczny: Bibliogr. 28 poz., rys.

Twórcy

autor

Stasiak M.

autor

Piechowiak M.

autor

Zwierzykowski P.

• Chair of Communications and Computer Networks, Poznań University of Technology, ul. Polanka 3, Poznań 60965, Poland,

Bibliografia

• 1. Wang Z., Crowcroft J.: “Quality-of-service routing for supporting multimedia applications,”IEEE Journal on Selected Area in Communications, vol. 14, no. 7, pp. 1228–1234, 1996.
• 2. Waxmann B.: “Routing of multipoint connections,” IEEE Journal on Selected Area in Communications, vol. 6, pp. 1617–1622, 1988.
• 3. Kou L., Markowsky G., Berman L.: “A fast algorithm for Steiner trees,” Acta Informatica, no. 15, pp. 141–145, 1981.
• 4. Zhu Q., Parsa M., Garcia-Luna-Aceves J. J.: “A source-based algorithm for delayconstrained minimum-cost multicasting,” in INFOCOM ’95: Proceedings of the Fourteenth Annual Joint Conference of the IEEE Computer and Communication Societies (Vol. 1)-Volume. IEEE Computer Society, 1995, p. 377.
• 5. Shaikh A., Shin K. G.: “Destination-Driven Routing for Low-Cost Multicast.” IEEE Journal on Selected Areas in Communications, vol. 15, no. 3, pp. 373–381, 1997.
• 6. Dijkstra E.: “A note on two problems in connexion with graphs,” Numerische Mathematik, vol. 1, pp. 269–271, 1959.
• 7. Bellman R.: “On a routing problem,” Quarterly of Applied Mathematics, vol. 16, no. 1, pp. 87–90, 1958.
• 8. Crawford J. S., Waters A. G.: “Heuristics for ATM Multicast Routing,” Proceedings of 6th IFIP Workshop on Performance Modeling and Evaluation of ATM Networks, pp. 5/1–5/18, July 1998.
• 9. Sun Q., Langendoerfer H.: “Efficient Multicast Routing for Delay-Sensitive Applications,” in Proceedings of the 2-nd Workshop on Protocols for Multimedia Systems
• 10. Piechowiak M., Zwierzykowski P.: “Heuristic Algorithm for Multicast Connections in Packet Networks,” in Proceedings of EUROCON 2007, Warsaw, September 2007, pp. 948–955.
• 11. Chojnacki A., Piechowiak M., Zwierzykowski P.: “Genetic routing algorithm for multicast conections in packet networks,” Image Processing and Communications, vol. 13, no. 1-2, pp. 13–20, 2008.
• 12. Szymaniak P., Piechowiak M., Zwierzykowski P.: “New genetic multicast routing algorithm for ad-hoc networks,” Image Processing and Communications, vol. 13, no. 1-2, pp. 3–11, 2008.
• 13. Zwierzykowski P., Piechowiak M.: “A New Multicast Routing Algorithm with Lagrange Relaxation,” in Pozn´n Telecommunicastions Workshop. Pozna´n University of Technology, December 2007.
• 14. Karp R.: “Reducibility among combinatorial problems,” Complexity of Computer Computations, pp. 85–104, 1972.
• 15. Kompella V. P., Pasquale J., Polyzos G. C.: “Multicasting for Multimedia Applications,”in INFOCOM, 1992, pp. 2078–2085.
• 16. Piechowiak M., Zwierzykowski P.: “The Influence of Network Topology on the Efficiency of QoS Multicast Heuristic Algorithms,” in 5th International Symposium: Communication Systems Networks and Digital Signal Processing, 2006, pp. 115–119.
• 17. Dreyfus S.: “An appraisal of some shortest path algorithms,” Operations Research, no. 17, pp. 395–412, 1969.
• 18. Yen J. Y.: “Finding the K Shortest Loopless Paths in a Network,” Management Science, vol. 17, no. 11, pp. 712–716, 1969.
• 19. Rink K. A., Rodin E. Y., Sundarapandian V.: “Routing airlift aircraft by the double-sweep algorithm,” Mathematical and Computer Modelling, vol. 17, no. 30, pp. 133–147, 1999.
• 20. Prim R.: “Shortest connection networks and some generalizations,” Bell Systems Tech J., vol. 36, pp. 1389–1401, 1957.
• 21. Newman M., Barabási A., Watts D., Eds.: The Structure and Dynamics of Networks, ser. Princeton Studies in Complexity. Princeton University Press, 2007.
• 22. Pastor-Satorras R., Vespignani A.: Evolution and Structure of the Internet: A Statistical Physics Approach. Cambridge University Press, 2004.
• 23. Zegura E.W., Donahoo M. J., Calvert K. L.: “A Quantitative Comparison of Graph-based Models for Internet Topology,” IEEE/ACM Transactions on Networking, 1997.
• 24. Barabasi A. L., Albert R.: “Emergence of scaling in random networks,” Science, pp. 509–512, 1999.
• 25. Medina A., Lakhina A., Matta I., Byers J.: “BRITE: An Approach to Universal Topology Generation,” IEEE/ACM MASCOTS, pp. 346–356, 2001.
• 26. Zwierzykowski P., Piechowiak M.: “Performance of Fast Multicast Algorithms in Real Networks,” in Proceedings of EUROCON 2007, Warsaw, Poland, September 2007, pp. 956–961.
• 27. Piechowiak M., Zwierzykowski P.: “Efficiency Analysis of Multicast Routing Algorithms in Large Networks,” in Proceedings of The Third International Conference on Networking and Services ICNS 2007, Athens, Greece, June 2007, pp. 101–106.
• 28. Piechowiak M., Zwierzykowski P.: “Quantitative Comparison of Multicast Heuristic Algorithms,” Polish Teletraffic Symposium (PSRT’2005), pp. 101–110, September 2005.