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

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

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

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

Full Text Views

0

Cite this

Summary :

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.

Publication: IEICE TRANSACTIONS on Information Vol.E82-D No.3 pp.677-686

Publication Date: 1999/03/25

Publicized

Online ISSN

DOI

Type of Manuscript: PAPER

Category: Fault Tolerant Computing

Cite this

Copy

Shih-Chang WANG, Jeng-Ping LIN, Sy-Yen KUO, "A Fault-Tolerant Deadlock-Free Multicast Algorithm for Wormhole Routed Hypercubes" in IEICE TRANSACTIONS on Information, vol. E82-D, no. 3, pp. 677-686, March 1999, doi: .
Abstract: 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.
URL: https://global.ieice.org/en_transactions/information/10.1587/e82-d_3_677/_p

Copy

@ARTICLE{e82-d_3_677,
author={Shih-Chang WANG, Jeng-Ping LIN, Sy-Yen KUO, },
journal={IEICE TRANSACTIONS on Information},
title={A Fault-Tolerant Deadlock-Free Multicast Algorithm for Wormhole Routed Hypercubes},
year={1999},
volume={E82-D},
number={3},
pages={677-686},
abstract={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.},
keywords={},
doi={},
ISSN={},
month={March},}

Copy

TY - JOUR
TI - A Fault-Tolerant Deadlock-Free Multicast Algorithm for Wormhole Routed Hypercubes
T2 - IEICE TRANSACTIONS on Information
SP - 677
EP - 686
AU - Shih-Chang WANG
AU - Jeng-Ping LIN
AU - Sy-Yen KUO
PY - 1999
DO -
JO - IEICE TRANSACTIONS on Information
SN -
VL - E82-D
IS - 3
JA - IEICE TRANSACTIONS on Information
Y1 - March 1999
AB - 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.
ER -