Content-addressable memory lookup device supporting iterative lookup operations

In one embodiment, multiple content-addressable memory entries are associated with each other to effectively form a batch content-addressable memory entry that spans multiple physical entries of the content-addressable memory device. To match against this content-addressable memory entry, multiple lookup operations are required—i.e., one lookup operation for each combined physical entry. Further, one embodiment provides that a batch content-addressable memory entry can span one, two, three, or more physical content-addressable memory entries, and batch content-addressable memory entries of varying sizes could be programmed into a single content-addressable memory device. Thus, a lookup operation might take two lookup iterations on the physical entries of the content-addressable memory device, with a next lookup operation taking a different number of lookup iterations (e.g., one, three or more).

TECHNICAL FIELD

The present disclosure relates generally to content-addressable memory devices, such as, but not limited to, those used in forwarding packets in a communications network.

BACKGROUND

The communications industry is rapidly changing to adjust to emerging technologies and ever increasing customer demand. This customer demand for new applications and increased performance of existing applications is driving communications network and system providers to employ networks and systems having greater speed and capacity (e.g., greater bandwidth). In trying to achieve these goals, a common approach taken by many communications providers is to use packet switching technology.

Content-addressable memories (CAMs), including, but not limited to, binary content-addressable memories (binary CAMs) and ternary content-addressable memories (ternary CAMs or TCAMs) are often used in packet switching device in processing of packets. Each entry of a binary CAM typically includes a value for matching against, while each TCAM entry typically includes a value and a mask. The binary or ternary CAM compares a lookup word against all of the entries in parallel, and typically generates an indication of the highest priority entry that matches the lookup word. An entry matches the lookup word in a binary CAM if the lookup word and the entry value are identical, while an entry matches the lookup word in a TCAM if the lookup word and the entry value are identical in the bits that are not indicated by the mask as being irrelevant to the comparison operations.

DESCRIPTION OF EXAMPLE EMBODIMENTS

One embodiment includes performing one or more of iterations of lookup operations, based on a lookup word, on a plurality of content-addressable memory entries to identify an overall lookup result. In one embodiment, performing these one or more of iterations of lookup operations includes: performing a lookup operation on bits of the lookup word corresponding to the current iteration on the plurality of content-addressable memory entries to identify a native result for each of the plurality of content-addressable memory entries; determining which of the native results correspond to a match and which of the native results correspond to a non-match in the current iteration based on a batch mask vector and also, for a non-first iteration, on previous cumulative results. In one embodiment, the batch mask vector identifies for each particular entry of the plurality of content-addressable memory entries a lookup iteration to which said particular entry corresponds.

One embodiment includes an apparatus, comprising: a plurality of content-addressable memory entries; a batch mask vector configured to identify for each particular entry of the plurality of content-addressable memory entries a lookup iteration to which said particular entry corresponds; a cumulative result vector configured to maintain a current cumulative snapshot of lookup results of one or more prior lookup iterations on the plurality of content-addressable memory entries; and match logic configured to determine an overall lookup result based on one or more iterations of lookup operations, based on a lookup word, on the plurality of content addressable memory entries. In one embodiment, this configuration to determine the overall lookup result includes: configuration to cause a lookup operation to be performed, based on bits of the lookup word corresponding to the current iteration, on the plurality of content-addressable memory entries to identify a native result for each of the plurality of content-addressable memory entries; configuration to determine which of the native results correspond to a match and which of the native results correspond to a non-match in the current iteration based on a batch mask vector and also, for a non-first iteration, on the cumulative result vector; and configuration to update the cumulative result vector with said determination of which of the native results correspond to a match and which of the native results correspond to a non-match.

