Programmable packet filtering in a prioritized chain

• US 7,133,409 B1
• Filed: 07/19/2001
• Issued: 11/07/2006
• Est. Priority Date: 07/19/2001
• Status: Active Grant

• Current Assignee: Xylon LLC (Intellectual Ventures LLC)
• Original Assignee: Null Networks LLC (Intellectual Ventures LLC)
• Inventors: Willardson, Richard
• Primary Examiner(s): Patel, Ajit
• Application Number:
  US09/910,116
• Time in Patent Office: 1,937 Days
• Field of Search: 370/355, 370/465, 370/466, 370/432, 370/351, 370/352, 370/401, 370/402, 370/403, 370/411, 370/412, 370/428, 370/389, 370/392, 711/108, 712/300, 707/6
• US Class Current: 370/401
• CPC Class Codes: H04L 45/742 Route cache; Operation thereof
• CPC Class Codes: H04L 69/22 Parsing or analysis of headers
• CPC Class Codes: Y10S 707/99936 Pattern matching access

Abstract

An apparatus is equipped with classifier logic to programmably extract key data from a data packet of a data stream based upon a dynamically programmable offset, compare the key data with one or more lookup tables of key entries, and store the result of the comparison as at least part of a categorization vector. The apparatus is further equipped with filter logic coupled to the classifier logic to receive the categorization vector and to programmably determine group membership of the data packet based at least in part upon the categorization vector, as well as to dynamically determine a disposition for the data packet based at least in part upon the group membership.

Claims

1. An apparatus comprising:

classifier logic to programmably extract key data from a data packet of a data stream based at least in part upon a dynamically programmable offset, compare said key data with one or more lookup tables of key entries, and store the result of said comparison as at least part of a categorization vector; and

filter logic coupled to the classifier logic to receive said categorization vector and to programmably determine group membership of said data packet based at least in part upon said categorization vector, and to dynamically determine a disposition for said data packet based at least in part upon said group membership.

2. The apparatus of claim 1, wherein at least one of said one or more key entries is unique.

3. The apparatus of claim 1, wherein said filter logic comprises cascaded logic representing N priority encoded filters and a default filter to determine said group membership.

4. The apparatus of claim 3, wherein said one or more lookup tables comprises N content addressable memories.

5. The apparatus of claim 3, wherein one or more of said priority encoded filters comprises function logic to specify at least one combinational operation to apply to the categorization vector, and action logic to dictate an action for said data packet based at least in part upon the outcome of said at least one combinational operation.

6. The apparatus of claim 5, wherein said function logic further comprises logic to store programmable value data, logic to store programmable mask data, and logic to perform one or more comparisons between said categorization vector and at least one of said programmable value data and said programmable mask data.

7. The apparatus of claim 5, wherein one or more of said priority encoded filters further comprises polarity logic to determine whether said action is to be dictated based at least in part upon the outcome of said one or more comparisons resulting in a match condition, or whether said action is specified based at least in part upon the outcome of said one or more comparisons resulting in a miss condition.

8. The apparatus of claim 5, wherein said combinational operation comprises a masked-AND operation.

9. The apparatus of claim 5, wherein said combinational operation comprises a masked-GOR operation.

10. The apparatus of claim 5, wherein said default filter comprises default action logic for determining the disposition of said data packet if said action logic of said priority encoded filters does not dictate an action.

11. The apparatus of claim 10, wherein said plurality of filter actions include a packet drop action, a packet divert action, and a packet pass action.

12. The apparatus of claim 11, wherein if said drop action is specified, said data packet is dropped from said data stream.

13. The apparatus of claim 11, wherein if said divert action is specified, said data packet is diverted from said data stream to a host processor for processing.

14. The apparatus of claim 11, wherein if said pass action is specified, said data packet is passed through said priority encoded filter as part of an output data stream.

15. The apparatus of claim 1, wherein said filter logic is adapted to determine a priority for said packet based at least in part upon said categorization vector.

16. A method comprising:

extracting key data from a data packet of a data stream based at least in part upon a dynamically programmable offset,

comparing said key data with one or more lookup tables of key entries, and storing the result of said comparison as at least part of a categorization vector;

determining group membership of said data packet based at least in part upon said categorization vector, and

dynamically determining a disposition for said data packet based at least in part upon said group membership.

17. The method of claim 16, wherein at least one of said one or more key entries is unique.

18. The method of claim 16, wherein said determining said group membership of said data packet further comprises performing one or more comparisons of said categorization vector against one or more dynamically programmable Boolean values.

19. The method of claim 18, wherein said performing one or more comparisons comprises performing one or more Boolean operations.

20. The method of claim 19, wherein said Boolean operations comprise at least one of a masked-AND and/or a masked-GOR operation.

21. The method of claim 18, wherein said disposition comprises at least one of a packet drop action, a packet divert action, and/or a packet pass action.

22. The method of claim 21, further comprising determining whether said disposition is to be performed based upon the outcome of said one or more comparisons resulting in a match condition, or whether said disposition is to be performed based upon the outcome of said one or more comparisons resulting in a miss condition.

23. The method of claim 16, further comprising:

determining a priority of said data packet based at least in part upon said categorization vector.

27. The method of claim 22, wherein said categorization vector further identifies a priority membership of said data packet relative to one or more additional packets.

24. A method comprising:

receiving a multi-bit categorization vector representation of a data packet, said categorization vector identifying membership of said data packet in one or more classes of data and one or more subclasses of data;

performing one or more combinatorial operations on said categorization vector to determine whether said data packet satisfies one or more established membership criteria; and

disposing of said data packet based at least in part upon whether said data packet satisfies said established membership criteria.

25. The method of claim 24, wherein said data packet may be disposed at least through a packet drop action, a packet divert action, and a packet pass action.

26. The method of claim 24, wherein determining whether said data packet satisfies one or more established membership criteria comprises performing one or more comparisons of said categorization vector against one or more dynamically programmable Boolean values.