Probabilistic analysis on fault tolerant routing algorithms on mesh networks

Mesh networks are 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. Supposing 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 linear time. Simulation results show that the length of the routing paths constructed by the algorithms is very close to the optimal length.

Probabilistic analysis on fault tolerant routing algorithms on mesh networks Academic Article