公开(公告)号：US07529746B2

公开(公告)日：2009-05-05

申请号：US11523958

申请日：2006-09-19

Applicant: Michael E. Ichiriu ,  Martin Fabry ,  Larry A. Wall ,  Sanjay Sreenath

Inventor： Michael E. Ichiriu ,  Martin Fabry ,  Larry A. Wall ,  Sanjay Sreenath

IPC: G06F17/30

CPC classification number: G06F17/30985 ,  Y10S707/99936

Abstract: A content search circuit for determining whether an input string matches one or more of a plurality of regular expressions, the content search circuit including an instruction memory for storing a plurality of microprograms, each microprogram embodying a corresponding one of the regular expressions, a control circuit having an input to receive the input string, and having a number of outputs, and a plurality of search engines, each having a first input coupled to a corresponding output of the control circuit and having a second input coupled to the instruction memory, wherein each search engine is selectable to execute any of the microprograms stored in the instruction memory to search the input string for any of the regular expressions embodied in the microprograms.

Abstract translation: 一种用于确定输入串是否匹配多个正则表达式中的一个或多个的内容搜索电路，所述内容搜索电路包括用于存储多个微程序的指令存储器，体现相应的正则表达式的每个微程序，控制电路 具有接收输入串的输入，以及具有多个输出的多个搜索引擎，以及多个搜索引擎，每个搜索引擎具有耦合到控制电路的对应输出的第一输入，并且具有耦合到指令存储器的第二输入，其中每个 可以选择搜索引擎来执行存储在指令存储器中的任何微程序，以搜索输入字符串中的微程序中体现的任何正则表达式。

公开(公告)号：US07440304B1

公开(公告)日：2008-10-21

申请号：US11780391

申请日：2007-07-19

Applicant: Sunder Rathnavelu Raj

Inventor： Sunder Rathnavelu Raj

IPC: G11C15/00

CPC classification number: G11C15/00 ,  G06F17/30985 ,  Y10S707/99932 ,  Y10S707/99933 ,  Y10S707/99943 ,  Y10S707/99945 ,  Y10S707/99948

Abstract: A method and apparatus for multiple string searching using a ternary content addressable memory. The method includes receiving a text string having a plurality of characters and performing an unanchored search of a database of a stored patterns matching one or more characters of the text string using a state machine, wherein the state machine comprises a ternary content addressable memory (CAM) and wherein the performing comprises comparing a state and one of the plurality of characters with contents of a state field and a character field, respectively, stored in the ternary CAM. In various embodiments, one or more of the following search features may be supported: exact string matching, inexact string matching, single character wildcard matching, multiple character wildcard matching, case insensitive matching, parallel matching and rollback.

Abstract translation: 一种使用三元内容可寻址存储器进行多字符串搜索的方法和装置。 该方法包括接收具有多个字符的文本串，并且使用状态机执行与文本串的一个或多个字符匹配的存储模式的数据库的非存储搜索，其中，所述状态机包括三进制内容可寻址存储器（CAM ），并且其中所述执行包括将所述多个字符中的状态与所述一个字符分别与存储在所述三元CAM中的状态字段和字符字段的内容进行比较。 在各种实施例中，可以支持以下搜索特征中的一个或多个：精确字符串匹配，不精确字符串匹配，单字符通配符匹配，多字符通配符匹配，不区分大小写匹配，并行匹配和回滚。

公开(公告)号：US07433217B1

公开(公告)日：2008-10-07

申请号：US12006972

申请日：2008-01-07

Applicant: Dinesh Maheshwarl

Inventor： Dinesh Maheshwarl

IPC: G11C15/00

CPC classification number: G11C15/04

Abstract: A CAM cell (200) can include a compare section (206) and a configuration section (208). In a binary mode of operation, two compare data values can be driven on value lines VL1 to VL4 (216-0 to 216-3) for comparison against two stored data values. In a ternary mode of operation, one compare data value can driven on two of the value lines, while the other two value lines can be forced to a potential unrelated to a compare data value allowing for dynamic configuration between binary and ternary modes of operation.

Abstract translation: CAM单元（200）可以包括比较部分（206）和配置部分（208）。 在二进制操作模式下，可以在值线VL1至VL4（216 - 0至216 - 3）上驱动两个比较数据值，以便与两个存储的数据值进行比较。 在三元操作模式下，一个比较数据值可以在两个值行上驱动，而另外两个值行可以被强制为与允许二进制和三进制操作模式之间的动态配置的比较数据值无关的电位。

公开(公告)号：US07426518B2

公开(公告)日：2008-09-16

申请号：US10402887

申请日：2003-03-28

Applicant: Srinivasan Venkatachary ,  Pankaj Gupta

Inventor： Srinivasan Venkatachary ,  Pankaj Gupta

