Title :
Feasibility of a fault tolerant routing algorithm for hypercube multiprocessors
Author :
Ali, Rashid ; Abbas, Ash Mohammad ; Khan, Iqbal Ahmad
Author_Institution :
Dept. of Comput. Eng., Aligarh Muslim Univ., India
Abstract :
In this paper, we have evaluated the performance of a fault tolerant routing algorithm based on safety vectors of a node for hypercube interconnection network. We have investigated the feasibility of the algorithm through extensive simulations. The faults are uniformly randomly distributed. We observed that number of faults tolerated by the algorithm for 100% feasibility is less than the dimension n of the hypercube for n≥3. We have heuristically provided a formula for the feasibility of the algorithm. We have observed that empirical feasibility approximately matches with that obtained from simulations.
Keywords :
approximation theory; fault tolerant computing; hypercube networks; network routing; performance evaluation; random processes; approximate matching; empirical feasibility; fault tolerant routing algorithm; hypercube multiprocessor; interconnection network; performance evaluation; safety vector; uniform random distribution; Algorithm design and analysis; Ash; Fault tolerance; Hypercubes; Multiprocessing systems; Multiprocessor interconnection networks; Prototypes; Routing; Safety; Unicast;
Conference_Titel :
India Annual Conference, 2004. Proceedings of the IEEE INDICON 2004. First
Print_ISBN :
0-7803-8909-3
DOI :
10.1109/INDICO.2004.1497786
