三元内容可寻址存储器中的错误检测方法

摘要

三元内容可寻址存储器中的错误检测方法。本发明涉及用于在三元内容可寻址存储器TCAM中优选实时地进行错误检测的方法，其中利用在指定的输入地址（200）处的读取操作来发起错误检测，提供附加的随机存取存储器RAM，所述RAM具有与TCAM相同数量的位置，各自由数据和掩码组成的对应读取数据条目（210）被放置在相同的地址位置。本发明涉及用于在三元内容可寻址存储器TCAM中优选实时地进行错误检测的方法，其中错误检测是通过所搜索的输入关键字（400）的发现来触发的，并且以在指定的存储器地址（410）处的读取操作开始，其中提供附加的随机存取存储器RAM，所述RAM具有与TCAM相同数量的位置，各自由数据和掩码组成的对应读取数据条目（420）被放置在相同的地址位置。

权利要求

1.一种用于在三元内容可寻址存储器TCAM中优选实时地进行错误检测的方法，其中错误检测利用在指定的输入地址（200）处的读取操作来发起，其特征在于，提供附加的随机存取存储器RAM，其中所述RAM具有与TCAM相同数量的位置，其中在两个存储器TCAM和RAM中，各自由数据和掩码组成的对应读取数据条目（210）被放置在相同的地址位置处，并且其中在由输入地址（200）指向的位置处执行从TCAM和RAM的数据和掩码读取操作，并且在第一检验阶段（220）中，将在由输入地址（200）指向的位置处从TCAM读取的所述数据和掩码与在由相同输入地址（200）指向的位置处从RAM读取的数据和掩码进行比较，并且如果第一校验阶段（220）的结果是正确的，则执行TCAM_SEARCH阶段（270），否则，执行数据恢复校验（230），其之后是数据刷新（240），对存储在TCAM和RAM两者中所述输入地址（200）处的数据条目（250）的第二读取，并且执行第二校验阶段（260），在所述第二阶段（260）中，执行从TCAM和RAM两者读取的数据和掩码的比较，以及并且其中TCAM_SEARCH阶段（270）使用从RAM读取的数据作为输入搜索关键字，并且作为输出返回TCAM匹配向量和/或单个TCAM地址，并且其中TCAM匹配校验（280）校验

在TCAM匹配向量的情况下，TCAM_SEARCH（270）的结果——即由来自TCAM匹配向量（275）的地址（200）指向的标志——是否为二进制1，或者在非匹配（错误）的情况下，在TCAM地址校验（310）中校验的TCAM单个地址（300），并且如果TCAM地址（300）是比所述输入地址（200）低的地址，则执行在所述TCAM地址（300）处的TCAM读取，并且如果在TCAM搜索验证（340）中，在TCAM地址（300）处读取的TCAM数据与在RAM处读取的数据相同，并且其中优选地，所述方法移动到由擦洗机制提供的下一个输入地址（286），并且可以重复整个提议的错误检测方法。

2.根据权利要求1所述的方法，其特征在于使用数据条目校验和比较的TCAM和RAM低存储器带宽需求过程的校验和阶段（220，260）。

3.根据权利要求1所述的方法，其特征在于使用数据条目校验和比较的TCAM和RAM高存储器带宽需求过程的校验和阶段（220，260），其包括纠错码或散列算法。

4.根据前述权利要求中任一项所述的方法，其中，如果校验的结果为假，则数据恢复校验（230）升起数据完整性错误标志（265）。

5.根据前述权利要求中任一项所述的方法，其中，提供第二校验（260）阶段，如果校验的结果为假，则所述第二校验（260）阶段升起数据完整性错误标志（265）。

6.根据前述权利要求中任一项所述的方法，其中，执行TCAM匹配校验（280），如果校验的结果是二进制1，则所述TCAM匹配校验（280）完成错误检测，否则，它升起搜索错误标志（285）。

7.根据前述权利要求中任一项所述的方法，其中，执行TCAM搜索验证（340），如果在TCAM地址（300）处读取的数据的比较结果没有在RAM中提供匹配，则所述TCAM搜索验证（340）升起搜索错误标志（285）。

8.一种用于在三元内容可寻址存储器TCAM中优选实时地进行错误检测的方法，其特征在于，提供附加的随机存取存储器RAM，其中所述RAM具有与TCAM相同数量的位置，其中，在两个存储器TCAM和RAM中，各自由数据和掩码组成的对应读取数据条目被放置在相同的地址位置处，并且其中通过从TCAM_SEARCH命令（400）输出的所接收输入地址（410）来发起错误检测，其中存储器读取（420）对存储在TCAM和/或RAM中的所述输入地址（410）处的数据和掩码进行读取，并且其中校验（430）对所述数据和掩码的完整性进行校验，并且如果没有发现错误，则执行关键字匹配校验（440），其中输入搜索关键字（405）与位于TCAM和/或RAM存储器中地址（410）处的数据和掩码进行比较。

