Cycle embedding in faulty enhanced hypercube networks
Yihan Fan, Hongmei Liu, Qing Liu · 2012
In recent three decades, several variants of the hypercube networks have been proposed to enhance the performance and reliability. The so called enhanced hypercube networks (denoted by Qn,k) is one of the most versatile and efficient interconnection networks for the parallel computation, aiming to fully realize the potential of those networks where reliability, speed and tolerance are critical. In this paper, the properties related to cycles embedding in faulty Qn,khave been investigated. This study demonstrates that when the number of fault nodes in Qn,kis only one, if n and k have the same parity, then the cycles of every even length from 4 to 2n- 2 can be embedded in the faulty Qn,k; if n and k have different parity, then the cycles of every even length from 4 to 2n- 2 and every odd length from n - k + 2 to 2n- 1 can be embedded in the faulty Qn,k. When the number of fault links is no more than n - 1, in Qn,k, if n and k have the same parity, then every non-fault link of Qn,klies on a cycle of every even length from 4 to 2n. These results show that with cycle embedding, the enhanced hypercube networks have very good fault tolerance and reliability as a topological structure of multi-computer networks.