Disclosed are, inter alia, methods, apparatus, computer-storage media, mechanisms, and means associated with content-addressable memory lookup device supporting iterative lookup operations. Each entry of a content-addressable memory (CAM) has a limited number of bits against which a bit of a lookup word is matched. The width of a CAM is typically either sized to meet the needs of the application, or what is commercially available as a device or library design. When a CAM is used for multiple purposes, the required width of CAM entries for each application may be different. In the past, a CAM would be selected with a width of each of its entries able to accommodate an entry required for each application. Thus, if the disparity in width requirements were great, a large number of bits in CAM entries would go unused.

To overcome drawbacks of prior approaches, one embodiment provides for multiple CAM entries to be associated with each other to effectively form a batch CAM entry that spans multiple physical entries of the CAM device. To match against this CAM entry, multiple lookup operations are required—i.e., one lookup operation for each combined physical entry. Further, one embodiment provides that a batch CAM entry can span one, two, three, or more physical CAM entries, and batch CAM entries of varying sizes can be programmed into a single CAM device. Thus, a lookup operation might take two lookup iterations on the physical entries of the CAM device, with a next lookup operation taking a different number of lookup iterations (e.g., one, three or more).

Embodiments described herein include various elements and limitations, with no one element or limitation contemplated as being a critical element or limitation. Each of the claims individually recites an aspect of the embodiment in its entirety. Moreover, some embodiments described may include, but are not limited to, inter alia, systems, networks, integrated circuit chips, embedded processors, ASICs, methods, and computer-readable media containing instructions. One or multiple systems, devices, components, etc. may comprise one or more embodiments, which may include some elements or limitations of a claim being performed by the same or different systems, devices, components, etc. A processing element may be a general processor, task-specific processor, a core of one or more processors, or other co-located, resource-sharing implementation for performing the corresponding processing. The embodiments described hereinafter embody various aspects and configurations, with the figures illustrating exemplary and non-limiting configurations. A computer-readable media and means for performing methods and processing block operations (e.g., a processor and memory or other apparatus configured to perform such operations) are disclosed and are in keeping with the extensible scope and spirit of the embodiments. The term “apparatus” is used consistently herein with its common definition of an appliance or device.

The steps, connections, and processing of signals and information illustrated in the figures, including, but not limited to, any block and flow diagrams and message sequence charts, may typically be performed in the same or in a different serial or parallel ordering and/or by different components and/or processes, threads, etc., and/or over different connections and be combined with other functions in other embodiments, unless this disables the embodiment or a sequence is explicitly or implicitly required (e.g., for a sequence of read the value, process said read value—the value must be obtained prior to processing it, although some of the associated processing may be performed prior to, concurrently with, and/or after the read operation). Also, nothing described or referenced in this document is admitted as prior art to this application unless explicitly so stated.

The term “one embodiment” is used herein to reference a particular embodiment, wherein each reference to “one embodiment” may refer to a different embodiment, and the use of the term repeatedly herein in describing associated features, elements and/or limitations does not establish a cumulative set of associated features, elements and/or limitations that each and every embodiment must include, although an embodiment typically may include all these features, elements and/or limitations. In addition, the terms “first,” “second,” etc. are typically used herein to denote different units (e.g., a first element, a second element). The use of these terms herein does not necessarily connote an ordering such as one unit or event occurring or coming before another, but rather provides a mechanism to distinguish between particular units. Moreover, the phrases “based on x” and “in response to x” are used to indicate a minimum set of items “x” from which something is derived or caused, wherein “x” is extensible and does not necessarily describe a complete list of items on which the operation is performed, etc. Additionally, the phrase “coupled to” is used to indicate some level of direct or indirect connection between two elements or devices, with the coupling device or devices modifying or not modifying the coupled signal or communicated information. Moreover, the term “or” is used herein to identify a selection of one or more, including all, of the conjunctive items. Additionally, the transitional term “comprising,” which is synonymous with “including,” “containing,” or “characterized by,” is inclusive or open-ended and does not exclude additional, unrecited elements or method steps. Finally, the term “particular machine,” when recited in a method claim for performing steps, refers to a particular machine within the 35 USC §101 machine statutory class.

