TY - GEN
T1 - Packet routing in optimal time on a butterfly
AU - Krishna, Arvind
AU - Pietracaprina, Andrea
AU - Hajek, Bruce
PY - 1991
Y1 - 1991
N2 - 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
AB - 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
UR - http://www.scopus.com/inward/record.url?scp=0025723748&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0025723748&partnerID=8YFLogxK
U2 - 10.1109/infcom.1991.147593
DO - 10.1109/infcom.1991.147593
M3 - Conference contribution
AN - SCOPUS:0025723748
SN - 0879426942
SN - 9780879426941
T3 - Proceedings - IEEE INFOCOM
SP - 840
EP - 849
BT - Networking in the 90s
PB - Publ by IEEE
T2 - Proceedings of the 10th Annual Joint Conference of the IEEE and Communications Societies - IEEE INFOCOM '91
Y2 - 7 April 1991 through 11 April 1991
ER -