Browse Prior Art Database

New BFSM concept based on advanced "default" rule engine

IP.com Disclosure Number: IPCOM000182887D
Original Publication Date: 2009-May-08
Included in the Prior Art Database: 2009-May-08
Document File: 3 page(s) / 21K

Publishing Venue

IBM

Abstract

An advanced default rule engine to increase the storage-efficiency and performance of a programmable state machine.

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

Page 1 of 3

New BFSM concept based on advanced

New BFSM concept based on advancedNew BFSM concept based on advanced

""""defaultdefaultdefault

default"

""" rule enginerule enginerule engine

rule engine

The original B-FSM concept described in [1] 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.

A block

diagram of a B-FSM based on a default B-FSM is shown in figure 1.

1

Page 2 of 3

input

State Reg.

next

state

Default B-FSM

Table Reg.

current

state input

value

default

rule

Rule Selector

Transition Rule Memory

 Address Generator

...