Randomized greedy hot-potato routing
Costas Busch, Maurice P. Herlihy, Rogert Wattenhofer · 2000
We present a novel greedy hot-potato routing algorithm for the 2-dimensional n n mesh or torus. This algorithm uses randomization to adjust packet priorities. For any permutation problem or random destination problem, it ensures that each packet reaches its destination in asymptotically optimal expected O(n) steps, and all packets reach their destinations in O(n ln n) steps with high probability, an improvement over the previously-known deterministic upper bound of O(n²) for greedy algorithms. For a general batch problem, with high probability all packets reach their destination nodes in at most O(m ln n) steps, where m = min(mr ; mc ), where mr and mc are respectively the maximum number of packets targeted to a single row or column.