Apparatus and method for memory efficient, programmable, pattern matching finite state machine hardware

Number of patents in Portfolio can not be more than 2000

United States of America Patent

PATENT NO 7082044
APP PUB NO 20060120137A1
SERIAL NO

10799367

Stats

ATTORNEY / AGENT: (SPONSORED)

Importance

Loading Importance Indicators... loading....

Abstract

See full text

A programmable finite state machine (FSM) includes, in part, first and second memories, and a selection circuit coupled to each of the memories. Upon receiving a (k+m)-bit word representative of the k-bit input symbol and the m-bit current state, the first memory supplies one ore more matching transition rules stored therein. The selection circuit selects the most specific of the supplied rules. The transition rules are stored in the first memory in a ranking order of generality. The second memory receives the selected transition rule and supplies the next state of the FSM. The first memory may be a ternary content addressable memory and the second memory may be a static random access memory. The contents of both the content addressable memory and the static random memory is determined by an algorithm which minimizes the number of terms required to represent the next-state transition functions.

Loading the Abstract Image... loading....

First Claim

See full text

Family

Loading Family data... loading....

Patent Owner(s)

Patent OwnerAddressTotal Patents
INTEL CORPORATIONSANTA CLARA, CA29226
Sensory Networks, Inc.PALO ALTO, CA5

International Classification(s)

  • [Classification Symbol]
  • [Patents Count]

Inventor(s)

Inventor Name Address # of filed Patents Total Citations
Barrie, Robert Matthew Double Bay, AU 22 625
de, Jong Nicholas Bondi Junction, AU 5 85
Gould, Stephen Queens Park, AU 43 755
Williams, Darren Newtown, AU 27 622

Cited Art Landscape

Patent Info (Count) # Cites Year
 
YALE UNIVERSITY (1)
* 6609189 Cycle segmented prefix circuits 61 1999
 
APPLE INC. (1)
* 5873097 Update mechanism for computer storage container manager 117 1996
 
MITEL NETWORKS CORPORATION (1)
2002/0131,402 Registering an IP phone with an IP phone switch 12 2001
 
Sensory Networks, Inc. (1)
* 2005/0114,700 Integrated circuit apparatus and method for high throughput signature based network applications 83 2003
 
XILINX, INC. (1)
5617573 State splitting for level reduction 8 1994
 
LOCKHEED MARTIN CORPORATION (1)
* 5125098 Finite state-machine employing a content-addressable memory 18 1989
 
RICOH COMPANY, LTD. (2)
* 5475388 Method and apparatus for using finite state machines to perform channel modulation and error correction and entropy coding 83 1993
* 5471206 Method and apparatus for parallel decoding and encoding of data 101 1994
 
BINARY SERVICES LIMITED LIABILITY COMPANY (1)
* 5610812 Contextual tagger utilizing deterministic finite state transducer 97 1994
 
AVAGO TECHNOLOGIES GENERAL IP (SINGAPORE) PTE. LTD. (1)
* 6418042 Ternary content addressable memory with compare operand selected according to mask value 40 1998
* Cited By Examiner

Patent Citation Ranking

Forward Cite Landscape

Patent Info (Count) # Cites Year
 
INTERNATIONAL BUSINESS MACHINES CORPORATION (1)
* 2004/0190,506 Method and apparatus for performing complex pattern matching in a data stream within a computer network 4 2003
 
Other [Check patent profile for assignment information] (1)
9824756 Mapping a lookup table to prefabricated TCAMS 0 2013
 
TREND MICRO INCORPORATED (5)
* 8069183 Fast identification of complex strings in a data stream 1 2011
8117229 Fast identification of complex strings in a data stream 0 2011
8423572 Fast identification of complex strings in a data stream 0 2012
8812547 Fast identification of complex strings in a data stream 0 2013
9600537 Fast identification of complex strings in a data stream 0 2014
 
THE BOEING COMPANY (3)
* 8442931 Graph-based data search 0 2008
* 2010/0138,375 Graph-Based Data Search 3 2008
8914320 Graph generation method for graph-based search 0 2013
 
MICROSOFT TECHNOLOGY LICENSING, LLC (5)
9147271 Graphical representation of aggregated data 0 2007
8234706 Enabling access to aggregated software security information 3 2007
8302197 Identifying data associated with security issue attributes 0 2007
8250651 Identifying attributes of aggregated data 12 2007
* 2009/0007,272 Identifying data associated with security issue attributes 6 2007
 
Sensory Networks, Inc. (3)
* 7180328 Apparatus and method for large hardware finite state machine with embedded equivalence classes 3 2004
* 7301792 Apparatus and method of ordering state transition rules for memory efficient, programmable, pattern matching finite state machine hardware 7 2006
* 2008/0022,401 Apparatus and Method for Multicore Network Security Processing 9 2006
 
HONEYWELL INTERNATIONAL INC. (1)
8166532 Decentralized access control framework 19 2006
 
AGERE SYSTEMS INC. (1)
* 2008/0080,505 Methods and Apparatus for Performing Packet Processing Operations in a Network 2 2006
 
ELECTRONICS AND TELECOMMUNICATIONS RESEARCH INSTITUTE (1)
8463988 System and method for matching patterns 0 2009
 
HUAWEI TECHNOLOGIES CO., LTD. (2)
* 8583961 Method and device for creating pattern matching state machine 0 2010
* 2010/0229,040 METHOD AND DEVICE FOR CREATING PATTERN MATCHING STATE MACHINE 0 2010
 
AVAGO TECHNOLOGIES GENERAL IP (SINGAPORE) PTE. LTD. (20)
* 7173452 Re-programmable finite state machine 6 2002
* 2004/0054,848 Re-programmable finite state machine 3 2002
7634500 Multiple string searching using content addressable memory 12 2003
* 7353332 Switching circuit implementing variable string matching 42 2005
* 2007/0083,646 Switching circuit implementing variable string matching 22 2005
* 7783654 Multiple string searching using content addressable memory 16 2006
7644080 Method and apparatus for managing multiple data flows in a content search system 27 2006
7624105 Search engine having multiple co-processors for performing inexact pattern search operations 12 2006
7539031 Inexact pattern searching using bitmap contained in a bitcheck command 13 2006
7539032 Regular expression searching of packet contents using dedicated search circuits 21 2006
7529746 Search circuit having individually selectable search engines 29 2006
* 2008/0071,780 Search Circuit having individually selectable search engines 29 2006
* 2008/0071,781 Inexact pattern searching using bitmap contained in a bitcheck command 31 2006
* 2008/0071,757 Search engine having multiple co-processors for performing inexact pattern search operations 10 2006
* 2008/0071,765 Regular expression searching of packet contents using dedicated search circuits 16 2006
* 2008/0071,779 Method and apparatus for managing multiple data flows in a content search system 14 2006
* 7889727 Switching circuit implementing variable string matching 3 2008
* 2008/0212,581 Switching Circuit Implementing Variable String Matching 14 2008
7969758 Multiple string searching using ternary content addressable memory 0 2008
8862603 Minimizing state lists for non-deterministic finite state automatons 5 2011
* Cited By Examiner

Maintenance Fees

Fee Large entity fee small entity fee micro entity fee due date
11.5 Year Payment $7400.00 $3700.00 $1850.00 Jan 25, 2018
Fee Large entity fee small entity fee micro entity fee
Surcharge - 11.5 year - Late payment within 6 months $160.00 $80.00 $40.00
Surcharge after expiration - Late payment is unavoidable $700.00 $350.00 $175.00
Surcharge after expiration - Late payment is unintentional $1,640.00 $820.00 $410.00