| 摘要 |
A method and apparatus are presented for tolerating up to k faults in a d-dimensional mesh architecture based on the approach of adding spare components (nodes) and extra links (edges) to a given target mesh where m spare nodes (m>/=k) are added and the maximum number of links per node (degree of the mesh) is kept small. The resulting architecture can be reconfigured, without the use of switches, as an operable target mesh in the presence of up to k faults, regardless of their distribution. According to one aspect of the invention, given a d-dimensional mesh architecture having N=n1xn2x. . . xnd nodes, the fault-tolerant mesh can be represented by a diagonal or circulant graph having N+m-k nodes, where m>/=k. This graph has the property that given any set of k or fewer faulty nodes, the remaining graph, after the performance of a pre-determined node renaming process, is guaranteed to contain as a subgraph the graph corresponding to the target mesh M so long as d>/=2 and nd>/=3. The invention also relates to a method and apparatus for efficiently locating a healthy target mesh in the presence of up to k faulty network components, given a fault-tolerant mesh constructed in accordance with the teaching set forth herein.
|
