On the Construction of Fault-Tolerant Cube-Connected Cycles Networks |
| |
Affiliation: | Caltech, Mail Code 116 81, Pasadena, CA 91125, USA; Johns Hopkins Univ, Dept Comp Sci, Baltimore, MD 21218, USA and IBM Corp, Almaden Res Lab, San Jose, CA 95120, USA |
| |
Abstract: | This paper presents a new approach to tolerating edge faults and node faults in (CCC) networks of Cube-Connected Cycles in a worst-case scenario. Our constructions of fault-tolerant CCC networks are obtained by adding extra edges to the CCC. The main objective is to reduce the cost of the fault-tolerant network by minimizing the degree of the network. Specifically, we have two main results. (i) We have created a fault tolerant CCC that can tolerate any single fault, either a node fault or an edge fault. When the dimension of the CCC is odd, the degree of the fault tolerant graph is 4. In the even case, there is a single node per cycle that is of degree 5 and the rest are of degree 4. (ii) We have created a fault-tolerant CCC, where every node has degree y + 2, which can tolerate any 2y − 1 cube-edge faults. Our constructions are extremely efficient for the case of edge faults-they result in healthy CCC networks that utilize all of the processors. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|