An optimal routing policy for mesh-connected topologies

We present a new routing policy, called maximum shortest paths (MP) routing policy, within the class of shortest-path routing policies for mesh-connected topologies which include popular 2-D and 3-D meshes, 2-D and 3-D tori, and n-dimensional hypercubes (n-cubes). In this policy, the routing message is always forwarded to a neighbor from which there exists a maximum number of shortest paths to the destination. An optimal routing defined in this paper is the one that maximizes the probability of reaching the destination from a given source without delays at intermediate nodes. We show that the MP routing policy is equivalent to the e-cube routing in n-cubes which is optimal, and it is also equivalent to the Badr and Podar´s zig-zag (Z²) routing policy in 2-D meshes which is also optimal. We prove that the Z² routing policy is not optimal in any N×N torus, where N is an even number larger than four. A routing algorithm is proposed to implement the MP routing policy in 2-D tori and if is proved to be at least suboptimal (optimal for some cases). Our approach is the first attempt to address optimal routing in the torus network which is still an open problem