Scalable computer network resource monitoring and location system

• US 6,529,953 B1
• Filed: 12/17/1999
• Issued: 03/04/2003
• Est. Priority Date: 12/17/1999
• Status: Expired due to Term

• Current Assignee: Reliable Network Solutions
• Original Assignee: Reliable Network Solutions
• Inventors: Van Renesse, Robbert
• Primary Examiner(s): Coulter, Kenneth R.
• Application Number:
  US09/466,165
• Time in Patent Office: 1,173 Days
• Field of Search: 707/101, 707/100, 707/1, 707/2, 709/223, 709/224, 709/200
• US Class Current: 709/223
• CPC Class Codes: H04L 41/0213 Standardised network management protocols, e.g. simple network management protocol [SNMP]
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation

Abstract

A computer network resource monitoring and locating system includes one or more hierarchical management information bases (HMIBs) through which a user can locate or obtain information relevant to managing or locating various network resources. The system maintains a portion of the HMIB information on each node, and a user starts from a local node and navigates through the system using the contact information that is part of the HMIBs. Each network node provides information directly to an associated lowest level MIB, referred to herein as a group MIB, and maintains a copy of that MIB. The system condenses the information in the gossip MIB and provides the condensed information as a row of a next highest level MIB, which is referred to herein as a subnetwork MIB. The system further condenses the information in this MIB to produce a row of a next highest level MIB, and so forth. Each row of the MIBs includes an identifier that identifies the source of the information, and contact information for at least a non-empty subset of the associated nodes. Each node maintains a view of each group MIB to which it has supplied information. The node also maintains views of each of the higher level MIBs that link the node to the highest or root level MIB, which contains condensed information of interest about every participating node. A user can obtain, through the contact information in the root MIBs maintained by the nodes, a point of contact for more detailed information about any participating node, such as, for example, the nodes in other subnetworks, and so forth. The system uses a hierarchical gossiping scheme to send gossip messages through contact nodes of various levels, to ensure that each node uses up-to-date information. Each node may also send broadcast and non-broadcast gossip messages to other nodes in the network. The gossiped information thus propagates through the network, using parallel routes and including in the message uncondensed information about only a portion of the nodes and condensed information about the remainder of the nodes in the network.

Claims

1. A system for communicating information among nodes of a network, the system including:

A. a lowest level of management information data base with columns containing information to be shared directly among a plurality of nodes and a row for each of the nodes that is to directly share the information, the nodes being members and each member maintaining a view of the lowest level data base;

B. one or more higher levels of management information data bases, the higher levels of data bases with columns containing condensed versions of the contents of a plurality of the next lower level of data bases, and a row for each of the lower level data bases from which information was condensed, the nodes associated with the condensed information each maintaining a view of the corresponding one or more higher levels of management information data bases; and

C. a condensing process for combining the information included in the lower level data bases to produce the rows of the higher level data bases, the condensing process including in each row contact information for a subset of the nodes associated with the lower level data base.

2. The system of claim 1 further including

D. row updating means for updating the rows of the data bases, the row updating means allowing each member node to make changes to the corresponding row of the lowest level data base and each node that maintains a higher level data base to make corresponding changes to the rows of the higher level data bases; and

E. a hierarchical gossip subsystem for providing gossip messages that indicate the rows to which the changes were made; and

F. table updating means for updating the data bases to include updated information.

3. The system of claim 2 wherein the hierarchical gossip subsystem includes

i. means for providing to a member of a given lowest level data base a gossip message that includes information which identifies the last changes made to each of the rows of the data bases at a gossiping node;

ii. means for providing to a selected node that is associated with a higher level of data base a gossip message that includes information which identifies the last changes to each of the rows of the higher level of data base with which the selected node is associated and the last changes to the rows of the even higher levels of data bases maintained by the gossiping node; and

iii. means for providing to the gossiping node changes that are included in the view of the data bases at the node that receives the associated gossip message but are not included in the view at the gossiping node.

4. The system of claim 3 further including

G. a compression process for compressing long byte string values to shorter string values, and including the shorter values in place of the long byte string values, and

H. a translation map for reproducing the long byte string values from the shorter string values.

5. The system of claim 4 further including a means for requesting a missing translation map entry from a node that includes the associated shorter string value in an update message.

6. The system of claim 5 wherein the compression process uses a hash function.

7. The system of claim 3 further including in the hierarchical gossip subsystem, a means for including in the gossip messages information that identifies the version of the gossip message.

8. The system of claim 7 wherein the information that identifies the version is a time stamp.

9. The system of claim 8 further including means for removing from the management information bases information relating to nodes that do not send gossip messages within a predetermined maximum time limit.

10. The system of claim 1 wherein the condensing means includes in each row of the higher level data bases an identifier that identifies the lower level data bases associated with the condensed information.

11. The system of claim 10 wherein the identifier is a public key.

12. The system of claim 11 wherein the row updating means

i. at an updating node signs each update of a higher level data base with a private key, and

