Fully reliable dynamic routing logic for a fault-tolerant NoC architecture

A fault-tolerant adaptive wormhole routing function for Networks-on-Chips (NoCs) is presented. The novelty of this routing logic is that it is capable of using runtime information on availability of links to dynamically bypass faulty channels. When faults occur, no offline reconfiguration or dropping of packets is necessary. Instead, dynamic routes are suggested on-the-fly. Routing decisions are based only on local knowledge, which allows for fast switching. Our approach does not use any costly virtual channels. As we do not prohibit cyclic dependencies, the routing function provides minimal routing from source to destination even in the presence of faults. We have implemented the architecture design using synthesizable HDL. Using simulations, we have assessed the overhead of our approach in terms of latency, power and area. On average, even with 40% of the links faulty our routing logic is capable performing correctly. Using formal verification, we have proven 100% reliability up to three faults, i.e., for any combination of three faults our routing logic remains connected, deadlock-free and livelock-free. Keywords: Network communications, Fault Tolerance, Deadlocks, Routing protocols, Mechanical Verificatio