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

摘要

Reviews a 1-fault-tolerant (1-ft) hypercube model with degree 2r: the ring-connected network (RCN), which has the lowest degree among all 1-ft, one-spare node, r-dimensional hypercube architectures yet discovered. Then, we propose a constant-time reconfiguration algorithm via an add-and-modulo automorphism. Furthermore, by introducing the equivalence from hypercubes to cube-connected cycles (CCCs) and to butterflies (BFs), we find that there is also a corresponding equivalence from RCNs to cubical ring-connected cycles (CRCCs) and to dynamic redundancy networks (DRNs). From this fact, we find that once a symmetric fault-tolerant structure has been discovered for one of the three models, then it can be applied directly to the other hypercubic networks. Applying the technique, we find a degree-6, 1-ft Benes network. We think that more attention should be paid to the strong relationship between hypercubes, CCCs and BFs. Finally, from this equivalence relationship we propose three new bounded-degree k-ft models: k-ft CCCs, k-ft BFs and k-ft Benes networks.