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

• US 20040213235A1
• Filed: 04/08/2003
• Published: 10/28/2004
• 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: Levenson, Herman, Marshall, John W., Schroter, Russell E.
• Granted Patent: US 8,040,886 B2
• Time in Patent Office: Days
• 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;

generating a final rule at an intermediate classification stage of the engine using the first rule and first criterion; and

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

2. A 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. A 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. A method as defined in claim 1 wherein the first criterion includes a packet field value that represents a field within the packet.

5. A 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 content-addressable memory (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. A 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. A 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. A 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. A 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. A method as defined in claim 7 comprising the step of:

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

11. A 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. A 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. A 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. 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;

an intermediate classification stage coupled to the initial classification stage and configured to generate a final rule using the first rule and the first criterion; and

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

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

16. A system as defined in claim 15 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.

17. A system as defined in claim 14 wherein the first criterion includes a packet field value that represents a field within the packet.

18. A system as defined in claim 17 comprising:

a packet field content-addressable memory (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.

19. A 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.

20. 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;

means for generating a final rule at an intermediate classification stage of the classification engine using the first rule and first criterion; and

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

21. A computer readable medium comprising computer executable instructions for execution in a processor for:

generating a first rule and a first criterion using information associated with a packet at an initial classification stage;

generating a final rule at an intermediate classification stage using the first rule and first criterion; and

generating an identifier associated with the packet at a final classification stage using the final rule.