Software-based rerouting for fault-tolerant pipelined communication

This paper presents a software-based approach to fault-tolerant routing in networks using wormhole or virtual cut-through switching. When a message en counters 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 s ystem. The message passing software can reroute this message, possibly alon g nonminimal paths. Alternatively, the message may be addressed to an inter mediate node, which will forward the message to the destination. A message may encounter multiple faults and pass through multiple intermediate nodes. The proposed techniques are applicable to both obliviously and adaptively routed networks. The techniques are specifically targeted toward commercial multiprocessors where the mean time to repair (MTTR) is much smaller than the mean time between router failures (MTBF), i.e., it is sufficient to tol erate a maximum of three failures. This paper presents requirements for buf fer management, deadlock freedom, and livelock freedom. Simulation results are presented to evaluate the degradation in latency and throughput as a fu nction of the number and distribution of faults. There are several advantag es of such an approach. Router designs are minimally impacted, and thus rem ain compact and fast. Only messages that encounter faulty components are af fected, while the machine is ensured of continued operation until the fault y components can be replaced. The technique leverages existing network tech nology, and the concepts are portable across evolving switch and router des igns. Therefore, we feel that the technique is a good candidate for incorpo ration into the next generation of multiprocessor networks.