6533b827fe1ef96bd1285bdb

RESEARCH PRODUCT

An efficient distributed algorithm for generating and updating multicast trees

Salvatore GaglioGiuseppe Lo ReL. Gatani

subject

Computer Networks and Communicationscomputer.internet_protocolComputer scienceDistributed computingNetwork ontology.Distance Vector Multicast Routing ProtocolMultimedia Broadcast Multicast ServiceSteiner tree problemTheoretical Computer Sciencesymbols.namesakeArtificial IntelligenceConvergence (routing)Multicast addressXcastCommunication complexityPragmatic General MulticastIntelligent systemSettore ING-INF/05 - Sistemi Di Elaborazione Delle InformazioniMulticast transmissionProtocol Independent MulticastMulticastInter-domainbusiness.industryNode (networking)Programmable networkComputer Graphics and Computer-Aided DesignSource-specific multicastHardware and ArchitectureDistributed algorithmNetwork serviceReliable multicastsymbolsSituation calculuIP multicastbusinesscomputerSoftwareComputer network

description

As group applications are becoming widespread, efficient network utilization becomes a growing concern. Multicast transmission represents a necessary lower network service for the wide diffusion of new multimedia network applications. Multicast transmission may use network resources more efficiently than multiple point-to-point messages; however, creating optimal multicast trees (Steiner Tree Problem in networks) is prohibitively expensive. This paper proposes a distributed algorithm for the heuristic solution of the Steiner Tree Problem, allowing the construction of effective distribution trees using a coordination protocol among the network nodes. Furthermore, we propose a novel distributed technique for dynamically updating the multicast tree. The approach proposed has been implemented and extensively tested both in simulation, and on experimental networks. Performance evaluation indicates that the distributed algorithm performs as well as the centralized version, providing good levels of convergence time and communication complexity.

yearjournalcountryeditionlanguage
2006-12-01Parallel Computing
https://doi.org/10.1016/j.parco.2006.09.002