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

Authors

DOI:

https://doi.org/10.26636/jtit.2019.135019

Keywords:

quality-of-service, multicast, routing, multicast saturation

Abstract

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.

Downloads

Download data is not yet available.

References

[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: https://doi.org/10.1002/dac.2407
View in Google Scholar

[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: https://doi.org/10.1109/ICEEOT.2016.7755009
View in Google Scholar

[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: https://doi.org/10.1109/CDAN.2016.7570946
View in Google Scholar

[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: https://doi.org/10.1109/CSNDSP.2016.7573902
View in Google Scholar

[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: https://doi.org/10.1109/CSNDSP.2012.6292693
View in Google Scholar

[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: https://doi.org/10.1016/j.aeue.2017.08.045
View in Google Scholar

[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: https://doi.org/10.1109/CSNDSP.2014.6923788
View in Google Scholar

[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: https://doi.org/10.1109/CCDC.2017.7978352
View in Google Scholar

[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: https://doi.org/10.1109/RTUWO.2015.7365721
View in Google Scholar

[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: https://doi.org/10.1109/ICEE-B.2017.8192154
View in Google Scholar

[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: https://doi.org/10.1109/ICC.2015.7249283
View in Google Scholar

[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
View in Google Scholar

[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).
View in Google Scholar

[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: https://doi.org/10.1109/65.752646
View in Google Scholar

[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. DOI: https://doi.org/10.17487/RFC7868
View in Google Scholar

[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.
View in Google Scholar

[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: https://doi.org/10.1109/NETWKS.2010.5624921
View in Google Scholar

[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: https://doi.org/10.1109/TETC.2015.2428654
View in Google Scholar

[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: https://doi.org/10.1109/AFRCON.2011.6072070
View in Google Scholar

[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: https://doi.org/10.1109/INFCOM.2001.916277
View in Google Scholar

[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: https://doi.org/10.1016/j.aeue.2014.01.002
View in Google Scholar

[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.00225-X). DOI: https://doi.org/10.1016/S0140-3664(99)00225-X
View in Google Scholar

[24] F. Gang, “A multi-constrained multicast QoS routing algorithm”, Comp. Commun., vol. 29, no. 10, p. 1811–1822, 2006. DOI: https://doi.org/10.1016/j.comcom.2005.10.014
View in Google Scholar

[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: https://doi.org/10.1109/INFCOM.2001.916274
View in Google Scholar

[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: https://doi.org/10.1109/MASCOT.2001.948886
View in Google Scholar

[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: https://doi.org/10.2478/v10177-012-0042-2
View in Google Scholar

[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.
View in Google Scholar

[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: https://doi.org/10.1007/978-3-642-32384-3_29
View in Google Scholar

Downloads

Submitted

2023-06-08

Published

2019-09-30

Issue

No. 3 (2019)

Section

ARTICLES FROM THIS ISSUE

License

Copyright (c) 2019 Journal of Telecommunications and Information Technology

Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.

How to Cite

[1]
K. Stachowiak and P. Zwierzykowski, “Comparison of Multicast Algorithm Evaluation Results in Low and High Multicast Saturation Environments”, JTIT, vol. 77, no. 3, pp. 3–7, Sep. 2019, doi: 10.26636/jtit.2019.135019.

Most read articles by the same author(s)