Browse Prior Art Database

Technique for Performing Generalized Prefix Matches

IP.com Disclosure Number: IPCOM000118554D
Original Publication Date: 1997-Mar-01
Included in the Prior Art Database: 2005-Apr-01

Publishing Venue

IBM

Related People

Budhiraja, N: AUTHOR

Abstract

Many routing and directory search protocols require the notion of generalized prefix matches on strings to make their routing or search decisions. Hard timing constraints on processing times have to be met by these generalized prefix matching protocols. The scheme presented here introduces the notion of a generalized prefix match and describes a protocol and the corresponding data structures to perform fast generalized prefix matches on arbitrary length binary strings.

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

Technique for Performing Generalized Prefix Matches

      Many routing and directory search protocols require the notion
of generalized prefix matches on strings to make their routing or
search decisions.  Hard timing constraints on processing times have
to be met by these generalized prefix matching protocols.  The scheme
presented here introduces the notion of a generalized prefix match
and describes a protocol and the corresponding data structures to
perform fast generalized prefix matches on arbitrary length binary
strings.

      Today's routing and directory search protocols that work in an
environment where destination addresses are hierarchically structured
need to make use of a fast prefix matching algorithm to make the
routing/search decisions efficiently.  In particular, some prefix of
the destination address can be used to locate the region of the
network where the destination might be located.  For example,
consider the space of E.164 addresses that can be used to address
Asynchronous Transfer Mode (ATM) destinations, and suppose that one
needs to locate a destination with address 1-914-784-7344.  In order
to keep the size of the database small (in order to scale), a router
or directory service usually merges information about a group of
destinations that are related to each other into a single entry.  In
the above example, a directory service may keep enough information to
locate all destinations whose addresses have prefixes 1-914, 1-607,
1-908, etc.  Consequently, on receiving a query to locate a resource
with address 1-914-784-7344, the directory service will perform a
longest prefix match (performing a longest match will be one
application of the protocol presented) on its database and return
information based on its 1-914 database entry.

      There currently exist protocols (e.g., (1)) that can
efficiently perform the prefix match described in the above example,
assuming that it is precisely "known" as to what the prefix is.  In
the above example of E.164 addresses, a directory service can perform
the prefix match only if it "knows" that 1-914 is a prefix of
1-914-784-7344.  In other words, the directory service will have to
know how E.164 addresses are represented.  An E.164 address is
represented as a string of 20 bytes, and each number in the address
is represented as a binary coded decimal.  Thus, both 1-914 and
1-914-784-7344 will have the same length and their encodings (as they
will look in binary) are as follows (we only show the last 8 bytes in
each string - the remaining 12 bytes have other information which we
can ignore):
  o  1-914=0000 0001 1001 0001 0100 1111 1111 1111 1111 1111
      1111 1111 1111 1111 1111 1111
  o  1-914-784-7344=0000 0001 1001 0001 0100 0111 1000 0100
      0111 0011 0100 0100 1111 1111 1111 1111

      Clearly, the first string is not a simple prefix of the second,
and unless the directory service knows how E.164 addresses are
represented (i.e...