Distributed Algorithms for Constructing Multicast Trees

G. Lo Re and L. Gatani (Italy)


Steiner Tree Problem, Multicast Transmission, Distributed Algorithms


This paper proposes two distributed algorithms for the heu ristic solution of the Steiner Tree Problem in Network (SPN). The problem has a practical application in the con struction of a minimum cost distribution tree for multicast transmission. Multicast transmission represents a neces sary lower network service for the wide diffusion of new multimedia network applications. Currently, given the lack of efficient distributed methods, the existing protocols build the multicast distribution tree using some selected central node. The proposed distributed algorithms allow the con struction of effective distribution trees using a coordination protocol among the network nodes. The algorithms have been implemented and tested both in simulation and on ex perimental active networks, and their performance values are presented.

Important Links:

Go Back