公开(公告)号：US08233493B2

公开(公告)日：2012-07-31

申请号：US12555462

申请日：2009-09-08

申请人： Yadi Ma ,  Suman Banerjee ,  Cristian Estan

发明人： Yadi Ma ,  Suman Banerjee ,  Cristian Estan

IPC分类号： H04L12/28 ,  H04L12/56

CPC分类号： H04L43/0835 ,  H04L43/028 ,  H04L43/04 ,  H04L45/742 ,  H04L47/20 ,  H04L69/12 ,  H04L69/22 ,  Y02D30/40

摘要： A computer-implemented method for classifying received packets using a hardware cache of evolving rules and a software cache having an original rule set. The method including receiving a packet, processing the received packet through a hardware-based packet classifier having at least one evolving rule to identify at least one cache miss packet, and processing the cache miss packet through a software based packet classifier including an original rule set. Processing the cache miss packet includes determining whether to expand at least one of the at least one evolving rules in the hardware-based packet classifier based on the cache miss packet. The determination includes determining whether an evolving rule has both the same action and lies entirely within one of the rule of the original rule set.

摘要翻译： 一种用于使用演进规则的硬件缓存和具有原始规则集的软件高速缓存来对接收的分组进行分类的计算机实现的方法。 所述方法包括接收分组，通过具有至少一个演进规则的基于硬件的分组分类器处理所接收的分组以识别至少一个高速缓存未命中分组，以及通过基于软件的分组分类器处理所述高速缓存未命中分组，所述分组包括原始规则集 。 处理高速缓存未命中分组包括基于高速缓存未命中分组确定是否扩展基于硬件的分组分类器中的至少一个演进规则中的至少一个。 确定包括确定演进规则是否具有相同的动作并完全落在原始规则集的规则之一内。

公开(公告)号：US08572106B1

公开(公告)日：2013-10-29

申请号：US12946440

申请日：2010-11-15

申请人： Cristian Estan

发明人： Cristian Estan

IPC分类号： G06F17/30

CPC分类号： G06F17/30985

摘要： A content search system includes multiple pipelined search engines that implement different portions of a regular expression search operation. For some embodiments, the search pipeline includes a DFA engine, an NFA engine, and a token stitcher that combines partial match results generated by the DFA and NFA engines. The token stitcher can be configured to implement unbounded sub-expressions without utilizing resources of the DFA or NFA engines. The token stitcher may comprise a flag bank for storing a number of flags. Each flag may identify a sub-expression that matches the input string. The flag bank may be configured to discard one or more flags upon satisfaction of a predetermined condition for purposes of recapturing hardware resources to provide a certain level of performance.

摘要翻译： 内容搜索系统包括实现正则表达式搜索操作的不同部分的多个流水线搜索引擎。 对于一些实施例，搜索流水线包括DFA引擎，NFA引擎和组合由DFA和NFA引擎生成的部分匹配结果的令牌拼接器。 令牌拼接器可以配置为在不使用DFA或NFA引擎的资源的情况下实现无界子表达式。 令牌装订器可以包括用于存储多个标志的标志库。 每个标志可以标识与输入字符串匹配的子表达式。 为了重新捕获硬件资源以提供一定水平的性能，标志库可以被配置为在满足预定条件时丢弃一个或多个标志。

公开(公告)号：US08861241B1

公开(公告)日：2014-10-14

申请号：US13226220

申请日：2011-09-06

申请人： Cristian Estan

发明人： Cristian Estan

IPC分类号： G11C15/00 ,  G11C15/04

CPC分类号： G11C15/04 ,  G11C15/00

摘要： A content addressable memory (CAM) device to dynamically reduces power consumption between a search key and data stored in a plurality of CAM blocks by selectively disabling a number of CAM blocks, requested for the search operation by an external network processor, based upon the contents of the search key.

摘要翻译： 一种内容可寻址存储器（CAM）装置，其通过基于所述内容选择性地禁用由外部网络处理器请求搜索操作的多个CAM块来动态地减少搜索关键字与存储在多个CAM块中的数据之间的功耗 的搜索关键字。

公开(公告)号：US08700593B1

公开(公告)日：2014-04-15

申请号：US12838323

申请日：2010-07-16

申请人： Cristian Estan ,  Greg Watson

发明人： Cristian Estan ,  Greg Watson

IPC分类号： G06F17/30

CPC分类号： G06F17/30985

摘要： A content search system includes multiple pipelined search engines that implement different portions of a regular expression search operations. For some embodiments, the search pipeline includes a DFA engine, an NFA engine, and a token stitcher that combines partial match results generated by the DFA and NFA engines in a manner that prevents either engine from becoming a bottleneck. In addition, the token stitcher can be configured to implement unbounded sub-expressions without utilizing resources of the DFA or NFA engines.

