Method and apparatus for fast and scalable matching of structured data streams

A computer-readable storage medium storing instructions that when executed by a computer cause the computer to perform a method for classifying elements in a structured data stream, the method comprising:

• receiving an element from the structured data stream;
• applying a hash function to the element to generate a single hash value for the element;
• dividing the single hash value into multiple sections, wherein each section comprises a fixed length of bits;
• using the multiple sections as inputs to a Bloom filter to determine if a node for the element exists in a lookup structure;
• and
• upon determining that the node exists in the lookup structure, looking up the node for the element in the lookup structure;
• whereby initially using the Bloom filter prevents unnecessary lookups in the lookup structure;
• and
• whereby using multiple sections of a single hash value as inputs to the Bloom filter eliminates the need to compute multiple hash values.

An apparatus that classifies elements in a structured data stream, comprising:

• a flow enforcement device configured to receive an element from the structured data stream;
• a flow manager coupled to the flow input device configured to:
• apply a hash function to the element to generate a single hash value for the element;
• divide the single hash value into multiple sections, wherein each section comprises a fixed length of bits;
• and
• use the multiple sections as inputs to a Bloom filter to determine if the element exists in a lookup structure;
• wherein upon determining that a node for the element exists in the lookup structure, the flow manager is configured to look up the node for the element in the lookup structure.