Hot-potato algorithms for permutation routing
Ilan Newman, Assaf Schuster · IEEE Transactions on Parallel and Distributed Systems · 1995
We develop a methodology for the design of hot-potato algorithms for routing permutations. The basic idea is to convert existing store-and-forward routing algorithms to hot-potato algorithms. Using it, we obtain the following complexity bounds for permutation routing: n/spl times/n Mesh: 7n+o(n) steps; 2/sup n/ hypercube: O(n/sup 2/) steps; n/spl times/n Torus: 4n+o(n) steps. The algorithm for the two-dimensional grid is the first to be both deterministic and asymptotically optimal. The algorithm for the 2/sup n/-nodes Boolean cube is the first deterministic algorithm that achieves a complexity of o(2/sup n/) steps.