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

Shih-Chang WANG  Jeng-Ping LIN  Sy-Yen KUO  

IEICE TRANSACTIONS on Information and Systems   Vol.E82-D   No.3   pp.677-686
Publication Date: 1999/03/25
Online ISSN: 
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Fault Tolerant Computing
fault tolerance,  wormhole routing,  hypercube,  multicast,  partitioning,  

Full Text: PDF(1.2MB)>>
Buy this Article

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 routing 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 has been done on fault-tolerant one-to-many (multicast) routing algorithms due to the difficulty in achieving deadlock-free routing on faulty networks. We will develop such an algorithm for faulty hypercubes. Our approach is not based on adding physical or virtual channels to the network topology. Instead, we integrate several techniques such as partitioning of nodes, partitioning of channels, node label assignments, and dual-path multicast to achieve fault tolerance. Both theoretical analysis and simulation are performed to demonstrate the effectiveness of the proposed algorithm.