摘要翻译： 内容搜索系统包括实现正则表达式搜索操作的不同部分的多个流水线搜索引擎。 对于一些实施例，搜索流水线包括DFA引擎，NFA引擎和令牌拼接器，其以防止引擎成为瓶颈的方式组合由DFA和NFA引擎生成的部分匹配结果。 此外，令牌拼接器可以被配置为在不使用DFA或NFA引擎的资源的情况下实现无界子表达式。

公开(公告)号：US20100238942A1

公开(公告)日：2010-09-23

申请号：US12407286

申请日：2009-03-19

申请人： Cristian Estan ,  Karthikeyan Sankaralingam

发明人： Cristian Estan ,  Karthikeyan Sankaralingam

IPC分类号： H04L12/56

CPC分类号： H04L45/00 ,  H04L45/60 ,  H04L45/742

摘要： An architecture for a specialized electronic computer for high-speed data lookup employs a set of tiles each with independent processors and lookup memory portions. The tiles may be programmed to interconnect to form different memory topologies optimized for the particular task.

摘要翻译： 用于高速数据查找的专用电子计算机的架构使用具有独立处理器和查找存储器部分的一组瓦片。 可以将瓦片编程为互连以形成针对特定任务优化的不同存储器拓扑。

公开(公告)号：US07219354B1

公开(公告)日：2007-05-15

申请号：US09747687

申请日：2000-12-22

申请人： Xun Wilson Huang ,  Cristian Estan ,  Srinivasan Keshav

发明人： Xun Wilson Huang ,  Cristian Estan ,  Srinivasan Keshav

IPC分类号： G06F3/00 ,  G06F9/54

CPC分类号： G06F9/547 ,  G06F9/468 ,  G06F9/545 ,  G06F2209/542

摘要： Super-user privileges are virtualized by designating a virtual super-user for each of a plurality of virtual processes and intercepting system calls for which actual super-user privileges are required, which are nevertheless desirable for a virtual super-user to perform in the context of his or her own virtual process. In one embodiment, a computer operating system includes multiple virtual processes, such as virtual private servers. Each virtual process can be associated with one or more virtual super-users. When an actual process makes a system call that requires actual super-user privileges, the call is intercepted by a system call wrapper.

摘要翻译： 超级用户权限通过为多个虚拟进程中的每一个指定虚拟超级用户而进行虚拟化，并且拦截系统呼叫，对于哪个实际的超级用户特权是必需的，这对于虚拟超级用户在上下文中执行是合乎需要的 他或她自己的虚拟过程。 在一个实施例中，计算机操作系统包括多个虚拟进程，诸如虚拟专用服务器。 每个虚拟进程可以与一个或多个虚拟超级用户相关联。 当实际进程进行需要实际超级用户权限的系统调用时，该调用将被系统调用包装器拦截。

公开(公告)号：US09305115B1

公开(公告)日：2016-04-05

申请号：US13247850

申请日：2011-09-28

申请人： Cristian Estan

发明人： Cristian Estan

IPC分类号： G06F12/00 ,  G06F17/30 ,  G06F1/32 ,  G06F3/06

CPC分类号： G06F17/30982 ,  G06F1/3275 ,  G06F3/0625 ,  G06F3/0634 ,  G06F3/0679 ,  Y02D10/45

摘要： A method and apparatus for comparing a search key with a plurality of rules of an access control list (ACL) stored in a plurality of content addressable memory (CAM) blocks of a content search system are disclosed. The search key is compared with a plurality of covering prefix entries stored in a covering prefix table, wherein a respective covering prefix entry includes first and second common prefix values. The first common prefix value is shared by all of the rules stored in a first of the CAM blocks, and the second common prefix value is shared by all of the rules stored in a second of the CAM blocks. A bitmap associated with a matching covering prefix entry selectively enables a subset of the CAM blocks for comparison with the search key to determine the highest priority matching rule.

摘要翻译： 公开了一种用于将搜索关键字与存储在内容搜索系统的多个内容可寻址存储器（CAM）块中的访问控制列表（ACL）的多个规则进行比较的方法和装置。 搜索密钥与存储在覆盖前缀表中的多个覆盖前缀条目进行比较，其中相应的覆盖前缀条目包括第一和第二公共前缀值。 第一公共前缀值由存储在第一CAM块中的所有规则共享，并且第二公共前缀值由存储在第二CAM块中的所有规则共享。 与匹配的覆盖前缀条目相关联的位图选择性地使得CAM块的子集与搜索关键字进行比较以确定最高优先级匹配规则。

公开(公告)号：US08935270B1

公开(公告)日：2015-01-13

申请号：US12779894

申请日：2010-05-13

