Programmable Header Parser based on B-FSM technology
Original Publication Date: 2005-Feb-10
Included in the Prior Art Database: 2005-Feb-10
A programmable header parser is proposed that exploits the ability of the B-FSM technology to support wide input and output vectors.
Programmable Header Parser based on B -FSM technology
One of the key features of the BaRT-based FSM (B-FSM) technology as described in
 is its ability to support very wide input and output vectors. This means that "walking through the state transition diagram" (i.e., selection of a state transition in any given current state) can be based on a relatively large number of input bits (e.g., 32 bits or more) while at the same time a large output vector (e.g., 16 bytes) can be associated with each state transition, which will be generated as output when the given state transition is "executed". The proposed idea exploits this feature of the B-FSM technology to create a very efficient and fast programmable header parser.
The concept of the B-FSM based programmable header parser is shown in Figure 1. For a detailed description of the B-FSM operation, in particular the "execution" of the state transition rules, testing conditions, generating output/control signals, programming of the state diagrams, etc., is referred to .
The header data is received over the input bus in sequence. The width of the input bus is assumed to be at least 32 bits but can also be 64 or 128 bits. A selected (multiplexed) portion of the input is provided directly to the B-FSM engine. This allows the B-FSM engine to select a state transition (i.e., to walk through the state transition diagram) based on selected portions of the input vector (i.e., header data). Selected (multiplexed) portions of the input vector can also be stored in a set of input registers which can be tested by the B-FSM engine if needed (typically at some later stage during the processing). A short pipeline is used to "delay" the input a few cycles which allows the B-FSM to determine the type of processing to be applied on the input. There are several types of processing possible, including performing a checksum calculation, storing selected portions of the input vector in selected output registers (on selected bit positions), loading selected portions/fields of the input vector in a counter. The result of the checksum calculation as well as counter related status (e.g., reached zero - in case of a downcounter), is also provided to the B-FSM engine as input.
This concept will now be explained using a very simple example involving the headers of IPv4 and IPv6 packets. The first four bits (0-3) in the header determine the version, either IPv4 or IPv6 in this case. Because the header structures are different for both versions, this determines the way the first and remaining input vectors containing the header data have to be processed.
The B-FSM based header parser will directly read the version field comprised of the first four bits of the first input vector (through the multiplexer). The remaining portion of the first input vector is stored in the input register(s) as shown in Figure 1. If the version happens to be IPv4, then the various relevant IPv4 header fields will be stored in sele...