Algorithmic TCAM based ternary lookup

A method for performing a service operation on a data message received by a network element comprising ternary content addressable memory (TCAM) and random access memory (RAM), the method comprising:

• at the network element:
• receiving a data message comprising a set of header values;
• using the set of header values to perform a lookup operation on a key table stored in the TCAM to identify a plurality of service rules stored in the RAM, each service rule storing (i) a data tuple to compare with the header value set and (ii) an action parameter for performing a service action on the data message;
• comparing the data tuples of the identified plurality of service rules retrieved from the RAM in parallel with the header value set of the data message to determine any of the data tuples that match the header value set;
• and
• in response to determining that multiple data tuples match the data message's header value set, using the action parameter of the matching record with a highest priority in order to perform the service operation on the data message.

A network switch for performing a ternary lookup, the network switch comprising:

• a random access memory (RAM) configured to store a plurality of records;
• a ternary content addressable memory (TCAM) configured to store a key table;
• for a data message received by the network switch, perform a lookup operation on the key table stored in the TCAM to identify a plurality of records stored in the RAM, each record to store (i) a first data tuple to compare with a header value set of the data message and (ii) a second data tuple to use to effectuate a forwarding decision to forward the data message;
• wherein the first data tuples of the identified plurality of records retrieved from the RAM are compared in parallel with the header value set of the data message to determine any of the first data tuples that match the header value set, and in response to determining that multiple first data tuples match the data message's header value set, the second data tuple of the matching record with a highest priority is used to effectuate a forwarding operation for the data message.