Generating an operational definition of baseline for monitoring network traffic data

• US 7,962,607 B1
• Filed: 09/08/2006
• Issued: 06/14/2011
• Est. Priority Date: 09/08/2006
• Status: Active Grant

• Current Assignee: NetScout Systems Incorporated
• Original Assignee: Network General Technology
• Inventors: Maturi, Mohan Kumar, Chang, Hung-Jen
• Primary Examiner(s): Serrao; Ranodhi N
• Assistant Examiner(s): Hussain; Farrukh
• Application Number:
  US11/518,015
• Time in Patent Office: 1,740 Days
• Field of Search: 709/223, 709/224, 707/101, 707/102, 711/123, 711/125, 711/126
• US Class Current: 709/224
• CPC Class Codes: H04L 41/142 using statistical or mathematical methods
• CPC Class Codes: H04L 41/147 for predicting network behaviour
• CPC Class Codes: H04L 43/04 Processing captured monitoring data, e.g. for logfile generation
• CPC Class Codes: H04L 43/045 for graphical visualisation of monitoring data

Abstract

A system and a method are disclosed for establishing a baseline and the corresponding bands of data for alarming, etc. Historical raw data are aggregated and grouped. For example, the data may be and hourly grouped as 168 groups of data in a weekly frame. Clusters of the groups of data are then formed based on dynamic data window by analyzing statistical similarity among the 168 groups of data. Data in each cluster of groups, originated from the raw data at specific hour(s) of day on specific day(s) of week, are used as historical data to predict a baseline and the envelopes at these associated hour(s) and day(s). Generating a baseline includes determining a mapping function, which transforms data in a cluster to become normal or nearly normal. A mean and standard deviation of the transformed data are calculated. Envelopes are determined using the mean and the standard deviation. An inverse transformation function is uniquely derived. The mean and the envelopes are inversely transformed using the inverse function. This operationally decides a baseline and the corresponding bands for every weekly time frame hour.

Claims

1. A method executed on a computer including at least one processor for establishing a baseline of network traffic data, the method comprising:

generating a configurable static window for grouping said network traffic data;

extracting, grouping and ordering said network traffic data based on the configurable static window;

generating a dynamic window for clustering said groups of network traffic data based on statistical similarity of groups;

clustering said groups of network traffic data based on the dynamic window;

determining a transformation function from historical network traffic data using feedback control, the transformation function making a data set having a normal distribution or a nearly normal distribution;

generating transformed network traffic data associated with a distribution having the normal distribution or having the nearly normal distribution by applying the transformation function to said network traffic data within a cluster to map the network traffic data within the cluster into the data set having the normal distribution or having a nearly normal distribution;

calculating an error indicating a similarity between the distribution associated with the transformed network traffic data and the normal distribution, and responsive to the error equaling or exceeding a threshold, modifying the transformation function to modify the distribution associated with the transformed network traffic data to reduce the error; and

generating a baseline of network traffic data for each cluster from the transformed network traffic data.

2. The method of claim 1 further comprising caching the groups of network traffic data in a defined data structure.

3. The method of claim 1 further comprising generating corresponding bands of network traffic data for each cluster.

4. The method of claim 3 wherein generating a baseline and the corresponding bands includes:

calculating a mean and standard deviation of the transformed network traffic data;

calculating envelopes using the mean and the standard deviation;

deriving the inverse transformation function based on the transformation function;

inversely transforming the mean and the envelopes using the inverse transformation function;

defining the inversely transformed mean as a baseline;

generating alarms responsive to the inversely transformed envelopes.

5. The method of claim 1, wherein the clustering of groups of network traffic data comprises:

calculating gradients between ordered groups based on centroids of the groups;

determining number of clusters of groups and initial clusters based on the distribution of the gradients;

marking the clusters as being in a first set;

calculating the centroids of the clusters in the first set;

clustering groups to form a second set of clusters based on distances to the centroids;

comparing the clusters in the second set with the clusters in the first set.

6. The method of claim 5 further comprising:

repeating the marking, calculating, clustering and comparing the clusters until the clusters after marking, calculating and clustering are the same as the clusters before marking, calculating and clustering.

7. The method of claim 4 wherein the calculating envelopes using the mean and the standard deviation includes calculating envelopes based on multipliers of the standard deviation from the mean.

8. The method of claim 7 wherein the multipliers are between 2.0 and 4.0 standard deviations.

9. The method of claim 7 wherein the multipliers are configurable by a user.

10. The method of claim 4 further comprising removing outlier network traffic data after the data transformation.

11. The method of claim 10 wherein the removing outlier network traffic data includes:

calculating the mean and standard deviation of a given data set;

determining the outlier that is the furthest datum and statistically far away from its closest neighbor and from the mean value;

discarding the outlier and forming a new set of data;

repeating the calculating, determining and discarding until no more outliers are detected.

12. The method of claim 4 wherein calculating the error indicating the similarity between the distribution associated with the transformed network traffic data and the normal distribution, and responsive to the error equaling or exceeding a threshold, modifying the transformation function to modify the distribution associated with the transformed network traffic data to reduce the error includes:

defining a parameterized transformation function;

setting initial parameter values;

applying the parameterized transformation function to the network traffic data;

calculating a result of an error function based on the transformed network traffic data and the desired values;

determining if the result of the error function error is below the threshold;

adjusting the parameters according to the result of the error function to update the parameterized transformation function;

repeating the applying, calculating, determining and adjusting until the result of the error function is below the threshold.

13. A computer program product for use in conjunction with a computer system, the computer program product comprising a non-transitory computer readable storage medium including a computer program mechanism executable by a processor embedded therein, the computer program mechanism including:

