Title :
Fault-tolerant adaptive and shortest routing in 2-D extended meshes using faulty-block-information
Author_Institution :
Dept. of Comput. Sci., Southwest Texas State Univ., San Marcos, TX, USA
Abstract :
In this paper, I first discuss the adaptive minimal routing algorithm in 2D extended meshes without faulty blocks. Then, a sufficient condition for the existence of a minimal path from the source to the destination is presented. After that, I propose the shortest fault-tolerant routing algorithm with one faulty block, with the guidance of faulty block information, and I extend the algorithm with one faulty block to one with multiple faulty blocks. This is the first attempt to address routing algorithms on an extended mesh
Keywords :
adaptive systems; fault tolerant computing; minimisation of switching nets; multiprocessor interconnection networks; network routing; 2D extended meshes; adaptive minimal routing algorithm; faulty block information; minimal path existence; multiple faulty blocks; shortest fault-tolerant routing algorithm; sufficient condition; Communication networks; Communication switching; Computer science; Costs; Fault tolerance; Hypercubes; Nearest neighbor searches; Network topology; Routing; Telecommunication network reliability;
Conference_Titel :
Parallel Processing, 2000. Proceedings. 2000 International Workshops on
Conference_Location :
Toronto, Ont.
Print_ISBN :
0-7695-0771-9
DOI :
10.1109/ICPPW.2000.869112
