Hybrid direct table and LPM searches
Original Publication Date: 2001-Mar-01
Included in the Prior Art Database: 2003-Jun-19
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 fixed part and a prefix or subnet part. It might be that the fixed part of each rule always applies to the very same bit positions in a new pattern X. Likewise, the LPM part of each rule always applies to the very same bit positions in X and that the two sets of bit positions (FM and LPM) are disjoint and complementary.