Method and apparatus for grouping nodes based on connection characteristics

• US 7,949,737 B2
• Filed: 11/03/2003
• Issued: 05/24/2011
• Est. Priority Date: 11/04/2002
• Status: Active Grant

• Current Assignee: Riverbed Technology, LLC (Riverbed Technology Incorporated)
• Original Assignee: Riverbed Technology Incorporated
• Inventors: Tan, Godfrey
• Primary Examiner(s): Shin; Kyung-Hye
• Application Number:
  US10/701,346
• Publication Number:
  US 20040199576A1
• Time in Patent Office: 2,759 Days
• Field of Search: 709/238, 709/223, 709/203, 709/249, 370/338
• US Class Current: 709/223
• CPC Class Codes: H04L 41/065 involving logical or physical relationship, e.g. grouping and hierarchies
• CPC Class Codes: H04L 41/0893 Assignment of logical groups to network elements
• CPC Class Codes: H04L 41/0894 Policy-based network configuration management
• CPC Class Codes: H04L 41/22 comprising specially adapted graphical user interfaces [GUI]
• CPC Class Codes: H04L 43/00 Arrangements for monitoring or testing data switching networks
• CPC Class Codes: H04L 43/045 for graphical visualisation of monitoring data
• CPC Class Codes: H04L 43/062 related to network traffic
• CPC Class Codes: H04L 43/065 related to network devices
• CPC Class Codes: H04L 43/0811 by checking connectivity
• CPC Class Codes: H04L 43/0894 Packet rate
• CPC Class Codes: H04L 43/12 Network monitoring probes
• CPC Class Codes: H04L 43/16 Threshold monitoring
• CPC Class Codes: H04L 61/00 Network arrangements, protocols or services for addressing or naming
• CPC Class Codes: H04L 61/10 of different types
• CPC Class Codes: H04L 61/50 Address allocation
• CPC Class Codes: H04L 63/1408 by monitoring network traffic monitoring network traffic per se H04L43/00
• CPC Class Codes: H04L 63/1416 Event detection, e.g. attack signature detection

Abstract

Techniques for correlating different results of role grouping includes receiving two sets of grouping of nodes on a network, grouping of the nodes according to connection characteristics of the nodes in the groups, each of the sets having associated identifications and correlating associated identifications of one set with those of the other set so that the two groups have the same identifications, if the member hosts of each set of groups have nearly identical connection habits.

Claims

1. A computer implemented method of correlating different results of role grouping, comprises:

receiving in a computer system two sets of groupings of nodes on a network, each grouping of the nodes being according to connection characteristics of the nodes in the groups, with each of the sets having associated identifications;

correlating associated identifications of one set of groupings with those of the other set of groupings by;

determining a degree of similarity between a first node in the one set of groupings and a second node in the other set of groupings based on a number of connections that the first and second node have with a node one hop away over a plurality of time-periods, wherein similarity between host members in the groups is related to a sum of similarity values that the members in one group have with their similar neighbors in the other group;

computing a set of nodes that existed at time t−

1 but have been removed at time t, and a set of nodes that only appear at time t, to provide two sets of nodes that represent difference sets so that changes in the connection set of each host are as a result of changing connection patterns between the host and its neighbors that existed at time t; and

identifying the set of nodes that have not changed their neighbors between different executions of the role grouping; and

producing a result which indicates a structured view of the network based on the groupings.

2. The method of claim 1 wherein correlating uses a unique host identifier that does not change.

3. The method of claim 2 wherein a DNS name comprises the unique host identifier, and changes in IP addresses are dynamically updated.

4. The method of claim 1 wherein correlating further comprises:

comparing received results from different executions of a grouping process;

updating an identification set of member hosts in a grouping based on the received results so that identifications of member hosts in one set are equal to identifications of member hosts of the other set if the member hosts of one set and the other set are considered to belong to the same group.

5. The method of claim 4 wherein member hosts of one set and the other set are considered to be in the same group if, the connection habits of the member hosts of one set and those of the other set are similar.

6. The method of claim 5 wherein correlating further comprises:

eliminating differences between the two host sets so that connection patterns can be compared.

7. The method of claim 6 wherein differences are the set of nodes that existed in one set but were removed in the other set, and the set of nodes that only appear in the other set.

