TOLERATING FAULTY EDGES IN A MULTIDIMENSIONAL MESH

We examine the problem of tolerating faulty edges in the multi-dimensional mesh architecture. This problem can be briefly defined as follows. Given a mesh M, find a mesh G which satisfies the following conditions: (1) G and M have the same number of nodes, (2) for any subset of k edges in G, there is a submesh in G isomorphic to M which excludes these k edges, and (3) G has the least possible number of edges. The mesh G which satisfies these conditions is called a symmetrically optimal k-edge-fault-tolerant (k-eft) extension of M. We show that, even for k=1, finding such a mesh G is a very difficult problem. We develop necessary and sufficient conditions for characterizing the class of symmetrically optimal 1-eft extensions of any given mesh. We propose two new methods for finding a symmetrically optimal, or symmetrically near-optimal, 1-eft extension. The first method finds an optimal solution, and is useful when the number of dimensions in the given mesh M is not very large. The second method finds a near-optimal solution by decomposing the given mesh M into several meshes (with a fewer number of dimensions) that can be solved by the first method.