Title :
A fault-tolerant routing strategy in hypercube multicomputers
Author :
Chiu, Ge-Ming ; Wu, Shui-Pao
Author_Institution :
Dept. of Electr. Eng. & Technol., Nat. Taiwan Inst. of Technol., Taipei, Taiwan
fDate :
2/1/1996 12:00:00 AM
Abstract :
We investigate fault-tolerant routing which aims at finding feasible minimum paths in a faulty hypercube. The concept of unsafe node and its extension are used in our scheme. A set of stringent criteria is proposed to identify the possibly bad candidates for forwarding a message. As a result, the number of such undesirable nodes is reduced without sacrificing the functionality of the mechanism. Furthermore, the notion of degree of unsafeness for classifying the unsafe nodes is introduced to facilitate the design of efficient routing algorithms which rely on having each node keep the states of its nearest neighbors. We show that a feasible path of length no more than the Hamming distance between the source and the destination plus four can always be established by the routing algorithm as long as the hypercube is not fully unsafe. The issue of deadlock freeness is also addressed in this research. More importantly, another fault-tolerant routing algorithm, which requires only a constant of five virtual networks in wormhole routing to ensure the property of deadlock freeness for a hypercube of any size, is presented in this paper
Keywords :
concurrency control; fault tolerant computing; hypercube networks; multiprocessing systems; network routing; parallel algorithms; Hamming distance; deadlock freeness; fault-tolerant routing algorithm; fault-tolerant routing strategy; faulty hypercube; hypercube multicomputers; minimum paths; routing algorithms; unsafe node; virtual networks; wormhole routing; Algorithm design and analysis; Computer Society; Delay; Fault tolerance; Hamming distance; Hypercubes; Nearest neighbor searches; Parallel processing; Routing; System recovery;
Journal_Title :
Computers, IEEE Transactions on