Method and apparatus for storing sparse and dense subtrees in a longest prefix match lookup table
AssigneeMosaid Technologies Incorporated
InventorDavid A. Brown
Life of this patent
Estimating the term…
Abstract
We present a lookup table which allows sparse subtree descriptors and dense subtree descriptors to be stored in the same memory. A subtree entry in the memory stores a dense subtree descriptor for a dense subtree or a plurality of sparse subtree descriptors for sparse subtrees. The subtree entry is indexed by a leaf in the previous subtree. The sparse subtree descriptor stores at least one node descriptor. The node descriptor describes a set of leaves in the sparse subtree having a common value. The common value is encoded in the node descriptor using run length encoding.
Claims8
A method for searching for a route corresponding to a key in a multi-level lookup table, comprising the steps of:
- selecting a subtree entry by a subtree index;
- selecting one of a plurality of sparse subtree descriptors in the selected subtree entry, the sparse subtree descriptor including a plurality of node descriptors;
- converting the node descriptors in the selected sparse subtree descriptor to masked values;
- loading the masked values in memory in longest prefix order;
- searching the memory for a longest prefix match for a portion of the key;
- and
- selecting the route stored in another memory dependent on the address of the longest prefix match.
Dependencies are inferred from the claim text.