IPC: G06F17/30

CPC classification number: H04L45/00 ,  G06F17/30625 ,  H04L45/7457 ,  Y02D10/45 ,  Y10S707/99942 ,  Y10S707/99943

Abstract: A method, apparatus, and storage medium product are provided for forming a forwarding database, and for using the formed database to more efficiently and quickly route packets of data across a computer network. The forwarding database is arranged into multiple sub-databases. Each sub-database is pointed to by a pointer within a pointer table. When performing a longest-match search of incoming addresses, a longest prefix matching algorithm can be used to find the longest match among specialized “spear prefixes” stored in the pointer table. After the longest spear prefixes are found, the pointer table will direct the next search within a sub-database pointed to by that spear prefix. Another longest-match search can be performed for database prefixes (or simply “prefixes”) within the sub-database selected by the pointer. Only the sub-database of interest will, therefore, be searched and all other sub-databases are not accessed. Using a precursor pointer and a sub-database of optimally bounded size and number ensures power consumption be confined only to the sub-database being accessed, and that higher speed lookup operations can be achieved since only the sub-database of interest is being searched.

Abstract translation: 提供了一种形成转发数据库的方法，装置和存储介质产品，并且用于使用形成的数据库更有效地并且快速地通过计算机网络路由数据包。 转发数据库被安排成多个子数据库。 每个子数据库由指针表中的指针指向。 当对输入地址执行最长匹配搜索时，可以使用最长的前缀匹配算法来找到存储在指针表中的专用“矛前置”之间的最长匹配。 在找到最长的矛前缀之后，指针表将指示由该矛前缀指向的子数据库中的下一个搜索。 可以在由指针选择的子数据库中的数据库前缀（或简称“前缀”）执行另一最长匹配搜索。 因此，仅搜索感兴趣的子数据库，并且不会访问所有其他子数据库。 使用前导指针和具有最大有界大小和数量的子数据库，确保功耗仅限于正在访问的子数据库，并且可以实现更高速度的查找操作，因为仅搜索感兴趣的子数据库。

公开(公告)号：US07382637B1

公开(公告)日：2008-06-03

申请号：US11022267

申请日：2004-12-24

Applicant: Sunder R. Rathnavelu ,  David W. Ng ,  Jose P. Pereira

Inventor： Sunder R. Rathnavelu ,  David W. Ng ,  Jose P. Pereira

IPC: G11C15/00

CPC classification number: G11C15/00

Abstract: A content addressable memory device including a memory to store a searchable database, a search circuit, and a first-in-first-out storage circuit. The search circuit generates a plurality of address values that correspond to unoccupied storage locations within the memory, and the plurality of address values are queued within the first-in-first-out storage circuit to enable the address values to be read in succession by an external device.

Abstract translation: 一种内容可寻址存储装置，包括存储可搜索数据库的存储器，搜索电路和先进先出存储电路。 搜索电路产生对应于存储器内的未占用存储位置的多个地址值，并且多个地址值在先入先出存储电路中排队，以使地址值能够依次读取 外部设备。

公开(公告)号：US07349332B1

公开(公告)日：2008-03-25

申请号：US10613347

申请日：2003-07-02

Applicant: Varadarajan Srinivasan ,  Sandeep Khanna

Inventor： Varadarajan Srinivasan ,  Sandeep Khanna

IPC: G01R31/08 ,  G06F11/00 ,  G08C15/00 ,  H04J1/16 ,  H04J3/14 ,  H04L1/00 ,  H04L12/26

CPC classification number: H04L47/10 ,  H04L45/7453 ,  H04L47/22 ,  H04L47/50 ,  H04L47/56

Abstract: A traffic management processor for processing different types of traffic flows includes a departure time calculator (DTC) circuit for calculating a departure time for each packet received, a content addressable memory (CAM) device coupled to the DTC circuit and having a plurality of rows, each row including a first portion for storing the departure time for a corresponding packet and including a second portion for storing a bit indicating a traffic type for the packet, and compare logic coupled to the CAM device and configured to determine which of the departure times stored in the CAM device is the earliest.

Abstract translation: 用于处理不同类型的业务流的流量管理处理器包括：用于计算接收的每个分组的出发时间的出发时间计算器（DTC）电路，耦合到DTC电路并具有多个行的内容可寻址存储器（CAM） 每行包括用于存储相应分组的出发时间的第一部分，并且包括用于存储指示分组的业务类型的比特的第二部分，以及耦合到所述CAM设备并被配置为确定所存储的出发时间中的哪一个 在CAM设备中是最早的。

公开(公告)号：US20080071779A1

公开(公告)日：2008-03-20

申请号：US11523881

申请日：2006-09-19

Applicant: M. Neil N. Mammen ,  Martin Fabry ,  Sanjay Sreenath ,  Minh G. Lieu

