Patent US4016847A successfully refreshed from Google Patents.
Patent US5592610A successfully refreshed from Google Patents.
US5592610A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for enhancing the fault-tolerance of a network
Assignee: Intel Corp
•
Filing: 1994-12-21
•
Granted: 1997-01-07
•
Expires: 2014-12-21
Abstract
Abstract A method and apparatus for enhancing the fault-tolerance of a network finds a set of computing nodes within the network which are available for use in the network upon detection of a faulty component. This set of available computing nodes is found by first determining a set of computing nodes within the network which are physically connected together. A connectivity value for each computing node within this set is then determined. A subset of this set is then generated such that each computing node in the subset is able to transfer data to and from each other computing node in the subset. This subset is then utilized as the set of available computing nodes. In one embodiment, the set of computing nodes which are physically connected together is the largest set of physically connected computing nodes in the system.
Inventors
- 👤 Suresh S. Chittor
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-28 12:33
CPC Classifications
H; H04; H04L; H04L49/00; H04L49/55; H04L49/557; H04L49/15; H04L49/1553; H04L49/1576; H04L49/555
Claims Analysis
Total Claims: 28
Claim 1
Independent Claim
153 words
A method for finding a set of available computing nodes in a network upon detection of a faulty network component, the method comprising the steps of: (a) determining a set of nodes in the network which are physically coupled together; (b) for a first node of the set of nodes determining a connectivity value which indicates a number of nodes of the set of nodes to which the first node has a deadlock-free path; (c) repeating the determining step (b) for each node of the set of nodes; (d) determining a subset of the set of nodes such that each node in the subset can transfer data to and from each other node in the subset, wherein the determining of the subset is based on the connectivity value for each node of the set of nodes; and (e) using the subset of the set of nodes as the set of available computing nodes.
Claim 2
Independent Claim
153 words
A method for finding a set of available computing nodes in a network upon detection of a faulty network component, the method comprising the steps of: (a) determining a set of nodes in the network which are physically coupled together; (b) for a first node of the set of nodes determining a connectivity value which indicates a number of nodes of the set of nodes to which the first node has a deadlock-free path; (c) repeating the determining step (b) for each node of the set of nodes; (d) determining a subset of the set of nodes such that each node in the subset can transfer data to and from each other node in the subset, wherein the determining of the subset is based on the connectivity value for each node of the set of nodes; and (e) using the subset of the set of nodes as the set of available computing nodes.
Claim 3
Dependent Claim
30 words
The method of claim 1, wherein the determining step (a) comprises determining a largest set of nodes in the network which are physically coupled together, excluding the faulty network component.
Claim 4
Dependent Claim
31 words
The method of claim 1, wherein the network supports a plurality of virtual networks, and wherein the determining step (b) comprises determining the connectivity value using the plurality of virtual networks.
Claim 5
Dependent Claim
40 words
The method of claim 3, wherein the determining step (d) comprises a step of checking whether a deadlock-free path exists between each node in the subset using a different deadlock-free routing scheme for each of the plurality of virtual networks.
Claim 6
Dependent Claim
26 words
The method of claim 1, wherein the determining step (d) comprises a step of checking whether a deadlock-free path exists between each node in the subset.
Claim 7
Dependent Claim
35 words
The method of claim 1, wherein the determining step (d) comprises a step of removing nodes from the set of nodes until a deadlock-free path exists between each node remaining in the subset of nodes.
Claim 8
Dependent Claim
35 words
The method of claim 6, wherein the determining step (d) further comprises removing a second node prior to removing a third node, wherein the second node has a lower connectivity value than the third node.
Claim 9
Dependent Claim
45 words
The method of claim 6, wherein the determining step (d) further comprises adding a second node to the subset of nodes, wherein the second node is one of the set of nodes, and wherein the second node was previously removed from the subset of nodes.
Claim 10
Independent Claim
126 words
An apparatus in a network comprising: a memory unit; a network interface unit coupled to the memory unit; and a processing unit coupled to the memory unit and the network interface unit which, upon discovery of a faulty network component, determines a set of nodes in the network which the apparatus is physically coupled to and determines a number of nodes of the set of nodes to which the apparatus has a deadlock-free path, wherein the processing unit also determines a subset of the set of nodes such that each node in the subset can transfer data to and from each other node in the subset, and wherein the processing unit uses the subset of the set of nodes as a set of available network nodes.
Claim 11
Independent Claim
126 words
An apparatus in a network comprising: a memory unit; a network interface unit coupled to the memory unit; and a processing unit coupled to the memory unit and the network interface unit which, upon discovery of a faulty network component, determines a set of nodes in the network which the apparatus is physically coupled to and determines a number of nodes of the set of nodes to which the apparatus has a deadlock-free path, wherein the processing unit also determines a subset of the set of nodes such that each node in the subset can transfer data to and from each other node in the subset, and wherein the processing unit uses the subset of the set of nodes as a set of available network nodes.
Claim 12
Dependent Claim
36 words
The apparatus of claim 9, wherein the processing unit also determines, for each node of the set of nodes, a number of nodes of the set of nodes to which each node has a deadlock-free path.
Claim 13
Dependent Claim
38 words
The apparatus of claim 9, wherein the network supports a plurality of virtual networks and wherein the processing unit determines the number of nodes to which the apparatus has a deadlock-free path using the plurality of virtual networks.
Claim 14
Dependent Claim
32 words
The apparatus of claim 9, wherein the processing unit selects the deadlock-free path between the apparatus and each node of the subset of nodes and stores the path in the memory unit.
Claim 15
Dependent Claim
15 words
The apparatus of claim 9, wherein the apparatus is one of the set of nodes.
Claim 16
Dependent Claim
142 words
A network system comprising: a plurality of routing devices; a plurality of communication links coupled to the plurality of routing devices; and a plurality of computing nodes coupled to the plurality of routing devices, wherein each node of the plurality of computing nodes determines, upon discovery of a faulty network component, a set of nodes in the network system which are physically coupled together and determines a number of nodes of the set of nodes to which each node has a deadlock-free path, wherein each of the plurality of computing nodes also determines a subset of the set of nodes such that each node in the subset can transfer data to and from each other node in the subset, and wherein each node of the subset of nodes uses the subset of the set of nodes as a set of available nodes.
Claim 17
Dependent Claim
142 words
A network system comprising: a plurality of routing devices; a plurality of communication links coupled to the plurality of routing devices; and a plurality of computing nodes coupled to the plurality of routing devices, wherein each node of the plurality of computing nodes determines, upon discovery of a faulty network component, a set of nodes in the network system which are physically coupled together and determines a number of nodes of the set of nodes to which each node has a deadlock-free path, wherein each of the plurality of computing nodes also determines a subset of the set of nodes such that each node in the subset can transfer data to and from each other node in the subset, and wherein each node of the subset of nodes uses the subset of the set of nodes as a set of available nodes.
Claim 18
Dependent Claim
20 words
The system of claim 14, wherein the plurality of routing devices are coupled together in a two-dimensional mesh network configuration.
Claim 19
Dependent Claim
25 words
The system of claim 14, wherein each of the plurality of computing nodes is connected to one routing device of the plurality of routing devices.
Claim 20
Dependent Claim
34 words
The system of claim 14, wherein each routing device of the plurality of routing devices comprises a plurality of input queues for each of the plurality of communication links input to each routing device.
Claim 21
Dependent Claim
19 words
The system of claim 14, wherein each of the plurality of routing devices supports a plurality of virtual networks.
Claim 22
Independent Claim
144 words
An apparatus for finding a set of available nodes in a network upon detection of a faulty network component comprising: means for determining a largest set of nodes in the network which are physically coupled together; for each node of the largest set of nodes, means for determining a connectivity value which indicates a number of nodes of the largest set of nodes to which a particular node has a deadlock-free path; means for determining a subset of the largest set of nodes such that each node in the subset can transfer data to and from each other node in the subset, wherein the means for determining a subset determines the subset based on the connectivity value for each node of the largest set of nodes; and means for using the subset of the largest set of nodes as the set of available nodes.
Claim 23
Independent Claim
144 words
An apparatus for finding a set of available nodes in a network upon detection of a faulty network component comprising: means for determining a largest set of nodes in the network which are physically coupled together; for each node of the largest set of nodes, means for determining a connectivity value which indicates a number of nodes of the largest set of nodes to which a particular node has a deadlock-free path; means for determining a subset of the largest set of nodes such that each node in the subset can transfer data to and from each other node in the subset, wherein the means for determining a subset determines the subset based on the connectivity value for each node of the largest set of nodes; and means for using the subset of the largest set of nodes as the set of available nodes.
Claim 24
Dependent Claim
33 words
The apparatus of claim 19, wherein the network supports a plurality of virtual networks, and wherein the means for determining the connectivity value determines the connectivity value using the plurality of virtual networks.
Claim 25
Dependent Claim
38 words
The apparatus of claim 20, wherein the means for determining a subset checks whether a deadlock-free path exists between each node in the subset using a different deadlock-free routing scheme for each of the plurality of virtual networks.
Claim 26
Dependent Claim
34 words
The apparatus of claim 19, wherein the means for determining a subset removes nodes from the largest set of nodes until a deadlock-free path exists between each node remaining in the subset of nodes.
Claim 27
Dependent Claim
36 words
The apparatus of claim 22, wherein the means for determining a subset also removes a first node prior to removing a second node, wherein the first node has a lower connectivity value than the second node.
Claim 28
Dependent Claim
47 words
The apparatus of claim 22, wherein the means for determining a subset also adds a first node to the subset of nodes, wherein the first node is one of the largest set of nodes, and wherein the first node was previously removed from the subset of nodes.
References Cited (Backward Citations)
US5008882A
Cited
US5105424A
Cited
US5138615A
Cited
US5218676A
Cited
US5058105A
Cited
US5151900A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2000-01-07 | 2000-07-08 | 2001-01-07 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2004-01-07 | 2004-07-08 | 2005-01-07 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2008-01-07 | 2008-07-08 | 2009-01-07 | $7700.00 | Window Closed / Lapsed |