Methods and apparatus for detection of hierarchical heavy hitters

• US 7,437,385 B1
• Filed: 01/24/2005
• Issued: 10/14/2008
• Est. Priority Date: 01/23/2004
• Status: Active Grant

• Current Assignee: AT&T Intellectual Property I LP (AT&T, Inc.)
• Original Assignee: AT&T Corporation (AT&T, Inc.)
• Inventors: Singh, Sumeet, Zhang, Yin, Duffield, Nicholas, Sen, Subhabrata, Lund, Carsten
• Primary Examiner(s): Vy; Hung T
• Application Number:
  US11/042,771
• Time in Patent Office: 1,359 Days
• Field of Search: 370/352, 370/395.3, 370/338, 370/310, 370/227, 370/408, 714/57, 707/104, 707100-102, 726/22
• US Class Current: 1/1
• CPC Class Codes: H04L 2101/604 Address structures or formats
• CPC Class Codes: H04L 63/1425 Traffic logging, e.g. anomaly detection
• CPC Class Codes: H04L 63/1441 Countermeasures against malicious traffic countermeasures against attacks on cryptographic mechanisms H04L9/002
• CPC Class Codes: H04L 63/1458 Denial of Service

Abstract

An efficient streaming method and apparatus for detecting hierarchical heavy hitters from massive data streams is disclosed. In one embodiment, the method enables near real time detection of anomaly behavior in networks.

Claims

1. A method for detecting at least one hierarchical heavy hitter from a stream of packets, comprising:

receiving at least one packet from said stream of packets;

associating at least one key with at least one field of said at least one packet;

applying an adaptive trie data structure, where each node of said adaptive trie data structure is associated with one of said at least one key; and

using said adaptive trie data structure to determine said at least one hierarchical heavy hitter, wherein said using said adaptive trie data structure to determine said at least one hierarchical heavy hitter comprises;

reconstructing a volume for each node this is an internal node;

estimating missed traffic for each of said internal node; and

determining said at least one hierarchical heavy hitter in accordance with a combination of said reconstructed volume and said estimated missed traffic.

2. The method of claim 1, wherein said estimating missed traffic comprises using at least one of:

a copy-all method, a no-copy method, and or a splitting method.

3. A computer-readable medium having stored thereon a plurality of instructions, the plurality of instructions including instructions which, when executed by a processor, cause the processor to perform the steps of a method for detecting at least one hierarchical heavy hitter from a stream of packets, comprising:

receiving at least one packet from said stream of packets;

associating at least one key with at least one field of said at least one packet;

applying an adaptive trie data structure, where each node of said adaptive trie data structure is associated with one of said at least one key; and

using said adaptive trie data structure to determine said at least one hierarchical heavy hitter, wherein said using said adaptive trie data structure to determine said at least one hierarchical heavy hitter comprises;

reconstructing a volume for each node this is an internal node;

estimating missed traffic for each of said internal node; and

determining said at least one hierarchical heavy hitter in accordance with a combination of said reconstructed volume and said estimated missed traffic.

4. The computer-readable medium of claim 3, wherein said estimating missed traffic comprises using at least one of:

a copy-all method, a no-copy method, or a splitting method.