Mesh网络路由算法容错性的概率分析

该文基于k-Mesh子网的概念提出了两个简单的基于局部信息和分布式的Mesh网络容错路由算法，并对其容错性进行概率分析；在每个结点具有独立的出错概率的假设条件下，推导出路由算法成功返回由正确结点组成的路径的概率．该文运用严格的数学推理，证明了Mesh网络结点出错概率只要控制在1．87％以内，则对于多达几十万个结点的Mesh网络，提出的路由算法具有99％的概率确保找到正确结点组成的路径．路由算法的时间复杂性是线性的．模拟结果表明路由算法所构造的路由路径长度非常接近于两结点之间的最优路径长度．

Probabilistic Analysis on Fault Tolerant Routing Algorithms on Mesh Networks

Mesh networks are a kind of very important network topologies in massively multiprocessor parallel systems. With the continuous increasing in network size, routing algorithm in large size networks with faults has become unavoidable. This paper mainly focuses on fault tolerant routing algorithm on mesh networks. Based on the concept of k submesh, this paper proposes two simple routing algorithms for mesh networks. The algorithms are distributed and local information based. Authors apply probabilistic analysis on the fault tolerance of above routing algorithms. Suppose each node has an independent failure probability, it is able to derive the probability that the routing algorithms successfully return a fault free routing path. For example, authors formally prove that as long as the node failure probability is bounded by 1.87%, the routing algorithms succeed in finding a fault free routing path with probability at least 99%. The routing algorithms run in liner time. Simulation results show that the length of the routing paths constructed by the algorithms is very close to the optimal length.