Maximum-shortest-path (MSP): an optimal routing policy for mesh-connected multicomputers

This paper presents a new routing policy maximum-shortest-path (MSP), 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 binary hypercubes (n-cubes). In MSP, the routing message is always forwarded to a neighbor from which there exists a maximum number of shortest paths to the destination. The optimal routing (defined in this paper) maximizes the probability of reaching the destination from a given source without delays at intermediate nodes, assuming that each link in the system has a given failure probability. The results show that: the optimal e-cube routing in n-cubes is a special implementation of MSP. MSP is equivalent to the Badr and Podar zig-zag (Z²) routing policy in 2-D meshes which is also optimal. The Z² routing policy is not optimal in any N×N torus, where N>4 is an even number. A new routing algorithm implements MSP in 2-D tori and is at least suboptimal. Two examples are used in 6×6 and 8×8 tori to demonstrate that MSP is optimal for some 2-D tori. This is the first attempt to address optimal routing in the torus network, which still is an open problem