Role grouping

• US 8,090,809 B2
• Filed: 11/03/2003
• Issued: 01/03/2012
• 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, Poletto, Massimiliano Antonio
• Primary Examiner(s): Dalencourt, Yves
• Assistant Examiner(s): Lai, Michael C
• Application Number:
  US10/701,392
• Publication Number:
  US 20040199792A1
• Time in Patent Office: 2,983 Days
• Field of Search: 709/223, 709/224, 709/228, 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/12 Discovery or management of network topologies
• 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/06 Generation of reports
• CPC Class Codes: H04L 43/0894 Packet rate
• CPC Class Codes: H04L 43/16 Threshold monitoring
• CPC Class Codes: H04L 63/1425 Traffic logging, e.g. anomaly detection
• CPC Class Codes: H04L 63/145 the attack involving the propagation of malware through the network, e.g. viruses, trojans or worms
• CPC Class Codes: H04L 63/1458 Denial of Service

Abstract

Techniques to assign nodes in a network to groups of nodes includes grouping nodes on a network into groups based on host connection set data by identifying bi-connected components in the host connection set data; and merging groups with similar connection habits as determined by examining the host connection set data into larger groups.

Claims

1. A computer implemented method to assign nodes in a network to groups of nodes, comprising:

observing connection patterns between nodes in the network;

identifying nodes with similar connection patterns in the network, wherein the similar connection patterns are based on regular communication with common network end nodes;

generating a connectivity graph based on observed connection patterns between nodes, wherein, in the connectivity graph, a vertex denotes a node, and an edge between vertices denotes a one-hop connectivity between the corresponding nodes;

grouping the identified nodes into groups based on the connectivity graph; and

merging a first group and a second group into a larger group in response to;

determining that a similarity measure between the first group and the second group exceeds a user-defined threshold, wherein the similarity measure is based on connection patterns from the first group and the second group, and

determining that a first average number of connected host pairs in the first group is within a pre-determined percentage of a second average number of connected host pairs in the second group.

2. The method of claim 1, wherein said grouping involves identifying bi-connected components, wherein a bi-connected component is a connected component in which any two edges of the component lie in a simple cycle.

3. The method of claim 1, wherein said grouping includes:

assigning a unique integer identifier to each group.

4. The method of claim 1, wherein said merging further comprises:

building a k-neighborhood graph from the connectivity graph;

removing group nodes from the connectivity graph; and

generating all bi-connected components in the k-neighborhood graph.

5. The method of claim 4, wherein for each bi-connected component in the all bi-connected components, forming the groups further comprises:

replacing the nodes in the connectivity graph by a new group node of the replaced nodes; and

labeling a group by a unique identifier and by a degree of similarity between the groups.

6. The method of claim 5 further comprising:

iteratively examining the connection graph until no ungrouped node remains or the degree of similarity between groups is zero.

7. The method of claim 1, wherein said grouping further comprises:

constructing a k-neighborhood graph to identify bi-connected components from the connectivity graph; and

responsive to a set of nodes placed into a group, assigning nodes in one group to a new group by removing vertices representing the nodes from the connectivity graph and replacing the vertices by one vertex representing the entire group.

8. The method of claim 1, wherein said grouping is repeated until the groups are large enough that no new groups are to be assigned.

9. The method of claim 1, wherein for each pair of two groups, G1 and G2, the merging the groups comprises:

appending a triple (G1, G2, s) to a list of node edges, where s represents a degree of similarity between the two groups, G1 and G2.

10. The method of claim 9, wherein said merging further comprises:

sorting the list of edges based on their s-values in descending order.

11. The method of claim 10, wherein said merging further comprises:

forming a new group based on G1 and G2 and assigning a number of connection pairs to a host in group G, which is a union of G1 and G2.

12. An apparatus comprising:

a processor;

a memory; and

an observation mechanism configured to observe connection patterns between nodes in a network;

an identification mechanism configured to identify nodes with similar connection patterns in the network, wherein the similar connection patterns are based on regular communication with common network end nodes;

a generating mechanism configured to generate a connectivity graph based on observed connection patterns between nodes, wherein, in the connectivity graph, a vertex denotes a node, and an edge between vertices denotes a one-hop connectivity between the corresponding nodes;

