DocumentCode
796448
Title
Fast algorithms for routing around faults in multibutterflies and randomly-wired splitter networks
Author
Leighton, F. Thomson ; Maggs, Bruce M.
Author_Institution
Dept. of Math., MIT, Cambridge, MA, USA
Volume
41
Issue
5
fYear
1992
fDate
5/1/1992 12:00:00 AM
Firstpage
578
Lastpage
587
Abstract
Simple deterministic O (log N )-step algorithms for routing permutations of packets in multibutterflies and randomly wired splitter networks are described. The algorithms are robust against faults (even in the worst case), and are efficient from a practical point of view. As a consequence, it is found that the multibutterfly is an excellent candidate for a high-bandwidth low-diameter switching network underlying a shared-memory machine
Keywords
computational complexity; fault tolerant computing; multiprocessor interconnection networks; algorithms; deterministic; fault routing algorithms; multibutterflies; packet permutations routing; randomly-wired splitter networks; shared-memory machine; switching network; Computer science; Concurrent computing; Hypercubes; Intelligent networks; Multiprocessor interconnection networks; Packet switching; Robustness; Routing; Switches; Wires;
fLanguage
English
Journal_Title
Computers, IEEE Transactions on
Publisher
ieee
ISSN
0018-9340
Type
jour
DOI
10.1109/12.142684
Filename
142684
Link To Document