Fault-tolerant message routing in hypercube using local neighborhood information

We present fault-tolerant message (packet) routing algorithms for hypercubes that make use of the 2-neighborhood information. Our algorithms can tolerate (i) up to n faulty components in any Hamming ball of radius 3, and (ii) up to n-1 faulty components in the Hamming ball of radius 2 centered at th...

Full description

Saved in:
Bibliographic Details
Main Authors: Pao, D.C.W., Chi-Kueng Chan
Format: Conference Proceeding
Language:English
Subjects:
Cities and towns
Fault tolerance
Hamming distance
Heuristic algorithms
Hypercubes
Peer to peer computing
Routing
System recovery
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We present fault-tolerant message (packet) routing algorithms for hypercubes that make use of the 2-neighborhood information. Our algorithms can tolerate (i) up to n faulty components in any Hamming ball of radius 3, and (ii) up to n-1 faulty components in the Hamming ball of radius 2 centered at the destination node. The path length of the packet is less than or equal to 3k, where k is the Hamming distance from the source to destination. We also show that /spl Omega/(k/sup 2/) faults are required to make a packet to undertake a route of length 3k. A simulation study of the performance of the routing algorithms is presented. The structured buffer pool technique can be incorporated into our routing algorithms to prevent deadlock from occurring.< >
DOI:10.1109/TENCON.1994.369262