On the Construction of Fault-Tolerant Cube-Connected Cycles Networks

✍ Scribed by J. Bruck; R. Cypher; C.T. Ho

• Publisher: Elsevier Science
• Year: 1995
• Tongue: English
• Weight: 772 KB
• Volume: 25
• Category: Article
• ISSN: 0743-7315
• DOI: 10.1006/jpdc.1995.1032

✦ Synopsis

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 (2 y-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. ol 1995 Academic Press. Inc.