An Efficient Distributed Algorithm for Generating and Updating Multicast Trees

Abstract

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.