9.根据权利要求8所述的方法，其中，特别是在TCAM的低可用带宽的情况下，在RAM处执行数据值和掩码的读取（420），或者特别是如果TCAM的可用带宽高，则在TCAM处执行存储器读取（420）。

10.根据权利要求8或9所述的方法，其中执行数据和掩码的完整性校验（430）。

11.根据权利要求8至10中任一项所述的方法，其中执行关键字匹配校验（440），并且如果在输入搜索关键字（405）与从地址（410）读取的数据和掩码之间不存在匹配，则将指示搜索错误（460）。

12.一种用于在根据权利要求1至11中任一项的方法中使用的存储器设备，其中所述存储器设备包括三元内容可寻址存储器TCAM和附加的随机存取存储器RAM，其中所述RAM具有与TCAM相同数量的位置，其中在两个存储器TCAM和RAM中，各自由数据和掩码组成的对应读取数据条目（210）可以被放置在相同的地址位置处。

13.一种设备，用于执行根据步骤1至12中任一个的方法，例如联网设备，特别是诸如路由器或交换机之类的高速联网设备，或基于TCAM的高速搜索引擎，所述设备包括根据权利要求12的存储器设备。

14.一种计算机网络，包括根据权利要求12和/或13的一个或多个设备。

说明书

三元内容可寻址存储器中的错误检测方法

技术领域

[0001] 本发明涉及用于在三元内容可寻址存储器TCAM中优选实时地进行错误检测的方法，其中错误检测是利用在指定输入地址处的读取操作来发起的。

[0002] 此外，本发明涉及用于在三元内容可寻址存储器TCAM中优选实时地进行错误检测的方法。

[0003] 本发明总地涉及计算和设备联网。更特别地，本发明涉及三元内容可寻址存储器（TCAM）中的实时错误检测机制。

背景技术

[0004] 三元内容可寻址存储器（TCAM）是专门化的内容可寻址存储器（CAM），其被设计用于在最长匹配上进行搜索的快速表查找，诸如由IP前缀组织的IP路由表。作为一类CAM存储器的TCAM具有存储在数据条目中的位，并且可以具有三个不同的位值，以用于与输入字匹配的目的（“1”、“0”和“无所谓”）。每个TCAM条目具有三个实体：值、掩码和结果。该值是将被匹配的模式（例如，IP/MAC地址）。掩码由与值模式相关联的掩码位（0、1和“无所谓”）组成，并且表示前缀。在查找搜索发现模式和掩码的情况下，结果是肯定结果。在搜索操作期间，TCAM将输入数据与存储在TCAM中的所有有效数据条目进行比较，给出多个匹配的列表，并且确定为比较的数据提供匹配的第一地址。更精确地，在一个时钟周期中，输入数据与存储在TCAM中的每个有效数据进行比较。当所有位都与存储数据匹配时，获得TCAM条目的肯定匹配结果。无论输入数据位具有哪个值，当存储在TCAM中的“无所谓”数据位与输入数据位进行比较时，所述存储在TCAM中的“无所谓”数据位将提供匹配。

[0005] 考虑到TCAM中的数据完整性错误，这样的错误通常由宇宙射线发射和电离辐射引入。这些类型的错误被表征为所谓的软错误。除了这些软错误之外，还存在称为搜索错误的另一种错误。由于针对TCAM搜索的输入是搜索关键字并且输出是为比较的关键字提供匹配的第一地址的事实，因此可能引入搜索错误。搜索错误可能导致：假匹配（假命中），当搜索关键字命中错的条目时，即较低优先级条目或不应当为所述搜索关键字提供匹配的条目；或者条目拒绝搜索关键字（假未命中），尽管它本应当匹配。

[0006] TCAM中的软错误比RAM中的软错误更具破坏性。虽然RAM中的软错误仅引起单个查找故障，但TCAM中的软错误可能引起许多不同的查找由于第一匹配语义而失败。这是因为搜索关键字的查找结果是该关键字匹配的第一条目的索引而发生。软错误引发TCAM中使用的许多已知的可靠性机制的最高故障率。

[0007] 无法容易地保护存储在TCAM中的数据。TCAM数据错误保护已被认为是复杂的过程，因为它要求在检测错误之前对TCAM条目进行读取和匹配。这些操作消耗集成电路带宽和功率。保护TCAM数据是合期望的，因为TCAM可以用于存储网络路由和其他信息。基于TCAM的设备可以执行在许多联网应用中使用的高速分组分类。为了支持分组分类，TCAM每秒钟执行数百万次关键字搜索操作，并且消耗大量功率。另外，TCAM在字长变化方面有灵活性差的问题。

