公开(公告)号：US07636717B1

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

申请号：US11689421

申请日：2007-03-21

Applicant: Pankaj Gupta ,  Srinivasan Venkatachary

Inventor： Pankaj Gupta ,  Srinivasan Venkatachary

IPC: G06F17/30 ,  G06F17/00

CPC classification number: G06F17/30985 ,  H04L63/1416 ,  Y10S707/99932 ,  Y10S707/99936 ,  Y10S707/99942

Abstract: A search tree embodying a plurality of signatures to be compared with an input string of characters and including a number of success transitions characterized by a success size parameter and including a number of failure transitions characterized by a failure size parameter is selectively modified to achieve a desired balance between processing speed and memory area requirements.

Abstract translation: 选择性地修改体现多个签名的搜索树，以便与输入的字符串进行比较，并且包括成功大小参数的特征，并且包括以故障大小参数为特征的多个故障转移的成功转换，以实现期望的 处理速度与内存区域要求之间的平衡。

公开(公告)号：US07437354B2

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

申请号：US10841607

申请日：2004-05-07

Applicant: Srinivasan Venkatachary ,  Pankaj Gupta ,  Anand Rangarajan

Inventor： Srinivasan Venkatachary ,  Pankaj Gupta ,  Anand Rangarajan

IPC: G06F17/30

CPC classification number: H04L45/00 ,  Y10S707/99931 ,  Y10S707/99932 ,  Y10S707/99933

Abstract: An improved architecture for a network search engine (NSE) is disclosed herein as including an interface manager, one or more levels of a splitting engine, an array of data processing units (DPUs), and a cascade block. A method for using the improved NSE architecture to form an efficient pointer entry database is also provided. As described herein, the improved NSE architecture simultaneously provides high speed, search throughput, update rate and capacity, coupled with low power and fixed latency searches for all search key widths.

Abstract translation: 网络搜索引擎（NSE）的改进的架构在此被公开为包括接口管理器，分离引擎的一个或多个级别，数据处理单元（DPU）阵列和级联块。 还提供了一种使用改进的NSE架构来形成有效的指针条目数据库的方法。 如本文所述，改进的NSE架构同时提供高速度，搜索吞吐量，更新速率和容量，以及针对所有搜索关键字宽度的低功率和固定延迟搜索。

公开(公告)号：US07017021B2

公开(公告)日：2006-03-21

申请号：US09827270

申请日：2001-04-04

Applicant: Pankaj Gupta ,  Srinivasan Venkatachary

Inventor： Pankaj Gupta ,  Srinivasan Venkatachary

IPC: G06F12/00

CPC classification number: H04L45/00 ,  H04L45/54 ,  H04L49/90 ,  H04L49/901 ,  H04L49/9021 ,  H04L49/9042

Abstract: The invention provides a method and system for lookup of message header information that has the advantages of low-power, speed, and flexibility. The invention uses a sequence of pipelined on-chip memories, each having only a portion of the header information intended for lookup. Each one of the on-chip memories simultaneously performs a lookup on a portion of the header information, allowing embodiments of the invention to operate on multiple messages worth of header information substantially simultaneously. The invention uses a novel data structure for recording destination addresses in the sequence of on-chip memories, having the property that moving information about destination addresses, or otherwise responding to changes in network topology is flexible, while at the same time maintaining relatively dense usage of the on-chip memories. The novel data structure allows embodiments of the invention to find the longest match destination address with no substantial additional processing over random-access memory lookup.

公开(公告)号：US08073856B2

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

申请号：US12171099

申请日：2008-07-10

Applicant: Srinivasan Venkatachary ,  Pankaj Gupta

Inventor： Srinivasan Venkatachary ,  Pankaj Gupta

IPC: G06F17/00

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

公开(公告)号：US07860849B1

公开(公告)日：2010-12-28

申请号：US11689437

申请日：2007-03-21

Applicant: Srinivasan Venkatachary ,  Pankaj Gupta

Inventor： Srinivasan Venkatachary ,  Pankaj Gupta

IPC: G06F7/00 ,  G06F17/30

CPC classification number: G06F17/30985 ,  H04L63/1416 ,  Y10S707/99932 ,  Y10S707/99936 ,  Y10S707/99942

Abstract: A search tree embodying a plurality of signatures and a number of states each having a failure transition to a fail state and one or more success transitions to next states is optimized by selecting a success size parameter that indicates a maximum number of input characters to be traversed on the success transitions and compressing the search tree to create a compressed search tree characterized by the selected success size parameter.

Abstract translation: 通过选择成功大小参数来优化体现多个签名和多个状态的搜索树，每个状态都具有到故障状态的故障转换和到下一个状态的一个或多个成功转换，该成功大小参数指示要被遍历的最大输入字符数 在成功转换并压缩搜索树以创建以选定的成功大小参数为特征的压缩搜索树。

公开(公告)号：US07610269B1

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

申请号：US11830360

申请日：2007-07-30

