Message routing in HARTS with faulty components

It is important to design a distributed system which is capable of delivering messages even in the presence of faulty components between their source and destination nodes. A routing scheme is developed in two steps for a wrapped hexagonal mesh, called HARTS (Hexagonal Architecture for Real-Time Systems), which assures the delivery of every message as long as there is a path between its source and destination. The proposed scheme can also detect the nonexistence of path between a pair of nodes in a finite amount of time. Moreover, the scheme requires each node in HARTS to know only the state (faulty or not) of each of its own links. The performance of the simple routing scheme is simulated for 3- and 5-dimensional H-meshes while varying the physical distribution of faulty components. It is shown that a shortest path between the source and destination of each message is taken with a high probability and a path, if it exists, is usually found very quickly.