[0008] 存在考虑到TCAM中的错误检测情境的许多出版物。US 8,473,832 B2描述了一种用于对TCAM中的多个录入的字执行互相排斥共享功能以便使用字比较和奇偶错误校验来检测数据损坏的方法。专利申请US2016/0283317 A1还公开了一种在TCAM中进行错误检测的方法，所述方法将计算的TCAM字校验和与从RAM中检索的匹配查询的校验和的存储值进行比较。在US 9,170,880 B1中提出的在TCAM搜索期间进行错误检测的方法包括：在TCAM中生成并且存储纠错码（ECC）和数据，为搜索关键字生成ECC，以及通过使用具有附带ECC的搜索关键字来检测存储数据中的任何错误。

[0009] 诸如纠错码之类的传统方法难以应用于TCAM。也就是说，大多数TCAM错误检测和校正方案要求对TCAM电路进行硬件修改。一种不要求对TCAM电路进行硬件改变就可以在搜索过程期间检测和修复错误的软件方法是在论文“TCAMChecker: A Software Approach to the Error Detection and Correction of TCAM-Based Networking Systems”（发表在网络和系统管理杂志（Journal of Network and Systems Management）中，21（3），2013年9月，DOI：10.1007/s10922-012-9238-0）中提出的解决方案。

发明内容

[0010] 本发明的目标是要提供一种用于检测错误、特别是可能出现在TCAM中的数据完整性错误和/或寻址错误和/或搜索错误的方法。

[0011] 该目标是利用一种用于在三元内容可寻址存储器TCAM中优选实时地进行错误检测的方法来实现的，其中错误检测利用在指定的输入地址处的读取操作来发起，其中根据本发明，提供了附加的随机存取存储器RAM，其中所述RAM具有与TCAM相同数量的位置，其中在两个存储器TCAM和RAM中，各自由数据和掩码组成的对应读取数据条目被放置在相同的地址位置处，并且其中在由输入地址指向的位置处执行从TCAM和RAM的数据和掩码读取操作，并且在第一校验阶段中，将在由输入地址指向的位置处从TCAM读取的所述数据和掩码与在由相同输入地址指向的位置处从RAM读取的数据和掩码进行比较，并且如果第一校验阶段的结果是正确的，则执行TCAM搜索阶段，否则执行数据恢复校验，其之后是数据刷新，对存储在TCAM和RAM两者中所述输入地址处的数据条目的第二读取，并且执行第二校验阶段，其中第二阶段执行从TCAM和RAM两者读取的数据和掩码的比较，并且其中TCAM搜索阶段使用从RAM读取的数据作为输入搜索关键字，并且作为输出返回TCAM匹配向量和/或单个TCAM地址，并且其中TCAM匹配校验在TCAM匹配向量的情况下校验TCAM搜索的结果（即来自TCAM匹配向量的地址所指向的标志）是否为二进制1，或者在非匹配（假）的情况下，校验在TCAM地址校验中校验的TCAM单个地址，并且如果TCAM地址是比所述输入地址低的地址，则执行在所述TCAM地址处的TCAM读取，并且如果在TCAM搜索验证中，在TCAM地址处读取的TCAM数据与在RAM处读取的数据相同，并且其中优选地，所述方法移动到由擦洗机制（scrubbing mechanism）提供的下一个输入地址，并且可以重复整个提议的错误检测方法。

[0012] 优选地，可以提供使用数据条目校验和比较的TCAM和RAM低存储器带宽需求过程的校验和阶段。

[0013] 优选地，可以提供使用数据条目校验和比较的TCAM和RAM高存储器带宽需求过程的校验和阶段，所述过程包括纠错码或散列算法。

[0014] 如果校验结果为假，则可以提供数据恢复校验，其升起数据完整性错误标志。

[0015] 如果校验结果为假，则可以提供第二校验阶段，其升起数据完整性错误标志。

[0016] 可以执行TCAM匹配校验，如果校验的结果是二进制1，则所述TCAM匹配校验完成错误检测，否则，它升起搜索错误标志。

[0017] 可以执行TCAM搜索验证，如果在TCAM地址处读取的数据的比较结果没有在RAM中提供匹配，则所述TCAM搜索验证升起搜索错误标志。