One embodiment includes performing one or more of iterations of lookup operations, based on a lookup word, on a plurality of content-addressable memory entries to identify an overall lookup result. In one embodiment, performing these one or more of iterations of lookup operations includes: performing a lookup operation on bits of the lookup word corresponding to the current iteration on the plurality of content-addressable memory entries to identify a native result for each of the plurality of content-addressable memory entries; determining which of the native results correspond to a match and which of the native results correspond to a non-match in the current iteration based on a batch mask vector and also, for a non-first iteration, on a cumulative result vector; and updating the cumulative result vector with said determination of which of the native results correspond to a match and which of the native results correspond to a non-match. In one embodiment, the batch mask vector identifies for each particular entry of the plurality of content-addressable memory entries a lookup iteration to which said particular entry corresponds.

One embodiment includes determining a single highest-priority result from the cumulative result vector. In one embodiment, the overall lookup result is the single highest priority result from the cumulative result vector. One embodiment includes shifting bits within the cumulative result vector by the number of iterations in said one or more of iterations of lookup operations prior to said determining the single highest-priority result from the cumulative result vector.

In one embodiment, the overall lookup result is the contents of the cumulative result vector after all of said iterations of said one or more of iterations of lookup operations have been performed. In one embodiment, said one or more of iterations of lookup operations consist of one lookup iteration. In one embodiment, said one or more of iterations of lookup operations consist of two lookup iterations. In one embodiment, said one or more of iterations of lookup operations comprise at least three lookup iterations. In one embodiment, the method is performed within a single integrated circuit device. In one embodiment, said based on the cumulative result vector includes determining from the cumulative result vector that all iterations of said one or more of iterations of lookup operations prior to the current iteration produced a corresponding match for related entries of the plurality of content-addressable memory entries. One embodiment includes programming related entries contiguously and in an iteration sequence order within the plurality of content-addressable memory entries.

One embodiment includes an apparatus, comprising: a plurality of content-addressable memory entries; a batch mask vector configured to identify for each particular entry of the plurality of content-addressable memory entries a lookup iteration to which said particular entry corresponds; a cumulative result vector configured to maintain a current cumulative snapshot of lookup results of one or more prior lookup iterations on the plurality of content-addressable memory entries; and match logic configured to determine an overall lookup result based on one or more iterations of lookup operations, based on a lookup word, on the plurality of content addressable memory entries. In one embodiment, this configuration to determine the overall lookup result includes: configuration to cause a lookup operation to be performed, based on bits of the lookup word corresponding to the current iteration, on the plurality of content-addressable memory entries to identify a native result for each of the plurality of content-addressable memory entries; configuration to determine which of the native results correspond to a match and which of the native results correspond to a non-match in the current iteration based on a batch mask vector and also, for a non-first iteration, on the cumulative result vector; and configuration to update the cumulative result vector with said determination of which of the native results correspond to a match and which of the native results correspond to a non-match.

One embodiment includes a priority encoder configured to determine a single highest-priority result from the cumulative result vector; wherein the overall lookup result is the single highest priority result from the cumulative result vector. In one embodiment, the cumulative result vector is configured to shift bits by the number of iterations in said one or more of iterations of lookup operations. In one embodiment, said one or more of iterations of lookup operations consist of one lookup iteration. In one embodiment, said one or more of iterations of lookup operations consist of two lookup iterations. In one embodiment, said one or more of iterations of lookup operations comprise at least three lookup iterations. In one embodiment, the apparatus is a single integrated circuit device. In one embodiment, said based on the cumulative result vector includes determining from the cumulative result vector that all iterations of said one or more of iterations of lookup operations prior to the current iteration produced a corresponding match for related entries of the plurality of content-addressable memory entries. In one embodiment, related entries are stored contiguously and in an iteration sequence order within the plurality of content-addressable memory entries.

