• 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)).

  Postscript Compressed Postscript
  Back to other publications

  Back to my home page