In many multicomputer applications is it necessary for one node to send an identical message to many nodes. One to many communications are called multicasts. Although broadcasts (one to all) and unicasts (one to one) have been widely implemented, multicasts, in spite of their importance to efficient use of multicomputer systems, have not received much attention.
Minimal traffic multicasting is equivalent to the minimal Steiner tree problem and is known to be NP-complete. Therefore, a heuristic polynomial time approximation must be used; but, to take advantage of advances in second generation multicomputer hardware such as wormhole routing, a distributed multicast routing algorithm must have a low order of complexity, preferably O(k) where k is the number of receiving nodes.
We present an O(k) algorithm for multicast routing. It is simple enough to be easily implemented in hardware and has the advantage over previously presented O(k) multicast routing algorithms that the choice of the channel on which to send to a particular destination depends only on statistical properties of those destinations already processed. Thus, a destination may be processed as soon as it arrives at a node. In addition, the algorithm we present appears to create in the mean less traffic than previously presented O(k) multicast routing algorithms on a 10-cube topology.
Sager, Thomas J. and McMillin, Bruce M., "A Fast O(k) Multicast Message Routing Algorithm" (1990). Computer Science Technical Reports. 18.
3rd Symposium on the Frontiers of Massively Parallel Computation (1990: Oct 9-10, College Park, MD)
Keywords and Phrases
Multicomputers; Heuristic Algorithms; NP-completeness; Hypercube; Multicast Communication; Message Routin
© 1990 University of Missouri--Rolla, All rights reserved.
22 Mar 1990