申请人： Cristian Estan ,  Greg Watson

发明人： Cristian Estan ,  Greg Watson

IPC分类号： G06F7/00 ,  G06F17/30

CPC分类号： G06F7/02 ,  G06F2207/025

摘要： A content search system for determining whether an input string matches one or more of a number of patterns embodied by a deterministic finite automaton (DFA) includes a plurality of DFA engines that simultaneously compare sequential overlapping segments of the input string. The overlap region shared by adjacent pairs of input string segments is of a predetermined size. Initially, the first DFA engine is designated as the master engine, and the remaining DFA engines are designated as slave engines whose state results are speculative. Resolution logic compares the state results of the master engine with the state results of the adjacent slave engine to selectively validate the state results of the successor engine, which upon validation becomes the new master engine.

摘要翻译： 用于确定输入字符串匹配由确定性有限自动机（DFA）体现的多个模式中的一个或多个的内容搜索系统包括同时比较输入字符串的顺序重叠片段的多个DFA引擎。 相邻输入串段共享的重叠区域具有预定的大小。 最初，第一个DFA引擎被指定为主引擎，其余的DFA引擎被指定为从属引擎，其状态结果是推测性的。 分辨率逻辑将主引擎的状态结果与相邻从属引擎的状态结果进行比较，以选择性地验证后继引擎的状态结果，后者在验证成为新的主引擎时。

公开(公告)号：US07962434B2

公开(公告)日：2011-06-14

申请号：US12032380

申请日：2008-02-15

申请人： Cristian Estan ,  Randy David Smith ,  Somesh Jha

发明人： Cristian Estan ,  Randy David Smith ,  Somesh Jha

IPC分类号： G06F17/00

CPC分类号： H04L63/1416 ,  H04L69/22

摘要： Deterministic finite automata (DFAs) are popular solutions to deep packet inspection because they are fast and DFAs corresponding to multiple signatures are combinable into a single DFA. Combining such DFAs causes an explosive increase in memory usage. Extended finite automata (XFAs) are an alternative to DFAs that avoids state-space explosion problems. XFAs extend DFAs with a few bytes of “scratch memory” used to store bits and other data structures that record progress. Simple programs associated with automaton states and/or transitions manipulate this scratch memory. XFAs are deterministic in their operation, are equivalent to DFAs in expressiveness, and require no custom hardware support. Fully functional prototype XFA implementations show that, for most signature sets, XFAs are at least 10,000 times smaller than the DFA matching all signatures. XFAs are 10 times smaller and 5 times faster or 5 times smaller and 20 times faster than systems using multiple DFAs.

摘要翻译： 确定性有限自动机（DFA）是深度分组检测的流行解决方案，因为它们是快速的，并且与多个签名相对应的DFA可以组合成单个DFA。 结合这样的DFA导致内存使用的爆炸性增加。 扩展有限自动机（XFAs）是避免状态空间爆炸问题的替代方案。 XFAs使用几个字节的“暂存内存”来扩展DFA，用于存储记录进度的位和其他数据结构。 与自动机状态和/或转换相关联的简单程序操纵该暂存存储器。 XFAs在运营中是确定性的，相当于表现力的DFA，并且不需要定制硬件支持。 全功能原型XFA实现表明，对于大多数签名集，XFA至少比匹配所有签名的DFA小10,000倍。 XFA比使用多个DFA的系统小10倍，5倍，5倍，20倍。

公开(公告)号：US08812480B1

公开(公告)日：2014-08-19

申请号：US13355051

申请日：2012-01-20

申请人： Greg Watson ,  Cristian Estan ,  Mark Birman ,  Alexei Starovoitov

发明人： Greg Watson ,  Cristian Estan ,  Mark Birman ,  Alexei Starovoitov

IPC分类号： G06F17/30

CPC分类号： H04L69/12 ,  G06F17/30657 ,  H04L67/02 ,  H04L69/22

摘要： A content search system for determining whether an input string matches one or more rules includes a parser, a rules database, and a search engine. The parser, which has an input to receive the input string, is to extract one or more selected portions of the input string to form a filtered input string, and is to generate a rule select signal in response to the selected portions of the input string. The rules database stores a plurality of sets of rules. The search engine is to compare the filtered input string with a selected set of rules selected in response to the rule select signal.

摘要翻译： 用于确定输入字符串是否匹配一个或多个规则的内容搜索系统包括解析器，规则数据库和搜索引擎。 具有用于接收输入字符串的输入的解析器是提取输入字符串的一个或多个所选部分以形成经滤波的输入字符串，并且响应于输入字符串的所选部分生成规则选择信号 。 规则数据库存储多组规则。 搜索引擎将滤波后的输入字符串与响应于规则选择信号选择的一组规则进行比较。