[0018] 此外，该目标利用一种用于在三元内容可寻址存储器TCAM中优选实时地进行错误检测的方法来实现，其中根据本发明，提供了附加的随机存取存储器RAM，其中所述RAM具有与TCAM相同数量的位置，其中，在两个存储器TCAM和RAM中，各自由数据和掩码组成的对应读取数据条目被放置在相同的地址位置处，并且其中通过从TCAM_SEARCH命令输出的所接收输入地址来发起错误检测，其中存储器读取对存储在TCAM和/或RAM中的所述输入地址处的数据和掩码进行读取，并且其中校验对所述数据和掩码的完整性进行校验，并且如果没有发现错误，则执行关键字匹配校验，其中输入搜索关键字与位于TCAM和/或RAM存储器中所述地址处的数据和掩码进行比较。

[0019] 优选地，特别是在TCAM的低可用带宽的情况下，在RAM处执行数据值和掩码的读取，或者特别是如果TCAM的可用带宽高，则在TCAM处执行存储器读取。

[0020] 可以执行数据和掩码的完整性校验。

[0021] 可以执行关键字匹配校验，并且如果在输入的搜索关键字与从地址读取的数据和掩码之间不存在匹配，则将指示搜索错误。

[0022] 根据本发明，使用具有与TCAM相同数量的条目的附加RAM，其中所述附加RAM实现擦洗机制、特别是在运行时期间执行的擦洗机制。另外，实现了运行时数据完整性校验机制和运行时搜索完整性校验机制，所述运行时数据完整性校验机制可以在读取数据时用信号通知存储在TCAM中的数据的完整性。

[0023] 本发明描述了一种方法，所述方法可以用于在运行时期间检测可能出现在TCAM中的软错误和搜索错误。所提议的方法可以比先前已知的技术更可靠地检测错误。根据本发明的方法由三个主要特征表征：数据完整性和搜索类型的错误两者的检测；考虑不同的搜索机制输出；以及在具有不同存储器带宽的TCAM中的适用性。此外，本发明使用附加的RAM存储器。RAM存储器需要与主TCAM存储器具有相同数量的位置。在两个存储器TCAM和RAM中，由数据和掩码组成的对应条目被放置在相同的地址位置处。从TCAM存储器的每个读取操作自动触发从RAM中的相同地址的读取和基于存储在RAM中的附加数据的数据完整性校验机制。

[0024] 为了实现上面提及的目标，所提出的TCAM错误检测方法提供了取决于以下各项的若干种实现方式：TCAM可用带宽；执行的主TCAM命令，即读取或搜索命令；以及考虑的搜索输出，即搜索向量和/或单个地址。在前两个本发明实施例中，在分别单独地考虑过程的内部搜索操作的不同输出（即搜索向量或单个地址）的情况下，表示了在通过TCAM主读取命令进行擦洗期间可以被激活的过程。第三实施例表示通过TCAM主搜索命令激活的本发明的实现方式。

[0025] 所呈现的发明的第一实施例表示一种实时TCAM错误检测方法，所述方法通过给定的输入地址来发起，并且由作为所述方法的内部TCAM搜索阶段结果的匹配向量来表征。它使用附加的RAM并且在两个存储器中的相同输入地址处读取数据条目，并且然后取决于TCAM可用带宽使用不同的数据完整性校验过程对它们进行比较。如果需要，则执行数据恢复，其包括从两个存储器刷新和再次读取的数据的数据完整性校验。所述方法以TCAM搜索阶段继续，所述TCAM搜索阶段使用先前从RAM或TCAM读取的数据作为输入搜索关键字，并且它作为输出返回TCAM匹配向量。然后，如果来自由给定输入地址索引的输出TCAM匹配向量的标志的值被发现为“1”，则所述方法完成，否则它升起搜索错误标志。

[0026] 在所呈现的发明的第二实施例中，描述了一种实时TCAM错误检测方法，所述方法通过给定的输入地址来发起，并且由作为所述方法的内部TCAM搜索阶段结果的单个地址来表征。它使用附加的RAM，并且执行与关于先前实施例所述相同的阶段——其包括在两个存储器中读取数据条目、使用不同的数据完整性校验对它们进行比较、数据恢复和重复的数据完整性校验（如果需要它的话）。所述方法以TCAM搜索阶段继续，所述TCAM搜索阶段使用从RAM读取的数据作为输入搜索关键字，并且它返回单个地址。然后，给定的输入地址与TCAM搜索阶段的输出进行比较，并且在错误匹配的情况下，校验TCAM地址是否为TCAM中比所述输入地址更高的地址。如果该校验的结果为真，则所述方法升起搜索错误标志。否则，执行在该地址处的TCAM读取，而如果在TCAM地址处读取的数据提供了针对先前搜索的关键字的匹配，则所述方法移动到由擦洗机制提供的下一个输入地址，并且可以重复整个提议的错误检测方法。如果先前TCAM_搜索校验的结果为假，或者针对从RAM读取的数据的TCAM数据校验的结果为假，则所述方法升起搜索错误标志。

