Programmable packet classification system using an array of uniform content-addressable memories

• US 8,040,886 B2
• Filed: 04/08/2003
• Issued: 10/18/2011
• Est. Priority Date: 04/08/2003
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Schroter, Russell E., Levenson, Herman, Marshall, John W.
• Primary Examiner(s): Ton; Dang
• Assistant Examiner(s): O CONNOR, BRIAN T
• Application Number:
  US10/408,987
• Publication Number:
  US 20040213235A1
• Time in Patent Office: 3,115 Days
• Field of Search: 370/392, 370/400, 370/389, 370/395.21, 370/394, 370/395.42
• US Class Current: 370/392
• CPC Class Codes: H04L 12/4641 Virtual LANs, VLANs, e.g. virtual private networks [VPN] LAN interconnection over a bridge based backbone H04L12/462; encapsulation techniques H04L12/4633; routing of packets H04L45/00; packet switches H04L49/00; virtual private networks for security H04L63/0272
• CPC Class Codes: H04L 45/10 Routing in connection-oriented networks, e.g. X.25 or ATM
• CPC Class Codes: H04L 45/7453 using hashing
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/2441 relying on flow classification, e.g. using integrated services [IntServ]

Abstract

A versatile and efficient technique for classifying packets in an intermediate node. According to the technique, criteria and rules associated with the packet are applied to one or more classification stages containing content-addressable memories (CAMs). Each stage examines specific criteria associated with the packet, e.g., a packet field, and generates a rule and additional criteria. The additional rule and criteria are provided to the next classification stage. This process continues until a final rule is provided to a final classification stage. At the final classification stage, the final rule is used to generate an identifier, e.g., queue identifier (ID), associated with the classified packet.

Claims

1. A method for classifying packets in an intermediate node, the method comprising the steps of:

generating a first rule and first criterion using information associated with a packet at an initial classification stage of a classification engine in the node, wherein the first rule includes an indication of a first criteria used to determine if the first rule is satisfied, and wherein the first criterion includes a first value derived from the information associated with the packet and that is to be compared to the first criteria;

applying the first rule and first criterion to a first intermediate classification stage of the engine that includes one or more content addressable storage memories (CAMs) to generate a second rule and a second criterion, wherein the second rule includes an indication of a second criteria used to determine if the second rule is satisfied, and wherein the second criterion includes a second value to be compared to the second criteria;

generating a final rule using one or more additional intermediate classification stages of the engine using the second rule and the second criterion, wherein the final rule includes an indication of a third criteria used to determine if the final rule is satisfied;

generating an identifier associated with the packet at a final classification stage of the engine using the final rule; and

using the identifier to classify the packet.

2. The method as defined in claim 1 wherein the information associated with the packet includes a destination port identifier (ID) and virtual local area network (VLAN) ID.

3. The method as defined in claim 2 further comprising the steps of:

selecting an entry in a port/channel table using the destination port ID;

selecting an entry in a VLAN table using the VLAN ID;

merging a rule contained in the selected port/channel table entry with a rule contained in the selected VLAN table entry to generate the first rule; and

merging a criterion contained in the selected port/channel table entry with a criterion contained in the selected VLAN table entry to generate the first criterion.

4. The method as defined in claim 1 wherein the first criterion includes a packet field value that represents a field within the packet.

5. The method as defined in claim 4 comprising the steps of:

examining the contents of the field represented by the packet field value within the packet;

generating a CAM value using the contents of the field and the packet field value; and

locating a matching packet field CAM entry by applying the generated value to a packet field CAM.

6. The method as defined in claim 5 comprising the step of:

locating a matching rule CAM entry by applying the first rule to a rule CAM.

7. The method as defined in claim 6 comprising the steps of:

generating a packet field CAM output;

generating a rule CAM output; and

generating a CAM table index by combining the packet field CAM output with the rule CAM output; and

selecting a CAM table entry using the CAM table index.

8. The method as defined in claim 7 comprising the step of:

applying a rule contained in the selected CAM table entry to a second rule CAM.

9. The method as defined in claim 7 comprising the step of:

applying a packet field value contained in the selected CAM table entry to a second packet field CAM.

10. The method as defined in claim 7 comprising the step of:

generating the final rule from a rule contained in the selected CAM table.

11. The method as defined in claim 1 comprising the steps of:

generating one or more classification rule satisfied values;

generating one or more classification rule priority values; and