Expressly turning to the figures,FIG. 1Aillustrates content-addressable memory (CAM) entries100. In one embodiment, CAM entries are binary CAM entries. In one embodiment, CAM entries are ternary CAM entries. In one embodiment, CAM entries are quaternary CAM entries. A common width of a CAM entry is 80 bits. So, for illustrative purposes,FIG. 1Auses a CAM entry width of 80 bits.

The shown nine CAM entries100are programmed into three batch entries101,102, and103. Batch entry A101consists of three CAM entries100; batch entry B102consists of two CAM entries100; and batch entry C103consists of five CAM entries100. Thus, this technique allows batch entries of different widths to be programmed into a same set of CAM entries. As shown, up to eighty bits are programmed into each CAM entry100of batch entries101,102, and103.

Batch mask vector (BMV)110is a separate memory (e.g., register(s), random access memory, non-associative memory) that includes a value corresponding to each of CAM entries100. BMV110includes data to identify whether a corresponding CAM entry100is a start entry (encoded as binary ‘10’ in one embodiment); middle entry (encoded as binary ‘00’ in one embodiment); an end entry (encoded as binary ‘11’ in one embodiment); or a batch entry consisting of a single CAM entry (encoded as binary ‘01’ in one embodiment). Each of batch entries101,102,103include a start entry and an end entry. Each of batch entries101and103include a middle entry. Batch entry102does not include a middle entry as it consists of two CAM entries100. A batch entry consisting of a single CAM entry100is typically marked as a start entry. In one embodiment, a start entry corresponds to the high-order bits of a batch entry and an end entry corresponds to the low-order bits of a batch entry. In one embodiment, a start entry corresponds to the low-order bits of a batch entry and an end entry corresponds to the high-order bits of a batch entry.

FIG. 1Bis similar toFIG. 1A, and is included herein to expressly illustrate that CAM entries140can be striped across multiple CAM banks to achieve wider CAM entries140. In this example, each of CAM entries140is four times eight bits wide, which equals three hundred-twenty bits wide. In one embodiment, batch entries141,142, and143are programmed in a same manner as described in relation to batch entries101,102, and103ofFIG. 1A. BMV110is the same inFIGS. 1A and 1B.

FIG. 2illustrates CAM entries200programmed as batch entries201,202, and203. Batch mask vector (BMV)210is programmed to describe the function of CAM entries200in batch entries201,202, and203. By having BMV210be distinct from CAM entries200, the information represented in BMV210does not consume any bits of CAM entries200.

For each lookup iteration, the matching results of each CAM entry200is captured in native result vector (NRV)209. In one embodiment, a one represents a match (e.g., hit), and a zero represents not a match (e.g., a miss). One embodiment uses a different representation, with logic computations performed accordingly. Cumulative result vector (CRV)211is used to aggregate the results over each iteration.

In one embodiment, if the lookup operation is to consist of a single iteration, then a single lookup operation is performed with the lookup word matched against each of CAM entries200, with the individual matching results of each CAM entry200captured in native result vector (NRV)209. The results in NVR209are filtered by control logic based on batch mask vector (BMV)210to consider any matching indication in NVR209that is not marked as a batch entry consisting of a single CAM entry in BMV210to be a miss. The result of this filtering is captured in cumulative result vector (CRV)211. Because a lookup operation on CAM entries200is being performed using a single lookup iteration, then CRV211contains the matches, and typically, a priority encoder is used to identify a single highest-priority matching entry identified in CRY211, or a miss if there are no matching entries identified in CRV211.

Otherwise, the desired matching batch entry spans multiple CAM entries200. In one embodiment, to perform a series of lookup operation on batch entries201,202, and203, a batch lookup counter (BLC)216is set to the number of iterations to be performed in the iterative lookup operation. The number of lookup iterations is typically determined from the width of the batch lookup word divided by the width of each of CAM entries200.

For a first lookup iteration, corresponding bits of the lookup word206for the first iteration are matched against each of CAM entries200, with the individual matching results of each CAM entry200captured in native result vector (NRV)209.

