RESOURCE DEADLOCKS AND PERFORMANCE OF WORMHOLE MULTICAST ROUTING ALGORITHMS

We show that deadlocks due to dependencies on consumption channels are a fundamental problem in wormhole multicast routing. This type of res ource deadlocks has not been addressed in many previously proposed wor mhole multicast algorithms. We also show that deadlocks on consumption channels can be avoided by using multiple classes of consumption chan nels and restricting the use of consumption channels by multicast mess ages. We provide upper bounds for the number of consumption channels r equired to avoid deadlocks. In addition, we present a new multicast ro uting algorithm, column-path, which is based on the well-known dimensi on-order routing used in many multicomputers and multiprocessors. Ther efore, this algorithm could be implemented in existing multicomputers with simple changes to the hardware. Using simulations, we compare the performance of the proposed column-path algorithm with the previously proposed Hamiltonian-path-based multipath and an e-cube-based multica st routing algorithms. Our results show that for multicast traffic, th e column-path routing offers higher throughputs, while the multipath a lgorithm offers lower message latencies. Another result of our study i s that the commonly implemented simplistic scheme of sending one copy of a multicast message to each of its destinations exhibits good perfo rmance provided the number of destinations is small.