Multicast communication in wormhole-routed star graph interconnection networks

Multicast, an important communication mechanism, is frequently applied in p arallel computing. The star graph interconnection network, when compared wi th the hypercube network, being with low degree and small diameter, has bee n recognized to be an attractive alternative to the popular hypercube netwo rk. In this paper, we derive a node labeling formula based on a hamiltonian path and propose four efficient multicast routing schemes in wormhole-rout ed star networks with multidestination routing capability. All of the four proposed schemes are path-based and deadlock-free. The first scheme, dual-p ath routing, sends the message in parallel through two independent paths (t oward high label nodes and low label nodes). The second one, shortcut-node- based dual-path routing, is similar to dual-path routing except that the ro uting tries to find a shortcut node to route the message as soon as possibl e to reduce the length of transmission path. The third one, multipath routi ng, is a multiple dual-path routing strategy that includes source-to-relay and relay-to-destination phases. The last scheme, proximity grouping routin g, is similar to multipath routing except that in the partitioning step of source anti destination nodes the relation of spatial locality of nodes is also taken into account to reduce the length of transmission paths. Finally , the experimental results are given to show that the performance based on unicast-based and traditional hamiltonian-path routing schemes can be impro ved significantly by the four proposed routing schemes respectively. (C) 20 00 Elsevier Science B.V. All rights reserved.