Applicant: Pankaj Gupta ,  Srinivasan Venkatachary

Inventor： Pankaj Gupta ,  Srinivasan Venkatachary

IPC: G06F17/30

CPC classification number: G06F17/30 ,  Y10S707/99932

Abstract: A method for representing a search tree embodying a plurality of signatures to be searched for in an input string of characters constructs a failure tree in which the states are re-organized in levels according to the number of failure transitions between each state and the root node of the search tree.

Abstract translation: 用于表示在输入字符串中体现要搜索的多个签名的搜索树的方法构造故障树，其中状态根据每个状态和根节点之间的故障转换次数被重新组织在一起 的搜索树。

公开(公告)号：US07805393B1

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

申请号：US11830397

申请日：2007-07-30

Applicant: Srinivasan Venkatachary ,  Pankaj Gupta

Inventor： Srinivasan Venkatachary ,  Pankaj Gupta

IPC: G06N5/00

CPC classification number: G06N5/02

Abstract: A method for assigning state codes to states of a state diagram embodying a plurality of signatures to be searched for in an input string of characters re-organizes the states of a search tree embodying the signatures to construct a failure tree in which the states are organized in levels according to a number of failure transitions between each state and the root node of the search tree.

Abstract translation: 用于将状态码分配给状态图的状态图的方式，该状态图表示输入的字符串中要搜索的多个签名，重新组织体现签名的搜索树的状态，以构造状态被组织的故障树 根据每个状态和搜索树的根节点之间的多个故障转换的级别。

公开(公告)号：US07676444B1

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

申请号：US11689446

申请日：2007-03-21

Applicant: Srinivasan Venkatachary ,  Pankaj Gupta

Inventor： Srinivasan Venkatachary ,  Pankaj Gupta

IPC: G06F17/00

CPC classification number: G06F17/30985 ,  H04L63/1416 ,  Y10S707/99932 ,  Y10S707/99936 ,  Y10S707/99942

Abstract: A search engine for selectively perform iterative compare operations between a searchable pattern and S overlapping substrings of an input string of characters includes a memory for storing a bitmap having S next success size (NSS) bits, wherein each NSS bit indicates whether an associated substring including a corresponding unique number of the input characters is to be compared with the searchable pattern in successive compare operations, and includes a compare circuit for selectively performing the successive compare operations in response to the NSS bits.

Abstract translation: 用于选择性地执行输入字符串的可搜索模式和S重叠子串之间的迭代比较操作的搜索引擎包括用于存储具有S个下一个成功大小（NSS）位的位图的存储器，其中每个NSS位指示是否包括相关联的子串 输入字符的对应唯一数量将与连续比较操作中的可搜索模式进行比较，并且包括用于响应于NSS位选择性地执行连续比较操作的比较电路。

公开(公告)号：US07624226B1

公开(公告)日：2009-11-24

申请号：US11614075

申请日：2006-12-20

Applicant: Srinivasan Venkatachary ,  Pankaj Gupta

Inventor： Srinivasan Venkatachary ,  Pankaj Gupta

IPC: G06F13/10

CPC classification number: H04L45/00 ,  H04L45/7453 ,  H04L45/7457

Abstract: A communication network, networking device and method is provided herein for locating (i.e., searching for) an interval of numbers i within a set of numbers N given a point P. The search algorithm provided herein provides fast search speed (e.g., requires only one memory access) with minimum storage requirements (e.g., consumes up to, but not exceeding, N entries within a memory device).

Abstract translation: 本文提供了一种通信网络，网络设备和方法，用于在给定点P的一组数字N内定位（即搜索）数字i的间隔。本文提供的搜索算法提供快速搜索速度（例如，仅需要一个 存储器访问），具有最小的存储要求（例如，消耗高达但不超过存储器设备内的N个条目）。

公开(公告)号：US07978709B1

公开(公告)日：2011-07-12

申请号：US12165541

申请日：2008-06-30

Applicant: Srinivasan Venkatachary ,  Pankaj Gupta

Inventor： Srinivasan Venkatachary ,  Pankaj Gupta

IPC: H04L12/28

CPC classification number: H04L45/00 ,  H04L45/54 ,  H04L45/7453

Abstract: A method of constructing a hierarchical database from an initial plurality of rules. A first rule of the initial plurality of rules is added to: a first sub-database if a first bit of the rule is a logic ‘0’ value; a second sub-database if the first bit is a logic ‘1’ value; or a third sub-database if the first bit is in a masked state, ‘X’, indicating that the first bit may be either a logic ‘1’ or a logic ‘0’ value.

Abstract translation: 一种从初始多个规则构建分层数据库的方法。 如果规则的第一位是逻辑“0”值，则将初始多个规则的第一规则添加到：第一子数据库; 第二个子数据库，如果第一个位是逻辑“1”值; 或第三子数据库，如果第一位处于屏蔽状态'X'，表示第一位可以是逻辑'1'或逻辑'0'值。