A FAMILY OF FAULT-TOLERANT ROUTING PROTOCOLS FOR DIRECT MULTIPROCESSOR NETWORKS

Our goal is to reconcile the conflicting demands of performance and fa ult-tolerance in interprocessor communication. To this end, we propose a pipelined communication mechanism-pipelined circuit-switching (PCS) -which is a variant of the well known wormhole routing (WR) mechanism. PCS relaxes some of the routing constraints imposed by WR and as a re sult enables routing behavior that cannot otherwise be realized. This paper presents a new class of adaptive routing algorithms-misrouting b acktracking with m misroutes (MB-m). This class of routing algorithms is made possible by PCS. We provide an analysis of the performance and static fault-tolerant properties of MB-m. The results of an experimen tal evaluation of PCS and MB-3 are also presented. This methodology pr ovides performance approaching that of WR, while realizing a level of resilience to static faults that is difficult to achieve with WR.