New BFSM concept based on advanced "default" rule engine
Original Publication Date: 2009-May-08
Included in the Prior Art Database: 2009-May-08
An advanced default rule engine to increase the storage-efficiency and performance of a programmable state machine.
New BFSM concept based on advanced
New BFSM concept based on advancedNew BFSM concept based on advanced
""" rule enginerule enginerule engine
The original B-FSM concept described in  involves a so called default rule table
which for each
input byte determines the state transition rule that would have been selected in case the B-FSM were in its
initial/default state. The result of this lookup on the default rule table is then provided together with the input
value to the actual B-FSM logic. If no matching transition rule was found for the hash-based lookup on the
transition rule memory, then the selected default rule is used instead. This concept allowed a drastic reduction
of the storage requirements because it enabled the removal of many transitions from the other states.
The presented idea makes a fundamental change to the default rule table concept by replacing it with a so
called default B-FSM. Instead of selecting a default rule solely based on one particular input value, now the
B-FSM allows to perform this selection based on multiple input values comprising a variable-sized window covering the
current and the most recent input values ("input history"). In a typical embodiment, the default B-FSM would still perform
this operation at a processing rate of one input byte per processing step.
The default B-FSM implements a pattern-matching function which scans the input stream for matches against a
selected set of small patterns,
which are typically subpatterns of the actual patterns. If it
finds a match, then the state
information, i.e., the state vector, table address and mask vector corresponding to a state associated with that prefix/input
sequence in the regular B-FSM data structure is provided as default rule to the regular B-FSM lookup and will be used
if no regular matching transition rule is found in the transition rule memory.
diagram of a B-FSM based on a default B-FSM is shown in figure 1.
Transition Rule Memory