Method and apparatus for tolerating faults in mesh architectures
US5280607A · kind A · utility
Assignee
Inventors
Key dates
| Filing date | Jun 28, 1991 |
| Grant date | Jan 18, 1994 |
| Priority date | — |
| Expiry date | Jun 28, 2011 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F11/2041
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
A method and apparatus are presented for tolerating up to k faults in d-dimensional mesh architectures based on the approach of adding spare components (nodes) and extra links (edges) to a given target mesh where exactly k spare nodes are added and the number of links per node (degree of the mesh) is kept to a minimum. The resulting architecture can be reconfigured, without the use of switches, as an operable target mesh in the presence of up to k faults. According to one aspect of the invention, given a d-dimensional mesh architecture M having N=n.sub.1 .times.n.sub.2 x . . . x n.sub.d nodes, the fault tolerant mesh can be represented by a circulant graph having exactly N+k nodes. This graph has the property that given any set of k or fewer faulty nodes, the remaining graph, after the performance of a predetermined node renaming process, is guaranteed to contain as a subgraph the graph corresponding to target mesh M so long as d.gtoreq.2 and n.sub.d .gtoreq.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 teach…
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.