Search engine for forwarding table content addressable memory
First Claim
1. A search engine for managing a forwarding table having a plurality of entry locations for storing packet flow information in a network node device, said search engine comprising:
- configuration registers in communication with a central processing unit (CPU);
a comparator for sequentially comparing at least one search criteria with entries in the forwarding table, wherein the at least one search criteria is stored in said configuration registers by the CPU;
means for acting when the comparison produces a positive result, wherein at least one action associated with at least one search criteria is stored in said configuration registers by the CPU; and
a memory in communication with said configuration registers and said comparator, said memory receiving addresses corresponding to locations in the forwarding table determined by said comparator to match the at least one search criteria.
1 Assignment
0 Petitions
Accused Products
Abstract
A hardware search engine facility is provided to allow CPU search and update of a Forwarding Table CAM under the control of software running on the CPU. The hardware search engine provides one or more comparand-mask pairs which allow for a match, exclusion or magnitude comparison on specific entry values and/or the option to ignore or “don'"'"'t care” certain bits of the entry. Control registers may be set in software to specify a start address and stop address in the CAM for the search. An indication of valid or invalid entries may be provided as well. Once the search is initiated by software, the search engine will read the entries sequentially starting from the programmed start address. It will perform a compare using the comparand-mask pair and attempt to identify a match. The locations in the CAM which match the search criteria may be put into a CPU-accessible memory. If the memory fills up before it can be read by the software, the search may be halted until the memory is emptied. A programmable action may instead, or in addition, be set to take place in the event of a match. Such programmable actions may include, but are not limited to, marking the entry, deleting the entry, change status bits corresponding to the entry, rewriting some of the entry, and the like.
160 Citations
11 Claims
-
1. A search engine for managing a forwarding table having a plurality of entry locations for storing packet flow information in a network node device, said search engine comprising:
-
configuration registers in communication with a central processing unit (CPU);
a comparator for sequentially comparing at least one search criteria with entries in the forwarding table, wherein the at least one search criteria is stored in said configuration registers by the CPU;
means for acting when the comparison produces a positive result, wherein at least one action associated with at least one search criteria is stored in said configuration registers by the CPU; and
a memory in communication with said configuration registers and said comparator, said memory receiving addresses corresponding to locations in the forwarding table determined by said comparator to match the at least one search criteria. - View Dependent Claims (2, 3)
a valid memory having at least two bits corresponding with each entry in the forwarding table, said bits indicating whether the corresponding entry is FREE, IN_USE, ASSIGNED or LOCKED.
-
-
3. A search engine in accordance with claim 1, further comprising:
a valid memory having at least one bit corresponding with each entry in the forwarding table, said at least one bit indicating whether or not the corresponding entry contains valid packet flow information.
-
4. A search engine to examine entries within a forwarding table, the search engine comprising:
-
means for acquiring a first comparison criterion, the first comparison criterion including a mask indicating which bits of the entries are to be considered, a comparand value to be compared to the bits to be considered, and a comparison type to be used in comparing the entries with the first comparison criterion;
means for acquiring at least one action associated with the first comparison criterion to be taken upon a positive comparison result;
means for acquiring a second comparison criterion, the second comparison criterion including a mask indicating which bits of the entries are to be considered, a comparand value to be compared to the bits to be considered, and a comparison type to be used in comparing the entries with the second comparison criterion;
means for acquiring at least one action associated with the second comparison criterion to be taken upon a positive comparison result;
means for conducting a comparison in accordance with the first comparison criterion and the second comparison criterion to at least one entry within the forwarding table;
means for taking the at least one action associated with the first comparison criterion in response to a positive comparison result with respect to the first comparison criterion; and
means for taking the at least one action associated with the second comparison criterion in response to a positive comparison result with respect to the second comparison criterion. - View Dependent Claims (5, 6, 7, 8, 9, 10, 11)
-
Specification