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

Probabilistic Study on Node-to-Node Network Routing Algorithms

基于网络中结点错误概率 ,提出一种新的概率分析方法 ,对网络中点对点的路由算法的容错性概率、路径长度、算法复杂性进行严格的推导 .以超立方体网络为分析的网络拓扑 ,提出在其上的一个路由算法 .分析表明 :在所有实际规模的超立方体网络中 (其结点数可以高达十亿个 ) ,在相当大的结点出错概率 (可高达 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%.