Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
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. 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 from the 3-tuple, which can either be a pointer to another (compressed) table or a search result. If a routing table contains entries that are prefixes of other entries then a search result can be found after a certain part of the IP destination address has been processed, while the remaining part of the IP destination address needs further processing to search for a longer matching prefix. In this situation, intermediate nodes in the data structure need to contain both a search result as well as a pointer to another table that is used to process the remaining part of the IP destination address.

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...