A fault-tolerant deadlock-free multicast algorithm for wormhole routed hypercubes

In this paper, we propose a novel fault-tolerant multicast algorithm for n- dimensional wormhole routed hypercubes. 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. Recently, wormhole routin g has become one of the most popular switching techniques in new generation multicomputers. Previous researches have focused on fault-tolerant one-to- one routing algorithms for n-dimensional meshes. However, little research h as been done on fault-tolerant one-to-many (multicast) routing algorithms d ue to the difficulty in achieving deadlock-free routing on faulty networks. We will develop such an algorithm for faulty hypercubes. Our approach is n ot based on adding physical or virtual channels to the network topology. In stead, we integrate several techniques such as partitioning of nodes, parti tioning of channels, node label assignments, and dual-path multicast to ach ieve fault tolerance. Both theoretical analysis and simulation are performe d to demonstrate the effectiveness of the proposed algorithm.