Enhanced Prefix Search Method
Original Publication Date: 2001-Apr-15
Included in the Prior Art Database: 2003-Jun-19
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.