8. The method of claim 1 wherein for neighboring nodes that are not in a same group, the method comprises:

determining if a relation exists between members of one group and an other group if the total number of connections between members of the one group are similar to the total number of connections between members of the other group.

9. The method of claim 1 wherein for members of the group that remain uncorrelated, the method comprises:

determining whether the uncorrelated host members are similar based on how similar connection patterns between a host member in one group and its neighbor groups are to those between a host member in an other group and its neighbor groups.

10. The method of claim 9 wherein to determine whether uncorrelated hosts are similar, the total number of connections between a neighbor host and the group is used as a factor to decide whether the two groups share similar neighbors.

11. The method of claim 10 further comprising:

sorting in descending order all neighbors of a member that are not in the same set of hosts by using the total number of connection between the neighbor host and the host member as a sort key.

12. The method of claim 11 wherein sorting is repeated for the host member of the other group and its neighbors;

and the method further comprises;

examining two sorted lists to determine whether a total number of connections each node has with the corresponding group is within a specified threshold.

13. The method of claim 12 wherein the two groups are considered to be similar if the degree of similarity between the two groups is greater than the specified threshold.

14. The method of claim 12 wherein correlating remaining uncorrelated groups examines the connection habits between groups.

15. A computer implemented method, comprises:

correlating in a computer system assigned identifiers associated with groups of hosts on a network that are in a first set of the groups, with assigned identifiers that are associated with groups of hosts on the network in a second set of the groups by;

determining a degree of similarity between a first node in the first set of groups and a second node in the second set of groups based on a number of connections that the first and second node have with a node one hop away over a plurality of time-periods, wherein similarity between host members in the groups is related to a sum of similarity values that the members in one group have with their similar neighbors in the other group;

computing a set of nodes that existed at time t−

1 but have been removed at time t, and a set of nodes that only appear at time t, to provide two sets of nodes that represent difference sets, so that changes in the connection set of each host are as a result of changing connection patterns between the host and its neighbors that existed at time t;

identifying the set of nodes that have not changed their neighbors from between different executions of the role grouping;

determining if both groups have a common host neighbor; and

assigning a similarity value based on the minimum value of an average number of connections that members of the groups have with the common host neighbor; and

producing a result which indicates a structured view of the network based on the first and second set of groups.

16. The method of claim 15 wherein the two sets of groups are produced by different executions of a grouping process.

17. The method of claim 15 wherein the assigned identifiers are time invariant, unique host identifiers.

18. The method of claim 15 wherein the assigned identifiers are DNS names used when protocols that change a host'"'"'s IP address over time are used.

19. The method of claim 15 wherein correlating further comprises:

comparing results of two executions of a grouping process.

20. The method of claim 15 wherein correlating further comprises:

comparing results of two executions of a grouping process; and

updating assigned identifiers (ID) of set G^t, ID(G^t) so that ID(g<sup>t−

1</sup>)=ID(g^t) where g^t is a member of the set G^t and g<sup>t−

1</sup> is a member of the set G^t if g^t and gt<sup>−

1</sup> are considered to be in the same group.

21. The method of claim 15 wherein correlating further comprises:

isolating primary events that directly affect connection habits of groups;

identifying nodes that have not changed their neighbors; and

heuristically computing a similarity measure between the connection habits of two groups; and

assigning an assigned identifier (ID), ID(g^t) to be equal to an assigned identifier (ID), ID(g<sup>t−

1</sup>) if g<sup>t−

1</sup> has a predetermined degree of similarity with g^t.

22. The method of claim 15 wherein correlating further comprises:

eliminating differences between the two groups to compare the connection patterns of the hosts.

23. The method of claim 22 further comprising:

checking similarity between the connection habits of hosts in each group, by identifying the set of nodes that have not changed their neighbors from t−

1 to t.

24. The method of claim 23 wherein similarity is a value corresponding to a minimum value of an average number of connections that two groups g^t and g^t−

1, have with a common host neighbor (nH_same).

25. The method of claim 24 wherein for all neighboring nodes that are not in common, host neighbor nH_same the relation between neighboring nodes Nh^t−

1 and a group g^t, is that the connections are considered similar to that between Nh<sup>t−

