Abstract

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.

Meeting Name

3rd Symposium on the Frontiers of Massively Parallel Computation (1990: Oct 9-10, College Park, MD)

Department(s)

Computer Science

Keywords and Phrases

Multicomputers; Heuristic Algorithms; NP-completeness; Hypercube; Multicast Communication; Message Routin

Report Number

CSc-90-2

Document Type

Technical Report

Document Version

Final Version

File Type

text

Language(s)

English

Rights

© 1990 University of Missouri--Rolla, All rights reserved.

Publication Date

22 Mar 1990

Download

Share

 
COinS