Pure Greedy Hot-Potato in the 2-D Mesh with Random Destinations
Paul Spirakis, Vassilis Triantafillou · Parallel Processing Letters · 1997
We analyze here a pure greedy hot-potato routing strategy on a two-dimensional mesh of n 2 nodes. We specifically study the case of n 2 packets, originating one per node, to be delivered at random uniform destinations. Each packet attempts to follow the shortest path leading first to the destination row/column (whichever is closest) and then to the actual destination node. A deflection policy ia adopted to solve conflicts. We prove that all packets are delivered to the destinations in average time O(nlogn). The average is taken over all possible destination functions. No average case analysis of pure greedy hot-potato routing was known up to now.