Richard O. La Maire, Arvind Krishna, et al.
IEEE Journal on Selected Areas in Communications
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
Richard O. La Maire, Arvind Krishna, et al.
IEEE Journal on Selected Areas in Communications
Richard O. LaMaire, Arvind Krishna, et al.
IEEE Communications Magazine
Adrian Segall, Pravin Bhagwat, et al.
Journal of High Speed Networks
Gianfranco Bilardi, Andrea Pietracaprina, et al.
IPDPS 2007