Browse Prior Art Database

Novel Patricia Tree Search with Deterministic Search Performance

IP.com Disclosure Number: IPCOM000010246D
Original Publication Date: 2002-Nov-13
Included in the Prior Art Database: 2002-Nov-13
Document File: 2 page(s) / 61K

Publishing Venue

IBM

Abstract

x

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

Page 1 of 2

Novel Patricia Tree Search with Deterministic Search Performance

  A main disadvantage of Patricia tree searches is their non-deterministic search performance. For example, if a typical 1-bit Patricia tree is used to perform a longest-matching prefix search on a 32-bit address, in, for example, a routing table search, then the tree depth can vary between 1 and 32, depending on the routing table characteristics. The BaRT scheme overcomes this problem for exact- and prefix-match searches by delivering deterministic search performance (a maximum of 3 or 4 memory accesses to search a 32-bit address) as described in [1]. The performance is independent of the characteristics of the routing table and input trace. However, the BaRT scheme is optimized for exact-match, prefix-match and range-match searches, while a Patricia tree can also be used for ternary-match searches.

The BaRT scheme can be modified to support ternary-match searches more efficiently, by removing the test operation of the segment value at each stage against test values stored in pointer entries, and instead performing a test against the entire search key at the end. Fig.1 shows the new entry format definitions. The test value field is now removed from the pointer entries (entry types 10b and 11b) while the test value and test mask fields of the result entry (entry type 01b) have been enlarged to match the size of the entire search key. A new update algorithm can be employed to construct the data structu...