×

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
First Claim
Patent Images

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.

View all claims
  • 3 Assignments
Timeline View
Assignment View
    ×
    ×