Fault tolerant distributed routing algorithms for mesh Networks-on-Chip

The reliability of networks-on-chip can be increased by developing routing algorithms that provide fault tolerance. Distributed routing algorithms are a class of algorithms where the routing decisions are made without knowledge of the global state of the network. The paper presents a distributed routing algorithm, which targets to maximal fault tolerance. Total of 11 different algorithms are analyzed in their fault tolerance and average hop count using a dedicated in-house C++ simulator. Five of the algorithms are variations of the proposed algorithm and the rest are references or algorithms presented in literature. The developed fully adaptive algorithm is shown to provide superior fault tolerance. The best deadlock-free algorithm is the variation based on the north-last turn model. In the class of minimal algorithms the dynamic xy algorithm provides the highest fault tolerance.