Multi-cast Tree Construction in Bus-Based Networks.

摘要

A bus-based computer network is one in which every communication link is multiple-access medium. Such networks include interconnected local area networks, multichannel networks, and bus-based interconnection networks for parallel processors. This paper is concerned with communication among groups of cooperating processes in bus-based computer networks. Implementing multi-cast communication by requiring processes to send a separate copy of each message to every other group member may result in high bandwidth consumption and network traffic congestion. Multi-cast trees provide an alternative mechanism for process group communication. Unfortunately, constructing an optimal multi-cast tree for a group of nodes in a general bus-based network is an NP-hard problem. A heuristic algorithm that produces multi-cast trees in general bus-based networks is presented. By taking into account the broadcast property of the media, this algorithm performs better than a well-known multi-cast tree algorithm for point-to-point networks in terms of the average number of bus visits per multi-cast and the amount of state information required to forward packets. Keywords: Multi-cast tree construction; Bus based networks; Multi-cast communication. (JHD)