Software Based Fault-Tolerant Oblivious Routing in Pipelined Networks.

Abstract

This paper presents a software based approach to fault-tolerant routing in oblivious, wormhole routed networks. When a message encounters a faulty output link it is removed from the network by the local router and delivered to the messaging layer of the local node's operating system. The message passing software can reroute this message along a non-minimal oblivious path or via an intermediate node, which will forward the message to the destination. A message may encounter multiple faults and pass through multiple intermediate nodes. This paper discusses deadlock, livelock, and performance issues. Router designs are minimally impacted remaining compact, oblivious, and fast. Therefore this approach is a good candidate for incorporation into the next generation of wormhole routed multiprocessor networks.