Browse Prior Art Database

Buffer Data Alignment Using Tree Search Technique

IP.com Disclosure Number: IPCOM000106866D
Original Publication Date: 1993-Dec-01
Included in the Prior Art Database: 2005-Mar-21
Document File: 4 page(s) / 99K

Publishing Venue

IBM

Related People

Ashton, JL: AUTHOR [+4]

Abstract

Disclosed is a State Transition technique, utilizing a set of control block entries, which greatly improves the performance associated with placing received packets into a communication controllers internal data buffers. As a packet is received, its header is used to transition thru the Header Format Table (State Transition Tree) located in the adapter. The output of the Transition tree determines the correct positioning of the data within the controllers buffers. Correct positioning involves placing the correct number of bytes at the correct offset in the first buffer and providing the correct buffer offset for the second buffer. It is assumed that all buffers after the first are completely filled and that all buffers after the second have zero offsets.

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

Buffer Data Alignment Using Tree Search Technique

      Disclosed is a State Transition technique, utilizing a set of
control block entries, which greatly improves the performance
associated with placing received packets into a communication
controllers internal data buffers.  As a packet is received, its
header is used to transition thru the Header Format Table (State
Transition Tree) located in the adapter.  The output of the
Transition tree determines the correct positioning of the data within
the controllers buffers.  Correct positioning involves placing the
correct number of bytes at the correct offset in the first buffer and
providing the correct buffer offset for the second buffer.  It is
assumed that all buffers after the first are completely filled and
that all buffers after the second have zero offsets.  Received data
can be simultaneously checked against many search patterns using this
technique providing and advantage over other search methods.  This
invention reduces the time required to search the complete format
table and hence increases the communication controllers performance.

      The method utilizes two different control block formats, linked
together such that a state transition table is produced.  The first
control block, "Comparison Link-List", defines the state transitions
as well as the Nth data byte in the table.  The second type, "Buffer
Offset and Control Entry", defines the Offsets and Byte Counts to be
used when transferring data into the communication controllers
buffers.

      The "Comparison Link-List" control block contains four
information fields.  The first field, the Code field" contains a code
that defines the structure of the tree.  A bit in the Code defines
byte alignment of the receive data, odd or even byte assuming
halfword addressability.  Also contained in the Code is an indication
of possible parallel tree paths (multiple possible compare data).
Included in the Code is an end of search indication.  The second
field of the "Com...