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

公开(公告)号：US07917694B1

公开(公告)日：2011-03-29

申请号：US11207323

申请日：2005-08-18

Applicant: Srinivasan Venkatachary

Inventor： Srinivasan Venkatachary

IPC: G06F12/00

CPC classification number: G06F12/0873

Abstract: A storage system and method of operating the same can speed the operation of cache management functions. Generally, a storage system can include data stored in stripes, with each stripe including a number of blocks. A cache memory can store data blocks for fast access. A method can include providing a ternary content addressable memory (TCAM) with a processor coupled thereto, and tracking a block count for each active stripe with the processor and TCAM. The block count for each active stripe can be the number of data blocks belonging to the same stripe that are stored in the cache memory.

Abstract translation: 一种存储系统和操作方法可以加快缓存管理功能的运行。 通常，存储系统可以包括以条纹存储的数据，每个条带包括多个块。 缓存存储器可以存储用于快速访问的数据块。 一种方法可以包括提供与其耦合的处理器的三元内容可寻址存储器（TCAM），以及利用处理器和TCAM跟踪每个活动条带的块计数。 每个活动条带的块计数可以是属于存储在高速缓冲存储器中的相同条带的数据块数。

公开(公告)号：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: 用于表示在输入字符串中体现要搜索的多个签名的搜索树的方法构造故障树，其中状态根据每个状态和根节点之间的故障转换次数被重新组织在一起 的搜索树。

公开(公告)号：US07451267B1

公开(公告)日：2008-11-11

申请号：US10948050

申请日：2004-09-22

Applicant: Srinivasan Venkatachary ,  Ajay Srikrishna ,  Jagadeesan Rajamanickam

Inventor： Srinivasan Venkatachary ,  Ajay Srikrishna ,  Jagadeesan Rajamanickam

IPC: G06F12/00

CPC classification number: G11C15/00

Abstract: A search engine method and apparatus can store and update status information for each entry of a content addressable memory (CAM) array, for a learn operation, or the like. A search engine can include a status memory block external to and independent of the CAM array. A status memory block (800) can include a number of memory sections (806-0 to 806-2) that each includes a number of bit locations for storing a free/not-free status of CAM entries in a hierarchical fashion. Corresponding control sections (808-0 to 808-2) can include priority encoders (812-0 to 812-2) that determine a first free element in a memory section for a next hierarchical level, as well as status aggregation logic (814-0 to 814-2) that can generate an aggregated status that is propagated to a previous hierarchical level.

Abstract translation: 搜索引擎方法和装置可以存储和更新用于学习操作等的内容可寻址存储器（CAM）阵列的每个条目的状态信息。 搜索引擎可以包括外部并独立于CAM阵列的状态存储器块。 状态存储器块（800）可以包括多个存储器部分（806-0至806-2），每个存储器部分包括用于以分级方式存储CAM条目的空闲/不自由状态的多个位位置。 相应的控制部分（808-0至808-2）可以包括确定用于下一层级的存储器部分中的第一空闲元素的优先编码器（812-0至812-2）以及状态聚合逻辑（814- 0到814-2），其可以生成被传播到先前分层级的聚合状态。

公开(公告)号：US20080263270A1

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

申请号：US12214952

申请日：2008-06-23

Applicant: Mark Birman ,  Ajay Srikrishna ,  Srinivasan Venkatachary

Inventor： Mark Birman ,  Ajay Srikrishna ,  Srinivasan Venkatachary

IPC: G06F12/00

CPC classification number: G11C15/00 ,  Y10S707/99936

Abstract: A content addressable memory device (100) and method can have CAM blocks (102-0 to 102-29) organized in block sections (104-0 to 104-6). In an overlay mode of operation, an overlay engine (106) can access an algorithmic search (SPEAR) CAM (102-28 and 102-29) to generate overlay data set search keys (keyFIB and ). Multiple data sets (e.g., FIB0, FIB1, ACL0) can be accommodated on the same CAM device by search key multiplexers (108-0 to 108-6) that selectively apply any of a number of data set search keys (keyACL , keyFIB and keyFIB ).

