Runtime adaptable search processor

• US 7,685,254 B2
• Filed: 12/30/2005
• Issued: 03/23/2010
• Est. Priority Date: 06/10/2003
• Status: Active Grant

• Current Assignee: Memory Access Technologies LLC
• Original Assignee: Protocol Acquisition LLC
• Inventors: Pandya, Ashish A.
• Primary Examiner(s): Etienne; Ario
• Assistant Examiner(s): Halim; Sahera
• Application Number:
  US11/323,165
• Publication Number:
  US 20060136570A1
• Time in Patent Office: 1,544 Days
• Field of Search: 707/3, 707/6, 709/200, 709/217, 709/238, 709/231, 709/230, 370/389, 711/202, 711/121
• US Class Current: 709/217
• CPC Class Codes: G06F 16/90344 by using string matching techniques
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 9/30029 Logical and Boolean instructions, e.g. XOR, NOT
• CPC Class Codes: G06F 9/30036 Instructions to perform operations on packed data, e.g. vector, tile or matrix operations
• CPC Class Codes: H04L 63/145 the attack involving the propagation of malware through the network, e.g. viruses, trojans or worms
• CPC Class Codes: H04L 63/20 for managing network security; network security policies in general filtering policies H04L63/0227
• CPC Class Codes: H04L 67/10 in which an application is distributed across nodes in the network software deployment G06F8/60; multiprogramming arrangements G06F9/46
• CPC Class Codes: H04L 67/1097 for distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS]
• CPC Class Codes: H04L 69/12 Protocol engines
• CPC Class Codes: H04L 69/16 Implementation or adaptation of Internet protocol [IP], of transmission control protocol [TCP] or of user datagram protocol [UDP]
• CPC Class Codes: H04L 69/161 Implementation details of TCP/IP or UDP/IP stack architecture; Specification of modified or new header fields
• CPC Class Codes: H04L 69/32 Architecture of open systems interconnection [OSI] 7-layer type protocol stacks, e.g. the interfaces between the data link level and the physical level

Abstract

A runtime adaptable search processor is disclosed. The search processor provides high speed content search capability to meet the performance need of network line rates growing to 1 Gbps, 10 Gbps and higher. The search processor provides a unique combination of NFA and DFA based search engines that can process incoming data in parallel to perform the search against the specific rules programmed in the search engines. The processor architecture also provides capabilities to transport and process Internet Protocol (IP) packets from Layer 2 through transport protocol layer and may also provide packet inspection through Layer 7. Further, a runtime adaptable processor is coupled to the protocol processing hardware and may be dynamically adapted to perform hardware tasks as per the needs of the network traffic being sent or received and/or the policies programmed or services or applications being supported. A set of engines may perform pass-through packet classification, policy processing and/or security processing enabling packet streaming through the architecture at nearly the full line rate. A high performance content search and rules processing security processor is disclosed which may be used for application layer and network layer security. Scheduler schedules packets to packet processors for processing. An internal memory or local session database cache stores a session information database for a certain number of active sessions. The session information that is not in the internal memory is stored and retrieved to/from an additional memory. An application running on an initiator or target can in certain instantiations register a region of memory, which is made available to its peer(s) for access directly without substantial host intervention through RDMA data transfer. A security system is also disclosed that enables a new way of implementing security capabilities inside enterprise networks in a distributed manner using a protocol processing hardware with appropriate security features.

Claims

1. A runtime adaptable search processor for operating on information content and having a plurality of hardware configurations, said runtime adaptable search processor comprising:

a. a control processor and scheduler structured to control and schedule the information content for processing and for performing an analysis of the information content;

b. an adaptation controller structured to configure said hardware configurations of the runtime adaptable search processor configurations at runtime based on the performed analysis of the information content;

c. at least one configuration memory for storing at least said plurality of hardware configurations;

d. at least one runtime adaptable non-deterministic finite state automaton (NFA) search engine comprising logic gates for performing search on said information content, said NFA search engine comprising at least one NFA;

e. at least one runtime adaptable deterministic finite state automaton (DFA) search engine comprising logic gates for performing search on said information content, said DFA search engine comprising at least one DFA;

f. at least one state logic block (SLB) for performing state logic operations for a state; and

g. at least one application state memory for storing application state information, said at least one application state memory comprising;

at least one application state context that represents the context information to be programmed in said NFA search engine when the at least one application state context is selected to be configured in said NFA search engine,

wherein the application state context comprises NFA parameters which are applicable to all SLBs of said at least one SLB, and at least one SLB parameter set which is applicable to one SLB of said at least one SLB.