1</sup> and g<sup>t−

1</sup>, if a total number of connections between Nh^t and g^t is close to a total number of connections between Nh<sup>t−

1</sup> and g<sup>t−

1</sup>.

26. Apparatus comprises:

a processor;

a memory;

and a non-transitory computer readable medium storing a computer program product for correlating groupings of nodes in a network, comprising instructions for causing the computer to;

receive two sets of results of nodes on a network associated into groups according to connection characteristics of the nodes in the groups, each of the sets having associated identifiers (IDs);

correlate IDs of one set with those of the other set so that the two groups have the same IDs by;

determining a degree of similarity between a first node in one group of the two sets of results of nodes and a second node in a second set of the two sets of results of nodes based on a number of connections that the first and second node have with a node one hop away over a plurality of time-periods, wherein similarity between host members in the groups is related to a sum of similarity values that the members in one group have with their similar neighbors in the other group;

computing a set of nodes that existed at time t−

1 but have been removed at time t and a set of nodes that only appear at time t, to provide two sets of nodes that represent difference sets so that changes in the connection set of each host are as a result of changing connection patterns between the host and its neighbors that existed at time t;

identifying the set of nodes that have not changed their neighbors from between different executions of the role grouping;

determining if both groups have a common host neighbor; and

assigning a similarity value based on the minimum value of an average number of connections that members of the groups have with the common host neighbor; and

produce a result which indicates a structured view of the network based on the two groups.

27. The apparatus of claim 26 wherein instructions to correlate uses a unique host identifier that does not change.

28. The apparatus of claim 27 wherein a DNS name is the unique host identifier and changes in IP addresses are dynamically updated.

29. The apparatus of claim 27 wherein instructions to correlate further comprises instructions to:

compare the received results from different executions of a grouping process;

update the ID set of member hosts in the groups based on the received results so that identifications of members of one set are equal to identifications of members of the other set if member hosts of one set and the other set are considered to belong to the same group.

30. The apparatus of claim 29 wherein member hosts one set and the other set are considered to be in a same group if connection habits of the member hosts of one set and those of the other set are similar.

31. The apparatus of claim 26 wherein instructions to correlate further comprises instructions to:

eliminate differences between the two host sets so that connection patterns can be compared.

32. Apparatus comprises:

a processor;

a memory; and

a non-transitory computer readable medium storing a computer program product for correlating groupings of nodes in a network, comprising instructions for causing the computer to;

correlate assigned identifiers associated with groups of hosts on a network that are in a first set of the groups, with assigned identifiers that are associated with groups of hosts on the network in a second set groups by;

determining a degree of similarity between a first node in the first set of groups and a second node in the second set of groups based on a number of connections that the first and second node have with a node one hop away over a plurality of time-periods, wherein similarity between host members in the groups is related to a sum of similarity values that the members in one group have with their similar neighbors in the other group;

computing a set of nodes that existed at time t−

1 but have been removed at time t, and a set of nodes that only appear at time t, to provide two sets of nodes that represent difference sets, so that changes in the connection set of each host are as a result of changing connection patterns between the host and its neighbors that existed at time t;

identifying the set of nodes that have not changed their neighbors from between different executions of the role grouping;

determining if both groups have a common host neighbor; and

assigning a similarity value based on the minimum value of an average number of connections that members of the groups have with the common host neighbor; and

produce a result which indicates a structured view of the network based on the two sets of groups.

33. The apparatus of claim 32 wherein the two sets of groups are produced by different executions of a grouping process.

34. The apparatus of claim 32 wherein the assigned identifiers are time invariant, unique host identifiers.

35. The apparatus of claim 32 wherein the assigned identifiers are DNS names used when protocols that change a host'"'"'s IP address over time are used.

36. The apparatus of claim 32 wherein instructions to correlate further comprises instructions to:

compare results of two executions of a grouping process.

37. The apparatus of claim 36 wherein correlating further comprises instructions to:

compare results of two executions of a grouping process; and

update assigned identifiers (ID) of set G^t, ID(G^t) so that ID(g<sup>t−

1</sup>)=ID(g^t) where g^t is a member of the set G^t and g<sup>t−

