Packet routing in optimal time on a butterfly

Author

Krishna, Arvind ; Pietracaprina, Andrea ; Hajek, Bruce

Author_Institution

Illinois Univ., Urbana, IL, USA

fYear

1991

fDate

7-11 Apr 1991

Firstpage

840

Abstract

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

Keywords

packet switching; telecommunication networks; N-node butterfly; PRAM; butterfly network; fixed queue size; optimal time; packet routing; permutation routing; probabilistic random access machine; routing algorithm; routing time; uniform random traffic; upper bounds; Algorithm design and analysis; Emulation; Hypercubes; Phase change random access memory; Routing; Sorting; System recovery; Traffic control; Upper bound;

fLanguage

English

Publisher

ieee

Conference_Titel

INFOCOM '91. Proceedings. Tenth Annual Joint Conference of the IEEE Computer and Communications Societies. Networking in the 90s., IEEE

Conference_Location

Bal Harbour, FL

Print_ISBN

0-87942-694-2

Type

conf

DOI

10.1109/INFCOM.1991.147593

Filename

147593