Abstract translation: 内容可寻址存储器件（100）和方法可以具有以块部分（104-0至104-6）组织的CAM块（102-0至102-29）。 在覆盖操作模式中，覆盖引擎（106）可以访问算法搜索（SPEAR）CAM（102-28和102-29）以产生覆盖数据集搜索关键字（keyFIB <0>和<1>）。 多个数据集（例如，FIB 0，FIB 1，ACL 0）可以通过搜索关键多路复用器（108-0至108-6）容纳在相同的CAM设备上，该多路复用器选择性地应用多个数据集搜索键（keyACL <0>，keyFIB <0>和keyFIB <1>）。

公开(公告)号：US07085924B2

公开(公告)日：2006-08-01

申请号：US10961920

申请日：2004-10-08

Applicant: Paramvir Bahl ,  Srinivasan Venkatachary ,  Anand Balachandran

Inventor： Paramvir Bahl ,  Srinivasan Venkatachary ,  Anand Balachandran

IPC: G06F15/173 ,  H04Q7/38 ,  H04L9/32 ,  H04L9/00

CPC classification number: H04L63/04 ,  G06Q30/02 ,  H04L63/061 ,  H04L63/08 ,  H04L63/102

Abstract: Systems and methods for providing network access, e.g. Internet access, are described. An architecture includes a host organization network through which network access is provided. The host organization network can be advantageously deployed in public areas such as airports and shopping malls. An authentication/negotiation component is provided for authenticating various users and negotiating for services with service providers on behalf of the system users. The authentication/negotiation component can include one or more specialized servers and a policy manager that contains policies that govern user access to the Internet. An authentication database is provided and authenticates various users of the system. An access module is provided through which individual client computing devices can access the Internet. In one embodiment, the access module comprises individual wireless access points that permit the client computing devices to wirelessly communicate data packets that are intended for the Internet. In one aspect, users are given a variety of choices of different service levels that they can use for accessing the Internet. The service levels can vary in such things as bandwidth allocation and security measures. The various service levels can be purchased by the users using their computing devices.

Abstract translation: 用于提供网络接入的系统和方法，例如 描述了互联网接入。 一种架构包括一个主机组织网络，通过它提供网络访问。 主机组织网络可以有利地部署在公共场所，如机场和商场。 提供用于认证各种用户并代表系统用户与服务提供商协商服务的认证/协商组件。 认证/协商组件可以包括一个或多个专用服务器和包含管理用户对因特网的访问的策略的策略管理器。 提供认证数据库并认证系统的各种用户。 提供访问模块，单个客户端计算设备可以通过该访问模块访问因特网。 在一个实施例中，访问模块包括单独的无线接入点，其允许客户端计算设备无线地传送旨在用于因特网的数据分组。 在一个方面，向用户提供可用于访问因特网的不同服务级别的各种选择。 服务水平可以在带宽分配和安全措施等方面有所不同。 各种服务级别可由用户使用其计算设备购买。

公开(公告)号：US06449256B1

公开(公告)日：2002-09-10

申请号：US09074277

申请日：1998-05-07

Applicant: George Varghese ,  Srinivasan Venkatachary

Inventor： George Varghese ,  Srinivasan Venkatachary

IPC: G01R3108

CPC classification number: H04L49/355 ,  H04L45/742 ,  H04L49/3009

Abstract: A new process called “crossproducting” allows level 4 switching to be performed at gigabit speeds. In crossproducting, a database of routing filters or rules is “sliced” into columns corresponding to fields. Each column represents a set of prefixes or ranges. Given a data packet P, a best matching prefix or narrowest enclosing range lookup is performed separately for each packet field. The results of the lookups on individual fields are concatenated to quickly determine the earliest matching rule. The search can be optimized further through such techniques as removing default entries, creating multiple crossproduct tables, caching crossproducts, and early stopping, the latter optimization being made possible by recognizing that it is not necessary in all cases to search all columns for a match. The inventive devices and methods are applicable to various types of networks, including, but not limited to, the Internet and related types of networks, and telephone switching networks.

