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

  • Zhen Jiang, Jie Wu
  • Published 2004 in 18th International Parallel and Distributed Processing Symposium, 2004. Proceedings.


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.


8 Figures and Tables

Download Full PDF Version (Non-Commercial Use)