Maximum-shortest-path (MSP) is not optimal for a general N x N torus
A shortest-path routing is optimal if it maximizes the probability of reaching the destination from a given source, assuming that each link in the system has a given failure probability. An approximation for the shortest-path routing policy, maximum-shortest-path (MSP) routing was proposed by Wu [3]. Reference [3] shows that MSP is optimal in the mesh and hypercube networks, shows that MSP is at least suboptimal in the torus network, shows that MSP is optimal for 6 x 6 and 8 x 8 tori, conjectured that MSP is optimal for 2-D tori in general. This short paper shows that, contrary to the claims in [3], MSP is not optimal for a general N x N torus-specifically, MSP is not optimal for a 12 x 12 torus, and its optimal routing depends on the success probability.
optimality torus probability mesh shortest path routing