Method for real-time auto-detection of outliers

• US 7,277,843 B1
• Filed: 07/15/2002
• Issued: 10/02/2007
• Est. Priority Date: 07/15/2002
• Status: Active Grant

• Current Assignee: Riverbed Technology, LLC (Riverbed Technology Incorporated)
• Original Assignee: Network Physics, Inc. (Riverbed Technology Incorporated)
• Inventors: Pavel, Tomas J., Wen, Han C.
• Primary Examiner(s): Rodriguez; Paul
• Assistant Examiner(s): PIERRE LOUIS, ANDRE
• Application Number:
  US10/195,905
• Time in Patent Office: 1,905 Days
• Field of Search: 703/21, 709/223, 709/224, 709/226
• US Class Current: 703/21
• CPC Class Codes: H04L 43/02 Capturing of monitoring data
• CPC Class Codes: H04L 43/16 Threshold monitoring

Abstract

A moving window of data is used to determine a local baseline as a moving average of the data weighted by the number of measurements in each time interval. A next measurement associated with a next time interval is compared to a value associated with the baseline to determine an outlier. In some cases, for example where the time series of the data shows small variability around a local mean, the next measurement is compared to a multiple of the weighted moving average to determine an outlier. In other cases, for example where the time series of the data shows significant variability around the local mean, the next measurement is compared to the sum of the weighted moving average and a multiple of a moving root mean square deviation value weighted by the number of measurements in each time interval and in some cases, a damping factor.

Claims

1. A machine implemented method for assessing performance of a network, comprising:

collecting data through the network, wherein the data include measurements of a metric to assess the performance of the network;

determining, for a number of the measurements of the metric within a plurality of time intervals, a baseline that includes computing a moving average of the measurements of the metric weighted by the number of measurements in each time interval, wherein the moving average comprises a result of dividing a first sum, over all time intervals, of a first product of the number of measurements for each time interval multiplied by values of the measurements within each time interval multiplied by a damping factor, by a second sum, over all time intervals, of a second product of the number of measurements for each time interval multiplied by the damping factor;

comparing a next metric measurement associated with a next time interval to the baseline that includes the moving average, to determine whether or not the next metric measurement should be classified as an outlier with respect to the baseline;

after determining whether or not the next metric measurement should be classified as the outlier with respect to the baseline, moving to a next data point of the measurements of the metrics; and

repeating the determining and the comparing for the next data point to automatically detect outliers in real time as the data is collected.

2. The method of claim 1 wherein the metric comprises a network performance metric.

3. The method of claim 2 wherein the metric is selected from the group comprising round trip time, server response time, packet loss, duration and file size.

4. The method of claim 1 wherein the next metric measurement is compared to the baseline that includes a multiple of the weighted moving average, to determine if the next metric measurement should be classified as an outlier.

5. The method of claim 4 wherein if the next metric measurement exceeds the multiple of the weighted moving average the next metric measurement is classified as an outlier.

6. The method of claim 5 wherein the multiple comprises 1.5, 2 or 2.5.

7. The method of claim 1 wherein the damping factor comprises a mathematical inverse of the number of time intervals.

8. The method of claim 1 wherein the next metric measurement is compared to the baseline that includes a multiple of a moving root mean square deviation value weighted by the number of measurements in each time interval.

9. The method of claim 8 wherein the moving root mean square deviation value is further weighted by a damping factor.

10. The method of claim 9 wherein the damping factor comprises a mathematical inverse of the number of time intervals.

11. The method of claim 8 wherein the multiple comprises 2, 3 or 4.

12. The method of claim 8 wherein if the next metric measurement exceeds a sum of the moving average and a multiple of the weighted root mean square deviation value, the next metric measurement is classified as an outlier.

13. The method of claim 12 wherein the multiple comprises 2, 3 or 4.

14. The method of claim 12 wherein the metric comprises a network performance metric.

15. The method of claim 4 wherein the metric comprises a network performance metric.

16. The method of claim 1 wherein the determining and comparing procedures are repeated using further metric measurements in place of the next metric measurement.

17. A machine readable medium containing executable instructions which when executed by a computer cause the computer to automatically in real time assess a performance of a network by performing operations comprising:

collecting data through a network, wherein the data include measurements of a metric;

determining, for a number of the measurements of the metric within a plurality of time intervals, a baseline that includes computing a moving average of the measurements of the metric weighted by the number of measurements in each time interval, wherein the moving average comprises a result of dividing a first sum, over all time intervals, of a first product of the number of measurements for each time interval multiplied by values of the measurements within each time interval multiplied by a damping factor, by a second sum, over all time intervals, of a second product of the number of measurements for each time interval multiplied by the damning factor;

comparing a next metric measurement associated with a next time interval to the baseline that includes the moving average, to determine whether or not the next metric measurement should be classified as an outlier with respect to the baseline;

after determining whether or not the next metric measurement should be classified as the outlier with respect to the baseline, moving to a next data point of the measurements of the metrics; and

repeating the determining and the comparing for the next data point to automatically detect outliers in real time as the data is collected.

18. The machine readable medium of claim 17 wherein the metric comprises a network performance metric.

19. The machine readable medium of claim 18 wherein the metric is selected from the group comprising round trip time, server response time, packet loss, duration and file size.

20. The machine readable medium of claim 17 wherein the next metric measurement is compared to the baseline that includes a multiple of the weighted moving average, to determine if the next metric measurement should be classified as an outlier.

21. The machine readable medium of claim 20 wherein if the next metric measurement exceeds the multiple of the weighted moving average the next metric measurement is classified as an outlier.

22. The machine readable medium of claim 21 wherein the multiple comprises 1.5, 2 or 2.5.

23. The machine readable medium of claim 17, wherein the damping factor comprises a mathematical inverse of the number of time intervals.

24. The machine readable medium of claim 17 wherein the next metric measurement is compared to the baseline that includes a multiple of a moving root mean square deviation value weighted by the number of measurements in each time interval.

25. The machine readable medium of claim 24 wherein the moving root mean square deviation value is further weighted by a damping factor.

26. The machine readable medium of claim 25 wherein the damping factor comprises a mathematical inverse of the number of time intervals.

27. The machine readable medium of claim 24 wherein the multiple comprises 2, 3 or 4.

28. The machine readable medium of claim 24 wherein if the next metric measurement exceeds a sum of the moving average and a multiple of the weighted root mean square deviation value, the next metric measurement is classified as an outlier.

29. The machine readable medium of claim 28 wherein the multiple comprises 2, 3 or 4.

30. The machine readable medium of claim 28 wherein the metric comprises a network performance metric.

31. The machine readable medium of claim 20 wherein the metric comprises a network performance metric.

32. The machine readable medium of claim 17 wherein the determining and comparing procedures are repeated using further metric measurements in place of the next metric measurement.