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

A probabilistic analysis on fault tolerance of hypercube networks

作　　者：王国军[1] 张祖平[1] 陈建二[1] 陈松乔[1] 

机构地区：[1]中南大学信息科学与工程学院,湖南长沙410083

出　　处：《中南工业大学学报》2003年第1期79-83,共5页Journal of Central South University of Technology(Natural Science)

基　　金：国家杰出青年自然科学基金(B类)资助项目(69928201);长江学者奖励计划项目(2000~2002年);教育部高等学校骨干教师资助计划项目(2000~2002年)

摘　　要：用概率分析的方法研究在给定结点错误概率的情况下超立方体网络容错性的概率,证明了一个具有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.

关 键 词：互联网络 超立方体网络 路由算法 容错性 概率分析 连通性 

分 类 号：O157.5[理学—数学] TP302[理学—基础数学]