Name
Abstract | ||
|---|---|---|
Efficient routing of messages is a key to the performance of multicomputers. Multicast communication refers to the delivery of the same message from a source node to an arbitrary number of destination nodes. While multicast communication is highly demanded in many applications, most of the existing multicomputers do not directly support this service; rather it is indirectly supported by multiple one-to-one or broadcast communications, which result in more network traffic and a waste of system resources. The authors study routing evaluation criteria for multicast communication under different switching technologies. Multicast communication in multicomputers is formulated as a graph theoretical problem. Depending on the evaluation criteria and switching technologies, they study three optimal multicast communication problems, which are equivalent to the finding of the following three subgraphs: optimal multicast path, optimal multicast cycle, and minimal Steiner tree, where the interconnection of a multicomputer defines a host graph. They show that all these optimization problems are NP-complete for the popular 2D-mesh and hypercube host graphs. Heuristic multicast algorithms for these routing problems are proposed |
Year | DOI | Venue |
|---|---|---|
1993 | 10.1109/71.246072 | Parallel and Distributed Systems, IEEE Transactions |
Keywords | DocType | Volume |
graph theory,message passing,multiprocessor interconnection networks,2d-mesh,np-complete,graph theoretical,heuristic algorithms,hypercube,minimal steiner tree,multicast communication,multicomputer networks,multicomputers,optimal multicast cycle,optimal multicast path,routing evaluation,routing of messages,switching technologies,heuristic algorithm,routing,topology,broadcasting,hypercubes,indexing terms,steiner tree,optimization problem,intelligent networks,np complete | Journal | 4 |
Issue | ISSN | Citations |
10 | 1045-9219 | 77 |
PageRank | References | Authors |
5.36 | 19 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Xiaola Lin | 1 | 1099 | 78.09 |
| Lionel M. Ni | 2 | 9462 | 802.67 |