In one embodiment, the entire lookup word having a width spanning multiple lookup iterations is initially received with different portions used for each iteration. In one embodiment, different bits/portions of a lookup word are received in sequence, one for lookup iteration.

The results in NVR209are filtered by control logic based on batch mask vector (BMV)210to consider any matching indication in NVR209that is not marked as a start entry in BMV210to be a miss. The result of this filtering is captured in cumulative result vector (CRY)211.

Batch lookup counter (BLC)216is decremented by one to reflect that one less lookup iteration remains to be performed.

If the lookup operation is seeking a batch entry of more than two CAM entries200, then one or more iterations for identifying matching with middle entries is performed; otherwise processing continues to look for an end entry as described supra.

For each middle entry sought, a lookup operation on each of CAM entries200is performed on a corresponding set of bits of the lookup word (206), with the individual matching results of each CAM entry200captured in native result vector (NRV)209. Cumulative result vector (CRV)211is then updated to reflect current snapshot of the aggregation of matches. CRV211will indicate a hit only in all positions within CRV211where:1. a corresponding CAM entry200matched the lookup word portion206(e.g., matching results reflected in NRV209);2. BMV indicates that this corresponding CAM entry200was a middle entry; and3. CRV211reflects that the start entry and previous middle entries, if any, of the batch entry including this corresponding CAM entry200matched correctly at each previous iteration.
Batch lookup counter (BLC)216is decremented by one to reflect that one less lookup iteration remains to be performed.

When BLC216reflects that there is one final iteration to be performed (e.g., for matching on CAM entries200marked in BMV210as being an end entry), a lookup operation on each of CAM entries200is performed on a corresponding last set of bits of the lookup word (206), with the individual matching results of each CAM entry200captured in native result vector (NRV)209. Cumulative result vector (CRV)211is then updated to reflect current snapshot of the aggregation of matches. CRV211will indicate a hit only in all positions within CRV211where:1. a corresponding CAM entry200matched the lookup word portion206(e.g., matching results reflected in NRV209);2. BMV indicates that this corresponding CAM entry200was an end entry; and3. CRV211reflects that the start entry and previous middle entries, if any, of the batch entry including this corresponding CAM entry200matched correctly at each previous iteration.
In one embodiment, CRV211is provided as the lookup result. In one embodiment, the results of CRV211are shifted up by the number of iterations so that the matching or no match indication of the batch entry (201-203) aligns with the first CAM entry200of a batch entry (201-203). In one embodiment, a priority encoder is used to find a single highest-priority matching batch entry reflected in CRV211.

FIG. 3Aillustrates one embodiment of CAM device300(e.g., apparatus, appliance, integrated circuit), which includes: lookup word iteration bit buffers301, CAM entries302, native result vectors303, match and control logic304, cumulative result vector (CRV)305, batch mask vector (BMV)307, and output logic308(e.g., shift register, priority encoder). Some of the data flows of CAM device300are illustrated inFIG. 3A. Control signals are not shown but are provided where needed. For illustrative purposes, numeric dimensions of one embodiment are presented inFIG. 3A. Of course, one embodiment has other numeric dimensions. The operation of CAM device300is described herein, such as that described in relation toFIG. 2and in relation toFIG. 4.

In one embodiment, such as that illustrated inFIG. 3A, it is possible that the lookup word for a current iteration is less than the full width of a possible lookup operation. For example, there are each of the illustrated four lookup word iteration bits buffer310are 80 bits wide, which correspond to the width of each entry of each CAM bank302. In one embodiment, a lookup operation is selectively performed on entries in one, two, three or all four of CAM banks302. Thus, each iteration on bits of a lookup word operation may be performed on a different number of bits. For example, a lookup word of width 800 bits may cause three lookup word iteration bit widths of 320 bits (i.e., lookup on all four banks302), 320 bits (i.e., lookup on all four banks302), and 160 bits (e.g., only lookup on a selected two of the four banks302). The order of these iterations corresponds to the programming of the entries in CAM banks320(e.g., CAM entries programmed in widths of 320 bits, 320 bits, and 160 bits). In one embodiment, the width of a current lookup word is different than a multiple of the width of a CAM bank302(but this is a more complicated implementation than that using a single enable line for each CAM bank302).