Inventor： M. Neil N. Mammen ,  Martin Fabry ,  Sanjay Sreenath ,  Minh G. Lieu

IPC: G06F17/30

CPC classification number: G06F17/30516

Abstract: A content search system for determining whether a plurality of input strings each belonging to any one of a number of different process flows matches one or more of a plurality of regular expressions, including a search circuit for searching the input strings for the regular expressions and a data management unit including a control circuit having an input to receive the plurality of input strings, wherein each input string has an associated flow identification (ID) value, a packet queue having a number of storage locations for storing the input strings, and a flow engine that forwards a selected input string from the packet queue to the search circuit.

Abstract translation: 一种内容搜索系统，用于确定属于多个不同处理流程中的任何一个的多个输入串是否匹配多个正则表达式中的一个或多个，包括用于搜索正则表达式的输入字符串的搜索电路和 数据管理单元，包括具有用于接收多个输入串的输入的控制电路，其中每个输入串具有相关联的流标识（ID）值，具有用于存储输入串的多个存储位置的分组队列，以及流 引擎，其将选择的输入串从分组队列转发到搜索电路。

公开(公告)号：US20080071765A1

公开(公告)日：2008-03-20

申请号：US11524351

申请日：2006-09-19

Applicant: Michael E. Ichiriu ,  Martin Fabry ,  Larry A. Wall ,  Sanjay Sreenath

Inventor： Michael E. Ichiriu ,  Martin Fabry ,  Larry A. Wall ,  Sanjay Sreenath

IPC: G06F17/30

CPC classification number: G06F17/30985

Abstract: A network system includes a content search system for determining whether an input string matches a regular expression comprising an exact pattern and an inexact pattern, the content search system including a first search circuit dedicated to perform an exact string match operation to determine whether the input string contains a first portion that matches the exact pattern, and a second search circuit dedicated to perform an inexact string match operation to determine whether the input string contains a second portion that matches the inexact pattern.

Abstract translation: 网络系统包括内容搜索系统，用于确定输入字符串是否匹配包含精确模式和不精确模式的正则表达式，内容搜索系统包括专用于执行精确字符串匹配操作的第一搜索电路，以确定输入字符串 包含匹配精确模式的第一部分和专用于执行不精确字符串匹配操作以确定输入字符串是否包含与不精确模式匹配的第二部分的第二搜索电路。

公开(公告)号：US07337267B1

公开(公告)日：2008-02-26

申请号：US10776441

申请日：2004-02-10

Applicant: Jose P. Pereira ,  Sunder R. Raj ,  David Ng

Inventor： Jose P. Pereira ,  Sunder R. Raj ,  David Ng

IPC: G06F12/00

CPC classification number: G11C15/00 ,  Y10S707/99936

Abstract: A hierarchical programmable-priority content addressable memory (CAM) system including first, second and third CAM devices. The first CAM device has a first priority number output and a first enable input. The second CAM device has a priority number input and an enable output coupled to the priority number output and the first enable input, respectively, of the first CAM device. The second CAM device also has a priority number output and an enable input. The third CAM device has a priority number input and an enable output coupled to the priority number output and the enable input, respectively, of the second CAM device.

Abstract translation: 包括第一，第二和第三CAM设备的分级可编程优先级内容可寻址存储器（CAM）系统。 第一CAM设备具有第一优先级号输出和第一使能输入。 第二CAM设备具有分别耦合到第一CAM设备的优先级编号输出和第一使能输入的优先级编号输入和使能输出。 第二CAM设备还具有优先级编号输出和使能输入。 第三CAM设备具有分别耦合到第二CAM设备的优先级编号输出和使能输入的优先级编号输入和使能输出。

公开(公告)号：US07319602B1

公开(公告)日：2008-01-15

申请号：US10883158

申请日：2004-07-01

Applicant: Varadarajan Srinivasan ,  Sandeep Khanna

Inventor： Varadarajan Srinivasan ,  Sandeep Khanna

IPC: G11C15/00 ,  G11C7/00

CPC classification number: G11C15/04 ,  G11C7/02 ,  G11C7/18

Abstract: A content addressable memory (CAM) device having CAM cells arranged in rows and columns. A plurality of first data line pairs extend along respective columns of the CAM cells. A plurality of second data line pairs extend along respective columns of the CAM array adjacent the first data line pairs, each second data line pair having a first and second constituent data lines that cross one another at a point along their lengths.

Abstract translation: 具有以行和列排列的CAM单元的内容可寻址存储器（CAM）装置。 多个第一数据线对沿着CAM单元的各个列延伸。 多个第二数据线对沿着与第一数据线对相邻的CAM阵列的相应列延伸，每个第二数据线对具有沿其长度的点彼此交叉的第一和第二组成数据线。