- Simple algorithms for routing on butterfly networks with bounded
queues. B. M. Maggs and R. K. Sitaraman, SIAM Journal on Computing,
Volume 28, Number 3, June 1999, pp. 1984-1003.

- This paper examines several simple algorithms for routing packets on
N-input butterfly networks with bounded queues. We show that for
any pure queuing protocol, a routing problem in which each of the
inputs sends a packet to a randomly chosen output requires O(log N)
steps, with high probability, provided that the queue size is a
sufficiently large, but fixed, constant. Previously, the best bound
known was O(N). We also show that for any deterministic
non-predictive queuing protocol, there exists a permutation that
requires Omega(N/q log N) time to route, where q is the maximum
queue size. Previously, the best lower bound known was
Omega(sqrt(N)). We present a new algorithm for routing a random
problem on a fully-loaded butterfly with bounded-size queues in
O(log N) steps, with high probability. The algorithm is simpler
than the algorithms of Ranade and Pippenger because it does not use
ghost messages, it does not compare the ranks or destinations of
packets as they pass through a switch, and it cannot deadlock.
Finally, using Valiant's idea of random intermediate destinations, we
generalize a result of Koch's by showing that, if each wire can
support q messages, then for any permutation, the expected number of
messages that succeed in locking down paths from their origins to
their destinations in back-to-back butterflies is Omega(N(log N)^(1/q)).

**Back to other
publications**

**Back to my home page**