providing the generated classification rule satisfied values and classification rule priority values to the final classification stage.

12. The method as defined in claim 11 comprising the steps of:

generating a final state table index by combining the classification rule satisfied values, classification rule priority values, and final rule; and

selecting a final state table entry associated with the packet using the final state table index.

13. The method as defined in claim 12 comprising the steps of:

generating the identifier using a queue ID contained in the selected final state table entry.

14. The method as defined in claim 1 wherein the step of applying further comprises:

applying the first rule and first criterion to the one or more CAMs to generate the second rule and the second criterion.

15. A classification engine system comprising:

an initial classification stage configured to generate a first rule and a first criterion using information associated with a packet, wherein the first rule includes an indication of a first criteria used to determine if the first rule is satisfied, and wherein the first criterion includes a first value derived from the information associated with the packet and that is to be compared to the first criteria;

a first intermediate classification stage that includes one or more content addressable storage memories (CAMs), coupled to the initial classification stage and configured to generate a second rule and a second criterion using the first rule and the first criterion, wherein the second rule includes an indication of a second criteria used to determine if the second rule is satisfied, and wherein the second criterion includes a second value to be compared to the second criteria;

one or more additional intermediate classification stages that include one or more CAMs, configured to receive the second rule and the second criterion and to generate a final rule, wherein the final rule includes an indication of a third criteria used to determine if the final rule is satisfied; and

a final classification stage coupled to the intermediate classification stages and configured to generate an identifier associated with the packet using the final rule.

16. The system as defined in claim 15 wherein the information associated with the packet includes a destination port identifier (ID) and virtual local area network (VLAN) ID.

17. The system as defined in claim 16 comprising:

a port/channel table containing one or more entries wherein each entry contains a rule and a criterion;

a VLAN table containing one or more entries wherein each entry contains a rule and a criterion; and

merge logic coupled to the port/channel table and the VLAN table and configured to merge the rule and the criterion contained in a selected port/channel table entry with the rule and the criterion contained in a selected VLAN table entry, respectively, to generate a first rule and first criterion.

18. The system as defined in claim 15 wherein the first criterion includes a packet field value that represents a field within the packet.

19. The system as defined in claim 18 comprising:

a packet field CAM containing one or more packet field CAM entries; and

a protocol detector coupled to the packet field CAM and configured to examine the contents of the field represented by the packet field value and using the contents, generate a packet field CAM value;

wherein the packet field CAM value is applied to the packet field CAM to locate one or more matching packet field CAM entries.

20. The system as defined in claim 18 comprising:

a rule CAM containing one or more rule CAM entries;

wherein the first rule is applied to the rule CAM to locate a matching rule CAM entry.

21. The system as defined in claim 15 wherein the intermediate classification stage is further configured to apply the first rule and first criterion to the one or more CAMs of the first intermediate classification stage to generate the second rule and the second criterion.

22. An apparatus comprising:

a classification engine;

means for generating a first rule and first criterion using information associated with a packet at an initial classification stage of the classification engine, wherein the first rule includes an indication of a first criteria used to determine if the first rule is satisfied, and wherein the first criterion includes a first value derived from the information associated with the packet and that is to be compared to the first criteria;

means for applying the first rule and first criterion to a first intermediate classification stage of the classification engine that includes one or more content addressable storage memories (CAMs), to generate a second rule and a second criterion, wherein the second rule includes an indication of a second criteria used to determine if the second rule is satisfied, and wherein the second criterion includes a second value to be compared to the second criteria;

means for generating a final rule using one or more additional intermediate classification stages of the classification engine using the second rule and the second criterion, wherein the final rule includes an indication of a third criteria used to determine if the final rule is satisfied; and

means for generating an identifier associated with the packet at a final stage of the classification engine using the final rule.

23. A non-transitory computer readable medium comprising computer executable instructions for execution in a processor for:

generating a first rule and first criterion using information associated with a packet at an initial classification stage of a classification engine in a node, wherein the first rule includes an indication of a first criteria used to determine if the first rule is satisfied, and wherein the first criterion includes a first value derived from the information associated with the packet and that is to be compared to the first criteria;

applying the first rule and first criterion to a first intermediate classification stage of the classification engine that includes one or more content addressable storage memories (CAMs), to generate a second rule and a second criterion, wherein the second rule includes an indication of a second criteria used to determine if the second rule is satisfied, and wherein the second criterion includes a second value to be compared to the second criteria;

