MULTICAST COMMUNICATION IN MULTICOMPUTER NETWORKS

Efficient routing of messages is a key to the performance of multicomp uters. Multicast communication refers to the delivery of the same mess age from a source node to an arbitrary number of destination nodes. Wh ile multicast communication is highly demanded in many applications, m ost of the existing multicomputers do not directly support this servic e; rather it is indirectly supported by multiple one-to-one or broadca st communications, which result in more network traffic and a waste of system resources. In this paper, we study routing evaluation criteria for multicast communication under different switching technologies. M ulticast communication in multicomputers is formulated as a graph theo retical problem. Depending on the evaluation criteria and switching te chnologies, we study three optimal multicast communication problems, w hich are equivalent to the finding of the following three subgraphs: o ptimal multicast path, optimal multicast cycle, and minimal Steiner tr ee, where the interconnection of a multicomputer defines a host graph. We will show that all these optimization problems are NP-complete for the popular 2D-mesh and hypercube host graphs. Heuristic multicast al gorithms for these routing problems are proposed.