METHODS AND APPARATUS FOR DETECTION OF HIERARCHICAL HEAVY HITTERS

• US 20090016234A1
• Filed: 09/23/2008
• Published: 01/15/2009
• 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
• Granted Patent: US 7,898,976 B2
• Time in Patent Office: Days
• US Class Current: 370/252
• 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.

2. The method of claim 1, wherein said stream of packets are received from a packet network.

3. The method of claim 2, wherein said packet network is a Voice over Internet Protocol (VoIP) network.

4. The method of claim 1, wherein said applying said adaptive trie data structure comprises:

updating said adaptive trie data structure for each received packet.

5. The method of claim 4, wherein said updating comprises:

updating a volume of at least one node in said adaptive trie data structure.

6. The method of claim 4, wherein said updating comprises:

determining whether an additional node is to be added into said adaptive trie data structure in accordance with a threshold.

7. The method of claim 1, further comprising:

applying said at least one detected hierarchical heavy hitter to perform change detection.

8. 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.

9. The computer-readable medium of claim 8, wherein said stream of packets are received from a packet network.

10. The computer-readable medium of claim 9, wherein said packet network is a Voice over Internet Protocol (VoIP) network.

11. The computer-readable medium of claim 8, wherein said applying said adaptive trie data structure comprises:

updating said adaptive trie data structure for each received packet.

12. The computer-readable medium of claim 11, wherein said updating comprises:

updating a volume of at least one node in said adaptive trie data structure.

13. The computer-readable medium of claim 11, wherein said updating comprises:

determining whether an additional node is to be added into said adaptive trie data structure in accordance with a threshold.

14. The computer-readable medium of claim 8, further comprising:

applying said at least one detected hierarchical heavy hitter to perform change detection.

15. An apparatus for detecting at least one hierarchical heavy hitter from a stream of packets, comprising:

means for receiving at least one packet from said stream of packets;

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

means for 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

means for using said adaptive trie data structure to determine said at least one hierarchical heavy hitter.

16. The apparatus of claim 15, wherein said stream of packets are received from a packet network.

17. The apparatus of claim 16, wherein said packet network is a Voice over Internet Protocol (VoIP) network.

18. The apparatus of claim 15, wherein said means for applying said adaptive trie data structure comprises:

means for updating said adaptive trie data structure for each received packet.

19. The apparatus of claim 15, wherein said means for using said adaptive trie data structure to determine said at least one hierarchical heavy hitter comprises:

means for reconstruction volume for each of said at least one node this is an internal node;

means for estimating missed traffic for each of said internal node;

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

20. The apparatus of claim 19, wherein said means for estimating missed traffic comprises using at least one of:

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