generating a final rule using one or more additional intermediate classification stages of the classification engine using the second rule and the second criterion, wherein the final rule includes an indication of a third criteria used to determine if the final rule is satisfied;

generating an identifier associated with the packet at a final classification stage of the classification engine using the final rule; and

using the identifier to classify the packet.

24. An apparatus comprising:

an initial classification stage of a classification engine configured to generate a first rule and a first criterion using information associated with a packet, the first rule indicating a first criteria used to determine if the first rule is satisfied, the first criterion indicating a field of the packet;

two or more content-addressable memory (CAM) stages of the classification engine, a first CAM stage of the two or more CAM stages configured to receive the first rule and the first criterion, and to apply the first rule to contents of the field of the packet indicated by the first criterion to generate a second rule and a second criterion, the second rule indicating a second criteria used to determine if the second rule is satisfied, the second criterion indicating another field of the packet, a second CAM stage of the two or more CAM stages configured to receive the second rule and the second criterion, and to apply the second rule to contents of the field of the packet indicated by the second criterion; and

a final classification stage of the classification engine coupled to the two or more CAM stages, the final classification stage configured to receive a final rule from one of the two or more CAM stages, the final rule indicating a final criteria used to determine if the final rule is satisfied, the final classification stage to use the final rule to generate a queue identifier (ID) for use with the packet.

25. The apparatus as defined in claim 24 wherein the information associated with the packet includes a destination port identifier (ID) and virtual local area network (VLAN) ID.

26. The apparatus as defined in claim 25 wherein the initial classification stage comprises:

a port/channel table containing one or more entries wherein each entry contains a rule and a criterion;

a VLAN table containing one or more entries wherein each entry contains a rule and a criterion; and

merge logic coupled to the port/channel table and the VLAN table and configured to merge the rule and the criterion contained in a selected port/channel table entry with the rule and the criterion contained in a selected VLAN table entry, respectively, to generate the first rule and the first criterion.

27. The apparatus as defined in claim 24 wherein the first CAM stage comprises:

a packet field CAM containing one or more packet field CAM entries;

a protocol detector coupled to the packet field CAM and configured to examine the contents of the field indicated by the first criterion and to use the contents to generate a packet field CAM value; and

wherein the packet field CAM value is applied to the packet field CAM to locate one or more matching packet field CAM entries.

28. The apparatus as defined in claim 27 wherein the first CAM stage further comprises:

a rule CAM containing one or more rule CAM entries;

wherein the first rule is applied to the rule CAM to locate a matching rule CAM entry.

29. A method comprising:

generating a first rule and a first criterion using information associated with a packet, the first rule indicating a first criteria used to determine if the first rule is satisfied, the first criterion indicating a field of the packet;

providing the first rule and the first criterion to a first content-addressable memory (CAM) stage of two or more CAM stages of a classification engine;

applying the first rule, by the first CAM stage, to contents of the field of the packet indicated by the first criterion;

generating a second rule and a second criterion at the first CAM stage, the second rule indicating a second criteria used to determine if the second rule is satisfied, the second criterion indicating another field of the packet;

providing the second rule and the second criterion to a second CAM stage of the two or more CAM stages of the classification engine;

applying the second rule, by the second CAM stage, to contents of the field of the packet indicated by the second criterion;

providing a final rule to a final classification stage of the classification engine, the final rule indicating a final criteria used to determine if the final rule is satisfied; and

using the final rule to generate a queue identifier (ID) for use with the packet.

30. The method as defined in claim 29 wherein the information associated with the packet includes a destination port identifier (ID) and virtual local area network (VLAN) ID.

31. The method as defined in claim 30 wherein generating a first rule comprises:

selecting an entry in a port/channel table using the destination port ID;

selecting an entry in a VLAN table using the VLAN ID;

merging a rule contained in the selected port/channel table entry with a rule contained in the selected VLAN table entry to generate the first rule; and

merging a criterion contained in the selected port/channel table entry with a criterion contained in the selected VLAN table entry to generate the first criterion.

32. The method as defined in claim 29 wherein applying the first rule comprises:

examining the contents of the field of the packet indicated by the first criterion;

generating a CAM value using the contents of the field; and

locating a matching packet field CAM entry by applying the generated value to a packet field CAM.

33. The method as defined in claim 32 wherein applying the first rule comprises:

locating a matching rule CAM entry by applying the first rule to a rule CAM.