2. The runtime adaptable search processor of claim 1 further comprising at least one search cluster comprising at least one search engine, said runtime adaptable search processor further comprising one or more of the following:

a. a global configuration controller for global configuration control of said at least one search cluster;

b. a configuration memory controller for controlling accesses to at least said configuration memory;

c. an inter cluster routing switch for controlling routing between a plurality of said at least one search cluster;

d. a global memory for said at least one search cluster; and

e. a global memory controller for at least said global.

3. The runtime adaptable search processor of claim 2, wherein said at least one search cluster further comprises:

a. a cluster configuration controller for configuring said at least one search cluster;

b. at least one runtime adaptable search engine; and

c. a configurable cluster interconnect network for connecting a plurality of said at least runtime adaptable search engine.

4. The runtime adaptable search processor of claim 3 wherein said at least one runtime adaptable search engine comprises one or more of the following:

a. a runtime adaptable NFA search engine for performing search using at least one NFA; and

b. a runtime adaptable DFA search engine for performing search using at least one DFA.

5. The runtime adaptable search processor of claim 2 wherein said at least one search cluster further comprises one or more of the following:

a. a cluster memory for providing memory storage;

b. a cluster memory controller for controlling at least said cluster memory;

c. a cluster routing switch for interconnecting said at least one runtime adaptable search engine to said at least one search cluster or said inter cluster routing switch; and

d. a cluster flow controller for at least storing and retrieving flow context.

6. The runtime adaptable search processor of claim 1 wherein said at least one runtime adaptable NFA search engine evaluates said at least one NFA and comprises:

a. at least one symbol detection logic for detecting a symbol; and

b. at least one application state controller for controlling the operation of said at least one runtime adaptable NFA search engine by configuring the at least one runtime adaptable NFA search engine based on application state information from the application state memory.

7. The runtime adaptable search processor of claim 6 wherein said at least one SLB comprises:

a. a state dependent vector (SDV) for enabling and disabling at least one interconnection between said state and one or more states of said NFA;

b. a current state vector (CSV) representing the current state of some of said one or more states of said NFA that said state depends on for its next state;

c. a received symbol vector (RSV) representing the value of said symbol received as input to said symbol detection logic;

d. a left-biased or right-biased signal that indicates the NFA type;

e. a state transition logic for using at least said SDV, said CSV, said RSV, and said left-biased or right-biased signal to generate the next state value for said state;

f. an initialization logic block to control the value of the next state for said state;

g. a state memory for storing the value of said state; and

h. an accept detect logic for detecting and signaling when said state is an accept state and is activated.

8. The runtime adaptable search processor of claim 7 wherein said at least one SLB further comprises one or more of the following:

a. a programmable storage for said SDV for enabling runtime configuration of said SDV;

b. a programmable storage for said left-biased (LB) or right-biased (RB) signal for enabling runtime configuration of a realized NFA type;

c. a programmable storage for storing a start flag to indicate if said state is a start state of said NFA;

d. a programmable storage for storing an accept flag to indicate if said state is an accept state of said NFA;

e. a programmable storage for storing an action field to indicate the action that should be taken when said state is activated or reached during said NFA evaluation; and

f. a programmable storage for storing a tag field to indicate a tag that is issued when said state is activated or reached during said NFA evaluation.

9. The runtime adaptable search processor of claim 1 wherein said at least one runtime adaptable NFA search engine further comprises one or more of the following:

a. pattern substitution control for performing pattern substitution;

b. counters for various events;

c. match logic for detecting a rule match; and

d. finite stat automation (FSA) extension logic for enabling said runtime adaptable NFA search engine to support larger FSAs.

10. The runtime adaptable search processor of claim 1 wherein said at least one runtime adaptable DFA search engine comprises:

a. at least one DFA operations engine for performing stat logic operations;

b. at least one DFA instruction and state flow memory for storing DFA operations; and

c. at least one DFA state controller for controlling the operation of said at least one runtime adaptable DFA search engine.

11. The runtime adaptable search processor of claim 1 wherein said at least one runtime adaptable DFA search engine further comprises one or more of the following:

a. pattern substitution control for performing pattern substitution;

b. counters for providing counters for various events;

c. a DFA context controller for controlling the application context of said DFA search engine; and

d. DFA extension logic for enabling said runtime adaptable DFA search engine to support larger FSAs.

12. The runtime adaptable search processor of claim 1 embedded in a system for operating on network packets or on local content, said system capable of being coupled to a network, wherein said runtime adaptable search processor processes content embedded within said network packets or within said local content, said runtime adaptable search processor further comprising runtime adaptable search processor array hardware to dynamically select hardware configurations within said runtime adaptable search processor to support application or service processing needs of said network packets or said local content.