Maximum-shortest-path (MSP) is not optimal for a general N X N torus
Li Sheng, Jie Wu · IEEE Transactions on Reliability · 2003
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 (see ibid., vol.48, no.3, p.247-55, 1999). Wu shows that: MSP is optimal in the mesh and hypercube networks; MSP is at least suboptimal in the torus network; MSP is optimal for 6 /spl times/ 6 and 8 /spl times/ 8 tori; and conjectured that MSP is optimal for 2-D tori in general. This short paper shows that, contrary to the claims by Wu, MSP is not optimal for a general N /spl times/ N torus-specifically, MSP is not optimal for a 12 /spl times/ 12 torus, and its optimal routing depends on the success probability.