The search functionality is under construction.

The search functionality is under construction.

Many researchers have used hypercube interconnection networks for their good properties to construct many parallel processing systems. However, as the number of processors increases, the probability of occurrences of faulty nodes also increases. Hence, for hypercube interconnection networks which have faulty nodes, several efficient dynamic routing algorithms have been proposed which allow each node to hold status information of its neighbor nodes. In this paper, we propose an improved version of the algorithm proposed by Chiu and Wu by introducing the notion of full reachability. A fully reachable node is a node that can reach all nonfaulty nodes which have Hamming distance *l* from the node via paths of length *l*. In addition, we further improve the algorithm by classifying the possibilities of detours with respect to each Hamming distance between current and target nodes. We propose an initialization procedure which makes use of an equivalent condition to perform this classification efficiently. Moreover, we conduct a simulation to measure the improvement ratio and to compare our algorithms with others. The simulation results show that the algorithms are effective when they are applied to low-dimensional hypercube interconnection networks.

- Publication
- IEICE TRANSACTIONS on Information Vol.E84-D No.1 pp.121-128

- Publication Date
- 2001/01/01

- Publicized

- Online ISSN

- DOI

- Type of Manuscript
- PAPER

- Category
- Fault Tolerance

The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.

Copy

Keiichi KANEKO, Hideo ITO, "Fault-Tolerant Routing Algorithms for Hypercube Interconnection Networks" in IEICE TRANSACTIONS on Information,
vol. E84-D, no. 1, pp. 121-128, January 2001, doi: .

Abstract: Many researchers have used hypercube interconnection networks for their good properties to construct many parallel processing systems. However, as the number of processors increases, the probability of occurrences of faulty nodes also increases. Hence, for hypercube interconnection networks which have faulty nodes, several efficient dynamic routing algorithms have been proposed which allow each node to hold status information of its neighbor nodes. In this paper, we propose an improved version of the algorithm proposed by Chiu and Wu by introducing the notion of full reachability. A fully reachable node is a node that can reach all nonfaulty nodes which have Hamming distance *l* from the node via paths of length *l*. In addition, we further improve the algorithm by classifying the possibilities of detours with respect to each Hamming distance between current and target nodes. We propose an initialization procedure which makes use of an equivalent condition to perform this classification efficiently. Moreover, we conduct a simulation to measure the improvement ratio and to compare our algorithms with others. The simulation results show that the algorithms are effective when they are applied to low-dimensional hypercube interconnection networks.

URL: https://global.ieice.org/en_transactions/information/10.1587/e84-d_1_121/_p

Copy

@ARTICLE{e84-d_1_121,

author={Keiichi KANEKO, Hideo ITO, },

journal={IEICE TRANSACTIONS on Information},

title={Fault-Tolerant Routing Algorithms for Hypercube Interconnection Networks},

year={2001},

volume={E84-D},

number={1},

pages={121-128},

abstract={Many researchers have used hypercube interconnection networks for their good properties to construct many parallel processing systems. However, as the number of processors increases, the probability of occurrences of faulty nodes also increases. Hence, for hypercube interconnection networks which have faulty nodes, several efficient dynamic routing algorithms have been proposed which allow each node to hold status information of its neighbor nodes. In this paper, we propose an improved version of the algorithm proposed by Chiu and Wu by introducing the notion of full reachability. A fully reachable node is a node that can reach all nonfaulty nodes which have Hamming distance *l* from the node via paths of length *l*. In addition, we further improve the algorithm by classifying the possibilities of detours with respect to each Hamming distance between current and target nodes. We propose an initialization procedure which makes use of an equivalent condition to perform this classification efficiently. Moreover, we conduct a simulation to measure the improvement ratio and to compare our algorithms with others. The simulation results show that the algorithms are effective when they are applied to low-dimensional hypercube interconnection networks.},

keywords={},

doi={},

ISSN={},

month={January},}

Copy

TY - JOUR

TI - Fault-Tolerant Routing Algorithms for Hypercube Interconnection Networks

T2 - IEICE TRANSACTIONS on Information

SP - 121

EP - 128

AU - Keiichi KANEKO

AU - Hideo ITO

PY - 2001

DO -

JO - IEICE TRANSACTIONS on Information

SN -

VL - E84-D

IS - 1

JA - IEICE TRANSACTIONS on Information

Y1 - January 2001

AB - Many researchers have used hypercube interconnection networks for their good properties to construct many parallel processing systems. However, as the number of processors increases, the probability of occurrences of faulty nodes also increases. Hence, for hypercube interconnection networks which have faulty nodes, several efficient dynamic routing algorithms have been proposed which allow each node to hold status information of its neighbor nodes. In this paper, we propose an improved version of the algorithm proposed by Chiu and Wu by introducing the notion of full reachability. A fully reachable node is a node that can reach all nonfaulty nodes which have Hamming distance *l* from the node via paths of length *l*. In addition, we further improve the algorithm by classifying the possibilities of detours with respect to each Hamming distance between current and target nodes. We propose an initialization procedure which makes use of an equivalent condition to perform this classification efficiently. Moreover, we conduct a simulation to measure the improvement ratio and to compare our algorithms with others. The simulation results show that the algorithms are effective when they are applied to low-dimensional hypercube interconnection networks.

ER -