Ring-connected hypercubes and their relationship to cubical ring connected cycles and dynamic redundancy networks

摘要

In this paper, we first present a 1-fault-tolerant (1-ft) hypercube model with degree 2r, the ring-connected hypercube (RCH), which has the lowest degree among all 1-ft, one spare node, r-dimensional hypercube architecture yet discovered. Then we propose a zero-time reconfiguration algorithm via an add-and-modulo automorphism. Furthermore, by introducing the equivalence from hypercubes to cube-connected cycles (CCC's) and to butterflies (BF's), we find there is also a corresponding equivalence from RCH's to cubical ring connected cycles (CRCC) and to dynamic redundancy networks (DRN's). From this fact, we find out that once a symmetric fault-tolerant structure has been discovered for one of the three models, then it can apply directly to the other hypercubic networks. Applying the technique, we find a degree 6, 1-ft Benes network. Another point is we think that the strong relationship between hypercubes, CCC's and BF's should be paid more attention, and finally from this equivalence relationship to the RCH's we propose three new bounded-degree k-ft models: k-ft CCC's, k-ft BF's, and k-ft Benes networks.