Method and device for improving scalability of longest prefix match

摘要

A Ternary Content Addressable Memory (TCAM)-based Longest Prefix Match (LPM) lookup table including a TCAM holding a plurality of prefix entries for looking up results in an associated RAM, the associated RAM storing results corresponding to TCAM match indices; additional Random Access Memory (RAM) storing results from the associated RAM; and one entry in the TCAM representing at least two entries in the additional RAM from the associated RAM, whereby at least one entry in the TCAM is made available.

主权项

1. A Ternary Content Addressable Memory (TCAM)-based Longest Prefix Match (LPM) lookup table comprising:
a TCAM, an associated Random Access Memory (RAM) and an additional RAM; the TCAM configured to store a TCAM entry referencing an LPM entry in the associated RAM and a TCAM entry corresponding to a common prefix of a plurality of LPM entries, wherein the plurality of LPM entries is selected by, in response to incremental changes in LPM entries, prioritizing based on the incremental changes candidate array entries corresponding to combination of LPM entries; the TCAM further configured to remove a plurality of TCAM entries each corresponding to one of said plurality of selected LPM entries other than said TCAM entry corresponding to said common prefix; the associated RAM configured to store a results entry corresponding to said stored TCAM entry and to overwrite results entries associate with each of said removed TCAM entries; and the additional RAM configured to store an array entry selected from the candidate array entries, the selected array entry corresponding to the combination of said plurality of selected LPM entries and including results entries corresponding to the overwritten results entries; wherein said LPM lookup table, after the TCAM removes the plurality of TCAM entries, still includes at least one TCAM entry referencing an LPM entry in the associated RAM.