Methods and apparatus for detection of hierarchical heavy hitters
First Claim
Patent Images
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 using the adaptive trie data structure to determine the hierarchical heavy hitter comprises;
reconstructing a volume for each node that is an internal node;
estimating missed traffic for each of the internal node; and
determining the hierarchical heavy hitter in accordance with a combination of the volume that is reconstructed and the missed traffic that is estimated.
2 Assignments
0 Petitions
Accused Products
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.
14 Citations
20 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 using the adaptive trie data structure to determine the hierarchical heavy hitter comprises; reconstructing a volume for each node that is an internal node; estimating missed traffic for each of the internal node; and determining the hierarchical heavy hitter in accordance with a combination of the volume that is reconstructed and the missed traffic that is estimated. - View Dependent Claims (2, 3, 4, 5, 6, 7)
-
-
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 using the adaptive trie data structure to determine the hierarchical heavy hitter comprises; reconstructing a volume for each node that is an internal node; estimating missed traffic for each of the internal node; and determining the hierarchical heavy hitter in accordance with a combination of the volume that is reconstructed and the missed traffic that is estimated. - View Dependent Claims (9, 10, 11, 12, 13, 14)
-
-
15. An apparatus comprising a processor for detecting a hierarchical heavy hitter from a stream of packets, comprising:
the processor configured to; receive a packet from the stream of packets; associate a key with a field of the packet; apply an adaptive trie data structure, where each node of the adaptive trie data structure is associated with the key; and use the adaptive trie data structure to determine the hierarchical heavy hitter, wherein the processor is configured to; reconstruct a volume for each node that is an internal node; estimate missed traffic for each of the internal node; and determine the hierarchical heavy hitter in accordance with a combination of the volume that is reconstructed and the missed traffic that is estimated. - View Dependent Claims (16, 17, 18, 19, 20)
Specification