Browse Prior Art Database

Data Structure for SNA Communications Finite State Machines

IP.com Disclosure Number: IPCOM000034976D
Original Publication Date: 1989-May-01
Included in the Prior Art Database: 2005-Jan-28
Document File: 3 page(s) / 37K

Publishing Venue

IBM

Related People

Allsen, JK: AUTHOR [+3]

Abstract

In System Network Architecture (SNA) communications, Finite State Machines (FSMs) are used in several protocol layers to verify the correctness of sending/receiving requests and responses. This process occupies a significant portion of the time, since every request/ response unit must be verified. This structure allows the FSMs to be driven efficiently and maintained easily. FSMs have been applied in many areas, such as lexical analyzers, string searching algorithms, etc. In compilers, two-dimensional arrays indexed by states and characters were considered as the fastest way to implement the FSMs. However, in SNA communications, to simply use two-dimensional arrays to represent the FSMs is not efficient. This is because the inputs to the FSMs are usually combinations of different attributes, i.e.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 53% of the total text.

Page 1 of 3

Data Structure for SNA Communications Finite State Machines

In System Network Architecture (SNA) communications, Finite State Machines (FSMs) are used in several protocol layers to verify the correctness of sending/receiving requests and responses. This process occupies a significant portion of the time, since every request/ response unit must be verified. This structure allows the FSMs to be driven efficiently and maintained easily. FSMs have been applied in many areas, such as lexical analyzers, string searching algorithms, etc. In compilers, two-dimensional arrays indexed by states and characters were considered as the fastest way to implement the FSMs. However, in SNA communications, to simply use two-dimensional arrays to represent the FSMs is not efficient. This is because the inputs to the FSMs are usually combinations of different attributes, i.e., begin chain, end chain, change direction, etc. For some FSMs, the number of possible combinations can reach the thousands. To check each input for an FSM would be a time-consuming and error- prone process. To overcome this problem, an efficient and tenable data structure for FSMs used in SNA communications is constructed. This data structure consists of three parts: the pattern tables, the index tables, and a driver. Depending on implementation, each FSM may contain one or more pattern tables and index tables. If the number of input attributes is very large, inputs to an FSM can be split into small subsets. Each subset needs a pattern table and an index table. The figure shows an FSM with two pattern tables and two associated index tables. A pattern table is an array of K bits. Among these K bits, each attribute is assigned L (L <= K) bits to represent all possible instances for this attribute.

For example, begin chain or not begin chain needs one bit to represent this attribute with the bit set meaning "begin chain" and the not set meaning "not begin chain". For each pattern table, there is an index table associated with it. An index table is an array of integers with 2**K entries. The integers in this array are input indices to the driver. A driver is a two-dimensional array indexed by the input indices and the current states. The entries i...