An adaptive routing algorithm is one in which the path a packet takes from its source to its destination may depend on other packets it encounters. Such algorithms potentially avoid network bottlenecks by routing pack- ets around "hot spots." Minimal adaptive routing al- gorithms have the additional advantage that the path each packet takes is a shortest one. For a large class of minimal adaptive routing algo- rithms, we present an (n2/k2) bound on the worst case time to route a static permutation of packets on an nxn mesh or torus with nodes that can hold up to k > 1 packets each. This is the first nontrivial lower bound on adaptive routing algorithms. The argument extends to more general routing problems, such as the h-h rout- ing problem. It also extends to a large class of dimen- sion order routing algorithms, yielding an (n2/k) time bound. To complement these lower bounds, we present two upper bounds. One is an O(n2/k) time dimension order routing algorithm that matches the lower bound. The other is the first instance of a minimal adaptive routing algorithm that achieves O(n) time with constant sized queues per node. We point out why the latter algorithm is outside the model of our lower bounds. "dci@cs.washington.edu; Department of Computer Science and Engineering, University of Washington, Seattle, WA 98195. This material is based upon work supported in part by the Na- tional Science Foundation under Grant MIP-9213469. ftl@math.mit.edu; Mathematics Department and Labora tory for Computer Science, Massachusetts Institute of Tech- nology, Cambridge, MA 02139. This material is based upon work supported in part by AFOSR Grant F49620-92-J-0125 and ARPA Grants N00014-91-J-1698 and N00014-92-1799. tompa@cs.washington.edu; Department of Computer Sci- ence and Engineering, University of Washington, Seattle, WA 98195. This material is based upon work supported in part by the National Science Foundation under Grants CCR-9002891 and CCR-9301186.