Network device that utilizes TCAM configured to output multiple match indices
A network device provides a search key corresponding to a packet to a TCAM. The TCAM determines that the search key matches one or more search patterns stored in the TCAM. The network device selects one search pattern among the one or more search patterns at least by analyzing respective priority information associated with the one or more search patterns. The respective priority information indicates one or more respective priority levels that are independent from one or more physical locations of the one or more search patterns within the TCAM. In connection with selecting the one search pattern, the network device determines one or more actions to be performed on the packet by the network device, the one or more actions corresponding to the selected one search pattern.
1 . A network device, comprising:
a packet processor configured to process packets communicated over a network, the processing including generating respective search keys representative of at least some of the packets; and
a lookup engine coupled to the packet processor, the lookup engine comprising:
a ternary content addressable memory (TCAM) configured to store a plurality of search patterns, the TCAM further configured to, in response to determining that a first search key, amongst the search keys, corresponding to a first packet, amongst the at least some packets, matches one or more search patterns stored in the TCAM, generate one or more indices corresponding to the one or more search patterns that match the first search key;
a memory separate from the TCAM; and
a controller configured to:
retrieve from the memory separate from the TCAM respective priority information associated with the one or more search patterns that match the first search key, the respective priority information indicating one or more respective priority levels of the one or more search patterns that match the first search key,
select one search pattern, from among the one or more search patterns that match the first search key, at least by analyzing the respective priority information associated with the one or more matching search patterns that match the first search key, and
in connection with selecting the one search pattern, determine a processing rule that corresponds to the one search pattern and provide the processing rule to the packet processor to process the first packet according to the processing rule.
2 . The network device of claim 1 , wherein the one or more search patterns that match the first search key are a plurality of matching search patterns that match the first search key, and wherein the controller is configured to, when the TCAM generates a plurality of instances corresponding to the plurality of search patterns that match the first search key:
retrieve from the memory separate from the TCAM respective priority information associated with the plurality of search patterns that match the first search key; and
select the one search pattern, from among the plurality of search patterns that match the first search key, as a search pattern having a highest priority as indicated by the respective priority information retrieved from the memory separate from the TCAM.
3 . The network device of claim 1 , wherein the memory separate from the TCAM comprises a random access memory (RAM), and wherein the controller is configured to:
select the one search pattern at least by analyzing respective priority information retrieved from the RAM.
4 . The network device of claim 1 , wherein the memory separate from the TCAM comprises a first memory and a second memory, and wherein the controller is configured to:
select the one search pattern at least by analyzing respective priority information retrieved from the first memory; and
retrieve from the second memory the processing rule that corresponds to the one search pattern.
5 . The network device of claim 1 , wherein:
the memory separate from the TCAM comprises a plurality of entries corresponding to respective search patterns stored in the TCAM;
each of at least some of the entries includes i) priority information corresponding to a respective search pattern stored in the TCAM, and ii) rule information corresponding to the respective search pattern stored in the TCAM; and
the controller is configured to retrieve from the memory separate from the TCAM the processing rule that corresponds to the one search pattern.
6 . The network device of claim 1 , wherein:
the controller is configured to determine the processing rule that corresponds to the one search pattern from amongst a plurality of processing rules having forwarding information for forwarding packets that are received by the network device; and
the packet processor is configured to use the processing rule that corresponds to the one search pattern to determine a network interface, amongst a plurality of network interfaces of, or coupled to, the network device, to which the first packet is to be forwarded for transmission.
7 . The network device of claim 1 , wherein:
the controller is configured to determine the processing rule that corresponds to the one search pattern from amongst a plurality of processing rules having classification information for classifying packets that are received by the network device; and
the packet processor is configured to use the processing rule that corresponds to the one search pattern to classify the first packet.
8 . A method for determining actions to be performed on packets by a network device, the method comprising:
providing a search key corresponding to a first packet to a ternary content addressable memory (TCAM);
determining, by the TCAM, that the search key matches one or more search patterns amongst a plurality of search patterns stored in the TCAM;
retrieving respective priority information associated with the one or more search patterns from respective one or more entries in a memory separate from the TCAM, the respective priority information indicating one or more respective priority levels of the one or more search patterns that match the search key;
selecting, by the network device, one search pattern among the one or more search patterns at least by analyzing the respective priority information associated with the one or more search patterns; and
in connection with selecting the one search pattern, determining, by the network device, one or more actions to be performed on the first packet by the network device, the one or more actions corresponding to the one search pattern.
9 . The method for determining actions to be performed on packets of claim 8 , wherein when the TCAM determines that the search key matches a multiple of search patterns:
retrieving respective priority information comprises retrieving from the memory separate from the TCAM respective priority information associated with the multiple of search patterns; and
selecting the one search pattern comprises selecting a search pattern, from among the multiple of search patterns, having a highest priority as indicated by the respective priority information retrieved from the memory separate from the TCAM.
10 . The method for determining actions to be performed on packets of claim 8 , wherein:
the memory separate from the TCAM comprises i) a first memory that stores respective priority information corresponding to respective search patterns amongst the plurality of search patterns stored in the TCAM, and ii) a second memory that stores respective rule information corresponding to the plurality of search patterns stored in the TCAM, the respective rule information indicating respective one or more actions to be performed on packets corresponding to the plurality of search patterns;
retrieving respective priority information associated with the one or more search patterns from respective entries in the memory separate from the TCAM comprises retrieving the respective priority information from respective entries in the first memory; and
determining the one or more actions to be performed on the first packet by the network device comprises retrieving rule information from an entry in the second memory that corresponds to the one search pattern.
11 . The method for determining actions to be performed on packets of claim 8 , wherein:
determining the one or more actions to be performed on the first packet by the network device comprises retrieving rule information from an entry in the memory separate from the TCAM that corresponds to the selected one search pattern, wherein the entry further includes priority information corresponding to the selected one search pattern.
12 . The method for determining actions to be performed on packets of claim 8 , wherein:
determining the one or more actions to be performed on the first packet by the network device comprises retrieving rule information from amongst a plurality of processing rules having forwarding information for forwarding packets that are received by the network device; and
the method further comprises using, by the network device, a processing rule that corresponds to the one selected search pattern to determine a network interface, amongst a plurality of network interfaces of, or coupled to, the network device, to which the first packet is to be forwarded for transmission.
13 . The method for determining actions to be performed on packets of claim 8 , wherein:
determining the one or more actions to be performed on the first packet by the network device comprises retrieving rule information amongst a plurality of processing rules having classification information for classifying packets that are received by the network device; and
the method further comprises using, by the network device, a processing rule that corresponds to the one selected search pattern to classify the first packet.
14 . A network device, comprising:
a packet processor configured to process packets communicated over a network, the processing including generating a search key representative of a first packet; and
a lookup engine coupled to the packet processor, the lookup engine comprising:
a ternary content addressable memory (TCAM) configured to store a plurality of search patterns in respective entries among a plurality of entries of the TCAM, wherein the plurality of entries are organized in a plurality of groups of multiple entries, wherein the TCAM is further configured to, in response to determining that the search key matches one or more search patterns stored in the TCAM, generate one or more indices corresponding to the one or more search patterns that match the search key, and wherein the TCAM is configured to generate at most one index for each group of multiple entries, the at most one index indicating at most one search pattern in the corresponding group of multiple entries that matches the search key;
a memory separate from the TCAM; and
a controller configured to:
select one search pattern, from among the one or more search patterns that match the search key, at least by analyzing respective priority information associated with the one or more search patterns, the respective priority information indicating one or more respective priority levels, and
in connection with selecting the one search pattern, determine a processing rule that corresponds to the one selected search pattern and provide the processing rule to the packet processor to process the first packet according to the processing rule.
15 . The network device of claim 14 , wherein:
the TCAM is configured to, for each group of multiple entries:
compare the search key to search patterns stored within entries of the group, and
when the search key matches multiple search patterns in the group, select one search pattern based on an ordering of entries within the group, and output a single index for the group that indicates the selected search pattern; and
the controller is configured to, when the TCAM generates multiple indices corresponding to matches in multiple groups of entries, select one of the indices, at least by analyzing respective first priority information associated with the multiple indices, the respective first priority information indicating one or more respective priority levels of respective first search patterns of the respective groups.
16 . The network device of claim 14 , wherein:
the controller is configured to determine the processing rule that corresponds to the one selected search pattern from amongst a plurality of processing rules having forwarding information for forwarding packets that are received by the network device; and
the packet processor is configured to use the processing rule that corresponds to the one selected search pattern to determine a network interface, amongst a plurality of network interfaces of, or coupled to, the network device, to which the first packet is to be forwarded for transmission.
17 . The network device of claim 14 , wherein:
the controller is configured to determine the processing rule that corresponds to the one selected search pattern from amongst a plurality of processing rules having classification information for classifying packets that are received by the network device; and
the packet processor is configured to use the processing rule that corresponds to the one selected search pattern to classify the first packet.
18 . A method for determining actions to be performed on packets by a network device, the method comprising:
providing a search key corresponding to a first packet to a ternary content addressable memory (TCAM), wherein the TCAM comprises a plurality of entries organized in a plurality of groups of multiple entries;
determining, by the TCAM, that the search key matches one or more search patterns amongst a plurality of search patterns stored in the TCAM;
generating, by the TCAM, at most one index for each group of multiple entries, the at most one index indicating at most one search pattern in the corresponding group of multiple entries that matches the search key;
selecting, by the network device, one search pattern among the one or more search patterns at least by analyzing respective priority information associated with the one or more search patterns, the respective priority information indicating one or more respective priority levels; and
in connection with selecting the one search pattern, determining, by the network device, one or more actions to be performed on the first packet by the network device, the one or more actions corresponding to the one search pattern.
19 . The method for determining actions to be performed on packets of claim 18 , wherein:
determining that the search key matches one or more search patterns stored in the TCAM comprises, for each of at least some of the groups of multiple entries:
comparing, by the TCAM, the search key to search patterns stored within entries of the group, and
when the search key matches multiple search patterns in the group, selecting, by the TCAM, a first search pattern based on an ordering of entries within the group, and outputting, by the TCAM, a single index for the group that indicates the first search pattern; and
selecting the one search pattern comprises: when the TCAM outputs multiple indices corresponding to matches in multiple groups of entries, selecting, by the network device, one of the indices at least by analyzing respective priority information associated with the multiple indices.
20 . The method for determining actions to be performed on packets of claim 18 , wherein:
determining the one or more actions to be performed on the first packet by the network device comprises retrieving rule information from amongst a plurality of processing rules having forwarding information for forwarding packets that are received by the network device; and
the method further comprises using, by the network device, the processing rule that corresponds to the one selected search pattern to determine a network interface, amongst a plurality of network interfaces of, or coupled to, the network device, to which the first packet is to be forwarded for transmission.
21 . The method for determining actions to be performed on packets of claim 18 , wherein:
determining the one or more actions to be performed on the first packet by the network device comprises retrieving rule information amongst a plurality of processing rules having classification information for classifying packets that are received by the network device; and
the method further comprises using, by the network device, the processing rule that corresponds to the one selected search pattern to classify the first packet.