Fault Tolerant Models And Fault Tolerant Routing Algorithms In Hypercube Networks With A Large Number Of Faulty Nodes

Hypercube network is one of the most important and attractive network topologies so far. In this thesis, we propose completely new hypercube fault tolerant models based on our new concept of subcube structures, design simple and efficient fault tolerant routing algorithms, and develop powerful and effective probabilistic techniques for analysis of fault tolerance of hypercube networks.We introduce two types of local-connectivity based on subcube structures. The first is the local k-subcube-connectivity, in which for each k-dimensional subcube, the number of non-faulty nodes is larger than that of faulty nodes, and the non-faulty nodes make a connected graph. The second is the local subcube-connectivity, in which for each k > 1, every k-dimensional subcube is contained in an h-dimensional subcube that is locally h-subcube connected. We show that a locally connected hypercube network may contain a constant fraction of faulty nodes, and prove that a locally connected hypercube network is also globally connected. The condition of local-connectivity can be detected and maintained in a distributed manner based on localized management.We develop efficient unicast, broadcast and parallel routing algorithms on locally connected hypercube networks. Our routing algorithms are distributed and local-information-based in the sense that each node in the network knows only its neighbors' status and no global information of the network is required by the algorithms. In particular, our unicast routing algorithms are applicable no matter whether the given hypercube network is locally connected: in case the network is locally connected, the algorithms successfully construct the routing path, while in case our algorithms fail in finding a routing path, they report correctly that the network is not locally connected.We develop powerful and effective probabilistic analysis techniques to study fault tolerant models and the corresponding routing algorithms. Much experiments and experience have shown that hypercube networks are highly fault tolerant. On the other hand, most proposed fault tolerant models for hypercube networks are only able to characterize very rare extreme situations thus significantly underestimating the power of hypercube network fault tolerance. We develop a new scheme that enables us to derive lower bounds for the probability of hypercube network fault tolerance andfor the probability of fault tolerant routing algorithms in terms of node failure probability. Our results provide formal proofs that the hypercube networks can sustain an extremely large number of node failures. Two typical examples are that a 10-cube network of 1024 nodes can sustain up to 10.0% faulty nodes while still keep the non-faulty nodes connected with probability 99.0%, and that if the failure probability of each individual node is bounded by 0.1%, then all hypercube networks of practical size are able to keep their non-faulty nodes connected with probability 99.9%. Our results are best in the hypercube research area. Our results are both theoretically significant and practically important. Our scheme offers very general and powerful techniques for establishing lower bounds on the probability for network connectedness. Our scheme is also applicable to the study of other hierarchical network structures and other network communication problems.