1</sup> is a member of the set G^t if g^t and g<sup>t−

1</sup> are considered to be in the same group.

38. A computer program product residing on a non-transitory computer readable medium for correlating groupings of nodes in a network, comprising instructions for causing the computer to:

receive two sets of results of nodes on a network associated into groups according to connection characteristics of the nodes in the groups, each of the sets having associated identifiers (IDs);

correlate IDs of one set with those of the other set so that the two groups have the same IDs by;

determining a degree of similarity between a first node in a first set of the two sets of results of nodes and a second node in a second set of the two sets of results of nodes based on a number of connections that the first and second node have with a node one hop away over a plurality of time-periods, wherein similarity between host members in the groups is related to a sum of similarity values that the members in one group have with their similar neighbors in the other group;

computing a set of nodes that existed at time t−

1 but have been removed at time t, and a set of nodes that only appear at time t, to provide two sets of nodes that represent difference sets, so that changes in the connection set of each host are as a result of changing connection patterns between the host and its neighbors that existed at time t;

identifying the set of nodes that have not changed their neighbors from between different executions of the role grouping;

determining if both have a common host neighbor; and

assigning a similarity value based on the minimum value of an average number of connections that members of the groups have with the common host neighbor; and

assigning a similarity value based on the minimum value of an average number of connections that members of the groups have with the common host neighbor; and

produce a result which indicates a structured view of the network based on the two sets of results of nodes.

39. The computer program product of claim 38 wherein instructions to correlate uses a unique host identifier that does not change.

40. The computer program product of claim 39 wherein a DNS name comprises the unique host identifier and changes in IP addresses are dynamically updated.

41. The computer program product of claim 38 wherein instructions to correlate further comprises instructions to:

compare received results from different executions of a grouping process;

update an identification set of member hosts in the groupings based on the received results so that identifications of member hosts in one set are equal to identifications of member hosts of the other set if the member hosts of one set and the other set are considered to belong to the same group.

42. The computer program product of claim 38 wherein member hosts in one set and the other set are considered to be in the same group if, the connection habits of the member hosts of one set and those of the other set are similar.

43. The computer program product of claim 38 wherein instructions to correlate further comprises instructions to:

eliminate differences between the two host sets so that connection patterns can be compared.

44. A computer program product residing on a non-transitory computer readable medium for correlating groupings of nodes in a network, comprising instructions for causing the computer to:

correlate assigned identifiers associated with groups of hosts on a network that are in a first set of the groups, with assigned identifiers that are associated with groups of hosts on the network in a second set of the groups by;

determining a degree of similarity between a first node in the first set of the groups and a second node in the second set of the groups based on a number of connections that the first and second node have with a node one hop away over a plurality of time-periods, wherein similarity between host members in the groups is related to a sum of similarity values that the members in one group have with their similar neighbors in the other group;

computing a set of nodes that existed at time t−

1 but have been removed at time t, and a set of nodes that on at time t, to provide two sets of nodes that represent difference sets, so that changes in the connection set of each host are as a result of changing connection patterns between the host and its neighbors that existed at time t;

identifying the set of nodes that have not changed their neighbors from between different executions of the role grouping;

determining if both groups have a common host neighbor; and

assigning a similarity value based on the minimum value of an average number of connections that members of the groups have with the common host neighbor; and

produce a result which indicates a structured view of the network based on the first and second set of groups.

45. The computer program product of claim 44 wherein the two sets of groups are produced by different executions of a grouping process.

46. The computer program product of claim 44 wherein the assigned identifiers are time invariant, unique host identifiers.

47. The computer program product of claim 44 wherein the assigned identifiers are DNS names used when protocols that change a host'"'"'s IP address over time are used.

48. The computer program product of claim 44 wherein instructions to correlate further comprises instructions to:

compare results of two executions of a grouping process.

49. The computer program product of claim 44 wherein instructions to correlate further comprises instructions to:

compare results of two executions of a grouping process; and

update assigned identifiers (ID) of set G^t, ID(G^t) so that ID(g<sup>t−

1</sup>)=ID(g^t) where g^t is a member of the set G^t and g<sup>t−

1</sup> is a member of the set G^t if g^t and g<sup>t−

1</sup> are considered to be in the same group.