A family of fault-tolerant routing protocols for directmultiprocessor networks |
| |
Authors: | Gaughan P.T. Yalamanchili S. |
| |
Affiliation: | Dept. of Electr. Eng., Alabama Univ., Tuscaloosa, AL; |
| |
Abstract: | Our goal is to reconcile the conflicting demands of performance and fault-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 result enables routing behavior that cannot otherwise be realized. This paper presents a new class of adaptive routing algorithms-misrouting backtracking 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 experimental evaluation of PCS and MB-3 are also presented. This methodology provides performance approaching that of WR, while realizing a level of resilience to static faults that is difficult to achieve with WR |
| |
Keywords: | |
|
|