instructions for generating a configurable static window for grouping network traffic data;

instructions for extracting, grouping and ordering said network traffic data based on the configurable static window;

instructions for generating a dynamic window for clustering said groups of network traffic data based on statistical similarity of groups;

instructions for clustering said groups of network traffic data based on the dynamic window;

instructions for determining a transformation function from historical network traffic data using feedback control, the transformation function making a data set having a normal distribution or a nearly normal distribution;

instructions for generating transformed network traffic data associated with a distribution having the normal or having the nearly normal distribution by applying the transformation function to said network traffic data within a cluster to map the network traffic data within the cluster to the data set having the normal distribution or having the nearly normal distribution;

instructions for calculating an error indicating a similarity between the distribution associated with the transformed network traffic data and the normal distribution, and responsive to the error equaling or exceeding a threshold, modifying the transformation function to modify the distribution associated with the transformed network traffic data to reduce the error; and

instructions for generating a baseline of network traffic data for each cluster from the transformed network traffic data.

14. The computer program product of claim 13 wherein instructions for generating a baseline includes:

instructions for calculating a mean and standard deviation of the transformed network traffic data;

instructions for calculating envelopes using the mean and the standard deviation;

instructions for deriving the inverse transformation function based on the transformation function;

instructions for inversely transforming the mean and the envelopes using the inverse transformation function;

instructions for defining the inversely transformed mean as a baseline;

instructions for generating alarms responsive to the inversely transformed envelopes.

15. The computer program product of claim 13, wherein the instructions for clustering of groups of network traffic data comprises:

instructions for calculating gradients between ordered groups based on centroids of the groups;

instructions for determining number of clusters of groups and initial clusters based on the distribution of the gradients;

instructions for marking the clusters as being in a first set;

instructions for calculating the centroids of the clusters in the first set;

instructions for clustering groups to form a second set of clusters based on distances to the centroids;

instructions for comparing the clusters in the second set with the clusters in the first set.

16. The computer program product of claim 15 further comprising:

instructions for repeating the marking, calculating, clustering and comparing the clusters until the clusters after marking, calculating and clustering are the same as the clusters before marking, calculating and clustering.

17. The computer program product of claim 14 wherein instructions for removing outlier data after the data transformation.

18. The computer program product of claim 17 wherein the instructions for removing outlier data comprises:

instructions for calculating the mean and standard deviation of a given data set;

instructions for determining the outlier that is the furthest datum and statistically far away from its closest neighbor and from the mean value;

instructions for discarding the outlier and forming a new set of data;

instructions for repeating the calculating, determining and discarding until no more outliers are detected.

19. The computer program product of claim 14 wherein instructions for calculating an error indicating a similarity between the distribution associated with the transformed network traffic data and the normal distribution, and responsive to the error equaling or exceeding a threshold, modifying the transformation function to modify the distribution associated with the transformed network traffic data to reduce the error include:

instructions for defining a parameterized transformation function;

instructions for setting initial parameter values;

instructions for applying the parameterized transformation function to the network traffic data;

instructions for calculating a result of an error function based on the transformed network traffic data and the desired values;

instructions for determining if the result of the error function is below the threshold;

instructions for adjusting the parameters according to the result of the error function to update the parameterized transformation function;

instructions for repeating the applying, calculating, checking and adjusting until the result of the error function is below the threshold.

20. A system comprising:

a processor for executing programs;

a module executable by the processor, the module including;

instructions for generating a configurable static window for grouping network traffic data;

instructions for extracting, grouping and ordering said network traffic data based on the configurable static window;

instructions for generating a dynamic window for clustering said groups of network traffic data based on statistical similarity of groups;

instructions for clustering said groups of network traffic data based on the dynamic window;

instructions for determining a transformation function from historical network traffic data using feedback control, the transformation function making a data set having a normal distribution or a nearly normal distribution;

instructions for generating transformed network traffic data associated with a distribution having the normal distribution or having the nearly normal distribution by applying the transformation function to said network traffic data within a cluster to map the network traffic data within the cluster into the data set having the normal distribution or having the nearly normal distribution;

instructions for calculating an error indicating a similarity between the distribution associated with the transformed network traffic data and the normal distribution, and responsive to the error equaling or exceeding a threshold, modifying the transformation function to modify the distribution associated with the transformed network traffic data to reduce the error; and

instructions for generating a baseline of network traffic data for each cluster from the transformed network traffic data.

21. The system of claim 20 wherein instructions for generating a baseline includes:

instructions for calculating a mean and standard deviation of the transformed network traffic data;

instructions for calculating envelopes using the mean and the standard deviation;

instructions for deriving the inverse transformation function based on the transformation function;

instructions for inversely transforming the mean and the envelopes using the inverse transformation function;

instructions for defining the inversely transformed mean as a baseline;

instructions for generating alarms responsive to the inversely transformed envelopes.

22. The system of claim 20, wherein the instructions for clustering of groups of network traffic data comprises:

instructions for calculating gradients between ordered groups based on centroids of the groups;

instructions for determining number of clusters of groups and initial clusters based on the distribution of the gradients;

instructions for marking the clusters as being in a first set;

instructions for calculating the centroids of the clusters in the first set;

instructions for clustering groups to form a second set of clusters based on distances to the centroids;

instructions for comparing the clusters in the second set with the clusters in the first set.

23. The system of claim 22 further comprising:

instructions for repeating the marking, calculating, clustering and comparing the clusters until the clusters after marking, calculating and clustering are the same as the clusters before marking, calculating and clustering.

24. The system of claim 21 wherein instructions for removing outlier data after the data transformation.