Comparison of Multicast Algorithm Evaluation Results in Low and High Multicast Saturation Environments

• Autorzy: Stachowiak Krzysztof , Zwierzykowski Piotr

Identyfikatory

DOI

10.26636/jtit.2019.135019

• Języki publikacji: EN

Abstrakty

EN

The multicast quality of service-enabled routing is a computationally challenging task. Despite ongoing research efforts, the associated mathematical problems are still considered to be NP-hard. In certain applications, computational complexity of finding the optimal connection between a set of network devices may be a particularly difficult challenge. For example, connecting a small group of participants of a teleconference is not much more complex than setting up a set of mutual point-to-point connections. On the other hand, satisfying the demand for such services as IPTV, with their receivers constituting the majority of the network, requires applying appropriate optimization methods in order to ensure real system execution. In this paper, algorithms solving this class of problems are considered. The notion of multicast saturation is introduced to measure the amount of multicast participants relative to the entire network, and the efficiency of the analyzed algorithms is evaluated for different saturation degrees.

Słowa kluczowe

EN

quality of service; multicast; routing; multicast saturation

• Wydawca: Instytut Łączności - Państwowy Instytut Badawczy
• Czasopismo: Journal of Telecommunications and Information Technology
• Rocznik: 2019
• Tom: nr 3
• Strony: 3--7
• Opis fizyczny: Bibliogr. 29 poz., rys.

Twórcy

autor

Stachowiak Krzysztof

• Chair of Communication and Computer Networks, Faculty of Electronics and Telecommunications, Poznan University of Technology, Pl. Marii Skłodowskiej-Curie 5, 60-965 Poznań, Poland

autor

Zwierzykowski Piotr

• Chair of Communication and Computer Networks, Faculty of Electronics and Telecommunications, Poznan University of Technology, Pl. Marii Skłodowskiej-Curie 5, 60-965 Poznań, Poland

Bibliografia

