US5537653A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method for on-line diagnosis for distributed network systems
Assignee: Carnegie Mellon University
•
Filing: 1995-03-24
•
Granted: 1996-07-16
•
Expires: 2015-03-24
Abstract
Abstract An on-line adaptive distributed diagnostic method for use in an arbitrary network comprised of N nodes, where N is greater than or equal to 3. The algorithms of the present invention provide on-line diagnosis in the presence of node and link failure. In the network, each node is capable of executing an algorithm used in the diagnostic method to update a packet which communicates between network nodes.
Inventors
- 👤 Ronald P. Bianchini, Jr.
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-06 05:50
CPC Classifications
G; G06; G06F; G06F11/00; G06F11/22; G06F11/2273
Claims Analysis
Total Claims: 11
Claim 1
Independent Claim
227 words
An on-line adaptive distributed diagnostic system for a network of arbitrary topology, comprising: N nodes where N is greater than or equal to three, each node having a state of either faulty or fault-free; M communication links where M is greater than or equal to two, each link having a state of either faulty or fault-free and each node being in direct communication with at least one neighboring node through one of the links; means associated with each node for directly testing a neighboring node, the determination of which neighboring node to test being based on a testing assignment associated with the network; means associated with each node for indirectly communicating with a non-neighboring node through intervening nodes such that each node can be furnished with diagnostic information about a non-neighboring node in the network; means associated with each node for coordinating the performance of diagnosis by it with the performance of diagnosis by another node in the network, whereby the need for central synchronization is eliminated; means for maintaining diagnosis in the absence of a state change by any of the nodes and links; and means for restoring diagnosis in the presence of a state change by any of the nodes by adaptively replacing the testing assignment with a new independent testing assignment such that every node in the network is tested by a fault-free node.
Claim 2
Dependent Claim
227 words
An on-line adaptive distributed diagnostic system for a network of arbitrary topology, comprising: N nodes where N is greater than or equal to three, each node having a state of either faulty or fault-free; M communication links where M is greater than or equal to two, each link having a state of either faulty or fault-free and each node being in direct communication with at least one neighboring node through one of the links; means associated with each node for directly testing a neighboring node, the determination of which neighboring node to test being based on a testing assignment associated with the network; means associated with each node for indirectly communicating with a non-neighboring node through intervening nodes such that each node can be furnished with diagnostic information about a non-neighboring node in the network; means associated with each node for coordinating the performance of diagnosis by it with the performance of diagnosis by another node in the network, whereby the need for central synchronization is eliminated; means for maintaining diagnosis in the absence of a state change by any of the nodes and links; and means for restoring diagnosis in the presence of a state change by any of the nodes by adaptively replacing the testing assignment with a new independent testing assignment such that every node in the network is tested by a fault-free node.
Claim 3
Dependent Claim
17 words
The system of claim 1 wherein each fault-free node is in communication with every other fault-free node.
Claim 4
Dependent Claim
24 words
The system of claim 1 wherein the restoring means further restores diagnosis in the presence of a state change by any of the links.
Claim 5
Dependent Claim
11 words
The system of claim 1 wherein each node comprises a processor.
Claim 6
Dependent Claim
21 words
The system of claim 1 wherein the direct testing means comprises a memory and a computer program stored in the memory.
Claim 7
Dependent Claim
45 words
The system of claim 1 wherein the restoring means adaptively changes the testing assignment at each node based on results of tests performed at that node by the direct testing means and based on any diagnostic information furnished to that node from any non-neighboring nodes.
Claim 8
Dependent Claim
13 words
The system of claim 1 wherein the indirect communication means comprises message packets.
Claim 9
Dependent Claim
15 words
The system of claim 1 wherein the direct testing means periodically tests a neighboring node.
Claim 10
Dependent Claim
32 words
The system of claim 1 wherein each node activates the restoring means by propagating a message packet when the node detects a state change of another node that it is directly testing.
Claim 11
Dependent Claim
22 words
The system of claim 9 wherein the restoring means is deactivated when a message packet has traversed the network without being updated.
References Cited (Backward Citations)
US4451916A
Cited
US4872165A
Cited
US4991174A
Cited
US4709365A
Cited
US4747100A
Cited
US4912656A
Cited
US5016243A
Cited
US5337320A
Cited
US5218601A
Cited
US5173689A
Cited
US5265241A
Cited
US5295244A
Cited
US5325518A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1999-07-16 | 2000-01-15 | 2000-07-16 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2003-07-16 | 2004-01-15 | 2004-07-16 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2007-07-16 | 2008-01-15 | 2008-07-16 | $7700.00 | Window Closed / Lapsed |