[0027] 本发明的第三实施例描述了在TCAM中实时地进行错误检测的方法，所述方法通过从TCAM主搜索命令接收的输入地址输出来发起，所述TCAM主搜索命令读取被存储在TCAM和/或RAM中的输入地址处的数据和掩码——这取决于TCAM可用的存储器带宽，并且校验数据和掩码的完整性。完整性校验使用简单或更复杂的方案——这取决于TCAM可用的存储器带宽，并且如果没有发现错误，则所述方法执行对TCAM主搜索命令的输入搜索关键字与在该过程中读取的条目的比较。

[0028] 本发明还涉及一种用于在上述方法中使用的存储器设备，其中所述存储器设备包括优选实时的三元内容可寻址存储器TCAM和附加的随机存取存储器RAM，其中所述RAM具有与TCAM相同数量的位置，其中在两个存储器TCAM和RAM中，各自由数据和掩码组成的对应读取数据条目可以放置在相同的地址位置处。

[0029] 此外，本发明涉及一种设备，例如联网设备，特别是诸如路由器或交换机之类的高速联网设备，或者包括这样的存储器设备的基于TCAM的高速搜索引擎。

附图说明

[0030] 在下文中，为了进一步展示本发明，讨论了如附图中所示的说明性且非限制性的实施例，附图示出了：图1表示搜索过程的示意性一般原理以及在完整性校验过程中使用的附加RAM。

[0031] 图2表示当内部搜索操作的结果是匹配向量时本发明的第一实施例的图表图解。

[0032] 图3表示当内部搜索操作的结果是地址时本发明的第二实施例的图表图解。

[0033] 图4表示当请求TCAM_SEARCH命令时本发明的第三实施例的图表图解。

具体实施方式

[0034] 本发明描述了一种方法，所述方法可以用于在运行时期间检测可能出现在TCAM存储器中的错误。所述方法由三个方面表征：数据完整性和搜索错误两者的检测；考虑不同的搜索机制输出；以及对各种可用存储器带宽的适用性。根据第一特征，存在所提议的方法可以检测的两种类型的错误：数据完整性错误，其指代存储数据的完整性和寻址错误；以及搜索错误。除了这些类型的错误之外，所提议的方法区分搜索输出的两种情况：在第一种情况下，传递在TCAM存储器阵列中发现的搜索关键字的多次命中，而在第二种情况下，搜索机制的输出是单个地址。在第一种情况下，优先级规则用于对最终输出地址进行编码。最终，第三特征涉及所提议的方法的实现方式，该实现方式支持对可用存储器带宽的优化解决方案。在可用存储器带宽低的条件下，所述方法可以实现由校验和/奇偶校验位操作所支持的数据和地址的简单直接比较，而在高存储器带宽的条件下，所提议的方法可以实现更复杂的方案，诸如散列或纠错码（ECC）算法。

[0035] 除了本发明的这三个方面之外，所述方法还要求牵涉到附加的RAM存储器。RAM存储器需要与主TCAM存储器具有相同数量的位置。在TCAM和RAM存储器两者中，由数据和掩码组成的对应条目被放置在相同的地址位置处。

[0036] 解释了在提议的错误检测方法中采用的以下TCAM和RAM命令：TCAM_DATA_READ（地址）命令将返回被存储在TCAM存储器中由“地址”指向的位置处的“数据”。该命令的输出是“tcam_data”。

[0037] TCAM_MASK_READ（地址）命令将返回被存储在TCAM存储器中由“地址”指向的位置处的“掩码”。该命令的输出是“tcam_mask”。

[0038] TCAM_DATA_READ和TCAM_MASK_READ命令可以被认为是原子操作，并且可以被记为TCAM_READ，并且其输出被记为“tcam_data&mask”。从TCAM仅读取“数据”的值或者仅读取“掩码”的值是没有意义的，因为除非在TCAM中没有存储具有值“X”的位的情况，否则有一个而没有另一个就无法提供关于TCAM位值的信息。

[0039] TCAM_DATA_WRITE（地址）命令将把“数据”存储在TCAM存储器中由“地址”指向的位置处。

[0040] TCAM_MASK_WRITE（地址）命令将把“掩码”存储在TCAM存储器中由“地址”指向的位置处。

