David A Lees

US Patent:

20030051043, Mar 13, 2003

Filed:

Dec 3, 2001

Appl. No.:

10/005462

Inventors:

Daniel Wyschogrod - Newton MA, US
Alain Arnaud - Newton MA, US
David Lees - Lexington MA, US
Leonid Leibman - Weston MA, US

Assignee:

Raqia Networks Inc. - Newton MA

International Classification:

G06F015/173
G06F015/16

US Classification:

709/230000, 709/238000

Abstract:

A system and method in accordance with the present invention determines in real-time the portions of a set of characters from a data or character stream which satisfies one or more predetermined regular expressions. A eal-time eterministic inite state utomaton (RDFA) ensures that the set of characters is processed at high speeds with relatively small memory requirements. An optimized state machine models the regular expression(s) and state related alphabet lookup and next state tables are generated. Characters from the data stream are processed in parallel using the alphabet lookup and next state tables, to determine whether to transition to a next state or a terminal state, until the regular expression is satisfied or processing is terminated. Additional means may be implemented to determine a next action from satisfaction of the regular expression.

US Patent:

20030065800, Apr 3, 2003

Filed:

Aug 8, 2002

Appl. No.:

10/217592

Inventors:

Daniel Wyschogrod - Newton MA, US
Alain Arnaud - Newton MA, US
David Lees - Lexington MA, US
Leonid Leibman - Weston MA, US

Assignee:

Raqia Networks Inc. - Newton MA

International Classification:

G06F015/173
G06F015/16

US Classification:

709/230000, 709/238000

Abstract:

A method for generating look-up tables for a high speed multi-bit Real-time Deterministic Finite state Automaton (hereinafter RDFA). The method begins with a DFA generated in accordance with the prior art. For each state in the DFA, and for each of the bytes recognized in parallel the following occurs. First an n-closure list is generated. An n-closure list is a list of states reachable in n-transitions from the current state. Next an alphabet transition list is generated for each state. An “alphabet transition list” is a list of the transitions out of a particular state for each of the characters in an alphabet. Finally, the transitions are grouped into classes. That is, the transitions that go to the same state are grouped into the same class. Each class is used to identify the next state. The result is a state machine that has less states than the original DFA.

US Patent:

20030110208, Jun 12, 2003

Filed:

Jan 24, 2003

Appl. No.:

10/350540

Inventors:

Daniel Wyschogrod - Newton MA, US
Alain Arnaud - Newton MA, US
David Lees - Lexington MA, US

Assignee:

Raqia Networks, Inc. - Newton MA

International Classification:

G06F015/16

US Classification:

709/202000

Abstract:

Data that spans multiple packets is processes. A finite state machine is used to process the data in each packet and the “state” of a finite state machine is saved after processing a packet. The saved state is stored with information that identifies the particular data stream from which the packet originated. This means that a state machine engine (hardware implementation of the finite state machine) is not tied to a particular data stream. The present invention makes it possible to utilize state machine co-processors very efficiently in a multiple engine/multiple data stream system.