RSD Fault Block Model for Highly Efficient Fault-Tolerant Manhattan Routing Algorithms in 2D Mesh

摘要

In this article, we present a RSD (Rectangle defined by 'Source' node and 'Destination' node) fault block model for highly efficient fault-tolerant Manhattan routing algorithms in 2D mesh. For any given pair of the source node and the destination node, RSD fault block model will not take the shape of a single RSD faulty block and fault nodes outside RSD into account. The procedure of constructing of all RSD fault blocks is restricted in the range of RSD and no available Manhattan paths will be omitted. The worst-case and average time complexity of constructing RSD fault blocks are O(M_0~2 + N~2) and O(M_0~2) (N is not the length and width of the whole 2D mesh but that of RSD, M_0 is the number of initial fault nodes not in the whole 2D mesh but in RSD), respectively. Using the result of constructing RSD fault block, it is easy to judge whether there exist some Manhattan paths or not Then all possible fault-tolerant Manhattan paths achieved can provide flexibility of designing different fault-tolerant Manhattan routing algorithms with or without some restrictions. It is more efficient for fault-tolerant multicast Manhattan routing algorithms.