FAULT TOLERANT ROUTING IN THE SUPERCUBE
Vincenzo Auletta, Adele Anna Rescigno, Vittorio Scarano · Parallel Processing Letters · 1993
In this paper we study the fault-tolerant properties of the Supercube, a new inter-connection network recently introduced by Sen [15]. The Supercube is a generalization of the Hypercube that can be realized for any number of nodes and not only for powers of 2. Moreover, it has the same diameter and connectivity of the Hypercube. We shall prove that the diameter of the surviving route graph of the N-node Supercube SN, if less than [ log 2 N] nodes or edges fail, is at most 4 for any minimal routing, and exhibit a minimal routing for which the surviving route graph has diameter 2. Then, we will show that, when 2s+2s−1≤N<2s+1 the failures are [log2 N], the diameter of the surviving route graph is at most 5 for any minimal routing. We will also prove that the fault diameter of SN is exactly [ log 2 N]+1 when N∉{2s+1−1, 2s+1−2, 2s+2s−1+1} and [ log 2 N]+2 otherwise.