超立方体网络容错性的概率分析

A probabilistic analysis on fault tolerance of hypercube networks

用概率分析的方法研究在给定结点错误概率的情况下超立方体网络容错性的概率,证明了一个具有1024个结点的10维超立方体网络能够容许多达10%的错误结点而具有99％的概率确保正确结点的连通性;如果结点的错误概率不超过0.1％,则所有实际规模的超立方体网络(结点数可多达1万亿个)能够具有99.9％的概率确保正确结点的连通性.研究结果表明,所提出的方法也能够用于研究其他层次结构的网络和其他网络通信问题.

A new scheme that enables us to derive lower bounds for the probability of hypercube network fault tolerance in terms of node failure probability is developed. The authors formally prove that a 10-cube network of 1 024 nodes can sustain up to 10% faulty nodes (i. e. , over 100 faulty nodes) while still keep the non-faulty nodes connected with probability 99%, and that if the failure probability of each individual node is bounded by 0.1%, then all hypercube networks of practical size (e. g. , up to a trillion nodes) are able to keep their non-faulty nodes connected with probability 99. 9%. It is noticeable that the scheme is also applicable to the study of other hierarchical network structures and of other network communication problems.