[0041] TCAM_DATA_WRITE和TCAM_MASK_WRITE命令可以被认为是原子操作，并且被记为TCAM_WRITE，因为在TCAM存储器中写入“数据”而不同样写入“掩码”是没有意义的，这是因为如果“数据”和它们对应的“掩码”不一致那么搜索机制就无法正确地工作。

[0042] 出自“数据”和“掩码”可以采用的4个组合的仅3个组合允许TCAM位。TCAM位仅可以取3个值“0”、“1”和“X”。如果TCAM位值为“X”，则相应位与“关键字”的对应位的比较将返回匹配，即使“关键字”位为“0”或“1”亦如此。“数据”  “掩码”  TCAM位值
0            0            X （无所谓）
0            1            0
1            0            1
1            1            不允许
TCAM_SEARCH（关键字）命令将返回指向从0开始的第一位置的“tcam_address”，对于该第一位置，由存储在相应位置处的“掩码”指示的“关键字”的位与由存储在相应位置处的“掩码”所指示的相应位置处存储的“数据”位相匹配。

[0043] TCAM_SEARCH（关键字）命令也可以返回向量“tcam_match”，其具有等于TCAM的位置数量的宽度。“tcam_match”向量的每个位可以被认为是一个标志，该标志指示对应的TCAM位置作为对搜索操作的响应而提供命中。

[0044] 对于RAM，存在可以寻址的2个命令：RAM_READ（地址）命令将返回存储在附加RAM存储器中由“地址”指向的位置处的“数据”和“掩码”。该操作的输出被记为“ram_data&mask”。

[0045] RAM_WRITE（地址）命令将把“数据”和对应的“掩码”存储在附加RAM存储器中由“地址”指向的位置处。

[0046] 此外，定义了用于使条目无效和刷新条目的两个复杂命令：INVALIDATE（地址）命令将以在搜索过程中将不考虑所述位置的方式删除存储在TCAM和RAM存储器中由“地址”指向的位置处的信息/使该信息无效。

[0047] REFRESH（地址）命令将复原被存储在TCAM和RAM存储器中由“地址”指向的位置处的信息，使得将在搜索过程中考虑该位置。

[0048] 上面提到的TCAM_SEARCH（关键字）命令由一般的TCAM搜索机制规则表征。在以下文本中更详细地解释了TCAM搜索过程的主要特性。

[0049] 图1表示RAM和TCAM存储器阵列的总体方案，以及在TCAM搜索过程中牵涉的主要组件。TCAM存储器110中的每个位置在RAM存储器115中具有对应的位置，该对应的位置可以使用相同的地址105来访问。

[0050] 术语“存储器阵列”一般可以指代TCAM或RAM。每个存储器（TCAM，RAM）可以看作是可寻址的位置阵列。每个位置可以存储具有固定宽度的数据。TCAM_SEARCH指代在TCAM中的搜索操作。术语“存储器阵列搜索”指代在任何存储器中的搜索操作。

[0051] 图1示出了TCAM搜索270机制。TCAM搜索机制的输入数据由搜索关键字100给出。通过对照TCAM存储器110中的存储数据表而应用所述搜索关键字100，来发起TCAM搜索270机制。数据搜索的目的是要确定存储器110阵列中的任何数据是否与搜索关键字100完全匹配，并且返回与搜索关键字100匹配的数据的地址150。

[0052] TCAM存储器110中的存储数据表包含存储在不同地址上的数据TCAM数据1、TCAM数据2、…、TCAM数据m。在TCAM存储器阵列中，具有最低地址的条目（数据）具有最高优先级。

[0053] TCAM存储器110表示由存储数据条目组成的字阵列。每个存储数据具有相关联的匹配线130，该相关联的匹配线130指示搜索关键字100与存储数据TCAM数据1、TCAM数据2、…、TCAM数据m是相同的（匹配情况），还是不同的（失配情况）。匹配线130与匹配寄存器
120中的对应位耦合。如果存在匹配，则二进制1将被放置在匹配寄存器120中，或者在失配情况下为二进制0。匹配线130被馈送到编码器140，编码器140生成对应于处于匹配状态的匹配线130的匹配位置。

[0054] 编码器140用在TCAM存储器110实现方式中，在该实现方式中预期匹配寄存器120中的单个匹配。更具体地，为搜索关键字100执行的TCAM搜索270机制将返回TCAM地址150，该TCAM地址150是从TCAM存储器阵列中的地址零开始的第一位置，对于该第一位置，搜索关键字100的位与被存储在相同的相应地址位置处并且由存储在TCAM 110中的相应位置处的掩码所指示的数据位相匹配。

