Programmable packet classification system using an array of uniform content-addressable memories
First Claim
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.
1 Assignment
0 Petitions
Accused Products
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.
-
Citations
33 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14)
-
-
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. - View Dependent Claims (16, 17, 18, 19, 20, 21)
-
-
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. - View Dependent Claims (25, 26, 27, 28)
-
-
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. - View Dependent Claims (30, 31, 32, 33)
-
Specification