Optimal Fault Tolerance on Crossed Cube Networks with Conditional Faults

Recently, advances in VLSI circuit technology made it possible to build a large parallel and distributed system involving thousands or even tens of thousands of processors. Designing the topology is very important in a parallel and distributed system. Among these networks, the hypercube is a popular interconnection network with many attractive properties. On the other hand, the crossed cube, which is a variation of the hypercube, possesses some properties superior to the hypercube.

Since node and/or link faults may occur to networks, it is significant to consider faulty networks. There are two commonly used fault models, i.e., the arbitrary fault model and the conditional fault model. The arbitrary fault model assumes that the faults may occur everywhere without any restriction, whereas the conditional fault model assumes that the distribution of faults must satisfy some properties.

In this thesis, we are interesting in fault tolerance of crossed cubes under conditional faults. Assuming that each node is incident with at least two fault-free links, we show that an n-dimensional crossed cube contains a fault-free Hamiltonian cycle, even if there are up to 2n-5 link faults. We further show that an n-dimensional crossed cube contains fault-free cycles of all possible lengths. The result is optimal with respect to the number of link faults
tolerated. We also verify that the assumption is practically meaningful by evaluating its probability to occur, which is very close to 1. On the other hand, assuming that each node has at least one fault-free neighbor, we show that an n-dimensional crossed cube has connectivity equal to 2n-2 and (2n-3)-fault diameter equal to [(n+1)/2]+3. All these result shows the fault tolerance of crossed cube is as good as hypercube, under the conditional fault model.