Simple algorithms for routing on butterfly networks with bounded queues
This paper examines several simple algorithms for routing packets on butterfly networks with bounded queues. We show that for any pure queuing protocol, a routing problem in which each of the N 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. We also show that for any deterministic non-predictive queuing protocol, there exists a permutation that requires Ω(N/q logN) time to route, where q is the maximum queue size. We present a new algorithm for routing a random problem on a fully-loaded butterfly with bounded-size queues in O(logN) steps, with high probability. The algorithm is simpler than the previous 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 Ω(N/(log JV)1/q). The analysis also applies to store-and-forward algorithms that drop packets if they attempt to enter full queues.
