网络容错路由算法概率分析的一种新的方法  

A New Approach to Probabilistic Analysis of Network Fault Tolerant Routing Algorithms

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

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

出　　处：《计算机工程与应用》2003年第15期49-52,59,共5页Computer Engineering and Applications

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

摘　　要：该文提出了一种新的概率分析方法来研究在给定结点错误概率的情况下超立方体网络强容错路由算法的容错性的概率。针对文中提出的基于新的局部连通性网络容错模型的高效的强容错路由算法犤1犦,该文首次严格证明了一个具有1024个结点的10维超立方体网络能够容许多达4.7%的错误结点而具有99%的概率确保找到正确结点组成的路径,而如果结点的错误概率不超过0.1%,则所有实际规模的超立方体网络能够具有99.9%的概率确保找到正确结点组成的路径。该算法的时间性能是最优的,且该算法构造的路径的长度不超过源结点和目的结点之间海明距离的两倍加上一个很小的常数。This paper develops a new probabilistic analysis approach to derive lower bounds for the probability of strongly fault tolerant routing algorithm in hypercube networks in terms of node failure probability.With the efficient and strongly fault tolerant routing algorithm based on the new locally-connected hypercube fault tolerant model 1 ,the paper formally proves the following results:a10(cube network of1024nodes can sustain up to4.7%faulty nodes while still keeping the routing algorithm running well with probability99%,and if the failure probability of each individual node is bounded by0.1%,then all hypercube networks of practical size are able to keep the routing algorithm running well with probability99.9%.Here,the“running well”means that the routing algorithm runs in optimal time and constructs a routing path of length bounded by a small constant plus twice of the Hamming distance between any two given non-faulty nodes.

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

分 类 号：TP302[自动化与计算机技术—计算机系统结构]