A Lower Bound for Nearly Minimal Adaptive and Hot Potato Algorithms |
| |
Authors: | I Ben-Aroya D D Chinn A Schuster |
| |
Affiliation: | (1) Department of Computer Science, Technion, Haifa, Israel 32000. ishai@cs.technion.ac.il., IL;(2) Department of Computer Science and Engineering, University of Washington, Box 352350, Seattle, WA 98195, USA. dci@cs.washington.edu. Current address: Microsoft Corporation, One Microsoft Way, Redmond, WA 98052, USA. dchinn@microsoft.com., US;(3) Department of Computer Science, Technion, Haifa, Israel 32000. assaf@cs.technion.ac.il., IL |
| |
Abstract: | Recently, Chinn et al. 10] presented lower bounds for store-and-forward permutation routing algorithms on the n \times n mesh with bounded buffer size and where a packet must take a shortest (or minimal ) path to its destination. We extend their analysis to algorithms that are nearly minimal. We also apply this technique to
the domain of hot potato algorithms, where there is no storage of packets and the shortest path to a destination is not assumed
(and is in general impossible). We show that ``natural' variants and ``improvements' of several algorithms in the literature
perform poorly in the worst case. As a result, we identify algorithmic features that are undesirable for worst-case hot potato
permutation routing.
Recent works in hot potato routing have tried to define simple and greedy classes of algorithms. We show that when an algorithm
is too simple and too greedy, its performance in routing permutations is poor in the worst case. Specifically, the technique
of 10] is also applicable to algorithms that do not necessarily send packets in minimal or even nearly minimal paths: it
may be enough that they naively attempt to do so when possible. In particular, our results show that a certain class of greedy
algorithms that was suggested recently by Ben-Dor et al. 6] contains algorithms that have poor performance in routing worst-case
permutations.
Received August 24, 1995; revised May 27, 1997. |
| |
Keywords: | , Packet routing in interconnection networks, Permutation routing algorithms, Shortest path routing, |
本文献已被 SpringerLink 等数据库收录! |
|