A Fault-Tolerant Deadlock-Free Multicast Algorithm for Wormliole Routed Hypercubes

摘要

In this paper, we propose a novel fault-tolerant multicast algorithm for n-dimensional wormhole routed hyper- cubes. The multicast algorithm will remain functional if the number of faulty nodes in an n-dimensional hypercube is less than n. Multicast is the delivery of the same message from one source node to an arbitrary number of destination nodes. Re- cently, wormhole routing has become one of the most popular switching techniques in new generation multicomputers. Previ- ous researches have focused on fault-tolerant one-to-one routing algorithms for n-dimensional meshes. However, little research has been done on fault-tolerant one-to-many (multicast) routing algorithms due to the difficulty in achieving deadlock-free rout- ing on faulty networks. We will develop such an algorithm for faulty hypercubes. Our approach is not based on adding phys- ical or virtual channels to the network topology. Instead, we integrate several techniques such as partitioning of nodes, parti- tioning of channels, node label assignments, and dual-path mul- ticast to achieve fault tolerance. Both theoretical analysis and simulation are performed to demonstrate the effectiveness of the proposed algorithm.