FIG. 3Bis a block diagram of an apparatus340used in one embodiment associated with content-addressable memory lookup device supporting iterative lookup operations. In one embodiment, apparatus340determines and/or programs content-addressable entries, and/or performs one or more processes, or portions thereof, corresponding to one of the flow diagrams illustrated or otherwise described herein, and/or illustrated in another diagram or otherwise described herein.

In one embodiment, apparatus340includes one or more processing element(s)341, memory342, storage device(s)343, content-addressable memory entries345, and interface(s)347for communicating information (e.g., signaling lookup results, sending and receiving packets, user-interfaces, displaying information, etc.), which are typically communicatively coupled via one or more communications mechanisms349, with the communications paths typically tailored to meet the needs of a particular application. In one embodiment, processing elements341and memory342are used to maintain and process batch mask vector, native result vector, and cumulative result vector data structures, and to control iterative lookup operations on content-addressable memory entries345to produce an overall lookup operation result as described herein (e.g., especially in relation toFIG. 2and/orFIG. 4).

Various embodiments of apparatus340may include more or fewer elements. The operation of apparatus340is typically controlled by processing element(s)341using memory342and storage device(s)343to perform one or more tasks or processes. Memory342is one type of computer-readable/computer-storage medium, and typically comprises random access memory (RAM), read only memory (ROM), flash memory, integrated circuits, and/or other memory components. Memory342typically stores computer-executable instructions to be executed by processing element(s)341and/or data which is manipulated by processing element(s)341for implementing functionality in accordance with an embodiment. Storage device(s)343are another type of computer-readable medium, and typically comprise solid state storage media, disk drives, diskettes, networked services, tape drives, and other storage devices. Storage device(s)343typically store computer-executable instructions to be executed by processing element(s)341and/or data which is manipulated by processing element(s)341for implementing functionality in accordance with an embodiment.

FIG. 4illustrates a process performed in one embodiment. The previous discussion and figures, especiallyFIGS. 2 and 3A, provide a good backdrop for the discussion of the process described inFIG. 4.

Processing of the flow diagram ofFIG. 4begins with process block400. In process block402, a lookup operation is performed on all CAM entries using corresponding bits of the overall lookup word to generate matching results stored in a native result vector (NVR).

As determined in process block403, if the batch lookup operation consists of a single iteration, then in process block404, for each entry K of the CAM entries (e.g., sequence through the CAM entries with K ranging from zero to one less than the number of CAM entries), the entry K in cumulative result vector (CMV) is marked as a one (‘1’) to indicate a match (e.g., hit) where entry K in NVR indicates a match and entry K in batch mask vector (BMV) indicates a batch entry consisting of a single CAM entry (e.g., ‘01’); else entry K in CMV is marked as a zero (‘0’) to indicate no match (e.g., miss). Processing then proceeds to process block426, wherein the highest priority result in CRV is signaled as the overall matching result (if no match, then this result is no match). Processing of the flow diagram ofFIG. 4is complete as indicated by process block429.

Otherwise, in process block404, for each entry K of the CAM entries (e.g., sequence through the CAM entries with K ranging from zero to one less than the number of CAM entries), the entry K in cumulative result vector (CMV) is marked as a one (‘1’) to indicate a match (e.g., hit) where entry K in NVR indicates a match and entry K in batch mask vector (BMV) indicates a start batch entry (e.g., ‘10’); else entry K in CMV is marked as a zero (‘0’) to indicate no match (e.g., miss).

