Browse Prior Art Database

Enhanced Prefix Search Method

IP.com Disclosure Number: IPCOM000013916D
Original Publication Date: 2001-Apr-15
Included in the Prior Art Database: 2003-Jun-19
Document File: 2 page(s) / 52K

Publishing Venue

IBM

Abstract

Disclosed is a method for performing a longest matching prefix search, that can exploit wide data buses of embedded memory and larger cache lines to achieve a more compact data structure.

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 58% of the total text.

Page 1 of 2

Enhanced Prefix Search Method

  Disclosed is a method for performing a longest matching prefix search, that can exploit wide data buses of embedded memory and larger cache lines to achieve a more compact data structure.

The paper "Routing lookups in hardware at memory access speeds", INFOCOM'98, by Gupta et al., describes an implementation of a longest matching prefix search operation for routing lookups using a data structure consisting of linked tables that are indexed by successive segments of the IP destination address. The disclosed method improves this type of search schemes by compressing the individual tables that occur in that data structure in order to obtain a more compact data structure.

Figure 1 shows an example in which a segment of an IP destination address consisting of 8 bits is used to index a table that is compressed according to the disclosed method. First, a selected set of bits is extracted from the address segment and is used to index the compressed table. The index in this example consists of two bits. Next, the indexed table entry is retrieved from the compressed table. This entry contains one or multiple 3-tuples consisting of a test value (TVal), a test mask (TMask), and a result. The address segment is then compared in parallel with all tuples by testing it against the test values at the bit locations indicated by the test masks contained in the same tuple as the test values. Upon a positive test result, the corresponding result is taken...