Feasibility of a fault tolerant routing algorithm for hypercube multiprocessors

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/spl ges/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.