Browse Prior Art Database

Method for Fast Search Operation on Stand-Alone Search Structure

IP.com Disclosure Number: IPCOM000016215D
Original Publication Date: 2002-Aug-11
Included in the Prior Art Database: 2003-Jun-21
Document File: 3 page(s) / 94K

Publishing Venue

IBM

Abstract

This proposal involves a technique for improving the search performance of a software-based search engine by minimizing of the number of memory accesses per lookup, while maintaining a stand-alone data structure that contains all the information needed to perform an update operation. The proposal relates specifically to a search engine that is based on the BART (Balanced Routing Table) search algorithm, developed by the same author. The BaRT algorithm is described in detail in [1][2].

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

Page 1 of 3

Method for Fast Search Operation on Stand-Alone Search Structure

  This proposal involves a technique for improving the search performance of a software-based search engine by minimizing of the number of memory accesses per lookup, while maintaining a stand-alone data structure that contains all the information needed to perform an update operation. The proposal relates specifically to a search engine that is based on the BART (Balanced Routing Table) search algorithm, developed by the same author. The BaRT algorithm is described in detail in [1][2].

The technique will be explained using the example shown in Fig. 1 (which is Fig. 10 in
[1] - for a description see this paper). The tables at levels 2 and 3 (indexed by search key segments 2 and 3) are compressed tables, containing complete prefix information in the form of test values and test masks.

IPv4 destination address

8 bits

8 bits

segment 3

imask/ptr tval/tmask/result

tval/result/imask/ptr

16 bits

segment 1 segment 2

compressed index

compressed index

tval/tmask/result

FFFFh

Fh

EFh

FFh

W

Eh

E0h

F0h

V

ABCDh

0FhCDh

.. .. 3
0h

E0h

F0h

V

2

FFh

U

78h

1full index

FFh

T

0

6xh

F0h

S

imask/ptr

1234h

00h

56h

R

90h

0000h

level 1 level 2

level 3

Figure 1.

The table at level 1 is not compressed and is indexed by the entire first segment of the search key. This table does not contain any prefix information. In order to construct a stand-alone data structure, all tables must be compressed tables (see [1], e.g., Section III-D). However, compressed tables are indexed efficiently by segments consisting of up

to 8 bits, while uncompressed tables can be indexed efficiently by segments of up to about 16 bits (e.g., the table at level 1 in Fig. 1 is indexed by a segment of 16 bits) resulting in fewer memory accesses per lookup. The proposed technique combines both approaches. Fig. 2 shows an IP address partitioned into 4 segments...