Logarithmic time range-based multifield-correlation packet classification

1. A method comprising:

generating a filter-identifier based, at least in part, on one or more filter elements associated with a data packet header field, wherein the filter-identifier is different from a policy-identifier that identifies a policy applicable to data packets having specified entries in the one or more filter elements;

characterizing the specified entries in the filter elements as either a range-based value or an exact value;

generating a bit mask from the characterizing, each bit in the bit mask corresponding to a filter element;

setting a bit in the bit mask to be a first logical value when its corresponding filter element has a range-based value;

setting a bit in the bit mask to be a second, different logical value when its corresponding filter element has an exact value;

determining respective sets of one or more filter-identifiers, each set associated with a respective filter element; and

producing a result-set of filter-identifiers based on an intersection of the filter-identifier sets.

2. The method of claim 1 further comprising: associating each filter-identifier with a policy-identifier.

3. The method of claim 1 wherein producing the result-set comprises: selecting a particular filter-identifier from one of the filter element sets as a search-identifier; searching the other filter element sets for a match of the search-identifier; and adding the search-identifier to a result set if the search-identifier is found in all of the other sets.

4. The method of claim 3 further comprising iteratively repeating the selecting, searching and adding with respect to at least one subsequent filter-identifier until a last filter-identifier in any set is reached.

5. The method of claim 4 further comprising: placing the filter-identifiers in a hierarchical order; and performing said searching from a filter-identifier with a highest value towards a filter-identifier with a lowest value in the hierarchy.

6. The method of claim 5 wherein selecting a particular filter-identifier comprises: selecting an initial filter-identifier from each filter element set, said initial filter-identifier having a highest value among the filter-identifiers in that filter element set; and selecting one of the initial filter-identifiers as the particular filter-identifier, said one of the initial filter-identifiers having a lowest value among the initial filter-identifiers.

7. The method of claim 6 wherein iteratively selecting a subsequent filter-identifier comprises: selecting a filter-identifier from each filter element set, said filter-identifier having a highest value among the filter-identifiers in that filter element set that is lower in value than the search-identifier value; and selecting one of the filter-identifiers as the iterative particular filter-identifier, said one of the iterative filter-identifiers having a lowest value among the iterative filter-identifiers.

8. A method comprising:

generating node values in a tree for each endpoint value associated with at least one policy-identifier;

associating a first set of policy-identifiers with a particular one of the node values, wherein the first set of policy-identifiers is applied to data-packets having packet-header classifier fields matching the particular one of the node values; and

associating a second set of policy-identifiers with the particular node value, wherein the second set of policy-identifiers is applied to data-packets having packet-header classifier fields with a value between the particular one of the node values and a next higher node value.

9. The method of claim 8 further comprising deriving the second set of policy-identifiers from an intersection set of the first set of policy-identifiers and a first set of policy-identifiers associated with the next higher node value.

10. An article of manufacture comprising a non-transitory machine-readable medium storing machine-executable instructions that when applied to a machine cause the machine to:

generate a filter-identifier based, at least in part, on one or more filter elements associated with a data packet header field, wherein the filter-identifier is different from a policy-identifier that identifies a policy applicable to data packets having specified entries in the one or more filter elements;

characterize the specified entries in the filter elements as either a range-based value or an exact value;

generate a bit mask from the characterizing, each bit in the bit mask corresponding to a filter element;

set a bit in the bit mask to be a first logical value when its corresponding filter element has a range-based value;

set a bit in the bit mask to be a second, different logical value when its corresponding filter element has an exact value;

determine respective sets of one or more filter-identifiers associated with respective filter elements; and

produce a result-set of filter-identifiers that is based on an intersection of the filter-identifier sets.

11. The article of claim 10 further comprising machine-executable instructions for causing the machine to associate each filter-identifier with a policy-identifier.

12. The article of claim 11 comprising the machine-executable instructions to cause the machine to: select a particular filter-identifier from one of the filter element sets as a search-identifier; search the other filter element sets for a match of the search-identifier; add the search-identifier to a result set if the search-identifier is found in all of the other sets; and iteratively repeat the selection, search and addition with respect to at least one subsequent filter-identifier until a last filter-identifier in any set is reached.

13. The article of claim 12 further comprising machine-executable instructions for causing the machine to: place the filter-identifiers in a hierarchical order; and search from a filter-identifier with a highest value towards a filter-identifier with a lowest value in the hierarchy.

14. The article of claim 13 wherein the machine-executable instructions to select a particular filter-identifier further comprise instructions to cause the machine to: select an initial filter-identifier from each filter element set, said initial filter-identifier having a highest value among the filter-identifiers in that filter element set; and select one of the initial filter-identifiers as the particular filter-identifier, said one of the initial filter-identifiers having a lowest value among the initial filter-identifiers.

