COMPRESSIONLESS ROUTING - A FRAMEWORK FOR ADAPTIVE AND FAULT-TOLERANTROUTING

Compressionless Routing (CR) is a new adaptive routing framework which provides a unified framework for efficient deadlock-free adaptive rou ting and fault-tolerance. CR exploits the tight-coupling between wormh ole routers for flow control to detect and recover from potential dead lock situations. Fault-tolerant Compressionless Routing (FCR) extends CR to support end-to-end fault-tolerant delivery. Detailed routing alg orithms, implementation complexity, and performance simulation results for CR and FCR are presented. These results show that the hardware fo r on and FCR networks is modest. Further, CR and FCR networks can achi eve superior performance to alternatives such as dimension-order routi ng. Compressionless Routing has several key advantages: deadlock-free adaptive routing in toroidal networks with no virtual channels, simple router designs, order-preserving message transmission, applicability to a wide variety of network topologies, and elimination of the need f or buffer allocation messages. Fault-tolerant Compressionless Routing has several additional advantages: data integrity in the presence of t ransient faults (nonstop fault-tolerance), permanent faults tolerance, and elimination of the need for software buffering and retry for reli ability. The advantages of CR and FCR not only simplify hardware suppo rt for adaptive routing and fault-tolerance, they also can simplify so ftware communication layers.