Robust algorithms for packet routing in a mesh

Abstract

This paper considers the problem of permutation packet routing on a √ × √ meshconnected array of processors. Each node in the array is assumed to be independently faulty with a probability bounded above by a value p. This paper gives a routing algorithm which, if p < 0.29, will with very high probability route every packet that can be routed in O(√nlog n) steps with queue lengths that are O(log 2 n). Extensions to higher-dimensional meshes are given.