• [1] T. Bartczak and P. Zwierzykowski, “Lightweight PIM – a new multicast routing protocol”, Int. J. of Commun. Syst., vol. 27, no. 10, pp. 1441–1458, 2014 (doi: 10.12/dac.2407).
• [2] M. Pushpalatha, T. K. Ramesh, C. V. Giriraja, and S. K. Konda, “Power efficient multicast routing protocol for dynamic intra cluster device to device communication”, in Proc. Int. Conf. on Elec., Electron., and Optimiz. Techniq. ICEEOT 2016, Chennai, India, 2016, pp. 1853–1856 (doi: 10.1109/ICEEOT.2016.7755009).
• [3] V. Matre and R. Karandikar, “Multipath routing protocol for mobile adhoc networks”, in Proc. Sym. on Colossal Data Anal. and Netw. CDAN 2016, Indore, India, 2016, pp. 428–432 (doi: 10.1109/CDAN.2016.7570946).
• [4] M. Piechowiak, P. Zwierzykowski, P. Owczarek, and M. Wasłowicz, “Comparative analysis of routing protocols for wireless mesh networks”, in Proc. 10th Int. Symp. on Commun. Syst., Netw. and Digit. Sig. Process. CSNDSP 2016, Prague, Czech Republic, 2016, pp. 1–5 (doi: 10.1109/CSNDSP.2016.7573902).
• [5] T. Bartczak and P. Zwierzykowski, “Performance evaluation of source-specific multicast routing protocols for IP networks”, in Proc. 8th Int. Symp. on Commun. Syst., Netw. & Digit. Sig. Process. CSNDSP 2012, Poznań, Poland, 2012, 2012, pp. 1–6 (doi: 10.1109/CSNDSP.2012.6292693).
• [6] S. Yahiaoui, M. Omar, A. Bouabdallah, E. Natalizio, and Y. Challal, “An energy efficient and QoS aware routing protocol for wireless sensor and actuator networks”, AEU – Int. J. of Electron. and Commun., vol. 83, no. Supplement C, pp. 193–203, 2018 (doi: 10.1016/j.aeue.2017.08.045 [Online]. Available: http://www.sciencedirect.com/science/article/pii/ S143484111730897X
• [7] B. Waxman, “Routing of multipoint connections”, IEEE J. on Selec. Areas in Commun., vol. 6, no. 9, p. 1617–1622, 1988 (doi: 10.1109/49.12889).
• [8] M. Piechowiak, P. Zwierzykowski, K. Stachowiak, and T. Bartczak, “Quality of multicast trees in ad-hoc networks with topology control”, in Proc. 9th Int. Symp. on Commun. Syst., Netw. Digit. Sign CSNDSP 2014, Manchester, UK, 2014, pp. 7–11 (doi: 10.1109/CSNDSP.2014.6923788).
• [9] Z. Xiaoxia, S. Xuanyao, T. Jiewei, and L. Guoxuan, “A hybrid ant colony optimization based on cloud model for OoS multicast routing problem”, in Proc. 29th Chinese Control and Dec. Conf. CCDC 2017, Chongqing, China, 2017, pp. 6551–6554 (doi: 10.1109/CCDC.2017.7978352).
• [10] N. Anwar and H. Deng, “Ant colony optimization based multicast routing algorithm for mobile ad hoc networks”, in Proc. Adv. in Wirel. and Optical Commun. RTUWO 2015, Riga, Latvia, 2015, pp. 62–67 (doi: 10.1109/RTUWO.2015.7365721).
• [11] M. Mahseur, Y. Meraihi, A. Boukra, and A. Ramdane-Cherif, “QoS multicast routing based on a hybrid quantum evolutionary algorithm with firefly algorithm”, in Proc. 5th Int. Conf. on Elec. Engin. – Boumerdes ICEE-B 2017, Boumerdes, Algeria, 2017, pp. 1–6 (doi: 10.1109/CEE-B.2017.8192154).
• [12] D. Papadimitriou, B. Fortz, and E. Gorgone, “Lagrangian relaxation for the time-dependent combined network design and routing problem”, in Proc. IEEE Int. Conf. on Commun. ICC 2015, London, UK, 2015, pp. 6030–6036 (doi: 10.1109/ICC.2015.7249283).
• [13] J. Moy, “OSPF Version 2”, RFC 2328 (Standard), IETF, Apr. 1998, updated by RFC 5709 [Online]. Available: http://www.ietf.org/rfc/rfc2328.txt
• [14] J. F. Kurose and K. Ross, Computer Networking: A Top-Down Approach Featuring the Internet, 2nd ed. Boston, MA, USA: AddisonWesley, 2003 (ISBN: 0201976994).
• [15] S. Chen and K. Nahrstedt, “An overview of quality of service routing for next-generation high-speed networks: problems and solutions”, IEEE Netw., vol. 12, no. 6, pp. 64–79, 1998 (doi: 10.1109/65.752646).
• [16] D. Savage, J. Ng, S. Moore, D. Slice, P. Paluch, and R. White, “Cisco’s Enhanced Interior Gateway Routing Protocol (EIGRP)”, RFC 7868 (Informational), RFC Editor, Fremont, CA, USA, pp. 1–80, May 2016 [Online]. Available: https://www.rfc-editor.org/rfc/rfc7868.txt
• [17] K. Stachowiak, P. Zwierzykowski, M. Piechowiak, and P. Prokopowicz, “Evaluation of different path composition approaches to multicast optimization with fuzzy set”, Mediterranean J. of Electron. and Commun., vol. 9, no. 3, pp. 594–600, 2013.
• [18] M. Piechowiak, P. Zwierzykowski, and M. Stasiak, “Multicast routing algorithm for packet networks with the application of the Lagrange relaxation”, in Proc. of the 14th Int. Telecommun. Netw. Strat. and Plann. Symp. NETWORKS 2010, Warsaw, Poland, 2010, pp. 197–202 (doi: 10.1109/NETWKS.2010.5624921).
• [19] Y. Xiao, K. Thulasiraman, G. Xue, and M. Yadav, “QoS routing under multiple additive constraints: A generalization of the Larac algorithm”, IEEE Trans. on Emerg. Topics in Comput., vol. 4, no. 2, pp. 242–251, 2016 (doi: 10.1109/TETC.2015.2428654).
• [20] K. Stachowiak, J. Weissenberg, and P. Zwierzykowski, “Lagrangian relaxation in the multicriterial routing”, in Proc. IEEE AFRICON 2011, Livingstone, Zambia, 2011, p. 646–651 (doi: 10.1109/AFRCON.2011.6072070).
• [21] A. Juttner, B. Szviatovski, I. Mecs, and Z. Rajko, “Lagrange relaxation based method for the QoS routing problem”, in Proc. IEEE INFOCOM 2001 – Twentieth Ann. Joint Conf. of the IEEE Comp. and Commun. Soc., Anchorage, AK, USA, 2001, vol. 2, pp. 859–868 (doi: 10.1109/INFCOM.2001.916277).
• [22] K. Stachowiak and P. Zwierzykowski, “Rendezvous point based approach to the multi-constrained multicast routing problem”, AEU – Int. J. of Electron. and Commun., vol. 68, no. 6, pp. 561–564, 2014 (doi: 10.1016/j.aeue.2014.01.002).
• [23] H. D. Neve and P. V. Mieghem, “Tamcra: a tunable accuracy multiple constraints routing algorithm”, Comp. Commun., vol. 23, no. 7, pp. 667–679, 2000 (doi: 10.1016/S0140-3664(99)00225-X).
• [24] F. Gang, “A multi-constrained multicast QoS routing algorithm”, Comp. Commun., vol. 29, no. 10, p. 1811–1822, 2006 (doi: 10.1016/j.comcom.2005.10.014).
• [25] T. Korkmaz and M. Krunz, “Multi-constrained optimal path selection”, in Proc. of IEEE Int. Conf. on Comp. Commun. INFOCOM 2001, Anchorage, AK, USA, 2001, pp. 834–843 (doi: 10.1109/INFCOM.2001.916274).
• [26] A. Medina, A. Lakhina, I. Matta, and J. Byers, “BRITE: An approach to universal topology generation”, in Proc. 9th Int. Symp. on Model., Anal. and Simul. of Comp. and Telecommun. Syst. MASCOTS 2001, Cincinnati, OH, USA, 2001, pp. 346–356 (doi: 10.1109/MASCOT.2001.948886).
• [27] K. Stachowiak and P. Zwierzykowski, “Lagrangian relaxation and linear intersection based QoS routing algorithm”, Int. J. of Electron. and Telecommun., vol. 58, no. 4, p. 307–314, 2013 (doi: 10.2478/v10177-012-0042-2).
• [28] M. Piechowiak, K. Stachowiak, and P. Zwierzykowski, “Properties of multiconstrained multicast trees in ad-hoc networks with topology control”, in Proc. of the IEICE Inform. and Commun. Technol. Forum ICTF 2015, Manchester, UK, 2015, pp. 1–5 2015.
• [29] M. Piechowiak and S. Pucek, “Topology properties of ad-hoc networks”, in Image Processing and Communications Challenges 4, R. S. Choraś, Ed. Berlin, Heidelberg: Springer, 2013, pp. 233–240 (doi: 10.1007/978-3-642-32384-3 29).

Uwagi

Opracowanie rekordu w ramach umowy 509/P-DUN/2018 ze środków MNiSW przeznaczonych na działalność upowszechniającą naukę (2019).