点对点网络容错路由算法的概率分析  

Probabilistic Study on Node-to-Node Network Routing Algorithms

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

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

出　　处：《小型微型计算机系统》2004年第10期1754-1758,共5页Journal of Chinese Computer Systems

基　　金：国家杰出青年自然科学基金 ( 6992 82 0 1)资助;国家自然科学基金 ( 60 3 73 0 83 )资助;长江学者奖励计划

摘　　要：基于网络中结点错误概率 ,提出一种新的概率分析方法 ,对网络中点对点的路由算法的容错性概率、路径长度、算法复杂性进行严格的推导 .以超立方体网络为分析的网络拓扑 ,提出在其上的一个路由算法 .分析表明 :在所有实际规模的超立方体网络中 (其结点数可以高达十亿个 ) ,在相当大的结点出错概率 (可高达 8% )的情况下 ,路由算法可达到 99.Based on node failure probability,proposesed a new probabilistic analysis method to study the success probability,routing path length,and time complexity of network routing algorithms.It used hypercube as our network topology and propose a routing algorithm.The analysis shows that for all hypercube networks of practical size (can be up to 10 9 nodes),and for very significant node failure probability (can be up to 8%),the algorithm runs in linear time and successfully constructs a routing path with probability larger than 99.9%.

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

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