Browse Prior Art Database

Fast Address/ Pattern Recognition Using Hashing

IP.com Disclosure Number: IPCOM000122435D
Original Publication Date: 1991-Dec-01
Included in the Prior Art Database: 2005-Apr-04
Document File: 2 page(s) / 66K

Publishing Venue

IBM

Related People

Lasko, DD: AUTHOR [+2]

Abstract

This article describes a technique that can reduce the amount of logic needed to directly perform large address/pattern compare decodes. Using a hashing technique, a signature can be built for each address/pattern to be decoded. This signature will be used to significantly reduce the time required to search a table for a match.

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

Fast Address/ Pattern Recognition Using Hashing

      This article describes a technique that can reduce the
amount of logic needed to directly perform large address/pattern
compare decodes.  Using a hashing technique, a signature can be built
for each address/pattern to be decoded.  This signature will be used
to significantly reduce the time required to search a table for a
match.

      Current implementations of large address decodes are either
slow, costly, or require lots of hardware.  Some applications demand
both low cost and high speed.

      To overcome these problems, hashing can be used to generate a
signature for each address.  That signature is used as a direct or
indirect pointer to a particular address bucket.  In a direct mode,
the signature points directly to a fixed-length address bucket.  For
an indirect mode, the signature points to a table of bucket pointers.
These bucket pointers point to the address bucket which can be
variable in length (see figure).

      A bucket will contain all the stored patterns/addresses with
identical signatures.  A hardware compare circuit will compare the
incoming pattern against all patterns in the associated bucket.  This
direct compare eliminates the inaccurateness of hashing alone.  The
entire decode and hashing process is under the control of a
Picoprocessor.

      A programmable parallel CRC-type algorithm is used to generate
the signature of each pattern.  A 64-bit seed can be loaded...