Local Fault-Tolerant Routing in 3D Mesh NoCs using Single-Hop Rollback

IEEE Access. 2026. Vol. 14. P. 2169–3536.

Edward R. Rzaev, Aleksandr Y. Romanov, Andrey M. Sukhov

This work presents a hierarchy of strictly local fault-tolerant routing algorithms for 3D mesh networks-on-chip, culminating in an algorithm that combines a live-neighbor selection rule with a bounded single-hop rollback mechanism. The proposed algorithms operate exclusively on immediate neighbor information, maintain O(1) per hop complexity, and require no global topology knowledge, additional virtual channels, or reconfigurable routing tables. For systematic evaluation, a reproducible benchmark of 36 deterministic and stochastic test scenarios organized into 5 functional categories is developed. Experimental results show that the proposed algorithms achieve an average path-length deviation of 1.64% from the A* reference at fault densities up to 50%, exceeding the deviation of the LOFT baseline by a factor of more than 137. The proposed Algorithm 8 maintains a routing success rate of up to 86% at fault densities of 13–30% while executing 16.7 times faster than A* and 22.5 times faster than LOFT. Compared to the LOFT baseline, the proposed approach reduces path-length deviation by a factor of more than 137 while executing 22.5 times faster. The benchmark and the algorithm implementations are publicly released to support reproducibility and future research.

Keywords: бенчмарк, optimal routing, оптимальная маршрутизация, network-on-chip design, benchmark, 3D mesh, разработка сети на кристалле, 3D сеть