Hypercube network fault tolerance: a probabilistic approach

Abstract

Extensive experience has shown that hypercube networks are highly fault tolerant. What is frustrating is that it seems very difficult to properly formulate and formally prove this important fact, despite extensive research efforts in the past two decades. Most proposed fault tolerance models for hypercube networks are only able to characterize very rare extreme situations thus significantly underestimating the fault tolerance power of hypercube networks, while for more realistic fault tolerance models, the analysis becomes much more complicated. We develop new techniques to analyze a realistic fault tolerance model and derive lower bounds for the probability of hypercube network fault tolerance. Our results are both theoretically significant and practically important. Theoretically, our method offers very general and powerful techniques for formally proving lower bounds on the probability of network connectivity, while practically, our results provide formally proven and precisely given upper bounds on node failure probabilities for manufacturers to achieve a desired probability for network connectivity. Our techniques are also useful for analysis of the performance of routing algorithms.