METHODS AND APPARATUS FOR SPACE EFFICIENT ADAPTIVE DETECTION OF MULTIDIMENSIONAL HIERARCHICAL HEAVY HITTERS

• US 20090073891A1
• Filed: 08/25/2008
• Published: 03/19/2009
• Est. Priority Date: 01/23/2004
• Status: Abandoned Application

• Current Assignee: AT&T Intellectual Property II LP (AT&T, Inc.)
• Original Assignee: AT&T Intellectual Property II LP (AT&T, Inc.)
• Inventors: Zhang, Yin, Duffield, Nicholas, Sen, Subhabrata, Lund, Carsten
• Application Number:
  US12/197,424
• Publication Number:
  US 20090073891A1
• Time in Patent Office: Days
• US Class Current: 370/252
• CPC Class Codes: H04L 43/022 by sampling
• CPC Class Codes: H04L 43/024 by adaptive sampling
• CPC Class Codes: H04L 63/1408 by monitoring network traffic monitoring network traffic per se H04L43/00

Abstract

The present invention develops an efficient streaming method for detecting multidimensional hierarchical heavy hitters from massive data streams and 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 two keys with at least two fields of said at least one packet;

applying an adaptive trie data structure, where each node of said adaptive trie data structure is associated with said at least two keys; 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 two keys with at least two fields of said at least one packet;

applying an adaptive trie data structure, where each node of said adaptive trie data structure is associated with said at least two keys; 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-switch network.

10. The computer-readable medium of claim 9, wherein said packet-switch 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 two keys with at least two fields 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 said at least two keys; 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 15, wherein said means for applying said adaptive trie data structure comprises:

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

18. The apparatus of claim 17, wherein said means for updating comprises:

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

19. The apparatus of claim 17, wherein said means for updating comprises:

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

20. The apparatus of claim 15, further comprising:

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