Fault-Tolerant Routing In Hypercube Networks With Extended Local-Connectivity

In an n-dimensional hypercube, or n-cube for short, removing neighbors of any node u will disconnect u from the other part of the network. Therefore, the fault tolerance of an n- dimensional hypercube is n ? 1. But it is an extreme situation. In the realistic case, the pro-bability that the n faulty nodes are exactly the neighbors of a nonfaulty node is very low. Also, the ratio of the number of faulty nodes to the total number of nodes is too small to have a practical impact. Much effort has been devoted to introduce realistic definitions to improve fault tolerant capacity. Wang Guo-jun et al proposed two distributed routing algorithms in hypercube with large amount of faulty nodes based on two local subcube-connectivities, but faulty nodes were less than half the nodes of hypercube .In this paper,based on the concepts of local k-subcube-connectivity and local subcube-connectivity for hypercube networks, two new concepts—extended local k-subcube-connectivity and extended local subcube-connectivity are proposed.We prove that all non-faulty nodes in a hypercube network with extended local k-subcube-connectivity or extended local subcube-connectivity are connected.Based on extended local subcube-connectivity,the unicast fault-tolerant routing algorithm is proposed . Based on extended local k-subcube-connectivity and extended local subcube-connectivity,we give out unicast fault-tolerant routing algorithm,broadcast fault-tolerant routing algorithm and multcast fault-tolerant routing algorithm in a hypercube network. According to the simulation experiment result,compared with the algorithms based on local-connectivity,the algorithms based on extended local-connectivity improve fault tolerant capacity and generality.