James Giles, Bruce Hajek
IEEE Trans. Inf. Theory
We present an algorithm that does packet routing on an N‐node butterfly in time O(log N) with small constants. The algorithm is based on Ranade's probabilistic PRAM emulation. We simplify the algorithm by focusing on packet routing and prove bounds on its performance for the cases of permutation routing and uniform, random traffic. The main results are upper bounds on the probability that the routing time exceeds t for a fixed queue size. The simplifications made to Ranade's original algorithm and a more careful analysis enabled us to achieve better constants, which, to the best of our knowledge, are the best to date. © 1994 by John Wiley & Sons, Inc. Copyright © 1994 Wiley Periodicals, Inc., A Wiley Company
James Giles, Bruce Hajek
IEEE Trans. Inf. Theory
Ilan Kessler, Arvind Krishna
IEEE/ACM Transactions on Networking
Gianfranco Bilardi, Kieran Herley, et al.
Journal of Parallel and Distributed Computing
Pravin Bhagwat, Partha Bhattacharya, et al.
Wireless Networks