公开(公告)号：US07750675B2

公开(公告)日：2010-07-06

申请号：US11642012

申请日：2006-12-19

申请人： Ajay Dholakia ,  Jan Van Lunteren

发明人： Ajay Dholakia ,  Jan Van Lunteren

IPC分类号： H03K19/173 ,  H03K19/00

CPC分类号： G06F9/52

摘要： A method and computer program product for running state machines by the steps of running at least a first and a second state machine in parallel, observing at least the first state machine for at least one first synchronization rule, and changing the state of the second state machine when the first synchronization rule applies.

摘要翻译： 一种用于通过并行运行至少第一和第二状态机的步骤来运行状态机的方法和计算机程序产品，至少观察至少一个第一同步规则的第一状态机，并且改变第二状态的状态 当第一个同步规则适用时机器。

公开(公告)号：US07546281B2

公开(公告)日：2009-06-09

申请号：US11466472

申请日：2006-08-23

申请人： Everett A. Corl, Jr. ,  Clark D. Jeffries ,  Brooks Johnston ,  Plyush C. Patel ,  Jan Van Lunteren

发明人： Everett A. Corl, Jr. ,  Clark D. Jeffries ,  Brooks Johnston ,  Plyush C. Patel ,  Jan Van Lunteren

IPC分类号： G06N5/00

CPC分类号： G06F17/30289

摘要： A system for reducing the size of a database includes a memory in which the database configured in a ternary matrix array structure is stored. A processor executing at least one reduction algorithm scans the database tagging superfluous entries that are subsequently deleted. The tagging and deleting are done in such a way that the logical contents of the original database is unchanged, even though the size of the database is reduced.

摘要翻译： 用于减小数据库大小的系统包括其中存储以三元矩阵阵列结构配置的数据库的存储器。 执行至少一个还原算法的处理器扫描数据库标记随后被删除的多余条目。 标签和删除是以原始数据库的逻辑内容不变的方式完成的，即使减少了数据库的大小。

公开(公告)号：US06886073B2

公开(公告)日：2005-04-26

申请号：US10173994

申请日：2002-06-18

申请人： Gordon Taylor Davis ,  Clark Debs Jeffries ,  Jan Van Lunteren

发明人： Gordon Taylor Davis ,  Clark Debs Jeffries ,  Jan Van Lunteren

IPC分类号： G06F12/00 ,  G06F17/30 ,  H04L29/06

CPC分类号： H04L69/22 ,  H04L69/12

摘要： A method and system for storing and searching for prefixes for rules, such as filter rules, in a computer system is disclosed. The method and system include providing a ternary content addressable memory (TCAM). The filter rules use range(s) of values in at least one dimension and correspond to prefix(es). The range(s) are described by prefix(es). Some filter rules may intersect. The method and system include providing priorities for the filter rules. The priorities include at least one different priority for the filter rules that intersect. The method and system also include storing the prefixes in the TCAM in block(s) in an order based upon the priorities of the filter rules. In another aspect, the method and system include searching the TCAM for a longest prefix match for a key and searching an additional storage for an almost exact match for the key in parallel with the TCAM. In this aspect, the method and system include returning the longest prefix match having a lowest or a highest location if the longest prefix match is found in the TCAM and the almost exact match is not found in the additional storage.

摘要翻译： 公开了一种用于在计算机系统中存储和搜索诸如过滤规则的规则的前缀的方法和系统。 该方法和系统包括提供三元内容可寻址存储器（TCAM）。 过滤器规则使用至少一个维度中的值的范围，并对应于前缀（es）。 范围由前缀（es）描述。 一些过滤规则可能会相交。 该方法和系统包括为过滤规则提供优先级。 优先级至少包含与交叉的过滤规则的一个不同的优先级。 该方法和系统还包括基于过滤器规则的优先级按顺序将块中的前缀存储在块中。 在另一方面，所述方法和系统包括搜索TCAM对于密钥的最长前缀匹配，并且搜索附加存储器以与所述TCM并行的所述密钥几乎精确匹配。 在这方面，如果在TCAM中找到最长前缀匹配并且在附加存储器中找不到几乎精确的匹配，则该方法和系统包括返回具有最低或最高位置的最长前缀匹配。

公开(公告)号：US06381668B1

公开(公告)日：2002-04-30

申请号：US09194275

申请日：1998-11-20

申请人： Jan Van Lunteren

发明人： Jan Van Lunteren

IPC分类号： G06F1200

CPC分类号： G06F12/0607

摘要： For optimizing access to system memory having a plurality of memory banks, interleaving can be used when storing data so that data sequences are distributed over memory banks. The invention introduces an address-mapping method applying a table lookup procedure so that arbitrary, non-power-of-two interleave factors and numbers of memory banks are possible for various strides.

