Network event grouping

Patent metadata

Field	Value
Publication number	US-10447526-B2
Application number	US-201615341718-A
Country	US
Kind code	B2
Filing date	Nov 2, 2016
Priority date	Nov 2, 2016
Publication date	Oct 15, 2019
Grant date	Oct 15, 2019

Abstract

Systems and methods are disclosed for network event grouping. For example, methods may include generating a graph including vertices and edges, wherein at least one of the vertices is associated with an event type from a set of event types and wherein at least one of the edges is associated with a weight; removing, based on an associated weight and a first threshold, one or more edges from the graph; determining, after removing the one or more edges from the graph, whether the graph is chordal; responsive to determining that the graph is chordal, identifying a connected subgraph within the graph; determining a group of event types to include event types that are associated with vertices in the identified connected subgraph; and transmitting, storing, or displaying data specifying the group of event types.

First claim

What is claimed is:

1. A system for improving efficiency of computing network management, the system comprising:
a memory;
a processor; and
a network interface,
wherein the memory includes instructions executable by the processor to:
generate a graph including a plurality of vertices and a plurality of edges based on historical event data of a computing network, wherein at least one of the plurality of vertices is associated with an event type from a set of event types that occurred in the historical event data and wherein at least one of the plurality of edges is associated with a weight;
remove, based on an associated weight and a first threshold, one or more edges from the graph;
determine, after removing the one or more edges from the graph, whether the graph is chordal;
responsive to determining that the graph is chordal, identify one or more connected subgraphs within the graph;
determine a group of event types that includes two or more event types associated with vertices in a connected subgraph of the one or more connected subgraphs identified within the graph, wherein each of the vertices in the connected subgraph is connected to at least one other vertex in the connected subgraph by a respective edge;
store data specifying the group of event types;
receive additional event data associated with the computing network;
aggregate the additional event data into respective event types and groups of event types based on the stored data specifying the group of event types; and
transmit the aggregated additional event data to a display device for presentation to a user.

2. The system of claim 1 , wherein the instructions to generate the graph include instructions executable by the processor to:
determine the weight associated with one of the plurality of edges that connects a first vertex of the plurality of vertices that is associated with a first event type with a second vertex of the plurality of vertices that is associated with a second event type, wherein the weight is determined based on an estimate of mutual information between a plurality of events of the first event type and a plurality of events of the second event type.

3. The system of claim 1 , wherein a subset of event types in the set of event types comprise a plurality of alerts reflecting a status of a network resource.

4. The system of claim 3 , wherein one of the plurality of alerts comprises a first identifier of a configuration item and a second identifier of a metric.

5. The system of claim 1 , wherein a subset of event types in the set of event types comprise a plurality of alarms reflecting a network security threat.

6. The system of claim 1 , wherein the instructions to generate the graph include instructions executable by the processor to:
partition an analysis period, during which one or more events have occurred, into a plurality of time intervals, wherein the one or more events are classified into respective event types from the set of event types; and
determine the weight associated with one of the plurality of edges that connects one of the plurality of vertices associated with a first event type to one of the plurality of vertices that is associated with a second event type, wherein the weight is determined based at least in part on a first count of the plurality of time intervals in which a first event has occurred that is classified as the first event type, a second count of the time intervals in which a second event has occurred that is classified as the second event type, and a third count of the time intervals in which both the first event that is classified as the first event type and the second event that is classified as the second event type have occurred.

7. The system of claim 6 , wherein the instructions to determine the weight include instructions executable by the processor to:
determine a logarithm of a ratio of the third count to a product of the first count and the second count.

8. The system of claim 6 , wherein the plurality of edges connect one or more pairs of vertices of the plurality of vertices in the graph, wherein each such connected pair of vertices is associated with a pair of event types for which events classified in both event types of the pair of event types have co-occurred in at least one of the time intervals.

9. The system of claim 6 , wherein the weight is determined based at least in part on a fourth count of the time intervals in which a fourth event has occurred.

10. The system of claim 6 , wherein the weight is determined based at least in part on a fourth count of the time intervals in which a fourth event that is classified as the first event type or the second event type has occurred.

11. The system of claim 1 , wherein the memory includes instructions executable by the processor to:
select the first threshold; and
store data specifying the first threshold.

12. The system of claim 11 , wherein the instructions to select the first threshold include instructions executable by the processor to:
iteratively increase an edge pruning threshold, remove edges from the graph with weights less than the edge pruning threshold, and determine whether a resulting graph is chordal; and
responsive to determining the resulting graph is chordal, select the edge pruning threshold that resulted in the resulting graph becoming chordal as the first threshold.

13. The system of claim 1 , wherein the memory includes instructions executable by the processor to:
determine a count of the one or more connected subgraphs in the graph, where wherein each connected subgraph of the one or more connected subgraphs includes at least two vertices of the plurality of vertices and is disconnected from other vertices of the plurality of vertices in the graph; and
determine whether the count of the one or more connected subgraphs corresponds to a peak over variation of a pruning threshold applied to the graph, wherein determining the count of the one or more connected subgraphs corresponding to the peak is a precondition of determining whether the graph is chordal.

14. The system of claim 1 , wherein the memory includes instructions executable by the processor to:
partition an analysis period, during which one or more events have occurred, into a plurality of time intervals, wherein the one or more events are classified into respective event types from the set of event types;
for each time interval of the plurality of time intervals, determine a score for the group of event types, wherein the score is equal to a number of event types from the group of event types occurring in each time interval of the plurality of time intervals divided by a total number of event types in the group of event types;
determine an average score for the group of event types across the plurality of time intervals; and
determine a first metric for the group of event types, wherein the first metric is equal to a first count of time intervals of the plurality of time intervals for which the score for the group of event types is greater than the average score divided by a second count of time intervals of the plurality of time intervals for which the score of the group of event types is greater than zero.

15. The system of claim 14 , wherein the memory includes instructions executable by the processor to:
determine the first metric for the plurality of groups of event types;
for one of the plurality of groups of event types, determine whether the first metric is less than a second threshold; and
responsive to the first metric for one of the plurality of groups of event types being less than the second threshold, removi

Assignees

• Servicenow Inc

Inventors

• Tucker Stephen Scott
• Li Qingbin

Classifications

• H04L43/067

  using time frame reporting · CPC title

• H04L41/064

  involving time analysis · CPC title

• H04L41/142 Primary

  using statistical or mathematical methods · CPC title

• H04L41/0613

  based on the type or category of the network elements · CPC title

• H04L63/1416

  Event detection, e.g. attack signature detection · CPC title