A LOWER-BOUND FOR NEARLY MINIMAL ADAPTIVE AND HOT POTATO ALGORITHMS

Recently, Chinn et al. [10] presented lower bounds for store-and-forwa rd permutation routing algorithms on the n x n mesh with bounded buffe r size and where a packet must take a shortest (or minimal) path to it s destination. We extend their analysis to algorithms that are nearly minimal. We also apply this technique to the domain of hot potato algo rithms, where there is no storage of packets and the shortest path to a destination is not assumed (and is in general impossible). We show t hat ''natural'' variants and ''improvements'' of several algorithms in the literature perform poorly in the worst case. As a result, we iden tify algorithmic features that are undesirable for worst-case hot pota to permutation routing. Recent works in hot potato routing have tried to define simple and greedy classes of algorithms. We show that when a n algorithm is too simple and too greedy, its performance in routing p ermutations is poor in the worst case. Specifically the technique of [ 10] is also applicable to algorithms that do not necessarily send pack ets in minimal or even nearly minimal paths: it may be enough that the y naively attempt to do so when possible. In particular, our results s how that a certain class of greedy algorithms that was suggested recen tly by Ben-Dor et al. [6] contains algorithms that have poor performan ce in routing worst-case permutations.