Role correlation

• US 20040199576A1
• Filed: 11/03/2003
• Published: 10/07/2004
• 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
• Granted Patent: US 7,949,737 B2
• Time in Patent Office: Days
• US Class Current: 709/203
• 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 method of correlating different results of role grouping, comprises:

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 identification, if the member hosts of each set of groups have nearly identical connection habits.

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

3. The method of claim 2 wherein DNS names are the unique identifiers and changes in IP addresses are dynamically updated.

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

comparing the received results grouping process;

updating the identification set of members in the groups so that ID of member in one set are equal to identification of members of if the members of one set and the other set are considered to be the same group.

5. The method of claim 4 wherein members one set and the other set are considered to be in the same group if, the connection habits of the members 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 correlating groups comprises:

checking similarity between the connection habits of hosts in each group.

9. The method of claim 8 wherein correlating further comprises:

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

determining if both groups have a common host neighbor assigning a similarity value as the minimum value of the average numbers of connections that members of the groups, have with the common host neighbor.

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

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

11. The method of claim 1 wherein similarity between members in the groups is related to the sum of similarity values that the members in one group have with their similar neighbors in the other group.

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

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

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

14. The method of claim 13 further comprising:

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

15. The method of claim 14 wherein sorting is repeated for the member of the other group and its neighbors;

and the method further comprises;

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

16. The apparatus of claim 15 wherein the two groups are considered to be similar if the degree of similarity between the two groups is greater than the predetermined threshold.

17. The method of claim 15 wherein correlating the remaining uncorrelated groups examines the connection habits between groups.

18. A computer implemented method, comprises:

correlating 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, so that for the two sets of groups, those groups of hosts in the two sets that have substantially identical connection habits will have the same assigned identifiers.

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

20. The method of claim 18 wherein the assigned identifiers are time invariant, unique host identifiers.

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

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

comparing results of two executions of a grouping process.

23. The method of claim 18 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^t-1)=ID(g^t) where g^t is a member of the set G^t and g^t-1 is a member of the set G^t if g^t and g^t-1 are considered to be in the same group.

24. The method of claim 18 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^t-1) if g^t-1 has a predetermined degree of similarity with g^t.

25. The method of claim 18 wherein correlating further comprises:

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

26. The method of claim 25 further comprising:

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.

27. The method of claim 26 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.

28. The method of claim 27 wherein similarity is a value corresponding to a minimum value of the average numbers of connections that two groups g^t and g^t-1, have with a common host neighbor (nH_same).

29. The method of claim 28 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^t-1 and g^t-1 if the total number of connections between Nh^t and g^t is close to the total number of connections between between Nh^t-1 and g^t-1.

30. Apparatus comprises:

a processor;

a memory;

and a 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 ID'"'"'s; and

correlate IDs of one set with those of the other set so that the two groups have the same ID, if the member hosts of each set of groups have nearly identical connection habits.

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

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

compare the received results grouping process;

update the ID set of members in the groups so that ID of member in one set are equal to ID of members of if the members of one set and the other set are considered to be the same group.

34. The apparatus of claim 33 wherein members one set and the other set are considered to be in the same group if, the connection habits of the members of one set and those of the other set are similar.

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

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

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

check similarity between the connection habits of hosts in each group.

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

identify the set of nodes that have not changed their neighbors from between different executions of the role grouping and determining similarity by;

determine if both groups have a common host neighbor assigning a similarity value as the minimum value of the average numbers of connections that members of the groups, have with the common host neighbor.

38. The apparatus of claim 31 wherein similarity between members in the groups is related to the sum of similarity values that the members in one group have with their similar neighbors in the other group.

32. The apparatus of claim 32 wherein DNS names are the unique identifiers and changes in IP addresses are dynamically updated.

39. Apparatus comprises:

a processor;

a memory;

and a 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 of the groups, so that for the two sets of groups, those groups of hosts in the two sets that have substantially identical connection habits will have the same assigned identifiers.

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

41. The apparatus of claim 39 wherein the assigned identifiers are time invariant, unique host identifiers.

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

43. The apparatus of claim 39 wherein instructions to correlate further comprises instructions to:

compare results of two executions of a grouping process.

44. The apparatus of claim 43 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^t-1)=ID(g^t) where g^t is a member of the set G^t and g^t-1 is a member of the set G^t if g^t and g^t-1 are considered to be in the same group.

45. A computer program product residing on a 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 ID'"'"'s; and

correlate IDs of one set with those of the other set so that the two groups have the same ID, if the member hosts of each set of groups have nearly identical connection habits.

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

47. The computer program product of claim 46 wherein DNS names are the unique identifiers and changes in IP addresses are dynamically updated.

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

compare the received results grouping process;

update the ID set of members in the groups so that ID of member in one set are equal to ID of members of if the members of one set and the other set are considered to be the same group.

49. The computer program product of claim 45 wherein members one set and the other set are considered to be in the same group if, the connection habits of the members of one set and those of the other set are similar.

50. The computer program product of claim 45 wherein instructions to correlate further comprises instructions to:

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

51. The computer program product of claim 45 wherein instructions to correlate further comprises instructions to:

check similarity between the connection habits of hosts in each group.

52. The computer program product of claim 45 wherein instructions to correlate further comprises instructions to:

identify the set of nodes that have not changed their neighbors from between different executions of the role grouping and determining similarity by;

determine if both groups have a common host neighbor assigning a similarity value as the minimum value of the average numbers of connections that members of the groups, have with the common host neighbor.

53. The computer program product of claim 45 wherein similarity between members in the groups is related to the sum of similarity values that the members in one group have with their similar neighbors in the other group.

54. A computer program product residing on a 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, so that for the two sets of groups, those groups of hosts in the two sets that have substantially identical connection habits will have the same assigned identifiers.

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

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

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

58. The computer program product of claim 54 wherein instructions to correlate further comprises instructions to:

compare results of two executions of a grouping process.

59. The computer program product of claim 54 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^t-1)=ID(g^t) where g^t is a member of the set G^t and g^t-1 is a member of the set G^t if g^t and g^t-1 are considered to be in the same group.