Packet routing in optimal time on a butterfly
A. Krishna, Andrea Pietracaprina, Bruce Hajek · 1991
An algorithm is presented that does packet routing on an N-node butterfly in time O(log N) with small constants. The algorithm is based on A. Ranade's (1987) probabilistic random access machine (PRAM) emulation. The algorithm is simplified by focusing on packet routing. Bounds on the performance of the algorithm are proven for 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 constants achieved are the best to date. A complete description of the routing algorithm is given.>