15. The article of claim 14 further comprising the machine-executable instructions for causing the machine to: select a filter-identifier from each filter element set, said filter-identifier having a highest value among the filter-identifiers in that filter element set that is lower in value than the search-identifier value; and select one of the filter-identifiers as the iterative particular filter-identifier, said one of the iterative filter-identifiers having a lowest value among the iterative filter-identifiers.

16. An article of manufacture comprising a non-transitory machine-readable medium storing machine-executable instructions that when applied to a machine cause the machine to:

generate node values in a tree for each endpoint value associated with at least one policy-identifier;

associate a first set of policy-identifiers with a particular one of the node values, wherein the first set of policy-identifiers is applied to data-packets having packet-header classifier fields matching the particular one of the node values; and

associate a second set of policy-identifiers with the particular one of the node values, wherein the second set of policy-identifiers is applied to data-packets having packet-header classifier fields with a value between the particular one of the node values and a next higher node value.

17. The article of claim 16 further comprising instructions to produce the second set of policy-identifiers from an intersection set of the first set of policy-identifiers and a first set of policy-identifiers associated with the next higher node value.

18. An apparatus comprising:

a network interface adapter;

a first circuitry communicatively coupled to the network interface adapter to generate a filter-identifier based, at least in part, on one or more filter elements associated with a data packet header field, wherein the filter-identifier is different from a policy-identifier that identifies a policy applicable to data packets having specified entries in the one or more filter elements;

a second circuitry communicatively coupled to the network interface adapter to:

characterizing the specified entries in the filter elements as either a range-based value or an exact value;

generating a bit mask from the characterizing, each bit in the bit mask corresponding to a filter element;

setting a bit in the bit mask to be a first logical value when its corresponding filter element has a range-based value;

setting a bit in the bit mask to be a second, different logical value when its corresponding filter element has an exact value;

a third circuitry communicatively coupled to the network interface adapter to determine respective sets of one or more filter-identifiers associated with respective filter elements; and

a fourth circuitry communicatively coupled to the network interface adapter to produce a result-set of filter-identifiers that is based on an intersection of the filter-identifier sets.

19. The apparatus of claim 18 further comprising a fifth circuitry communicatively couple to the network interface adapter to associate each filter-identifier with a policy-identifier.

20. The apparatus of claim 19 further comprising a sixth circuitry communicatively coupled to the network interface adapter to: select a particular filter-identifier from one of the filter element sets as a search-identifier; search the other filter element sets for a match of the search-identifier; add the search-identifier to a result set if the search-identifier is found in all of the other sets; and iteratively repeat the selection, search and addition with respect to at least one subsequent filter-identifier until a last filter-identifier in any set is reached.

21. The apparatus of claim 20 further comprising a seventh circuitry communicatively coupled to the network interface adapter to: place the filter-identifiers in a hierarchical order; and search from a filter-identifier with a highest value towards a filter-identifier with a lowest value in the hierarchy.

22. The apparatus of claim 21 further comprising an eighth circuitry communicatively coupled to the network interface adapter to: select an initial filter-identifier from each filter element set, said initial filter-identifier having a highest value among the filter-identifiers in that filter element set; and select one of the initial filter-identifiers as the particular filter-identifier, said one of the initial filter-identifiers having a lowest value among the initial filter-identifiers.

23. The apparatus of claim 22 further comprising a ninth circuitry communicatively coupled to the network interface adapter to: select a filter-identifier from each filter element set, said filter-identifier having a highest value among the filter-identifiers in that filter element set that is lower in value than the search-identifier value; and select one of the filter-identifiers as the iterative particular filter-identifier, said one of the iterative filter-identifiers having a lowest value among the iterative filter-identifiers.

24. A system comprising: a network; and a network device communicatively coupled to the network, the device including a processor and instructions executable by the processor to cause the processor to:

generate a filter-identifier based, at least in part, on one or more filter elements associated with a data packet header field, wherein the filter-identifier is different from a policy-identifier that identifies a policy applicable to data packets having specified entries in the one or more filter elements;

characterize the specified entries in the filter elements as either a range-based value or an exact value;

generate a bit mask from the characterizing, each bit in the bit mask corresponding to a filter element;

set a bit in the bit mask to be a first logical value when its corresponding filter element has a range-based value;

set a bit in the bit mask to be a second, different logical value when its corresponding filter element has an exact value;

determine respective sets of one or more filter-identifiers associated with respective filter elements; and

produce a result-set of filter-identifiers that is based on an intersection of the filter-identifier sets.

25. The system of claim 24 further comprising instructions to cause the processor to associate each filter-identifier with a policy-identifier.

26. The system of claim 25 further comprising instructions to cause the processor to: select a particular filter-identifier from one of the filter element sets as a search-identifier; search the other filter element sets for a match of the search-identifier; add the search-identifier to a result set if the search-identifier is found in all of the other sets; and iteratively repeat the selection, search and addition with respect to at least one subsequent filter-identifier until a last filter-identifier in any set is reached.