摘要翻译： 为了优化对具有多个存储体的系统存储器的访问，可以在存储数据时使用交织，使得数据序列分布在存储体上。 本发明引入了一种应用表查找过程的地址映射方法，使得任意的非功率二交织因子和多个存储体组对于各种步骤是可能的。

公开(公告)号：US20120158635A1

公开(公告)日：2012-06-21

申请号：US12970127

申请日：2010-12-16

申请人： Jan Van Lunteren

发明人： Jan Van Lunteren

IPC分类号： G06N5/02

CPC分类号： G06N5/025

摘要： A state machine includes a rule selector. The rule selector receives input data, and one or more transition rules. The one or more transition rules including a next state. The state machine also includes a character classifier communicatively coupled to the rule selector. The character classifier includes a plurality of base classes. The character classifier receiving the input data, and sending one or more of the plurality of base classes to the rule selector in response to receiving the input data. The rule selector selects one of the one or more transition rules in response to determining that the input data and one of the plurality of base classes correspond to the transition rule. The current state of the state machine is then set to the next state of the selected one of the one or more transition rules.

摘要翻译： 状态机包括规则选择器。 规则选择器接收输入数据，以及一个或多个转换规则。 一个或多个转换规则包括下一个状态。 状态机还包括通信地耦合到规则选择器的字符分类器。 字符分类器包括多个基类。 字符分类器接收输入数据，并且响应于接收到输入数据而将多个基类中的一个或多个发送到规则选择器。 响应于确定输入数据和多个基类中的一个与转换规则相对应，规则选择器选择一个或多个转换规则之一。 然后将状态机的当前状态设置为所述一个或多个转换规则中所选择的一个的下一状态。

公开(公告)号：US07787474B2

公开(公告)日：2010-08-31

申请号：US12123183

申请日：2008-05-19

申请人： Jan Van Lunteren

发明人： Jan Van Lunteren

IPC分类号： H04L12/28

CPC分类号： H04L63/02 ,  H04L45/7457 ,  H04L69/12 ,  H04L69/22

摘要： A method and apparatus for deep packet processing including a parsing and a searching method supported by a data structure storing the state-transition rules in the state-transition rule tables of a programmable state machine for parsing. The state-transition rule table is then compressed using the BaRT compression algorithm. Each transition rule comprises a test value, a test mask and a next state field. In a second embodiment the state-transition rule table is split into more than one state-transition rule table corresponding to disjoints state spaces, thus allowing more flexibility in the use of storage space. Finally a parsing and searching method can be implemented using the same hardware. The searching and parsing methods can be implemented alternatively or in any combination at wire-speed.

摘要翻译： 一种用于深度分组处理的方法和装置，包括由可编程状态机的状态转换规则表中存储状态转换规则的数据结构支持的解析和搜索方法，用于解析。 然后使用BaRT压缩算法压缩状态转换规则表。 每个转换规则包括测试值，测试掩码和下一个状态字段。 在第二实施例中，状态转移规则表被分成与不相交状态空间相对应的多于一个的状态转移规则表，从而允许使用存储空间的更大的灵活性。 最后，可以使用相同的硬件实现解析和搜索方法。 搜索和解析方法可以以线速交替地或以任何组合来实现。

公开(公告)号：US07703058B2

公开(公告)日：2010-04-20

申请号：US11740487

申请日：2007-04-26

申请人： Rolf Fritz ,  Markus Kaltenbach ,  Ulrich Mayer ,  Thomas Pflueger ,  Cordt Starke ,  Jan Van Lunteren

发明人： Rolf Fritz ,  Markus Kaltenbach ,  Ulrich Mayer ,  Thomas Pflueger ,  Cordt Starke ,  Jan Van Lunteren

IPC分类号： G06F17/50

CPC分类号： G06F17/5045

摘要： The invention relates to a method and system for the design and implementation of state machine engines. A first constraints checking step checks a state transition function created by a designer against constraints imposed by the implementation technology in order to detect all portions of the state transition function that are in conflict with the constraints. A subsequent conflict resolution step tries to determine one or more suggested ways to meet the conflicting constraints, by investigating how the original state transition function can be modified such that all constraints are met. A final presentation and selection step provides the designer textual and/or graphically results of the constraints check and suggested modifications. The modifications can be accepted interactively, or the state transition function can be changed manually. In the latter case, the modified state transition function will be processed starting again with the constraints checking step.

