A limited-global information model for dynamic fault-tolerant routing in cube-based multicomputers

The safety level model is a special coded fault information model designed to support fault-tolerant routing in hypercubes. In this model, each node is associated with an integer, called safety level, which is an approximated measure of the number and distribution of faulty nodes in the neighborhood. The safety level of each node in an n-dimensional hypercube (n-cube) can be easily calculated through (n-1) rounds of information exchanges among neighboring nodes. We focus on routing capability using safety levels in a dynamic system; that is, a system in which new faults might occur during a routing process. In this case, the updates of safety levels and the routing process proceed hand-in-hand. Our approach is based on an early work (2001) in a special fault model. In that model, each fault appears at a different time step and before each fault occurrence the safety levels in the cube are stabilized. This paper extends our results to a general fault model without any limitation on fault occurrence. Under the assumption that the total number of faults is less than n, we provide an upper bound of detour number in a routing process. Simulation results are also provided to compare with the proposed upper bound.