For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
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
Publication Date: 1999/03/25
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Fault Tolerant Computing
fault tolerance, wormhole routing, hypercube, multicast, partitioning,
Full Text: PDF(1.2MB)>>
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.