Pipelined circuit-switching: a fault-tolerant variant of wormhole routing

Abstract

An effort is made to reconcile the conflicting demands of performance and fault-tolerance in interprocessor communication protocols. To this end, the authors propose a pipelined communication mechanism-pipelined circuit-switching (PCS)-which is variant of the well known wormhole routing (WR) mechanism. They present a new class of adaptive routing algorithms, misrouting backtracking-m (MB-m), made possible by PCS and proofs of some 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 fault-tolerant behavior that is difficult to achieve with WR.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>