Crossed Cube And To Strengthen Cross-cube Interconnection Networks And Fault-tolerant Nature

In designing or selecting a topology for a parallel processing system, one fundamental consideration is system-level fault tolerance. In order to improve the fault tolerance, the paper analyses from the two following sides: One is by adding the less links related to the original networks, modifying the topology of the original one, we get higher fault tolerance of the new network; The other is under the same topology network, ignoring the likelihood of one processor and ail its neighbors failing at the same time, or considering the distribution of the faulty nodes, that is studying the fault tolerance under the conditional connectivity or cluster-fault-lolerance. the paper proved under these condition, the fault tolerance of the network is improved remarkably. More, if under the fault-tolerant systems, how to find a free path from any two free processors? That related to fault tolerant routing which is also hot recently.The recently introduced interconnection network, the crossed cube, has attracted much attention in the parallel processing area due to its many attractive features, for example, its small diameter, strong connectivity, the ability to simulate other architectures, and its high degrees of diagnosability etc. In order to improve the faulty tolerance of the crossed cube, we proposed a new network, the enhanced crossed cube. The paper will study the upper questions based on the two interconnection networks.First, we give a fault-tolerant routing algorithm under the connectivity of the crossed cube in O(n) time and the length of the longest routing path; Second, with the rapid progress in VLSI, the failing probability of processors and links is very low, the traditional connectivity underestimates the resilience of large networks/Here by applying the concept "conditional connectivity" introduce by Harary, we show that the n-crossed cube can tolerate up to 2n-3 (n>2)processors failure and remain connected provide that all the neighbors of each processor do not'fail at the same time, the result is the same as the hypercube. We also give a related algorithm in O(n) time, and the length of the longest path; Third, we apply cluster faun tolerance introduced by Q.-P. Gu to the crossed cube, and proved that for node-to-node routing, the crossed cube can tolerate as many as n-1 faulty clusters of diameter ai most 1 with at most 2n-3 (n>2)faully nodes in total which isas good as the hypercube.For the next interconnection network, we proved the connectivity of the n-enhanced crossed cube is n+1, and its conditional connectivity is 2n(n>3) provided that all the neighbors of each professor do not fail at the same time, which is better than the hypercube and the crossed cube, two related algorithms in O(n) time are also given; More, we proved that the n-enhanced crossed cube can tolerate as many as n faulty clusters of diameter at most 1 with at most 2n-1 faulty nodes in total(n>3), which is better than the hypercube and the crossed cube also.