Pankaj D Gupta

US Patent:

7017021, Mar 21, 2006

Filed:

Apr 4, 2001

Appl. No.:

09/827270

Inventors:

Pankaj Gupta - Mountain View CA, US
Srinivasan Venkatachary - Sunnyvale CA, US

Assignee:

Cypress Semiconductor Corp. - San Jose CA

International Classification:

G06F 12/00

US Classification:

711169

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.

US Patent:

7281085, Oct 9, 2007

Filed:

Jan 31, 2005

Appl. No.:

11/047793

Inventors:

Ashish Garg - San Jose CA, US
Pankaj Gupta - Palo Alto CA, US

Assignee:

Netlogic Microsystems, Inc. - Mountain View CA

International Classification:

G06F 12/00

US Classification:

711108, 370235

Abstract:

A system () can provide data aggregation with a single primary table () formed in a content addressable memory (CAM) section (). Within a primary table () CAM entries can be part of a primary table, one or more aggregate tables, or both. In one arrangement, valid bits in each CAM entry can indicate which particular schemes a CAM entry belongs to (primary table, or any of the aggregate tables). Associated data for each table can be stored in a RAM section () and can be accessed according to an offset address generated according to a scheme value (i).

US Patent:

7304873, Dec 4, 2007

Filed:

Jan 25, 2005

Appl. No.:

11/043391

Inventors:

Pankaj Gupta - Palo Alto CA, US

Assignee:

Netlogic Microsystems, Inc. - Mountain View CA

International Classification:

G11C 15/00

US Classification:

365 49, 36518907, 711200

Abstract:

A CAM system () can include a number of entries (- to -) having one portion for storing a data value (e. g. , E) and another portion for storing a replicated data value (E(REP)). For on-the-fly error correction, the entries can be searched by applying an appended key value that includes a key portion (KEY) and replicated key portion (KEY(REP)).

US Patent:

7426518, Sep 16, 2008

Filed:

Mar 28, 2003

Appl. No.:

10/402887

Inventors:

Srinivasan Venkatachary - Sunnyvale CA, US
Pankaj Gupta - Mountain View CA, US

Assignee:

NetLogic Microsystems, Inc. - Mountain View CA

International Classification:

G06F 17/30

US Classification:

707101, 707102

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.

US Patent:

7437354, Oct 14, 2008

Filed:

May 7, 2004

Appl. No.:

10/841607

Inventors:

Srinivasan Venkatachary - Sunnyvale CA, US
Pankaj Gupta - Palo Alto CA, US
Anand Rangarajan - Sunnyvale CA, US

Assignee:

NetLogic Microsystems, Inc. - Mountain View CA

International Classification:

G06F 17/30

US Classification:

707 3, 707204, 707 1, 707 2

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.

US Patent:

7571156, Aug 4, 2009

Filed:

Mar 25, 2004

Appl. No.:

10/809244

Inventors:

Pankaj Gupta - Palo Alto CA, US
Srinivasan Venkatachary - Sunnyvale CA, US

Assignee:

NetLogic Microsystems, Inc. - Mountain View CA

International Classification:

G06F 7/00
G06F 17/30

US Classification:

707 3, 707101, 707102

Abstract:

Network devices, storage mediums and methods for updating a memory structure in a data plane of the network device when route updates are received in the control plane of the network device. The methods described herein can be used to perform one of the following algorithms: a Basic Incremental Split-Merge (BISM) algorithm, a Lazy Incremental Split-Merge (LISM) algorithm, and a Down-support Split-Merge (DSM) algorithm. Each of the algorithms described herein may be used to incrementally update portions of a forwarding database stored within the memory structure, where the updated portions correspond to only those portions affected by the route updates.

US Patent:

7610269, Oct 27, 2009

Filed:

Jul 30, 2007

Appl. No.:

11/830360

Inventors:

Pankaj Gupta - Palo Alto CA, US
Srinivasan Venkatachary - Sunnyvale CA, US

Assignee:

NetLogic Microsystems, Inc. - Mountain View CA

International Classification:

G06F 17/30

US Classification:

707 2, 707100

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.

US Patent:

7624226, Nov 24, 2009

Filed:

Dec 20, 2006

Appl. No.:

11/614075

Inventors:

Srinivasan Venkatachary - Sunnyvale CA, US
Pankaj Gupta - Palo Alto CA, US

Assignee:

NetLogic Microsystems, Inc. - Mountain View CA

International Classification:

G06F 13/10

US Classification:

711108

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).