Low-complexity detection of potential network anomalies using intermediate-stage processing

Abstract

In an embodiment, a computer implemented method receives flow data for a network flows. The method extracts a tuple from the flow data and calculates long-term and short-term trends based at least in part on the tuple. The long-term and short-term trends are compared to determine whether a potential network anomaly exists. If a potential network anomaly does exist, the method initiates a heavy hitter detection algorithm. The method forms a low-complexity intermediate stage of processing that enables a high-complexity heavy hitter detection algorithm to execute when heavy hitters are likely to be detected.

What is claimed is: 
     
         1 . A computer implemented method, comprising:
 receiving flow data for a network flow;   parsing the flow data into a plurality of time buckets;   extracting a plurality of tuples describing the flow data, the tuple comprising a time duration of the network flow and information identifying an amount of data transmitted during the flow;   calculating a first trend based at least in part on at least a first tuple and a first time bucket of the plurality of time buckets;   calculating a second trend based at least in part on a second tuple and a more recent time bucket of the plurality of time buckets;   determining that the second trend diverges from the first trend to detect a potential network anomaly; and   when the potential network anomaly is detected, initiating a heavy hitter detection algorithm.   
     
     
         2 . The method of  claim 1 , further comprising assigning one or more tuples of the plurality of tuples to a time bucket. 
     
     
         3 . The method of  claim 2 , wherein calculating the first trend comprises forming a long-term bucket comprising tuples assigned to at least one of two or more buckets including the first time bucket. 
     
     
         4 . The method of  claim 3 , wherein calculating the first trend further comprises normalizing the first tuple relative to other tuples in the long-term bucket. 
     
     
         5 . The method of  claim 1 , wherein calculating the first trend comprises assigning the first tuple to a long-term cluster of a plurality of long-term clusters. 
     
     
         6 . The method of  claim 5 , wherein calculating the second trend comprises assigning the second tuple to a short-term cluster of a plurality of short-term clusters. 
     
     
         7 . A system, comprising:
 a memory; and   at least one processor coupled to the memory and configured to:
 receive flow data for a network flow; 
 parse the flow data into a plurality of time buckets; 
 extract a plurality of tuples describing the flow data, wherein a tuple comprises a time duration of the network flow and information identifying an amount of data transmitted during the flow; 
 calculate a first trend based at least in part on at least a first tuple and a first time bucket of the plurality of time buckets; 
 calculate a second trend based at least in part on a second tuple and a most recent time bucket of the plurality of time buckets; 
 determining that the second trend diverges from the first trend to detect a potential network anomaly; and 
 when the potential network anomaly is detected, initiate a heavy hitter detection algorithm. 
   
     
     
         8 . The system of  claim 7 , wherein the at least one processor is further configured to assign one of more tuples of the plurality of tuples to a time bucket. 
     
     
         9 . The system of  claim 8 , wherein the at least one processor is configured to calculate the first trend by forming a long-term bucket comprising tuples assigned to at least one of two or more buckets including the first time bucket. 
     
     
         10 . The system of  claim 9 , wherein the at least one processor is further configured to calculate the first trend by normalizing the first tuple relative to other tuples in the long-term bucket. 
     
     
         11 . The system of  claim 7 , wherein the at least one processor is configured to calculate the first trend by assigning the first tuple to a long-term cluster of a plurality of long-term clusters. 
     
     
         12 . The method of  claim 11 , wherein the at least one processor is configured to calculate the second trend by assigning the second tuple to a short-term cluster of a plurality of short-term clusters. 
     
     
         13 . A non-transitory computer-readable medium having instructions stored thereon that, when executed by at least one computing device, causes the at least one computing device to perform operations comprising:
 receiving flow data for a network flow;   parsing the flow data into a plurality of time buckets;   extracting a plurality of tuples describing the flow data, wherein a tuple comprises a time duration of the network flow and information identifying an amount of data transmitted during the flow;   calculating a first trend based at least in part on at least a first tuple and a first time bucket of the plurality of time buckets;   calculating a second trend based at least in part on a second tuple and a more recent time bucket of the plurality of time buckets;   determining that the second trend diverges from the first trend to detect a potential network anomaly; and   when the potential network anomaly is detected, initiating a heavy hitter detection algorithm.   
     
     
         14 . The non-transitory computer-readable medium of  claim 13 , the instructions further comprising assigning on or more tuples of the plurality of tuples to a time bucket. 
     
     
         15 . The non-transitory computer-readable medium of  claim 14 , wherein calculating the first trend comprises forming a long-term bucket comprising tuples assigned to at least one of two or more buckets including the first time bucket. 
     
     
         16 . The non-transitory computer-readable medium of  claim 15 , wherein calculating the first trend further comprises normalizing the first tuple relative to other tuples in the long-term bucket. 
     
     
         17 . The non-transitory computer-readable medium of  claim 13 , wherein calculating the first trend comprises assigning the first tuple to a long-term cluster of a plurality of long-term clusters.