Passive and comprehensive hierarchical anomaly detection system and method

• US 8,984,116 B2
• Filed: 04/23/2013
• Issued: 03/17/2015
• Est. Priority Date: 08/27/2011
• Status: Expired due to Fees

• Current Assignee: AT&T Intellectual Property I LP (AT&T, Inc.)
• Original Assignee: AT&T Intellectual Property I LP (AT&T, Inc.)
• Inventors: Ge, Zihui, Flavel, Ashley, Gerber, Alexandre, Pei, Dan, Shah, Hiren, Yan, He, Yates, Jennifer
• Primary Examiner(s): MIRZA, ADNAN M
• Application Number:
  US13/868,236
• Publication Number:
  US 20130282896A1
• Time in Patent Office: 693 Days
• Field of Search: 709/223, 709/224
• US Class Current: 709/223
• CPC Class Codes: H04L 41/0609 based on severity or priority
• CPC Class Codes: H04L 41/0622 based on time
• CPC Class Codes: H04L 43/04 Processing captured monitoring data, e.g. for logfile generation
• CPC Class Codes: H04L 43/0823 Errors, e.g. transmission errors
• CPC Class Codes: H04L 43/0864 Round trip delays
• CPC Class Codes: H04L 43/16 Threshold monitoring

Abstract

A technique for monitoring performance in a network uses passively monitored traffic data at the server access routers. The technique aggregates performance metrics into clusters according to a spatial hierarchy in the network, and then aggregates performance metrics within spatial clusters to form time series of temporal bins. Representative values from the temporal bins are then analyzed using an enhanced Holt-Winters exponential smoothing algorithm.

Claims

1. A method for detecting abnormal observations from a series of observations, comprising:

formulating, by a computer, an observation prediction by applying a working exponential smoothing model to a series of past observations;

determining, by the computer, whether a most recent observation is an abnormal observation by comparing the most recent observation to the observation prediction;

updating, by the computer, using the most recent observation, a shadow exponential smoothing model;

selectively updating, by the computer, using the most recent observation, the working exponential smoothing model based on the determining whether the most recent observation is an abnormal observation;

making a determination, by the computer, that a number of recent abnormal observations exceeds a threshold number of recent abnormal observations; and

upon making the determination that the number of recent abnormal observations exceeds a threshold number of consecutive abnormal observations, replacing, by the computer, the working exponential smoothing model with the shadow exponential smoothing model.

2. The method of claim 1, wherein selectively updating the working exponential smoothing model further comprises:

updating the working exponential smoothing model if and only if the most recent observation is not an abnormal observation, or the most recent observation is an abnormal observation and a number of abnormal observations received in a current time cycle is below a threshold number of abnormal observations for the current time cycle.

3. The method of claim 1, wherein the threshold number of recent abnormal observations comprises a threshold number of consecutive abnormal observations.

4. The method of claim 1, wherein the working exponential smoothing model and the shadow exponential smoothing model each comprise Holt Winters smoothing algorithm.

5. The method of claim 1, wherein the working exponential smoothing model and the shadow exponential smoothing model each comprise a current level component, a trend component and a seasonal component.

6. The method of claim 1, wherein the series of observations is a series of network communication round trip times in a network address spatial cluster.

7. The method of claim 6, wherein the round trip times are separated from each other by at least 600 seconds.

8. The method of claim 6, further comprising:

suppressing observations of the client round trip times by using observations of only a minimum round trip time in each of a plurality of time windows.

9. The method of claim 1, wherein the working exponential smoothing model and the shadow exponential smoothing model each comprise a modified Holt Winters smoothing algorithm that outputs a deviation score matching that in a standard Gaussian distribution.

10. The method of claim 9, wherein an observation is considered an abnormal observation when the deviation score exceeds 4.

11. A non-transitory computer-readable medium having stored thereon computer readable instructions for detecting abnormal observations from a series of observations, wherein execution of the computer readable instructions by a processor causes the processor to perform operations comprising:

formulating an observation prediction by applying a working exponential smoothing model to a series of past observations;

determining whether a most recent observation is an abnormal observation by comparing the most recent observation to the observation prediction;

updating, using the most recent observation, a shadow exponential smoothing model;

selectively updating, using the most recent observation, the working exponential smoothing model based on the determining whether the most recent observation is an abnormal observation;

making a determination that a number of recent abnormal observations exceeds a threshold number of recent abnormal observations; and

upon making the determination that the number of recent abnormal observations exceeds a threshold number of consecutive abnormal observations, replacing the working exponential smoothing model with the shadow exponential smoothing model.

12. The non-transitory computer-readable medium of claim 11, wherein selectively updating the working exponential smoothing model further comprises:

updating the working exponential smoothing model if and only if the most recent observation is not an abnormal observation, or the most recent observation is an abnormal observation and a number of abnormal observations received in a current time cycle is below a threshold number of abnormal observations for the current time cycle.

13. The non-transitory computer-readable medium of claim 11, wherein the threshold number of recent abnormal observations comprises a threshold number of consecutive abnormal observations.

14. The non-transitory computer-readable medium of claim 11, wherein the working exponential smoothing model and the shadow exponential smoothing model each comprise Holt Winters smoothing algorithm.

15. The non-transitory computer-readable medium of claim 11, wherein the working exponential smoothing model and the shadow exponential smoothing model each comprise a current level component, a trend component and a seasonal component.

16. The non-transitory computer-readable medium of claim 11, wherein the series of observations is a series of network communication round trip times in a network address spatial cluster.

17. The non-transitory computer-readable medium of claim 16, wherein the round trip times are separated from each other by at least 600 seconds.

18. The non-transitory computer-readable medium of claim 16, the operations further comprising:

suppressing observations of the client round trip times by using observations of only a minimum round trip time in each of a plurality of time windows.

19. The non-transitory computer-readable medium of claim 11, wherein the working exponential smoothing model and the shadow exponential smoothing model each comprise a modified Holt Winters smoothing algorithm that outputs a deviation score matching that in a standard Gaussian distribution.

20. The non-transitory computer-readable medium of claim 19, wherein an observation is considered an abnormal observation when the deviation score exceeds 4.