摘要翻译： 本发明涉及一种用于设计和实施状态机发动机的方法和系统。 第一约束检查​​步骤检查由设计者创建的状态转换函数，以抵制由实施技术施加的约束，以便检测与约束相冲突的状态转换函数的所有部分。 随后的冲突解决步骤尝试通过调查如何修改原始状态转换功能以满足所有约束来确定满足冲突约束的一种或多种建议方式。 最后的演示和选择步骤为设计者提供了约束检查和建议修改的文本和/或图形结果。 可以交互接受修改，也可以手动更改状态转换功能。 在后一种情况下，将通过约束检查步骤再次开始处理修改的状态转换功能。

公开(公告)号：US20090307175A1

公开(公告)日：2009-12-10

申请号：US12136386

申请日：2008-06-10

申请人： Iorio Francesco ,  Jan Van Lunteren

发明人： Iorio Francesco ,  Jan Van Lunteren

IPC分类号： G06N5/02

CPC分类号： G06F9/4498

摘要： A method, system and computer program product for performing pattern matching in parallel for a plurality of input streams. The method includes calculating a memory address in a translation table responsive to a current input value, a current state and current state information. A transition rule is retrieved from the transition rule table at the memory address, the transition rule including a test input value, a test current state, and next state information. It is determined if the current input value and the current state match the test input value and the test current state. The current state information is updated with the next state information in response to determining that the current input value and the current state match the test input value and the test current state. The current state information is updated with contents of a default transition rule in response to determining that the current input value and the current state do not match the test input value and the test current state.

摘要翻译： 一种用于对多个输入流并行执行模式匹配的方法，系统和计算机程序产品。 该方法包括响应于当前输入值，当前状态和当前状态信息来计算翻译表中的存储器地址。 从存储器地址的转移规则表中检索转移规则，转换规则包括测试输入值，测试当前状态和下一状态信息。 确定当前输入值和当前状态是否与测试输入值和测试当前状态相匹配。 响应于确定当前输入值和当前状态与测试输入值和测试当前状态匹配，当前状态信息被更新为具有下一状态信息。 响应于确定当前输入值和当前状态与测试输入值和测试当前状态不匹配，当前状态信息被更新为默认转换规则的内容。

公开(公告)号：US07562293B2

公开(公告)日：2009-07-14

申请号：US11140189

申请日：2005-05-27

申请人： Glenn A. Marcy ,  Jan Van Lunteren ,  Marcel Waldvogel

发明人： Glenn A. Marcy ,  Jan Van Lunteren ,  Marcel Waldvogel

IPC分类号： G06F17/27 ,  G06F11/00

CPC分类号： G06F17/2247 ,  G06F17/2725

摘要： A data processing method comprises receiving an electronically parseable document, scanning the document according to at least one predefined rule to determine if the document is suspicious, and, if the document is determined not to be suspicious, parsing the document with a first parser, and, if the document is determined to be suspicious, parsing the document with a second parser.

摘要翻译： 数据处理方法包括接收电子可解析文档，根据至少一个预定义规则扫描文档以确定文档是否可疑，以及如果文档被确定为不可疑，则用第一解析器解析文档，以及 如果文档被确定为可疑，则使用第二个解析器解析文档。

公开(公告)号：US20090171651A1

公开(公告)日：2009-07-02

申请号：US11966236

申请日：2007-12-28

申请人： Jan Van Lunteren ,  Heather D. Achilles ,  Joseph Allen ,  David J. Hoeweler ,  Jeffrey M. Peters

发明人： Jan Van Lunteren ,  Heather D. Achilles ,  Joseph Allen ,  David J. Hoeweler ,  Jeffrey M. Peters

IPC分类号： G06F9/455

CPC分类号： G06F9/30058 ,  G06F16/9014

摘要： The system and method of the present invention “emulates” the TCAM function using a data structure which is stored in an SDRAM device in such way that the size of emulated TCAM is substantially larger than the original TCAM device, thereby allowing the increase of the number of PPE programs which can be resident in memory. The present invention provides a new “emulCAM” algorithm which builds partially on BaRT, but is extended by providing multiple results per hash table entry with flexible assignment to “match-condition-combinations”, by utilizing MUX control vectors for extracting hash index instead of “index-mask-based extraction”, by moving part of CAM function to invoking emulCAM instruction and by providing “Pathological case handling” using multiple emulCAM instructions.

摘要翻译： 本发明的系统和方法使用存储在SDRAM设备中的数据结构“模拟”TCAM功能，使得仿真TCAM的大小显着大于原始TCAM设备，从而允许增加数量 可以驻留在记忆中的PPE程序。 本发明提供了一种新的“emulCAM”算法，其部分地构建在BaRT上，但是通过使用用于提取散列索引的MUX控制向量而不是以“匹配条件组合”提供具有对“匹配条件组合”的灵活分配的每个哈希表条目的多个结果来扩展 “基于索引掩码的提取”，通过将CAM功能的一部分移动到调用emulCAM指令，并通过使用多个emulCAM指令提供“病理案例处理”。