DocumentCode
1444820
Title
A tight lower bound on the number of channels required for deadlock-free wormhole routing
Author
Libeskindg-Hadas, R.
Author_Institution
Dept. of Comput. Sci., Harvey Mudd Coll., Claremont, CA
Volume
47
Issue
10
fYear
1998
fDate
10/1/1998 12:00:00 AM
Firstpage
1158
Lastpage
1160
Abstract
Wormhole routing is widely employed in current generation multicomputers and the design of deadlock-free wormhole routing algorithms is an important problem. In this note, we prove a tight lower bound on the number of channels required by a broad class of deadlockfree wormhole routing algorithms. This result has applications in proving that certain topologies do not admit deadlock-free wormhole routing algorithms, as well as applications in the design and analysis of fault-tolerant wormhole routing algorithms
Keywords
fault tolerant computing; multiprocessor interconnection networks; deadlock-free wormhole routing; fault-tolerant wormhole routing algorithms; multicomputers; tight lower bound; Algorithm design and analysis; Delay; Fault tolerance; Multiprocessor interconnection networks; Network topology; Radio access networks; Routing; System recovery; Tail;
fLanguage
English
Journal_Title
Computers, IEEE Transactions on
Publisher
ieee
ISSN
0018-9340
Type
jour
DOI
10.1109/12.729799
Filename
729799
Link To Document