Anomaly detection in time series data

• US 9,614,742 B1
• Filed: 03/14/2013
• Issued: 04/04/2017
• Est. Priority Date: 03/14/2013
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Zhang, Xinyi, Yu, Kevin
• Primary Examiner(s): Bates, Kevin
• Assistant Examiner(s): Pant, Ranjan
• Application Number:
  US13/827,144
• Time in Patent Office: 1,482 Days
• CPC Class Codes: H04L 41/142 using statistical or mathematical methods
• CPC Class Codes: H04L 43/0823 Errors, e.g. transmission errors

Abstract

Described herein are systems, mediums, and methods for detecting blockage of network traffic at a network server. A signal representative of time series data associated with network traffic is received at a processor for analysis. A data segmentation algorithm and an anomaly detection algorithm are applied in series to the received data. The segmentation algorithm detects regime shifts in the data. Data between regime shifts is considered a segment of data. The anomaly detection algorithm analyzes each segment individually to determine whether anomalies exist in the segment. If a cyclic pattern is found in the segment, the cyclic pattern is extracted from the segment leaving a residual data for analysis. A probability distribution of the residual data is determined for analysis. When an anomaly is detected in the segment o based on the probability distribution of the residual data, it is determined that blockage has occurred on the network traffic.

Claims

1. A non-transitory electronic device readable storage medium storing instructions that, when executed, cause one or more processors to:

receive a network traffic signal in form of time series data from one or more network servers;

identify a set of regime shift points in the received network traffic signal based on varying statistical properties of the received network traffic signal;

determine a segment of the network traffic signal based on the identified the set of regime shift points;

identify that a cyclic pattern exists in the segment of the network traffic signal;

responsive to identifying that the cyclic pattern exists, extract the cyclic pattern from the segment of the network traffic signal;

generate a residual segment of the network traffic signal based on the segment of the network traffic signal and the extracted cyclic pattern;

compute a probability distribution of the residual segment of the network traffic signal;

detect that an anomaly exists in the segment of the network traffic signal based on statistical properties of the probability distribution of the residual signal;

responsive to detecting that the anomaly exists, determine that there is a blockage of network service among the one or more network servers based on a magnitude of the anomaly and a magnitude of the network traffic signal; and

responsive to detecting that the anomaly exists, reconfigure a network comprising the one or more network servers.

2. The medium of claim 1, wherein the received network traffic signal is offline data received for a pre-determined amount of time.

3. The medium of claim 1, wherein a regime shift occurs when a trend in the received network traffic signal changes.

4. The medium of claim 3, wherein a trend corresponds to one or more long-term fluctuations in the received network traffic signal.

5. The medium of claim 4, further storing instructions that, when executed, cause one or more processors to:

determine a first trend before an identified regime shift point and a second trend, different from the first trend, after the identified regime shift point.

6. The medium of claim 1, wherein a segment of the network traffic signal is a chunk of data that exists between two consecutive regime shift points.

7. The medium of claim 1, wherein a cyclic pattern is a repetitive periodic feature occurring in the segment of the network traffic signal.

8. A system, comprising:

a processor that receives a network traffic signal in form of time series data from one or more network servers, the processor executing;

segmentation logic for;

identifying a set of regime shift points in the received network traffic signal based on varying statistical properties of the received network traffic signal; and

determining a segment of the network traffic signal based on the identified the set of regime shift points; and

anomaly detection logic for;

identifying that a cyclic pattern exists in the segment of the network traffic signal;

responsive to identifying that the cyclic pattern exists, extracting the cyclic pattern from the segment of the network traffic signal;

generating a residual segment of the network traffic signal based on the segment of the network traffic signal and the extracted cyclic pattern;

computing a probability distribution of the residual segment of the network traffic signal;

detecting that an anomaly exists in the segment of the network traffic signal based on statistical properties of the probability distribution of the residual signal;

responsive to detecting that the anomaly exists, determine that there is a blockage of network service among the one or more network servers based on a magnitude of the anomaly and a magnitude of the network traffic signal; and

responsive to detecting that the anomaly exists, reconfigure a network comprising the one or more network servers.

9. The system of claim 8, wherein:

a regime shift occurs when a trend in the received network traffic signal changes; and

the trend corresponds to one or more long-term fluctuations in the received network traffic signal.

10. The system of claim 9, wherein the processor executes the segmentation logic for:

determining a first trend before an identified regime shift point and a second trend, different from the first trend, after the identified regime shift point.

11. The system of claim 8, wherein a segment of the network traffic signal is a chunk of data that exists between two consecutive regime shift points.

12. The system of claim 8, wherein a cyclic pattern is a repetitive periodic feature occurring in the segment of the network traffic signal.

13. A computer-implemented method comprising:

receiving, by a computing device, a network traffic signal in form of time series data from one or more network servers;

identifying, by the computing device, a set of regime shift points in the received network traffic signal based on varying statistical properties of the received network traffic signal;

determining, using the computing device, a segment of the network traffic signal based on the identified the set of regime shift points;

identifying, by the computing device that a cyclic pattern exists in the segment of network traffic signal;

responsive to identifying that the cyclic pattern exists, extracting, by the computing device, the cyclic from the segment of the network traffic signal;

generating, by the computing device, a residual segment of the network traffic signal based on the segment of the network traffic signal and the extracted cyclic pattern;

computing, by the computing device, a probability distribution of the residual segment of the network traffic signal;

detecting, by the computing device, that an anomaly exists in the segment of the network traffic signal based on statistical properties of the probability distribution of the residual signal;

responsive to detecting that the anomaly exists, determining, by the computing device, that there is a blockage of network service among the one or more network servers based on a magnitude of the anomaly and a magnitude of the network traffic signal; and

responsive to detecting that the anomaly exists, reconfiguring, by the computing device, a network comprising the one or more network servers.

14. The method of claim 13, wherein:

a regime shift occurs when a trend in the received network traffic signal changes; and

the trend corresponds to one or more long-term fluctuations in the received network traffic signal.

15. The method of claim 14, further comprising:

determining a first trend before an identified regime shift point and a second trend, different from the first trend, after the identified regime shift point.

16. The method of claim 13, wherein:

a segment of data is a chunk of data that exists between two consecutive regime shift points, and

a cyclic pattern is a repetitive periodic feature occurring in the segment of the network traffic signal.