© 2002 by British Computer Society
| ||||||||||||||||||||||||||||||||||||||||||||||||||
A Fault-tolerant Adaptive and Minimal Routing Scheme in $n$-D Meshes
1 Department of Computer Science and Engineering, Florida Atlantic University, Boca Raton, FL 33431, USA Email: jie@cse.fau.edu
In this paper a sufficient condition is given for minimal routing in $n$-dimensional ($n$-D) meshes with faulty nodes contained in a set of disjoint fault regions. It is based on an early work of the author on minimal routing in low-dimensional meshes (such as 2-D meshes with faulty blocks). Unlike many traditional models that assume all the nodes know global fault distribution, our approach is based on the concept of limited global fault information. First, a novel fault model called Fault Region is proposed in which all faulty nodes in the system are contained in a set of disjoint regions. Fault information is coded in a $2n$-tuple called Extended Safety Level associated with each node of an $n$-D mesh to support minimal routing. Specifically, we study the existence of minimal paths at a given source node, limited distribution of fault information, minimal routing and deadlock-free routing. Our results show that any minimal routing that is partially adaptive can still be applied, as long as the destination node eets a certain safety condition. A dynamic planar-adaptive routing scheme is presented that offers better fault tolerance and adaptivity than the regular planar-adaptive routing scheme in $n$-D meshes. In 3-D meshes, both regular and dynamic planar-adaptive routing need three virtual channels. Our approach is the first attempt to address minimal routing in $n$-D meshes with faulty nodes using limited global fault information.