[0055] 在TCAM搜索270机制生成多个匹配（即搜索-匹配向量）的TCAM存储器阵列实现方式中，可以使用优先级编码器140。这样的优先级编码器140的目的是要解析多个匹配，并且对来自搜索-匹配向量135的最佳匹配进行编码。在这种情况下，对于TCAM 110中的每个数据匹配，二进制1将被放置在匹配寄存器120中。一旦搜索了TCAM存储器阵列，优先级编码器140就从匹配向量135中确定最高优先级匹配，并且将它的地址150位置编码成二进制格式。
根据先前描述的，TCAM搜索机制返回向量TCAM匹配，该TCAM匹配具有与TCAM 110的长度相等的宽度。TCAM匹配向量的每一位可以被认为是标志，该标志指示对应的TCAM位置作为对搜索操作的响应而提供命中。

[0056] 在优先级编码器140存在的情况下，如果不存在匹配，则TCAM搜索270机制将指示没有发现输入关键字。

[0057] 基于上面对TCAM存储器中的搜索如何工作的详细描述，在下文中对描述所呈现的发明的主要阶段的所提议的TCAM错误检测方法的三个实施例进行描述。

[0058] 图2描述了根据本发明的方法的第一实施例。特别地，图2示出了所提议的TCAM错误检测方法的状态图表，该方法考虑了TCAM_SEARCH阶段270的结果是匹配向量输出的情况。该方法使用附加的RAM存储器阵列，其具有与TCAM存储器阵列相同数量的位置。在两种存储器TCAM和RAM中，由数据及其对应的掩码组成的对应条目被放置在相同的地址位置处。

[0059] 检测方法以TCAM_READ和RAM_READ 210命令开始，根据TCAM_READ和RAM_READ 210命令，在TCAM和附加RAM存储器的指定输入地址200处执行读取操作。这些读取操作牵涉优选以原子方式执行的三个操作，即操作TCAM_MASK_READ、TCAM_DATA_READ和RAM_READ。在从两个存储器读取所述数据和掩码之后，跟随着校验220阶段。在该校验阶段220中，将在输入地址200所指向的位置处从TCAM读取的数据和掩码与在相同输入地址200所指向的位置处从RAM读取的数据和掩码进行比较。

[0060] 该简单校验阶段220可以包括奇偶校验位或校验和检查，其优选地在当仅低带宽的TCAM和RAM可用的时候的情况下执行。然而，如果可用的TCAM带宽高，为了节省RAM资源，在校验阶段220中实现附加的、更复杂的数据校验方法（如纠错码（ECC）算法或散列算法）是适当的，所述算法能够在运行时期间（例如在使用TCAM的IP核的运行时期间）检测和发现错误。如果校验操作220的结果是肯定的（“是”），则该方法以TCAM_SEARCH 270继续，否则（“否”）执行恢复校验230。

[0061] 在恢复校验230产生为假的比较结果的情况下，升起数据完整性错误标志265。否则，在完成恢复的地方执行数据REFRESH操作240。例如，存储在TCAM中的数据在其受到SEU（单个事件扰乱）影响的情况下被恢复，这使得一位或多位数据改变它们的值。刷新操作240在两个存储器中实现。

[0062] 取决于实现方式，可以完成存储在TCAM中的数据和掩码与存储在RAM中的数据和掩码之间的比较。或者，例如，当数据和掩码被写入TCAM中时，可以完成在被应用于从TCAM读取的数据和掩码的ECC/奇偶校验/CRC与被存储在RAM中的ECC/奇偶校验/CRC的值之间的比较。

[0063] 然后，该方法再次在指定地址200处执行TCAM和RAM的TCAM_READ和RAM_READ操作250。在校验操作260中，比较在输入地址200所指向的位置处从TCAM和RAM读取的数据和掩码。如果校验操作260的结果是否定的（“否”），则升起数据完整性错误标志265，否则，该方法以TCAM_SEARCH 270继续。阶段265中的两种类型的完整性错误指代存储数据的完整性和寻址错误。校验以与阶段220中相同的方式完成。

[0064] 如果阶段260中的结果是正确的（“是”），则具有来自RAM或TCAM存储器的数据的方法去往进行TCAM_SEARCH的阶段270。在如图1中所描述的TCAM_SEARCH 270中，基于由从RAM或TCAM存储器读取的数据组成的关键字以及在校验操作220或260之后获得的关键字，执行TCAM存储器阵列搜索。该实施例考虑作为TCAM_SEARCH 270的结果接收到TCAM匹配向量275的情况。TCAM_match 280校验TCAM_SEARCH 270的结果（即由来自TCAM_match向量275的地址200指向的标志）是否为二进制1，并且如果它是二进制1，则该方法移动到由擦洗机制提供的下一个输入地址286，并且可以重复整个提议的错误检测方法，否则，升起搜索错误标志285。

