GREEDY HOT-POTATO ROUTING ON THE 2-DIMENSIONAL MESH

We propose hot-potato (or, deflection) packet routing algorithms on th e two-dimensional mesh. The algorithms are strongly greedy in the sens e that they attempt to send packets in good directions whenever possib le. Furthermore, the routing operations are simple and independent of the time that has elapsed. The first algorithm gives the best evacuati on time known for delivering all the packets to their destinations. A batch of k packets with maximal source-to-destination distance d(max) delivered in 2(k - 1) + d(max). The second algorithm improves this bou nd to k + d(max) when all packets are destined to the same node. This also implies a new bound for the multitarget case, which is the first to take into account the number of in-edges of a node. The third algor ithm is designed for routing permutations with source-to-destination d istance at most three, in which case the algorithm terminates in at mo st seven steps. We also show a lower bound of five steps for this prob lem.