Browse Prior Art Database

Data Stream Analysis using Finite State Machines

IP.com Disclosure Number: IPCOM000115947D
Original Publication Date: 1995-Jul-01
Included in the Prior Art Database: 2005-Mar-30
Document File: 2 page(s) / 62K

Publishing Venue

IBM

Related People

Aaker, KD: AUTHOR [+3]

Abstract

A method for parsing a data stream with a network of separate Finite State Machines (FSMs) connected together in a tree structure is disclosed. Each byte in the stream is fed into the parsing network (tree structure) at the root FSM.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 52% of the total text.

Data Stream Analysis using Finite State Machines

      A method for parsing a data stream with a network of separate
Finite State Machines (FSMs) connected together in a tree structure
is disclosed.  Each byte in the stream is fed into the parsing
network (tree structure) at the root FSM.

      Each FSM in the network can do one of many things.  The action
depends on what the FSM's current state is, and the byte that is
input.

Each FSM may:
  1.  Pass the byte to another FSM down in the tree for further
       processing
  2.  Process the byte itself, and return
  3.  Send a signal to the FSM down in the tree for special
conditions
  4.  Or any combination of the above.

      Each FSM is responsible for keeping FSMs down in the tree
informed if any special conditions arise, such as errors or the end
of the data stream is encountered by a node further up in the tree
(network).  This can be accomplished by sending a special signal down
the path so all lower FSMs can reset.

      Each FSM also passes back a return code of a standard type when
it has completed processing of the input byte.  This will be passed
back back up the tree to it's calling FSM, or the initial feeder if
it is the Root FSM.  This allows each FSM in the path to act
accordingly (do further processing, reset, etc...) and be ready to
receive the next input.  Thus, each FSM in the path checks both input
data and return codes for validity.

      Information concerning the current command processing is stored
by the network in each of the FSM's state...