ii. at a node receiving the update information checks the information with an associated public key to determine if the information is authentic before updating the corresponding rows of the associated higher level data base.

13. The system of claim 10 wherein the identifier is a public key certificate.

14. The system of claim 13 wherein

i. the row update means signs each update of a higher level data base with a private key and includes in the update an authentication certificate,

ii. the update means authenticates the signature using the public key associated with the authentication certificate and authenticates the update using the public key contained in the authentication certificate.

15. The system of claim 1 wherein

a. the lowest level of management information data base includes information denoting, for each node, message subject matter that is of interest to the node, and

b. the higher levels of management information data bases include information denoting for each lower level database message subject matter to direct to the associated nodes.

16. The system of claim 15 further including means for using the data bases to route a given message to the nodes that have indicated that the subject matter of the message is of interest.

17. The system of claim 16 wherein the hierarchical gossip subsystem further includes means for routing a given gossip message to the selected node to which the subject matter of the gossip message is of interest.

18. The system of claim 1 wherein the condensing process takes the average of entries in certain columns of the lowest and higher levels of data bases.

19. The system of claim 1 wherein the condensing process takes the median of the entries in certain columns of the lowest and higher levels of data bases.

20. The system of claim 1 wherein the condensing process condenses into a single true or present indicator a column that includes one or more entries that indicate the subject matter referenced by the column is present in one or more of the associates nodes.

21. A method of providing information over a distributed system, the method including the steps of:

A. each node providing to a lowest level of management information data base information to be shared among nodes and each node maintaining a view of the associated lowest level of data base;

B. producing one or more higher levels of management information data bases each containing condensed information from a plurality of the next lower level of data bases, the higher levels of data bases containing a row for each of the lower level data bases from which the information was condensed and including in each row contact information for a selected number of the nodes that are associated with the condensed information contained in that row, the nodes each maintaining a view of each of the one or more higher levels of management information data bases with which they are associated;

C. updating the rows of the lowest and higher levels of data base with updated information provided by the respective nodes;

D. providing the updated information to the nodes that maintain views of the data bases.

22. The method of claim 21 wherein the step of providing updated information further includes gossiping about the updated information to selected nodes associated with the various levels of the data bases.

23. The method of claim 22 wherein the step of gossiping includes:

i. at a given node selecting from the lowest level of data base a node to which to send a lowest level of gossip message;

ii. if the given node does not select itself from the lowest level of data base, sending the lowest level of gossip message to the selected node;

iii. if the given node selects itself, selecting from a next higher level of data base a node to which to send a next higher level of gossip message;

iv. if the given node does not select itself from the next higher level of data base, sending the next higher level of gossip message to the selected node;

v. if the given node selects itself from the next higher level of data base repeating steps iii-iv until either the node selects another node to which to send the corresponding higher level gossip message or the node selects itself from the highest level of data base and refrains from gossiping.

24. The method of claim 23 wherein the step of gossiping further includes broadcasting from a given node at controlled intervals broadcast gossip messages.

25. The method of claim 24 wherein the step of gossiping further includes responding to the broadcast gossip messages at controlled rates.

26. The method of claim 23 wherein the step of gossiping further includes broadcasting a gossip message from a given node to the nodes that are associated with a given level of data base.

27. The method of claim 26 wherein the step of gossiping further includes responding to the broadcast gossip messages at controlled rates.

28. The method of claim 21 wherein the step of updating the rows includes

i. replacing long strings with associated hash codes in messages containing update information;

and

ii. at a given nodes receiving the messages, using a translation map to reproduce the long strings from the hash codes included in the messages.

29. The method of claim 28 wherein the step of updating the rows further includes, at a node receiving the messages.

iii. ignoring a message that includes a hash code that is not contained in the translation map,

iv. returning to the node that sent the message, a request for the long string value missing from the map, and

v. updating the translation map with a hash code produced by hashing the received long string value.

30. The method of claim 23 further including determining which nodes are interested in the information included in a given gossip message, and sending the message to a selected one or more of the interested nodes.

31. The method of claim 21 wherein

a. the step of each node providing information to a lowest level of management information data base includes providing to the data base information denoting one or more subjects of interest to the node, and

b. the step of providing condensed information provides to a next higher level of management information data base a union of all of the subject information included in the associated lower level data base.

32. The method of claim 31 further including the step of routing a given message to the nodes that have an interest in the subject matter of the given message.

33. The method of claim 21 wherein the step of producing one or more higher levels of management information databases includes condensing the entries in lower levels of management information databases by taking the average of entries in certain columns of the lower level databases.

34. The method of claim 21 wherein the step of producing one or more higher levels of management information databases includes condensing the entries in lower levels of management information databases by taking the median of entries in certain columns of the lower level databases.

35. The method of claim 21 wherein the step of producing one or more higher levels of management information databases includes condensing the entries in lower levels of management information databases by condensing into a single true or present indicator entries in a given column of the lower level database that includes one or more entries that indicate the subject matter referenced by the column is present in one or more of the associated nodes.