Logarithmic time range-based multifield-correlation packet classification

• US 7,684,400 B2
• Filed: 08/08/2002
• Issued: 03/23/2010
• Est. Priority Date: 08/08/2002
• Status: Active Grant

• Current Assignee: Tahoe Research Limited (f/k/a Learndale Limited) (Vector Capital Corporation)
• Original Assignee: Intel Corporation
• Inventors: Govindarajan, Priya, Chiu, Chun Yang, Durham, David M.
• Primary Examiner(s): Pham; Chi H
• Assistant Examiner(s): Wong; Warner
• Application Number:
  US10/216,051
• Publication Number:
  US 20040028046A1
• Time in Patent Office: 2,784 Days
• Field of Search: 370/89, 370/392
• US Class Current: 370/392
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/20 Traffic policing
• CPC Class Codes: H04L 47/2441 relying on flow classification, e.g. using integrated services [IntServ]
• CPC Class Codes: H04L 69/22 Parsing or analysis of headers

Abstract

Classification of network data packets includes a determination sets of one or more filter-identifiers where each set is associated with a respective data-packet classifier field. A result-set of filter-identifiers may be derived based on an intersection of the filter-identifier sets.

Claims

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.