Automated self-forming, self-healing configuration permitting substitution of software agents to effect a live repair of a system implemented on hardware processors

• US 7,549,077 B2
• Filed: 04/22/2005
• Issued: 06/16/2009
• Est. Priority Date: 04/22/2005
• Status: Expired due to Fees

• Current Assignee: US Army Corps of Engineers Humphreys Engineer Center
• Original Assignee: The United States Of America As Represented By The Secretary Of The Army
• Inventors: White, Barry C.
• Primary Examiner(s): Lohn; Joshua A
• Application Number:
  US11/116,171
• Publication Number:
  US 20060242225A1
• Time in Patent Office: 1,516 Days
• Field of Search: 714/4,10
• US Class Current: 714/4.12
• CPC Class Codes: H04Q 3/0079 involving restoration of networks, e.g. disaster recovery, self-healing networks

Abstract

A configuration for use with a processor that incorporates a suite of “flat” hardware architecture and superimposes thereon a self-forming, self-healing, hierarchical architecture implemented in software. Embodiments may be employed in various applications, such as maintaining network integrity. In one embodiment, a building security monitoring network provides for automated network agents to each be capable of communication with any other automated agents on a network at network startup. Shortly after network initialization, the software architecture is superimposed on the flat hardware architecture, re-arranging communication links to provide an efficient hierarchy of control and substituting working agents for compromised agents as necessary in the network. All of this is done in a “live” network, not requiring shutdown, or even reduced operation to accomplish. This “dual” architecture (hierarchical software and flat hardware) provides excellent reliability in those “layered” network applications requiring near total reliability, such as security surveillance.

Claims

1. An automated self-healing configuration for use with automated equipment establishing a distributed network incorporating nodes, comprising:

computer readable media and uniquely identifiable elements comprising at least in part hardware, said elements cooperating to accomplish at least one task, each said element having at least one function, each said element able to communicate with any other of said elements via at least one link in a flat architecture,

wherein when a said element is instantiated, it automatically finds its own connections, and automatically forms an efficient communication hierarchy as semi-optimal decision trees for fast, efficient and reliable communication; and

computer readable media incorporating at least one hierarchical architecture superimposed on said flat architecture to specify which said links are employed in a particular scenario,

wherein said superimposed hierarchical architecture automates said decision trees to minimize communication from a lowest level said node to a highest level said node, and

wherein said configuration automatically maintains self-ascertained necessary connections and a hierarchy if one or more said nodes are removed or overloaded, and

wherein at least a specified one of said elements assumes at least one function of any said element that is compromised during operation of said configuration, and

wherein said elements are not required to share data resources, and

wherein said configuration makes available for sharing only relevant time-sensitive data to minimize information overload.

2. The configuration of claim 1 further comprising rules incorporated in said software,

wherein said rules specify which said links are employed in a specified scenario.

3. The configuration of claim 1 in which at least parts of said elements are implemented in hardware and at least one of said functions is a control function.

4. The configuration of claim 3 in which said configuration is built starting from said flat architecture,

wherein said flat architecture is established at least partly as a hardware architecture.

5. The configuration of claim 3 in which said configuration is a network and at least some of said elements are agents, each said agent maintaining an IP address and at least one database with one entry in at least one of said databases being the class of said agent.

6. The configuration of claim 5 in which each said agent has at least one control function.

7. The configuration of claim 5 in which each said agent has at least one management function.

8. The configuration of claim 5 in which at least some of said elements are not agents.

9. The configuration of claim 5 in which new said agents are added unannounced.

10. The configuration of claim 5 in which new said agents are added and announced to at least one parent agent.

11. The configuration of claim 5 in which at least one said rule governs collaboration among said agents,

wherein said rules may be implemented via messaging, said messaging determining the agents that a specified agent may communicate with and insuring that each said agent is able to communicate up said immediately above existing level and down said immediately below existing level in said hierarchical architecture that establishes said distributed network, and

wherein at least each said agent abides by said rules so that after initiation of said software, said distributed network appears as a fixed hierarchical architecture.

12. The configuration of claim 5 in which each said agent is responsible for maintaining awareness only of their currently assigned said parent agent, if any, that are one level above said agent in said hierarchical architecture and their currently assigned children agents, if any, that are one level below said agent in said hierarchical architecture,

wherein said responsibility for awareness of only said parent agent, if any, and said children agents, if any, reduces the number of required said links in said configuration such that only links necessary to establish said hierarchical structure are enabled.

13. The configuration of claim 12 in which each said database of said agent includes at least in part a list of any said parent agents and any said children agents assigned thereto.

14. The configuration of claim 13 in which said agents at least comprise:

a first type termed the Agent Name and Type Server (ANATS) agent; and

