Patent ID: 7356663
Filing Date: 2008-04-08
Classification: H04L

Abstract:
1. An apparatus implementing a layered memory architecture and capable of string matching using deterministic finite automata, said apparatus comprising: a memory necessary for said string matching, wherein said memory comprises at least three memories including a first memory means, a second memory means, and a third memory means, wherein said first memory means is faster and smaller than said second memory means and said second memory means is faster and smaller than said third memory means; a partitioning mechanism for strategically partitioning said memory between said first, second, and third memory means, wherein said partitioning mechanism implements a data structure that organizes, associates, and stores data; a host interface enabling an external host to set necessary data structures in said memory through host commands; and a caching mechanism for caching data locally from said third memory means to said second memory means based on need; wherein said data structures include state transition tables, and output tables for said string matching; wherein said external host populates said necessary data structures in said first, second, and third memory means in a manner that enables next state and output determinations at line-rate; wherein said data structures comprise: a first data structure consisting of state-wise character-set-wise bitmaps stored in said third memory means and cached to said second memory means for fast access; a second data structure consisting of state-wise character-set-wise bitmaps and outputs for next state stored in said third memory means and fetched to a processing engine when required; a third data structure implementing a hash based indexing mechanism for storage of outputs stored in said second memory means and fetched to a processing engine when required; and a fourth data structure for cache management of set-wise rules based on the least recently used (LRU) scheme.