A constraint-based performance comparison of hypercube and star multicomputer with failures

Many theoretical studies have compared the hypercube and star graphs from a graph theoretical viewpoint, under structural and algorithmic properties. None of these studies have, however, considered real working conditions and implementation constraints. In this paper, the hypercube and star graphs are compared in view of fault tolerance and technological implementation constraints. In order to realize a fair comparison, we use the unsafety-vector fault tolerant routing algorithm, recently introduced in (J. Al-Sadi et al., 2002) and (R. Rezazaad et al., 2004), for the hypercube and star graph. Under two implementation constraints, namely constant bisection bandwidth and constant node pin-out, we have compared the performance of the two networks for different fault rates. The results obtained through simulation experiments reveal that, in the presence of low fault rates, the star graph is of better performance than the hypercube.