a second type termed the Hierarchical Self-Healing Network (HSHN) agent,

wherein said HSHN agents form said decision trees;

wherein at least one said ANATS agent maintains a directory of existing said HSHN agents, and

wherein when a request is made to said ANATS agent by one said agent for information about a said HSHN agent of a certain type, said ANATS agent sends said directory entry for said HSHN agent of a certain type to said requesting agent, and

wherein after said directory entry is made, a countdown counter is started, and

wherein after a pre-specified time elapses after said counter is started, the status of said directory entry is moved to the next lower status and said timer is re-started, and

wherein a hierarchy of said status from high to low is “

exists,”

“

unconfirmed,” and

“

non-existent,” and

wherein a “

grace copy”

is an unconfirmed entry.

15. Rules for implementing the configuration of claim 14 in which said ANATS agent employs said rules in order of priority, said rules comprising:

if said directory entry timer of a said existing HSHN agent reaches zero and it is an “

unconfirmed”

said directory entry, remove said HSHN agent from said directory;

if said directory entry timer of a said existing HSHN agent reaches zero and said entry is not a “

grace copy,”

send a verification request to said existing HSHN agent and establish said entry in said directory as “

unconfirmed;

”

if a said HSHN agent sends an “

IamHere”

message, add said HSHN agent to said directory and if there is an existing copy of a listing or a said “

grace copy”

of a listing remove said existing copy or said “

grace copy” and

send an “

ANATSConfirm”

message; and

if a said HSHN agent sends an “

AgentFromType”

message, return the next instance of the requested type of said HSHN agent in an “

AgentFromTypeResponse”

message.

16. The rules of claim 15 in which ANATS rules for said HSHN agents further comprise:

a first rule that if said ANATS agent has not acknowledged existence of said HSHN agent and said timer has not expired, wait for a response;

wherein each said agent has a perception of its environment including other said agents existing therein;

a second rule that if said ANATS agent has not acknowledged existence of said HSHN agent and said timer has expired, send a message to said ANATS agent and start a wait timer;

if a confirmation is received from said ANATS agent, set an acknowledgement flag to ignore said first and second rules; and

if said ANATS agent requests proof of the existence of a said HSHN agent, reset said acknowledgement flag to activate said second rule,

wherein if said HSHN agent is incapacitated, after said timer expires said ANATS agent changes the status of said HSHN agent to “

non-existent” and

removes said HSHN agent from said directory.

17. The rules of claim 16 in which parent processing rules for said HSHN agents comprise:

if said state of said parent HSHN agent is “

unconfirmed” and

a message is sent to said parent HSHN agent, wait for a response;

if said state of said parent HSHN agent is “

non-existent”

request a new name from said ANATS agent;

if said state of said parent HSHN agent goes to “

unconfirmed”

send a message to said parent HSHN agent for confirmation;

if said ANATS agent sends a name of said parent HSHN agent and the current said state of said parent HSHN agent is “

nada”

, replace the current said parent HSHN agent with a new said parent HSHN agent and set the status of said new parent HSHN agent to “

unconfirmed” and

send a message to said new parent HSHN agent for confirmation;

if said current parent HSHN agent replies, set the status of said current parent HSHN agent to “

exists;

” and

if said current parent HSHN agent requests confirmation of existence of said new parent HSHN agent, set said state of said new parent HSHN agent to “

unconfirmed” and

send a message to said new parent HSHN agent for confirmation.

18. The rules of claim 17 in which parent processing rules for said HSHN agents further comprise rules for child said HSHN agents comprising:

if said state of a said child HSHN agent goes to “

non-existent”

remove said child HSHN agent from said directory list of said parent HSFIIN agent;

if said state of a said child HSHN agent goes to “

unconfirmed”

send a request for a child verification message to said child HSHN agent;

if a said child HSHN agent sends a message to said parent HSHN agent, if said parent HSHN agent is in a said state “

exists,”

said parent HSHN agent adds said child HSHN agent to said directory list of said parent HSHN agent with the state “

exists” and

removes prior entries of said child HSHN agent and said parent HSHN agent responds to said child HSHN agent with a confirmation message.

19. The configuration of claim 14 further comprising a load balancing function implemented in said software.

20. The configuration of claim 5 in which at least one of said hierarchical architectures has at least two levels.

21. The configuration of claim 20 in which said agents may be added or subtracted to at least one of said levels via at least one self-forming attribute provided in said software.

22. The configuration of claim 21 in which said configuration permits changes thereto without need for interrupting operation of said configuration.

23. The configuration of claim 21 in which said configuration is scalable, wherein selected said hierarchical levels may be changed via said software to alter the number of said nodes via said self-forming function implemented in said software.

24. The configuration of claim 21 in which said elements further comprise at least in part physically mobile hardware.