MINIMAL ADAPTIVE ROUTING ON THE MESH WITH BOUNDED QUEUE SIZE

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 enco unters, Such algorithms potentially avoid network bottlenecks by routi ng packets around ''hot spots.'' Minimal adaptive routing algorithms h ave the additional advantage that the path each packet takes is a shor test one. For a large class of minimal adaptive routing algorithms, we present an Omega(n(2)/k(2)) bound on the worst case time to route a s tatic permutation of packets on an n x n mesh or torus with nodes that can hold up to k greater than or equal to 1 packets each, This is the first nontrivial lower bound on adaptive routing algorithms, The argu ment extends to more general routing problems, such as the h-h routing problem, It also extends to a large class dimension order routing alg orithms, yielding an Omega(n(2)/k) time bound. To complement these low er bounds, we present two upper bounds, One is an O(n(2)/k + n) time d imension order routing algorithm that matches the lower bound, The oth er is the first instance of a minimal adaptive routing algorithm that achieves O(n) time with constant sized queues per node, We point out w hy the latter algorithm is outside the model of our lower bounds. (C) 1996 Academic Press, Inc.