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
fDate :
5/1/1992 12:00:00 AM
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;
Journal_Title :
Computers, IEEE Transactions on
