A note on distributed multicast routing in point-to-point networks

The distributed algorithm for a multicast connection set-up, based on the ‘cheapest insertion’ heuristic, is reviewed. The multicast routing problem is translated into a Steiner tree problem in point-to-point networks where nodes have only a limited knowledge about the network. A solution is proposed in which the time complexity and the amount of information exchanged between network nodes are proportional to the number of members of the multicast group. The Steiner tree is constructed by means of a distributed table-passing algorithm. The analysis of the algorithm presented, backed up by simulation results, confirms its superiority over the algorithm based on ‘waving technique’.