Browse Prior Art Database

Techniques for Minimizing Chip Area Costs for a Hardware-based Search Engine

IP.com Disclosure Number: IPCOM000015589D
Original Publication Date: 2002-Jan-13
Included in the Prior Art Database: 2003-Jun-20
Document File: 4 page(s) / 72K

Publishing Venue

IBM

Abstract

The proposal involves several techniques for improving the cost-efficiency of a hardware-based search engine by reducing the chip area needed to implement the search engine. The proposal relates specifically to 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]. The proposed techniques are applicable to both versions of the BART algorithm. [1] J. van Lunteren, "Searching Very Large Routing Tables In Fast SRAM," IEEE Int'l Conf. on Computer Communications and Networks "ICCCN 2001", Phoenix, AZ, October 15-17, 2001. [2] J. van Lunteren, "Searching Very Large Routing Tables in Wide Embedded Memory," Globecom 2001, The Evolving Global Communications Network, San Antonio, TX, November 25-29, 2001.

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

Page 1 of 4

Techniques for Minimizing Chip Area Costs for a Hardware-based Search Engine

The proposal involves several techniques for improving the
cost-efficiency of a hardware-based search engine by reducing the
chip area needed to implement the search engine. The proposal
relates specifically to 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]. The proposed techniques are applicable
to both versions of the BART algorithm.

[1] J. van Lunteren, "Searching Very Large Routing Tables In
Fast SRAM," IEEE Int'l Conf. on Computer Communications and
Networks "ICCCN 2001", Phoenix, AZ, October 15-17, 2001.

[2] J. van Lunteren, "Searching Very Large Routing Tables in
Wide Embedded Memory,"

Globecom 2001, The Evolving Global Communications Network, San
Antonio, TX, November 25-29, 2001.

The proposal involves several techniques, which will be described
in the following sections. The first two techniques involve the
reduction of the size of several fields that are part of the
entries from which the data structure is constructed. This will
reduce the width of the memory arrays that are needed to store
the data structure and consequently the total storage
requirements. The third
technique reduces the size of the counter array that implements
part of the update function.

Reducing the Size of the Index Mask field

In the original version of the BART scheme, the index mask field
has the same size as the search key segment from which the index
is extracted. By limiting the bit positions from which the index
can be extracted to a selected subset of the search key segment,
the size of the index mask can be reduced to the size of that
selected subset. The subset selection can be made configurable
(for example, using a mask stored in a register). This can be
done for all levels in the data structure or for each individual
level.

Figure 1 shows a modified version of the example presented in
[2], involving the prefixes: 01000100b (44h), 01010110b (56h),
1110b (Eh) and 11101111b (EFh). In this case, the index can only
be extracted from the 6 most significant segment bits (the
selected subset) requiring an index mask of only 6 bits
(000110b). The 2 least significant segment bits are only involved

1

Page 2 of 4

in the compare operation against the test value and test mask
fields.

In order to support tables containing a maximum number entries,
the index mask has to consist of at least s+1-Log(N) bits (see
Section III.-B in [2]).

segment 2

memory bank

7

0

6

5

4

3

2

1

tval/tmask/result

tval/tmask/result

compressed index

E0hSF0hindex maskpointer000110b

11b

10b

56h

FFh

Q

56h

FFh

01b

EFh

E0hSF0h44h

Figure 1. Reducing the size of the index mask field.

Reducing the Sizes of the Test Value and Test Mask fields

In the original version of the BART scheme, the test value and
test mask fields have the same
size as the search key segment against which these fields are
compar...