Otherwise, as determined in process block405, the batch lookup operation comprises at least two iterations, and processing proceeds to process block406, wherein the batch lookup counter is set to the number of iterations in this batch lookup operation minus one.

Process block409determines whether the current iteration is to seek matching middle entries (process blocks410-416) or to complete the lookup operation by seeking matching end entries and to signal the overall matching result (process blocks420-429).

When determined in process block409to seek a middle entry in this iterative lookup operation, in process block410, a lookup operation is performed on all CAM entries using corresponding lookup word bits to generate matching results stored in a native result vector (NVR). In process block412, for each entry K>0 of the CAM entries (e.g., sequence through the CAM entries with K ranging from one to one less than the number of CAM entries), the entry K in cumulative result vector (CMV) is marked as a one (‘1’) to indicate a match (e.g., hit) where entry K in NVR indicates a match, entry K in batch mask vector (BMV) indicates a middle batch entry (e.g., ‘00’), and the entry K−1 in CMV indicates a match, else entry K in CMV is marked as a zero (‘0’) to indicate no match (e.g., miss); and also the entry K−1 in CMV is set to zero, as the relevant matching position is K in CMV, and the result of a previous iteration needs to be marked as not a hit to avoid detecting an incorrect hit of a batch entry by a priority encoder in process block426. In one embodiment, bit shifting is used to implement the arithmetic to find a previous entry (e.g., K−1 in CMV). Requiring that the previous entry in CMV indicates a match for determining a current match imposes a restriction that all previous iterations (e.g., matching a start entry, and matching all previous middle entries if any) determined to be a match for the corresponding batch entry programmed into consecutive CAM entries. In process block414, the batch loop counter (BLC) is reduced by one (e.g., one less iteration remaining to be performed). Processing returns to process block409.

When determined in process block409to seek an end entry in this iterative lookup operation, in process block420, a lookup operation is performed on all CAM entries using corresponding lookup word bits to generate matching results stored in a native result vector (NVR). In process block422, for each entry K>0 of the CAM entries (e.g., sequence through the CAM entries with K ranging from one to one less than the number of CAM entries), the entry K in cumulative result vector (CMV) is marked as a one (‘1’) to indicate a match (e.g., hit) where entry K in NVR indicates a match, entry K in batch mask vector (BMV) indicates an end batch entry (e.g., ‘11’), and the entry K−1 in CMV indicates a match; else entry K in CMV is marked as a zero (‘0’) to indicate no match (e.g., miss); and also the entry K−1 in CMV is set to zero, as the relevant matching position is K in CMV, and the result of a previous iteration needs to be marked as not a hit to avoid detecting an incorrect hit of a batch entry by a priority encoder in process block426. In one embodiment, bit shifting is used to implement the arithmetic to find a previous entry (e.g., K−1 in CMV). Requiring that the previous entry in CMV indicates a match for determining a current match imposes a restriction that all previous iterations (e.g., matching a start entry, and matching all previous middle entries if any) determined to be a match for the corresponding batch entry programmed into consecutive CAM entries. In process block424, all entries in the cumulative result vector (CMV) are shifted up (with zeros/no hit bits shifted in) by the number of lookup operations in the current batch lookup in order cause the matching result to be indicated at the start entry of each matching batch entry. In process block426, the highest priority result in CRV is signaled as the overall matching result (if no match, then this result is no match). Processing of the flow diagram ofFIG. 4is complete as indicated by process block429.

In view of the many possible embodiments to which the principles of the disclosure may be applied, it will be appreciated that the embodiments and aspects thereof described herein with respect to the drawings/figures are only illustrative and should not be taken as limiting the scope of the disclosure. For example, and as would be apparent to one skilled in the art, many of the process block operations can be re-ordered to be performed before, after, or substantially concurrent with other operations. Also, many different forms of data structures could be used in various embodiments. The disclosure as described herein contemplates all such embodiments as may come within the scope of the following claims and equivalents thereof.