Hypercube Network Fault Tolerance: A Probabilistic Approach*This work is supported in part by the USA NSF Grant CCR-0000206, and by the China NNSF Grants for Distinguished Young Scholars and for the Changjiang Scholar Reward Project Conference Paper uri icon

abstract

  • © 2002 IEEE. 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.

author list (cited authors)

  • Chen, J., Kanj, I. A., & Wang, G.

citation count

  • 13

publication date

  • January 2002