Browse Prior Art Database

High-Performance Searches in Software Disclosure Number: IPCOM000010856D
Original Publication Date: 2003-Jan-28
Included in the Prior Art Database: 2003-Jan-28
Document File: 4 page(s) / 108K

Publishing Venue



A preferred data structure for the Balanced Routing Table (BaRT) Search Engine is described, enabling quick and efficient operation for extracting information out of a compressed table.

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

Page 1 of 4

High-Performance Searches in Software

  Subject is a search engine that is based on the BaRT (Balanced Routing Table) search algorithm. Two versions of the BaRT algorithm for SRAM and wide embedded memory technologies are presented in [1] and [2]. Reference [3] shows a technique for improving the search performance of this software-based search engine through a special organization/encoding of the data structure. The proposed technique is in particular applicable to the wide embedded memory version of the BaRT algorithm. For a detailed description is referred to [2].

As described in [2], a search step involves inter alia: 1) finding the longest-matching result entry in a compressed table, and 2) finding a matching pointer entry in the compressed table - at most one pointer entry can match. [3] shows a reorganization of the data structure of the compressed table in order to test multiple - e.g. four - entries in parallel using bit-wise XOR and AND operations involving three 32-bit registers. However, according to the data structure as shown in Fig. 5 of [2], "type bits" indicating an entry type have to be tested in order to determine whether an entry is a pointer or a result entry.

A preferred encoding of entry formats and corresponding processing of the entries are now introduced such that no bit-level operations have to be performed in software. This encoding and the corresponding processing is illustrated in accordance with the following figures.

32 bits

11b entry mask

     test value pointer 10b index mask
test value pointer

Figure 1

Figure 1 illustrates the four entry types for the BaRT search structure. Each entry includes a field for a test value, a field for a mask, and a field for either a result or a pointer. The entry type is defined by first two bits of each entry, denoted as F0 and F1, in the following way:

1x (11 or 10) : pointer entry
01 : result entry
00 : "empty" entry

01b test mask result test value



[This page contains 1 picture or other non-text object]

Page 2 of 4

Figure 2 illustrates how a data block of four concatenated data words as described in [2] is reorganized, such that the first 32-bit word contains the F0 bit and test values of the four data words, and the second 32-bit word contains the F1 bits and mask values, and the remaining words contain the pointer/result values. In this case, the segment size, and consequently the test and mask value sizes equal 6 bits.

Figure 3 illustrates the test oper...