Browse Prior Art Database

A Simple Algorithm for the Longest-Prefix-Matching Problem

IP.com Disclosure Number: IPCOM000123334D
Original Publication Date: 1998-Sep-01
Included in the Prior Art Database: 2005-Apr-04
Document File: 2 page(s) / 69K

Publishing Venue

IBM

Related People

Alexander, CA: AUTHOR [+2]

Abstract

Disclosed is an algorithm for finding the longest prefix of a string s from a set T of strings {t1, t2, ..., tn). This problem occurs in many areas of computer science. In computer networking, for example, every IP router implements some solution to this problem.

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

A Simple Algorithm for the Longest-Prefix-Matching Problem

   Disclosed is an algorithm for finding the longest prefix
of a string s from a set T of strings {t1, t2, ..., tn).  This
problem occurs in many areas of computer science.  In computer
networking, for example, every IP router implements some solution to
this problem.

   The key idea behind this algorithm is to perform repeated
binary searches over T for some strategically-chosen prefixes of s.
The worst case time complexity of this search algorithm is
O(min(k,n,lsl).lg n) where k is the length of longest string in T.
The operation of adding/deleting an element to/from the set T, in the
worst case, can take time O(lg n).  In the case when T is a set of
bitstrings denoting IP subnets and s denoting an IP address, a
simulation study indicates that the average time complexity of the
search is much smaller than the theoretical worst case upper bound.
The main virtue of this algorithm, however, is its conceptual
simplicity; the few lines of the C-language implementation testifies
to this fact.
  1.  Store the elements of T in lexicographically increasing
      order
        If T is the set {abb, aa, abcc, abcdd, abcdee, a} then
      the lexicographic ascending representation of T is a, aa,
      abb, abc, abcdd, abcdee.
  2.  Find the lexicographically largest element, u, of T
      that lexicographically precedes s.  If none exists,
      then terminate search with the answer that s has no
      prefix in T.
        If s is the string abcde then the elements a, aa,
      abb, abc and abcdd lexicographically precede s.  The
      lexicographically largest element of them is
      abcdd.  Similarly, if s is abc, then u is abc.  The
      way to efficient perform step...