Methods and apparatus for detection of hierarchical heavy hitters

• US 8,218,451 B2
• Filed: 02/01/2011
• Issued: 07/10/2012
• Est. Priority Date: 01/23/2004
• Status: Expired due to Fees

• Current Assignee: AT&T Intellectual Property I LP (AT&T, Inc.)
• Original Assignee: AT&T Intellectual Property I LP (AT&T, Inc.)
• Inventors: Duffield, Nicholas, Lund, Carsten, Sen, Subhabrata, Zhang, Yin, Singh, Sumeet
• Primary Examiner(s): Vy, Hung T
• Application Number:
  US13/019,240
• Publication Number:
  US 20110122792A1
• Time in Patent Office: 525 Days
• Field of Search: 370/352, 370/395.3, 370/338, 370/310, 370/227, 370/252, 370/408, 370/241, 714/57, 707/790, 707/793, 209/231
• 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 a hierarchical heavy hitter from a stream of packets, comprising:

receiving a packet from the stream of packets;

associating a key with a field of the packet;

applying an adaptive trie data structure, where each node of the adaptive trie data structure is associated with the key; and

using via a processor the adaptive trie data structure to determine the hierarchical heavy hitter, wherein the hierarchical heavy hitter comprises a hierarchical aggregate of entities that account for a threshold portion of a total activity in the stream of packets.

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

3. The method of claim 2, wherein the packet network is a voice over internet protocol network.

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

updating the adaptive trie data structure for each received packet.

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

updating a volume of a node in the adaptive trie data structure.

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

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

7. The method of claim 1, further comprising:

applying the hierarchical heavy hitter to perform a change detection.

8. A non-transitory 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 a method for detecting a hierarchical heavy hitter from a stream of packets, comprising:

receiving a packet from the stream of packets;

associating a key with a field of the packet;

applying an adaptive trie data structure, where each node of the adaptive trie data structure is associated with the key; and

using the adaptive trie data structure to determine the hierarchical heavy hitter, wherein the hierarchical heavy hitter comprises a hierarchical aggregate of entities that account for a threshold portion of a total activity in the stream of packets.

9. The non-transitory computer-readable medium of claim 8, wherein the stream of packets is received from a packet network.

10. The non-transitory computer-readable medium of claim 9, wherein the packet network is a voice over internet protocol network.

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

updating the adaptive trie data structure for each received packet.

12. The non-transitory computer-readable medium of claim 11, wherein the updating comprises:

updating a volume of a node in the adaptive trie data structure.

13. The non-transitory computer-readable medium of claim 11, wherein the updating comprises:

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

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

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

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

a processor; and

a computer-readable medium in communication with the processor, the computer-readable medium having stored thereon a plurality of instructions, the plurality of instructions including instructions which, when executed by the processor, cause the processor to perform a method comprising;

receiving at least one packet from the stream of packets;

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

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

using the adaptive trie data structure to determine the at least one hierarchical heavy hitter, wherein the hierarchical heavy hitter comprises a hierarchical aggregate of entities that account for a threshold portion of a total activity in the stream of packets.

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

17. The apparatus of claim 16, wherein the packet network is a voice over internet protocol network.

18. The apparatus of claim 15, wherein the applying comprises updating the adaptive trie data structure for each received packet.

19. The apparatus of claim 18, wherein the updating comprises:

updating a volume of a node in the adaptive trie data structure.

20. The apparatus of claim 18, wherein the updating comprises:

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