A limited-global fault information model for dynamic routing in n-D meshes

Summary form only given. A fault-tolerant routing in nD meshes with dynamic faults is provided. It is based on an early work on fault-tolerant routing in dynamic 2D meshes and 3D meshes where faults occur during a routing process. Unlike many traditional models that assume all the nodes know global fault information, our approach is based on the concept of limited global fault information. First, a fault model called faulty block is used in which all faulty nodes in the system are contained in a set of disjoint faulty blocks. Then, the information of faulty block needs to be distributed to a limited number of nodes at the boundaries of faulty block to avoid a message entering a detour area. When new faults occur, faulty blocks need to be reconstructed and their fault information needs to be redistributed. In this case, the update of fault information and the routing process proceed hand-in-hand. During the converging period, the routing process may experience more detours with inconsistent information. We study the limited distribution of fault information in nD meshes with dynamic faults. Our study shows that fault information can be distributed quickly to help the routing process. Therefore, the performance of routing process degrades gracefully in such a dynamic system.