Abstract translation: 称为“交叉产品”的新过程允许以千兆位速度执行4级切换。 在交叉产品中，将路由过滤器或规则的数据库“切片”到与字段对应的列中。 每列表示一组前缀或范围。 给定数据分组P，对于每个分组字段分别执行最佳匹配前缀或最窄包围范围查找。 对各个字段的查找结果进行连接以快速确定最早的匹配规则。 可以通过删除默认条目，创建多个交叉产品表，高速缓存交叉产品和提前停止等技术进一步优化搜索，通过认识到在所有情况下都不需要搜索所有列进行匹配，后者的优化成为可能。 本发明的设备和方法可应用于各种类型的网络，包括但不限于因特网和相关类型的网络以及电话交换网络。

公开(公告)号：US6011795A

公开(公告)日：2000-01-04

申请号：US821100

申请日：1997-03-20

Applicant: George Varghese ,  Srinivasan Venkatachary

Inventor： George Varghese ,  Srinivasan Venkatachary

IPC: H04L12/56 ,  H04L29/12 ,  H04L12/46

CPC classification number: H04L61/1552 ,  H04L29/12132 ,  H04L29/12801 ,  H04L45/00 ,  H04L45/54 ,  H04L45/742 ,  H04L61/6004

Abstract: Many network protocols, including the Internet, have addresses that are structured hierarchically. The hierarchy is expressed by an address prefix P that represents all addresses in the given hierarchical level that starts with prefix P. The hierarchy is not strict and can be overridden by more inclusive hierarchies. This is achieved by having network routers find the longest prefix that matches a destination address in a message.The disclosed invention describes a method and apparatus for implementing controlled expansion: for expanding a set of prefixes into an equivalent (possibly larger) set of prefixes that have a smaller set of prefix lengths. The new set of prefixes can then be looked up significantly faster using any technique whose speed improves by reducing the number of prefix lengths. Our invention also incorporates fast techniques to insert and delete new prefixes, and a technique of pointer hoisting to halve the memory READs needed for trie search. Our solution to longest matching prefix also applies to other routing protocols such as OSI Routing, call routing in telephone networks, and to string matching problems.

Abstract translation: 许多网络协议（包括因特网）都具有层次结构的地址。 层次结构由地址前缀P表示，该地址前缀P表示以前缀P开始的给定分层级别中的所有地址。层次结构不是严格的，可以被更多包容的层次覆盖。 这通过使网络路由器找到与消息中的目的地地址匹配的最长前缀来实现。 所公开的发明描述了一种用于实现受控扩展的方法和装置：用于将一组前缀扩展成具有较小前缀长度集合的等效（可能较大）的前缀集合。 然后可以使用任何通过减少前缀长度数量来提高速度的技术来快速查找新的前缀集。 我们的发明还结合了快速技术来插入和删除新的前缀，以及一种指针提升技术，将搜索所需的存储器读数减半。 我们对最长匹配前缀的解决方案也适用于其他路由协议，如OSI路由，电话网络中的呼叫路由和字符串匹配问题。

公开(公告)号：US07904643B1

公开(公告)日：2011-03-08

申请号：US12732515

申请日：2010-03-26

Applicant: Srinivasan Venkatachary

Inventor： Srinivasan Venkatachary

IPC: G06F12/00

CPC classification number: G11C15/00

Abstract: A content addressable memory (CAM) device, method, and method of generating entries for range matching are disclosed. A CAM device (800) according to one embodiment can include a pre-encoder (806) that encodes range bit values W into additional bits E. Additional bits E can indicate compression of range rules according to particular bit pairs. A CAM array (802) can include entries that store compressed range code values (RANGE) with corresponding additional bit values (ENC). Alternate embodiments can include pre-encoders that encode portions of range values (K1 to Ki) in a “one-hot” fashion. Corresponding CAM entries can include encoded value having sections that each represent increasingly finer divisions of a range space.

Abstract translation: 公开了一种内容可寻址存储器（CAM）装置，方法和用于生成范围匹配的条目的方法。 根据一个实施例的CAM设备（800）可以包括将范围位值W编码为附加位E的预编码器（806）。附加位E可以指示根据特定位对的范围规则的压缩。 CAM阵列（802）可以包括存储具有相应附加位值（ENC）的压缩范围代码值（RANGE）的条目。 替代实施例可以包括以“一热”方式编码范围值（K1至Ki）的部分的预编码器。 相应的CAM条目可以包括具有每个表示范围空间越来越精细的部分的部分的编码值。