[0065] 图3表示本发明的第二实施例的状态图表，本发明的第二实施例公开了TCAM_SEARCH 270阶段的输出是单个TCAM地址300的情况。

[0066] 如在根据图2的先前实施例中所描述的，对应的条目被放置在TCAM和RAM存储器中的相同地址位置处。检测方法从两个存储器读取输入地址200处的数据和掩码，其之后是校验220阶段，以便比较从TCAM存储器和RAM存储器读取的数据和掩码。在TCAM和RAM 210中的读取牵涉三个原子操作，即操作TCAM_MASK_READ、TCAM_DATA_READ和RAM_READ。当TCAM和RAM低存储器带宽可用时，应用包括奇偶校验位或校验和检查的该简单校验220阶段。然而，如果可用的TCAM和RAM带宽是高的，那么为了节省RAM资源，可以在校验阶段220中实现更复杂的数据校验方法（如ECC或散列算法），所述数据校验方法能够在运行时期间检测和发现错误。

[0067] 当校验220的结果是肯定的时，该方法以TCAM_SEARCH 270继续，否则执行恢复校验230。如果恢复校验230的结果为假，则升起数据完整性错误标志265。否则，在数据刷新操作240中执行数据恢复。在恢复过程之后，该方法在指定地址200处重复TCAM和RAM操作的读取250。在校验260操作中，再次比较在输入地址200所指向的位置处从TCAM和RAM存储器读取的数据和掩码，并且如果结果是否定的，则升起数据完整性错误标志265，否则，该方法以TCAM_SEARCH 270继续，其中将从RAM或TCAM存储器取得的数据读取作为输入搜索关键字。

[0068] 如果TCAM_SEARCH 270的结果——TCAM地址300——与给定的输入地址200相同，则校验310引导该方法继续由擦洗机制提供的下一个输入地址286的处理。如果TCAM_SEARCH 270的输出——TCAM地址300——表示存储器阵列中相对于给定输入地址200的较高地址，则该方法指示搜索错误285。否则，将在TCAM地址300上执行TCAM读取操作330。TCAM_SEARCH结果验证340正在校验条件，即在TCAM地址300处发现的数据和掩码是否可以为用作TCAM_SEARCH 270的输入的RAM或TCAM数据266提供匹配。如果该校验的结果是“否”，则指示搜索错误285。否则，该方法移动到由擦洗机制提供的下一个输入地址286，并且可以重复整个提议的错误检测方法。

[0069] 图4中示出了本发明的第三实施例，其描绘了根据本发明的方法的更简单实现方式的细节，该方法通过具有输入关键字405的请求的TCAM_SEARCH命令400来发起。所述输入关键字405表示需要搜索的数据，例如MAC地址、模式等。如图4中所图示的，错误检测过程通过作为执行的TCAM_SEARCH操作400的输出被接收的存储器地址410来发起，并且更具体地，它表示TCAM存储器阵列中提供输入关键字405和对应TCAM条目的请求匹配的第一位置。接下来，如果在TCAM中发现输入关键字，则存储器读取420取决于可用TCAM带宽而从TCAM和/或从RAM存储器读取位于存储器地址410处的数据和掩码。在低可用带宽的情况下，在RAM处执行存储器读取操作420，否则，如果可用带宽是高的，则在TCAM和RAM处执行存储器读取420。给定的过程以数据和掩码的完整性校验430继续。如果可用的存储器带宽是高的，则可以实现更复杂的数据校验方法，即纠错码（ECC）算法或散列算法，所述方法能够在运行时中检测和发现错误。如果发现数据完整性中的错误，则其将由数据完整性错误450指示，否则执行关键字匹配校验440，其中将输入搜索关键字405与位于TCAM和/或RAM存储器中的地址
410处的数据和掩码进行比较。如果输入搜索关键字405与数据和掩码之间不存在匹配，则将指示搜索错误460。

[0070] 已经在详细的实施例描述和图表内呈现了本发明，所述详细的实施例描述和图表说明了指定的过程和关系的实现方式。所描述的过程可以实现在诸如用于使能实现快速路由和分组分类的更快地址查找的路由器之类的高速联网设备中，或者在它可以用于建立和查找MAC地址表的交换机中。另外，所呈现的发明可以用在数据压缩、模式匹配和人工智能应用中的其他基于TCAM的高速搜索引擎中。本文中描述的代表性过程可以在包括ASIC、FPGA等的集成电路上实现。然而，本发明容许关于上面讨论的给定数量的实施例的修改和替代实现方式。例如，实施例中描述的操作的进一步重新组合或重新排序不脱离本发明的范围。