Optimal Fault-Tolerant Path and Cycle Embedding of Hypercube Networks under the PEF Model

The hypercube serves as a high-performance interconnection network employed in various fields, including data center networks, network-on-chips, and wireless sensor networks. As the number of processing elements rapidly increases, these application fields are facing significant challenges in preserving communication efficiency with robust fault-tolerant mechanisms. Paths and cycles are two effective and popular tools for improving the communication efficiency of large-scale networks. Fault-tolerant path/cycle embedding is recognized as a solution to maintain communication efficiency and fault tolerance simultaneously. In this paper, we aim to enhance the fault-tolerant path/cycle embedding capability of hypercube networks by an emerging fault model, namely the Partitioned Edge Fault (PEF) model. Under this model, we put forward four distinct fault-tolerant path/cycle embedding algorithms that can handle large-scale faulty edges. Moreover, by proving the upper bound of these algorithms’ fault tolerance, we derive the optimal fault-tolerant Hamiltonian laceability and bipancyclicity of hypercubes under the PEF model. Furthermore, we conduct both theoretical and experimental analyses to show our algorithms’ outstanding fault-tolerant capability compared to the state-of-the-art. To validate the practical applicability of our theoretical results, we also develop a deadlock-free routing strategy leveraging the proposed embedding algorithm and compare its performance with benchmark routing algorithms. © 1968-2012 IEEE.