a grouping mechanism configured to group the identified nodes into groups based on the connectivity graph; and

a merging mechanism configured to merge a first group and a second group into a larger group in response to;

determining that a similarity measure between the first group and the second group exceeds a user-defined threshold, wherein the similarity measure is based on connection patterns from the first group and the second group, and

determining that a first average number of connected host pairs in the first group is within a pre-determined percentage of a second average number of connected host pairs in the second group.

13. The apparatus of claim 12, wherein the grouping mechanism is further configured to identify bi-connected components, wherein a bi-connected component is a connected component in which any two edges of the component lie in a simple cycle.

14. The apparatus of claim 12 wherein the grouping mechanism is further configured to:

assign a unique integer identifier to each group.

15. The apparatus of claim 12, wherein the merging mechanism is further configured to:

build a k-neighborhood graph from the connectivity graph;

remove group nodes from the connectivity graph; and

generate all bi-connected components in the k-neighborhood graph.

16. The apparatus of claim 15, wherein for each bi-connected component the group forming mechanism is configured to:

replace the nodes in the connectivity graph by a new group node of the replaced nodes; and

label a group by a unique identifier and by a degree of similarity between the groups.

17. The apparatus of claim 16 further comprising instructions to:

iteratively examining the connection graph until no ungrouped node remains or the degree of similarity between groups is zero.

18. The apparatus of claim 12, wherein the grouping mechanism is further configured to:

construct a k-neighborhood graph to identify bi-connected components in the connectivity graph; and

responsive to a set of nodes being placed into a group, assign nodes in one group to a new group by removing vertices representing the nodes from the connectivity graph and replacing the vertices by one vertex representing the entire group.

19. The apparatus of claim 12, wherein the grouping mechanism is configured to repeat until the groups are large enough that no new groups are to be assigned.

20. A computer program product residing on a non-transitory computer readable medium for assigning nodes in a network to groups of nodes comprising instructions, which when executed by a computer, cause the computer to:

observe connection patterns between nodes in the network;

identify nodes with similar connection patterns in the network, wherein the similar connection patterns are based on regular communication with common network end nodes;

generate a connectivity graph based on observed connection patterns between nodes, wherein, in the connectivity graph, a vertex denotes a node, and an edge between vertices denotes a one-hop connectivity between the corresponding nodes;

group the identified nodes into groups based on the connectivity graph; and

merge a first group and a second group into a larger group in response to;

determining that a similarity measure between the first group and the second group exceeds a user-defined threshold, wherein the similarity measure is based on connection patterns from the first group and the second group, and

determining that a first average number of connected host pairs in the first group is within a pre-determined percentage of a second average number of connected host pairs in the second group.

21. The computer program product of claim 20, wherein said instructions for causing the computer to group the identified nodes into groups include instructions to identify bi-connected components, wherein a bi-connected component is a connected component in which any two edges of the component lie in a simple cycle.

22. The computer program product of claim 20, wherein said instructions for causing the computer to group the identified nodes into groups comprise instructions to:

assign a unique integer identifier to each group.

23. The computer program product of claim 20, wherein said instructions to merge further comprise instructions to:

build a k-neighborhood graph from the connectivity graph;

remove group nodes from the connectivity graph; and

generate all bi-connected components in the k-neighborhood graph.

24. The computer program product of claim 23, wherein, for each bi-connected component in the all bi-connected components, said instructions for causing the computer to group the identified nodes into groups further comprise instructions to:

replace the nodes in the connectivity graph by a new group node of the replaced nodes; and

label a group by a unique identifier and by a degree of similarity between the groups.

25. The computer program product of claim 24 further comprising instructions to:

iteratively examining the connection graph until no ungrouped node remains or the degree of similarity between groups is zero.

26. The computer program product of claim 20, wherein said instructions for causing the computer to group the identified nodes into groups further comprise instructions to:

construct a k-neighborhood graph to identify bi-connected components in the connectivity graph; and

responsive to a set of nodes being placed into a group, assign nodes in one group to a new group by removing vertices representing the nodes from the connectivity graph and replacing the vertices by one vertex representing the entire group.

27. The computer program product of claim 20, wherein said instructions for causing the computer to group the identified nodes into groups repeat until the groups are large enough that no new groups are to be assigned.