Browse Prior Art Database

Hybrid direct table and LPM searches

IP.com Disclosure Number: IPCOM000014425D
Original Publication Date: 2001-Mar-01
Included in the Prior Art Database: 2003-Jun-19
Document File: 1 page(s) / 39K

Publishing Venue

IBM

Abstract

The lookup task known as longest prefix match (LPM) is defined as follows. A library of binary patterns called prefixes of various lengths from 1 to N is given. A search occurs when a new pattern X with length N is presented. The search consists of finding the longest prefix (if any) which has all its bits identical to the highest order bits of X. Two method for LPM search are standard: a tree structure testing one or a few bits of X at each branch, and a Content Addressable Memory (CAM or ternary CAM) testing selected bits of X in one step.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 52% of the total text.

Page 1 of 1

Hybrid direct table and LPM searches

The lookup task known as longest prefix match (LPM) is defined as follows. A library of binary patterns called prefixes of various lengths from 1 to N is given. A search occurs when a new pattern X with length >= N is presented. The search consists of finding the longest prefix (if any) which has all its bits identical to the highest order bits of X. Two method for LPM search are standard: a tree structure testing one or a few bits of X at each branch, and a Content Addressable Memory (CAM or ternary CAM) testing selected bits of X in one step.

Another lookup task is known as fixed match (FM). A library of binary patterns of length N is given. A search occurs when a new pattern X with length N is presented. The search consists of finding stored pattern (if there is one) which is identical to X. Routinely a hash function h is used. The hash function maps binary patterns of length N to much shorter binary patterns of length L. Before a search, every stored binary pattern is fed to the hash function to produce the hash values of length L. A search consists of first applying the hash function to a new pattern X to find h(X), then comparing h(X) to all the hash values of the stored patterns. If one or more stored patterns have the same hash value as h(X), then each such stored pattern is compared in full to X.

The present invention entails a hybridization of the above LPM and FM.

In some computer network tasks such as load balancing, it may be that a key (identifier of a packet) is tested by many rules. Each rule has a fixe...