Adaptive path-based multicast on wormhole-routed hypercubes

Abstract

In this paper, we consider path-based multicast on wormhole-routed hypercubes. A minimum set of routing restrictions is used as the base routing algorithm. To correctly perform multicast, we present the natural list to sort the destination nodes. It can be proved to be deadlock-free for both one-port and multi-port systems. Furthermore, it creates only one worm for each multicast. Between each pair of nodes in a multicast path with distance k, on the average, there are at least (k+1)!/2(k) adaptive shortest paths, which is superior to previous works. We also propose a heuristic algorithm to reduce the path length. The simulation result shows that its sustainable throughput is much better than related works. In addition, unicast and broadcast can be treated as degenerated cases and use the same routing algorithm. Therefore, it offers a comprehensive routing solution for communication on hypercubes.