Abstract
Rapid growth in the number of users, devices and applications and infrastructures generating and demanding massive amount of content traffic on the Internet has necessitated the available network infrastructures to evolve to cope up with the ever increasing content traffic. One of the approaches in reducing the content traffic and increasing the network throughput is the paradigm of multicast. Multicast is a one-to-many wave scheme for content distribution from a source to all or a large number of destinations. In this paper, we propose the first novel reliable concurrent content multicast algorithm, referred to as a CD-wave algorithm, for concurrent distribution of content from some or all peers to all other network peers. The proposed algorithm synchronises concurrent multicasts in sharing network resources while providing the desirable properties of self- and snap-stabilization. Concurrent mulicasts from different sources are synchronized so that multiple multicasts use each network channel mutually exclusively while ensuring that each multicast eventually succeeds to deliver its content to all system peers. Due to being reliable, each multicast content is guaranteed to be received by all system peers exactly once regardless of the arbitrary initial system configuration in the presence of potentially \(n-1\) other multicasts competing for network resources where n denotes the number of peers in the network. The snap-stabilization property of our proposed algorithm facilitates the reliability property by ensuring that content distribution proceeds as per its specification to reach all system peers without backtracking after starting in an arbitrary initial configuration.
Similar content being viewed by others
References
Jiménez-Soria D, Martín-Vega FJ, Aguayo-Torres MC (2021) Coordinated multicast/unicast transmission on 5g: a novel approach for linear broadcasting. Wirel Pers Commun 121:1–15
Jun D, Song J, Ren Y, Wang J (2021) Convergence of broadband and broadcast/multicast in maritime information networks. Tsinghua Sci Technol 26(5):592–607
Ahn SK, Jung H, Kwon S, Hur N, Choi DJ, Park SI (2021) Trends of terrestrial broadcasting technology based on MBMS. Electron Telecommun Trends 36(4):72–80
Samuylov A, Moltchanov D, Kovalchukov R, Pirmagomedov R, Gaidamaka Y, Andreev S, Koucheryavy Y, Samouylov K (2020) Characterizing resource allocation trade-offs in 5g nr serving multicast and unicast traffic. IEEE Trans Wireless Commun 19(5):3421–3434
Shen C, Liu C, Rouil RA., Choi HA (2020) Study of multicast broadcast single frequency network area in multicast communications. In: 2020 14th International Conference on Signal Processing and Communication Systems (ICSPCS), pp 1–8
Debnath SK, Saha M, Islam Md, Sarker PK, Pramanik I et al (2021) Evaluation of multicast and unicast routing protocols performance for group communication with QOS constraints in 802.11 mobile ad-hoc networks. Int J Comput Netw Inf Secur 13(1):1–15
Khabazian M, Aissa S, Mehmet-Ali M (2013) Performance modeling of safety messages broadcast in vehicular ad hoc networks. IEEE Trans Intell Transp Syst 14(380–387):03
Stephen Craig R (1986) The American forces network, Europe: a case study in military broadcasting. J Broadcast Electron Media 30(1):33–46
Davies B (1994) Safety critical problems in medical systems. In: Redmill F, Anderson T (eds) Technology and assessment of safety-critical systems. Springer, London, pp 55–68
Hong C-Y, Mandal S, Al-Fares M, Zhu M, Alimi R, Kondapa Naidu B, Bhagat C, Jain S, Kaimal J, Liang S, Mendelev K, Padgett S, Rabe F, Ray S, Tewari M, Tierney M, Zahn M, Zolla J, Ong J, Vahdat A (2018) B4 and after: managing hierarchy, partitioning, and asymmetry for availability and scale in google’s software-defined wan. In: Proceedings of the 2018 Conference of the ACM Special Interest Group on Data Communication, SIGCOMM ’18, pp 74–87, New York, NY, USA, Association for Computing Machinery
Sun G, Liao D, Zhao D, Xu Z, Yu H (2018) Live migration for multiple correlated virtual machines in cloud-based data centers. IEEE Trans Serv Comput 11(2):279–291
Mseddi A, Salahuddin M, Zhani M F, Elbiaze H, Glitho R (2018) Efficient replica migration scheme for distributed cloud storage systems. IEEE Trans Cloud Comput, Pp 1–1, 07
Sun G, Chen Z, Hongfang Y, Du X, Guizani M (2019) Online parallelized service function chain orchestration in data center networks. IEEE Access, Pp 1–1, 07
Jonathan A, Chandra A, Weissman J (2018) Multi-query optimization in wide-area streaming analytics. In: Proceedings of the ACM Symposium on Cloud Computing, SoCC ’18, pp 412–425, New York, NY, USA, Association for Computing Machinery
Noormohammadpour M, Raghavendra CS (2018) Datacenter traffic control: understanding techniques and tradeoffs. IEEE Commun Surv Tutor 20(2):1492–1525
Sun G, Xu Z, Yu H, Chang V, Du X, Guizani M (2019) Toward SLAs guaranteed scalable vdc provisioning in cloud data centers. IEEE Access 7:80219–80232
Hasimoto-Beltran R, Lopez-Fuentes F, Vera-Lopez M (2018) Hierarchical p2p architecture for efficient content distribution. Peer-to-Peer Netw Appl, 08
Peterson N, Anusuya-Rangappa L, Shirazi B, Song W, Huang R, Tran D, Chien S, Lahusen R (2010) Volcano monitoring: a case study in pervasive computing, pp 201–230. 01
Brown S, Johnson O, Tassi A (2018) Reliability of broadcast communications under sparse random linear network coding. IEEE Trans Veh Technol 67(5):4677–4682
Striccoli D, Piro G, Boggia G (2019) Multicast and broadcast services over mobile networks: a survey on standardized approaches and scientific outcomes. IEEE Commun Surv Tutor 21(2):1020–1063
Mcgrath S, Daria P, Whitebread CK (2000) Intelligent mobile agents in the military domain. In: Proceedings of the Autonomous Agents 2000 Workshop on Agents in Industry
Adamson B, Macker JP (Oct 2010) Reliable messaging for tactical group communication. In 2010 - Milcom 2010 Military Communications Conference, pp 1899–1904
Raynal M (2018) Reliable broadcast in the presence of byzantine processes. Springer International Publishing, Cham, pp 61–73
Bonomi S, Farina G, Tixeuil S (2018) Reliable broadcast in dynamic networks with locally bounded byzantine failures. In: Izumi T, Kuznetsov P (eds) Stabilization, safety, and security of distributed systems. Springer International Publishing, Cham, pp 170–185
Rand TW, Eby MS (Oct 2004) Algorithms for airborne conflict detection, prevention, and resolution. In: The 23rd Digital Avionics Systems Conference (IEEE Cat. No.04CH37576), vol 1, pp 521–31
Sharma K, Kumawat J, Maheshwari S, Jain N (2014) Railway security system based on wireless sensor networks: state of the art
Schiff L, Tsafrir Z, Aoun J, Taylor A, Theoharis E, Eisenstein D (2016) Quality of communication in robotic surgery and surgical outcomes. J SocLaparoendoscopic Surg 20(e2016):00026
Huang R, Wu J, Long C, Zhu Y, Lin Y (June 2017) Mitigate the obstructing effect of vehicles on the propagation of vanets safety-related information. In: 2017 IEEE Intell Veh Symp (IV), pp 1893–1898
Vni complete forecast highlights. Accessed: 2016
What netflix’s 1 billion video hours streamed means for bandwidth
Wendell P, Freedman MJ (2011) Going viral: flash crowds in an open CDN. In: Proceedings of the 2011 ACM SIGCOMM Conference on Internet Measurement Conference, IMC ’11, pp 549-558, New York, NY, USA, Association for Computing Machinery
Nygren E, Sitaraman RK, Sun J (2010) The Akamai network: a platform for high-performance internet applications. SIGOPS Oper. Syst. Rev. 44(3):2–19
Zhao M, Aditya P, Chen A, Lin Y, Haeberlen A, Druschel P, Maggs B, Wishon B, Ponec M (2013) Peer-assisted content distribution in Akamai Netsession. In: Proceedings of the 2013 Conference on Internet Measurement Conference, IMC ’13, pp 31–42, New York, NY, USA, Association for Computing Machinery
Smite D, Moe NB, Levinta G, Floryan M (2019) Spotify guilds: How to succeed with knowledge sharing in large-scale agile organizations. IEEE Softw 36(2):51–57
Yin H, Liu X, Zhan T, Sekar V, Qiu F, Lin C, Zhang H, Li B (2010) Livesky: Enhancing CDN with p2p. ACM Trans. Multimedia Comput. Commun. Appl. 6(3)
Li H (2012) The platform of spoof videos: the case of tudou.com. Cultural Sci J 5:07
Zhang G, Liu W, Hei X, Cheng W (2015) Unreeling Xunlei Kankan: understanding hybrid CDN-p2p video-on-demand streaming. IEEE Trans Multimed 17(2):229–242
Frank B, Poese I, Lin Y, Smaragdakis G, Feldmann A, Maggs B, Rake J, Uhlig S, Weber R (2013) Pushing CDN-ISP collaboration to the limit. ACM SIGCOMM Comput Commun Rev 43(3):34–44
Buyya R, Pathan A-MK, Broberg J, Tari Z (2006) A case for peering of content delivery networks. IEEE Distrib Syst Online 7(10):3–3
Gao G, Wen Y, Zhang W, Hu H (2015) Cost-efficient and QOS-aware content management in media cloud: implementation and evaluation. In: 2015 IEEE International Conference on Communications (ICC), pp 6880–6886. IEEE
Jin Y, Wen Y, Guan K (2016) Toward cost-efficient content placement in media cloud: modeling and analysis. IEEE Trans Multimed 18(5):807–819
Applegate D, Archer A, Gopalakrishnan V, Lee S, Ramakrishnan K K (2010) Optimal content placement for a large-scale vod system. In: Proceedings of the 6th International Conference, pp 1–12
Noormohammadpour M, Raghavendra C, Rao S, Kandula S(2017) Dccast: efficient point to multipoint transfers across datacenters. 07
Ji S., Liu S, Li B (2018) Deadline-aware scheduling and routing for inter-datacenter multicast transfers. In 2018 IEEE International Conference on Cloud Engineering (IC2E), pp 124–133
Stutzbach D, Rejaie R (2006) Understanding churn in peer-to-peer networks. In Proceedings of the 6th ACM SIGCOMM Conference on Internet Measurement, pp 189–202
Cong X, Shuang K, Sen S, Yang FC (2014) An efficient server bandwidth costs decreased mechanism towards mobile devices in cloud-assisted p2p-VoD system. Peer-to-Peer Network Appl 7(2):175–187
Pathan A-MK, Buyya R (2007) A taxonomy and survey of content delivery networks. Grid Computing and Distributed Systems Laboratory, University of Melbourne, Technical Report 4:70
Karamshuk D, Sastry N, Secker A, Chandaria J (2015) Isp-friendly peer-assisted on-demand streaming of long duration content in BBC iPlayer. In: 2015 IEEE Conference on Computer Communications (INFOCOM), pp 289–297. IEEE
Rückert J, Knierim T, Hausheer D (2014) Clubbing with the peers: a measurement study of bittorrent live. In: 14-th IEEE International Conference on Peer-to-Peer Computing, pp 1–10. IEEE
Venkataraman V, Yoshida K, Francis P (2006) Chunkyspread: heterogeneous unstructured tree-based peer-to-peer multicast. In: Proceedings of the Proceedings of the 2006 IEEE International Conference on Network Protocols, ICNP ’06, pp 2–11, USA, IEEE Computer Society
Ha TT, Kim J, Nam J (2017) Design and deployment of low-delay hybrid CDN—P2P architecture for live video streaming over the web. Wirel Pers Commun 94(3):513–525
Roverso R, Naiem A, Reda M, El-Beltagy M, El-Ansary S, Franzen N, Haridi S (2011) On the feasibility of centrally-coordinated peer-to-peer live streaming. In: 2011 IEEE Consumer Communications and Networking Conference (CCNC), pp 1061–1065. IEEE
Zhao M, Aditya P, Chen A, Lin Y, Haeberlen A, Druschel P, Maggs B, Wishon B, Ponec M (2013) Peer-assisted content distribution in akamai netsession. In: Proceedings of the 2013 conference on Internet measurement conference, pp 31–42
Hou D (2010) Design of streaming media information services architecture based on integrated CDN and P2P. In 2010 The 2nd Conference on Environmental Science and Information Application Technology, vol 1, pp 308–311
Hardwick J, Enfield UK (2004) IP multicast explained. Data Connection Limited
Sampaio A, Sousa P (2018) An adaptable and ISP-friendly multicast overlay network. Peer-to-Peer Networking and Applications, 09
Gong H, Fu L, Fu X, Zhao L, Wang K, Wang X (2017) Distributed multicast tree construction in wireless sensor networks. IEEE Trans Inf Theory 63(1):280–296
Shi S, Turner J, Waldvogel M (2001) Dimensioning server access bandwidth and multicast routing in overlay networks. 07
Ke K-W, Huang C-H (2013) Performance evaluation of multisource application layer multicast (ALM): theoretical and simulative aspects. Comput Netw 57(1408–1424):04
Xue Q, Ganz A (2003) Ad hoc QOS on-demand routing (AQOR) in mobile ad hoc networks. J Parallel Distrib Comput 63(2):154–165
Zhao X, Guo J, Chou CT, Misra A, Jha S (2011) A high-throughput routing metric for reliable multicast in multi-rate wireless mesh networks. In 2011 Proceedings IEEE INFOCOM, pp 2042–2050. IEEE
Liu Y, Niu D, Li B (2016) Delay-optimized video traffic routing in software-defined interdatacenter networks. IEEE Trans Multimedia 18(5):865–878
Mahdian M, Prakash N, Médard M, Yeh E (2018) Updating content in cache-aided coded multicast. IEEE J Sel Areas Commun 36(6):1203–1216
Zeebaree SRM, Rajab H (2019) Design and implement a proposed multi-sources to multi-destinations broadcasting video-signals. In 2019 4th Scientific International Conference Najaf (SICN), pp 103–108
Kamimura K, Hasegawa T, Hoshino H, Ano S, Hasegawa T (2005) A practical multicast transmission control method for multi-channel HDTV IP broadcasting system. In: Y-S Ho , H-J Kim (eds) Advances in multimedia information processing - PCM 2005, pp 429–440, Springer, Berlin
Rhee I, Balaguru N, Rouskas GN (1999) Mtcp: scalable tcp-like congestion control for reliable multicast. In: IEEE INFOCOM ’99. Conference on Computer Communications. Proceedings. Eighteenth Annual Joint Conference of the IEEE Computer and Communications Societies. The Future is Now (Cat. No.99CH36320), vol 3, pp 1265–1273
Rizzo L (2000) Pgmcc: A TCP-friendly single-rate multicast congestion control scheme. In: Proceedings of the Conference on Applications, Technologies, Architectures, and Protocols for Computer Communication, SIGCOMM ’00, pp 17–28, New York, NY, USA, Association for Computing Machinery
Hasimoto-Beltrán R, de Asís López-Fuentes F, Vera-Lopez M (2019) Hierarchical P2P architecture for efficient content distribution. Peer-to-Peer Netw Appl 12:724–739
Telco cdn (2002) Chapter 1: Peer-to-Peer streaming systems. In: Li Q, Shih TK (eds) Ubiquitous Multimedia Computing. CRC Press
Matsumoto J (2016) Multicast tree construction algorithm for stabilization of power quality in smart grid. In 2016 IEEE 17th International Conference on High Performance Switching and Routing (HPSR), pp 122–127
Chen Y, Wu EH, Chen G (2017) Bandwidth-satisfied multicast by multiple trees and network coding in lossy manets. IEEE Syst J 11(2):1116–1127
Magnetto A, Gaeta R, Grangetto M, Sereno M (2010) Turinstream: a totally push, robust, and efficient p2p video streaming architecture. IEEE Trans Multimedia 12(8):901–914
Banerjee S, Bhattacharjee B, Kommareddy C (2002) Scalable application layer multicast. In: Proceedings of the 2002 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications, SIGCOMM ’02, pp 205-217, New York, NY, USA, Association for Computing Machinery
Dijkstra EW (1973) Self-stabilizing systems in spite of distributed control. In EWD 391, In: Selected writings on computing: a personal perspective, pp 41–46
Dijkstra EW (1974) Self-stabilizing systems in spite of distributed control. Commun ACM 17(11):643–644
Blin L, Tixeuil S (2017) Compact deterministic self-stabilizing leader election on a ring: the exponential advantage of being talkative. Distrib Comput 31(2):139–166
Delaët S, Dolev S, Peres O (2009) Safer than safe: On the initial state of self-stabilizing systems. Lecture Notes in Computer Science Stabilization, Safety, and Security of Distributed Systems, pp 775—776
Katz S, Perry KJ (1990) Self-stabilizing extensions for massage-passing systems. In Proceedings of the 9th Annual ACM Symposium on Principles of Distributed Systems
Beauquier J, Delaët S, Haddad S (2006) A 1-strong self-stabilizing transformer. In: Datta AK, Gradinariu M (eds) Stabilization, safety, and security of distributed systems. Springer, Berlin, pp 95–109
Ghosh S, Gupta A, Herman T, Pemmaraju SV (2007) Fault-containing self-stabilizing distributed protocols. Distrib Comput 20(1):53–73
Turau V (2017) Computing the fault-containment time of self-stabilizing algorithms using Markov chains and lumping. pp 62–77, 10
Ghosh S, Gupta A (1996) An exercise in fault-containment: Self-stabilizing leader election. Inf Process Lett 59:281–288
Ghosh S, Gupta A, Herman T, Pemmaraju SV (1996) Fault-containing self-stabilizing algorithms. In: Proceedings of the Fifteenth Annual ACM Symposium on Principles of Distributed Computing - PODC 96
Köhler S, Turau V (2010) Fault-containing self-stabilization in asynchronous systems with constant fault-gap. In: 2010 IEEE 30th International Conference on Distributed Computing Systems
Ghosh S, Gupta A, Pemmaraju SV (1996) A fault-containing self-stabilizing algorithm for spanning trees. J Comput Inf 2:322–338
Azar Y, Kutten S, Patt-Shamir B (2010) Distributed error confinement. ACM Trans Algorithms 6(3):1–23
Kutten S, Patt-Shamir B (1997) Time-adaptive self stabilization. In: Proceedings of the Sixteenth Annual ACM Symposium on Principles of Distributed Computing, PODC ’97, pp 149–158, New York, NY, USA, ACM
Afek Y, Dolev S (1997) Local stabilizer. Proceedings of the sixteenth annual ACM symposium on Principles of distributed computing - PODC 97
Dolev S, Herman T (1997) Superstabilizing protocols for dynamic distributed systems. The Chicago J Theor Comput Sci, 3(4)
Delaet S, Tixeuil S (2002) Tolerating transient and intermittent failures. J Parallel Distrib Comput 62(5):961–981
Delaët S, Dolev S, Peres O (2009) Safe and eventually safe: comparing self-stabilizing and non-stabilizing algorithms on a common ground. Lecture Notes in Computer Science Principles of Distributed Systems, pp 315—329
Ghosh S, Bejan A (2003) A framework of safe stabilization. Lecture Notes in Computer Science Self-Stabilizing Systems, pp 129—140
Cournier A, Datta Ak, Petit F, Villain V (2002) Snap-stabilizing PIF algorithm in arbitrary networks. In: Proceedings 22nd International Conference on Distributed Computing Systems
Cournier A, Devismes S, Villain V (2009) Light enabling snap-stabilization of fundamental protocols. ACM Trans Autonom Adapt Syst 4(1):1–27
Leve F, Mohamed K, Villain V (2016) Snap-stabilizing PIF on arbitrary connected networks in message passing model. Lecture Notes in Computer Science Stabilization, Safety, and Security of Distributed Systems, pp 281—297
Leve F, Mohamed K, Villain V (2014) Snap-stabilizing PIF on non-oriented trees and message passing model. Lecture Notes in Computer Science Stabilization, Safety, and Security of Distributed Systems, pp 299—313
Cournier A, Devismes S, Villain V (2006) From self- to snap- stabilization, vol 4280, pp 199–213, 11
Cournier A, Datta AK, Devismes S, Petit F, Villain V (2016) The expressive power of snap-stabilization. Theoret Comput Sci 626:40–66
Blin L, Cournier A, Villain V (2003) An improved snap-stabilizing PIF algorithm. Lecture notes in computer science self-stabilizing systems, pp 199—214
Godard E (2018) Snap-stabilizing tasks in anonymous networks. Theory Comput Syst 63(2):326–343
Gouda MG, Haddix F (1999) The alternator. In: Proceedings 19th IEEE International Conference on Distributed Computing Systems, pp 48–53
Mizuno M, Nesterenko M (1998) A transformation of self-stabilizing serial model programs for asynchronous parallel computing environments. Inf Process Lett 66(6):285–290
Viger F., Latapy M. (2005) Efficient and simple generation of random simple connected graphs with prescribed degree sequence. In: International Computing and Combinatorics Conference, pp 440–449, Springer
Awerbuch B, Patt-Shamir B, Varghese G (1994) Bounding the unbounded [distributed computing protocols]. In: Proceedings of INFOCOM’94 Conference on Computer Communications, pp 776–783. IEEE
Acknowledgements
I would like to thank the anonymous referees for their suggestions and constructive comments on an earlier version of the paper. Their suggestions have greatly enhanced the readability of the paper. I would like to thank Ali Hamdan for his assistance on the simulation work. This work is supported by Kuwait University Research Administration, Grant No [EO-01/17]
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
About this article
Cite this article
Karaata, M.H., Dabees, A. & Alazemi, F. A reliable concurrent multicast algorithm for content distribution. J Supercomput 78, 10542–10574 (2022). https://doi.org/10.1007/s11227-021-04291-5
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11227-021-04291-5