Open Access System for Information Sharing

Login Library

 

Article
Cited 18 time in webofscience Cited 22 time in scopus
Metadata Downloads

DEADLOCK-FREE FAULT-TOLERANT ROUTING IN INJURED HYPERCUBES SCIE SCOPUS

Title
DEADLOCK-FREE FAULT-TOLERANT ROUTING IN INJURED HYPERCUBES
Authors
KIM, JSHIN, KG
Date Issued
1993-09
Publisher
IEEE COMPUTER SOC
Abstract
Wormhole routing with the e-cube algorithm is an excellent solution for deadlock-free interprocess communication in healthy hypercubes. However, it does not work for injured hypercubes where some nodes and/or links are faulty. In this paper, we propose a new deadlock-free routing scheme in an injured hypercube with the wormhole routing capability. All previously proposed schemes suggest the use of virtual channels to avoid the cycle of resource dependency. By contrast, our scheme is based on the re-establishment of a routing path to the destination, but it does not always yield a shortest path between the source and destination. The proposed routing scheme uses either wormhole routing or staged routing, depending on the availability of one or more healthy (n - 2)-cubes within an injured n-cube, Q(n). Every node decides the availability of a healthy Q(n-2) independent of others based on the information of faulty components broadcast to the node. To establish a deadlock-free path between every pair of nodes in an injured Q(n) using wormhole routing alone, there must exist at least one healthy Q(n-2) within the Q(n). Clearly, when the number of faults increases, it is less likely a healthy Q(n-2) will exist in the injured Q(n). In case no healthy Q(n-2) exists within an injured Q(n), our scheme switches to staged routing. The proposed scheme is analyzed in terms of robustness and average number of message hops, and is compared with a previously proposed virtual channel scheme. Our analytical results show that one can find at least one healthy Q(n-2) until approximately 2n (n < 10) nodes become faulty, and the increase in average message distance is at most one hop. Our simulation results show that the proposed scheme yields a smaller message latency and a higher percentage of successful message delivery than the virtual channel scheme.
URI
https://oasis.postech.ac.kr/handle/2014.oak/22018
DOI
10.1109/12.241597
ISSN
0018-9340
Article Type
Article
Citation
IEEE TRANSACTIONS ON COMPUTERS, vol. 42, no. 9, page. 1078 - 1088, 1993-09
Files in This Item:
There are no files associated with this item.

qr_code

  • mendeley

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.

Related Researcher

Researcher

김종KIM, JONG
Dept of Computer Science & Enginrg
Read more

Views & Downloads

Browse