Multi criterion multicast routing algorithm comparison for large networks

• Autorzy: Stachowiak K.
• Języki publikacji: EN

Abstrakty

EN

QoS enabled multicast routing is known to be of non-polynominal complexity, which leads to the necessity of using heuristic algorithms to find sub-optimal solutions to the problems of this class. The evaluation of such algorithms requires the use of the simulation techniques as the heuristics’ results are of stochastic nature. Because of the problem complexity the simulation times increase significantly in the function of the network size, therefore the results presented in the literature are often limited to only small models. In this article the results of the evaluation of different multicast QoS routing algorithms (further referred to as the Multi-Constrained Minimum Steiner Tree Problem-MCMST)have been presented for a wide range of network sizes reaching thousands of nodes.

Słowa kluczowe

EN

multicast routing; heuristic algorithms; simulation techniques

• Wydawca: Instytut Telekomunikacji i Informatyki Uniwersytetu Technologiczno-Przyrodniczego w Bydgoszczy
• Czasopismo: Image Processing & Communications
• Rocznik: 2017
• Tom: Vol. 22, no. 1
• Strony: 49--55
• Opis fizyczny: Bibliogr. 16 poz., rys.

Twórcy

autor

Stachowiak K.

• Chair of Telecommunications and Computer Networks Faculty of Electronics and Telecommunications Poznan University of Technology

Bibliografia

• [1] Ahuja R.K., Magnanti T.L., Orlin J.B. (1993). Network flows: theory, algorithms, and applications. Prentice-Hall, Inc., Upper Saddle River, NJ, USA.
• [2] Barabasi A-L.,AlbertR.(1999).Emergence of Scaling in Random Networks. Science, 286:509–912.
• [3] Chen S.,Nahrstedt K.(1998). An Overview of Quality of Service Routing for Next-generation Highspeed Networks: Problems and Solutions. IEEE Network, 12:64–79.
• [4] Gang F. (2006). A Multi-constrained Multicast QoS Routing Algorithm. Computer Communications, 29(10):1811–1822.
• [5] Ghaboosi N., Haghighat A. (2007). Tabu Search Based Algorithms for Bandwidth-delay constrained Least-cost Multicast Routing. Telecommunication Systems, 34:147–166.
• [6] Jin C., Chen Q., Jamin S. (2000). Inet: Internet Topology Generator. Technical Research Report CSE-TR-433-00, University of Michigan at Ann Arbor.
• [7] Li X., Ning Q., Jun-Ya Z., Yang-Qian L. (2008, July). An Improved GA for QoS Multicast Routing Algorithm. In Control and Decision Conference, 2008. CCDC 2008. Chinese, page 393–396, july 2008.
• [8] MolnÃar M., Bellabas A., Lahoud S. (2012). The Cost Optimal Solution of the Multi-constrained Multicast Routing Problem. Computer Networks, 56(13):3136–3149.
• [9] Stachowiak K., Weissenberg J., Zwierzykowski P. (2011, September). Lagrangian Relaxation in The Multicriterial Routing. In IEEE AFRICON, page 1– 6, Livingstone, Zambia.
• [10] Stachowiak K., Piechowiak M., Zwierzykowski P. (2010). The Effectiveness of Multicast Trees With Delay Constraints. In Information Systems Architecture and Technology ISAT 2010, pp. 199–209.
• [11] Stachowiak K., Zwierzykowski P. (2013). Lagrangian Relaxation and Linear Intersection Based QoS Routing Algorithm. International Journal of Electronics and Telecommunications, 58(4):307– 314.
• [12] Stachowiak K., Zwierzykowski P. (2014). Rendezvous Point Based Approach to the Multiconstrained Multicast Routing Problem. AEU - International Journal of Electronics and Communications, 68(6):561 – 564.
• [13] Van Mieghem P., De Neve H., Kuipers F. (2001, November). Hop-by-hop Quality of Service Routing. Comput. Netw., 37(3-4):407–423.
• [14] Wan S., Zhang Y. (2009). Research of MultiConstrained Multicast Routing Qos Using Heuristic Algorithm. In Information Engineering and Computer Science, 2009. ICIECS 2009. International Conference on, pp. 1–4.
• [15] Waxman B.M. (1988, December). Routing of Multipoint Connections. Selected Areas In Communications, IEEE Journal on, 6(9):1617–1622.
• [16] Yao R., Fei J. (2010, May). New Multicast Routing Algorithm for QoS Routing in Communication Network. In Future Computer and Communication (ICFCC), 2010 2nd International Conference on, volume 3, page V3–379–V3–382.

Uwagi

PL

Opracowanie ze środków MNiSW w ramach umowy 812/P-DUN/2016 na działalność upowszechniającą naukę (zadania 2017).