Fault-Tolerant Routing in Networks-on-Chip Using Self-Organizing Routing Algorithms

This work focuses on using self-organizing algorithms employed in the field of wireless sensor networks to networks-on-chip (NoCs) and presents a method for choosing hierarchical coordinates and a greedy forwarding algorithm for path finding. The features of algorithm functioning in the conditions of an overloaded NoC and the presence of fault nodes are considered, and a set of rules for bypassing blocked network sections is given. The proposed hierarchical coordinate method and a greedy forwarding fault tolerant routing algorithm are universal and suit for any NoC topology. To test the proposed solutions in NoCs with more than 300 nodes and mesh topology a special software simulator was developed, which confirmed the efficiency and stability of routing algorithms and coordinate assignment. Dependence of lengthening of the route and increase in the number of unreachable nodes on the number of disabled nodes (when using the routing algorithm proposed) was also investigated. It was shown that the proposed routing algorithm significantly exceeded fault tolerant algorithms and was only slightly inferior to the optimal algorithm (Dijkstra's algorithm) in the capability of constructing a route for the movement of packets through the network under nodes failures conditions.