Multicast tree construction in bus-based networks

The authors examine communication among groups of cooperating processes in bus-based computer networks. Implementing multicast communication by requiring processes to send a separate copy of each message to every other group member can result in high bandwidth consumption and network traffic congestion. Multicast trees provide an alternative mechanism for process group communication. Unfortunately, constructing an optimal multicast tree for a group of nodes in a general bus-based network is an NP-hard problem. A heuristic algorithm for this purpose is presented. By taking into account the broadcast property of the media, this algorithm performs better than a well-known multicast tree algorithm for point-to-point networks in terms of the average number of bus visits per multicast and the amount of state information required to forward packets.<>