三维Mesh网络容错路由算法及其概率分析

基于三维Mesh网络中k-Mesh子网连通的概念提出一个简单的基于局部信息和分布式的容错路由算法，并对其容错性进行概率分析．假设每个结点具有独立的出错概率，推导出路由算法成功返回由正确结点组成的路径的概率,结果表明即使三维Mesh网络上非常简单的路由算法也有相当高的成功概率．算法的时间复杂性是线性的,所构造的路由路径长度非常接近两点间的最优路径长度．另外，基于k-Mesh子网容错模型提出的容错路由算法是基于局部信息的和分布式的，因而具有很好的实际意义．

Probabilistic Analysis to Fault-Tolerant Routing Algorithm on 3-D Mesh Networks

With the continuous increasing in network size, routing algorithm in large size networks with faults has become unavoidable. This paper proposes a novel and simple fault tolerant routing algorithm based on the concept of k-submesh connectivity on 3-D mesh networks. Suppose each node has an independent failure probability, we derive the probability that our routing algorithm successfully return a fault-free routing path. The running time o{ the routing algorithm is in liner. Simulation results show that the length of the routing path constructed by this algorithm is very close to the optimal length. In addition, our routing algorithm is distributed and local-information-based and has practically important significance.